NLP7
Nelder-Mead Pattern Search
The Nelder-Mead algorithm is a pattern search method for use on unconstrained nonlinear models. It is also known as the downhill simplex method or the flexible polyhedron method. A simplex is simply a polytope of n+1 vertices in n-dimensions. So for example, it is a line segment on a line, a triangle on a plane, and a tetrahedron in three-dimensional space.
The Nelder-Mead method starts by forming an initial simplex from n+1 test points. It evaluates the function value at the test points, and replaces the worst of the test points by a point determined by reflecting the worst point through the centroid of the remaining n points. If the new point is better than the best current point, then the algorithm tries to stretch exponentially out along this line. On the other hand, if the new point isn't much better than the previous value then the algorithm knows it is stepping across a valley, so it shrinks the polytope towards the best point.
The following two animations are demonstrations of the Nelder-Mead method in action. The first animation is a simplex search over the well-known Rosenbrock banana-shaped objective function. Observe how the simplex moves, expands and shrinks until it converges upon the optimum point.
Notes:
These images were created by P.A. Simonescu under the following licenses:
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. Subject to disclaimers.
This file is licensed under the Creative Commons Attribution-ShareAlike license versions 2.5, 2.0, and 1.0. You may select the license of your choice.
See the Wikipedia article where the original diagrams appear at