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.
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.
Restart the animations by refreshing the web page.
|
The second animation shows a Nelder-Mead
simplex search over the Himmelblau function. Again, the triangle
replaces the worst points, shrinks, and expands while converging on the
minimum point.
|
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.
You may select the license of your choice. See the Wikipedia article where the original diagrams appear at http://en.wikipedia.org/wiki/Nelder-Mead_method |
|
|
|