Nelder-Mead method

From Wikipedia, the free encyclopedia


Nelder-Mead Symplex search over Rosenbrock banana function (above) and Himmelblau's function (below)

See simplex algorithm for the numerical solution of the linear programming problem.

The Nelder-Mead method or simplex method or downhill simplex method is a commonly used nonlinear optimization algorithm. It is due to Nelder & Mead (1965) and is a numerical method for minimising an objective function in a many-dimensional space.

The method uses the concept of a simplex, which is a polytope of N + 1 vertices in N dimensions; a line segment on a line, a triangle on a plane, a tetrahedron in three-dimensional space and so forth.

The method approximately finds a locally optimal solution to a problem with N variables when the objective function varies smoothly. For example, a suspension bridge engineer has to choose how thick each strut, cable and pier must be. Clearly these all link together, but it is not easy to visualise the impact of changing any specific element. The engineer can use the Nelder-Mead method to generate trial designs which are then tested on a large computer model. As each run of the simulation is expensive it is important to make good decisions about where to look. Nelder-Mead generates a new test position by extrapolating the behaviour of the objective function measured at each test point arranged as a simplex. The algorithm then chooses to replace one of these test points with the new test point and so the algorithm progresses.

The simplest step is to replace the worst point with a point reflected through the centroid of the remaining N points. If this point is better than the best current point, then we can try stretching exponentially out along this line. On the other hand, if this new point isn't much better than the previous value then we are stepping across a valley, so we shrink the simplex towards the best point.

Like all general purpose multidimensional optimisation algorithms, Nelder-Mead occasionally gets stuck in a rut. The standard approach to handle this is to restart the algorithm with a new simplex starting at the current best value. This can be extended in a similar way to simulated annealing to try and escape small local minima.

Many variations exist depending on the actual nature of problem being solved. The most common, perhaps, is to use a constant size small simplex that climbs local gradients to local maximums. Visualize a small triangle on an elevation map flip flopping its way up a hill to a local peak. This, however, tends to perform poorly against the method described in the paper as it makes lots of small unnecessary steps in areas of little interest.

This method is also known as the Flexible Polyhedron Method.

[edit] See also

Conjugate gradient method
Broyden-Fletcher-Goldfarb-Shanno or BFGS method
Simulated annealing
Differential evolution

[edit] References

J.A. Nelder and R. Mead, Computer Journal, 1965, vol 7, pp 308-313 [1]
Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.