yamauchi@cs.rochester.edu (Brian Yamauchi) (02/12/91)
I'm interested in fast algorithms for solving non-linear optimization problems where the function being optimized can be represented as a sum of "limited" types of non-linear functions. I'm familiar with gradient descent and Monte Carlo methods, and I was wondering what other sorts of algorithms have been developed? By fast, I mean polynomial in the number of functions and/or variables in "typical" cases. These algorithms could be exponential in pathological cases. They could also be designed to be return "good" values as opposed to being guaranteed to find the maximum in all cases. The limitations on the form of the functions could have any number of forms -- piecewise linear functions, sums of gaussians, discrete functions, etc -- as long as they are general enough to represent a wide variety of function "landscapes". The application is for behavior arbitration in reactive robotic systems. Each of the behaviors outputs an evaluation function which assigns priorities to the space of possible responses. The role of the arbitrator is to select the point in the response space which corresponds to the action with the greatest sum of priorities. I've been planning to use a voting scheme combined with a heuristic search procedure, but then I started wondering whether mathematicians have been thinking about the same problems... A quick look through a number of nonlinear optimization texts turned up a number of techniques, but most of these seemed like overkill -- too slow to run in real-time and unnecessarily general for my purposes. Any pointers to texts or articles would be greatly appreciated. Thanks in advance, -- _______________________________________________________________________________ Brian Yamauchi University of Rochester yamauchi@cs.rochester.edu Department of Computer Science _______________________________________________________________________________