Nelder–Mead method

Short description: Numerical optimization algorithm

An iteration of the Nelder-Mead method over two-dimensional space.

Search over the Rosenbrock banana function

Search over Himmelblau's function

Nelder–Mead minimum search of Simionescu's function. Simplex vertices are ordered by their value, with 1 having the lowest (best) value.

The Nelder–Mead method (also downhill simplex method, amoeba method, or polytope method) is a numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based on function comparison) and is often applied to nonlinear optimization problems for which derivatives may not be known. However, the Nelder–Mead technique is a heuristic search method that can converge to non-stationary points on problems that can be solved by alternative methods.

The Nelder–Mead technique was proposed by John Nelder and Roger Mead in 1965, as a development of the method of Spendley et al.

Overview

The method uses the concept of a simplex, which is a special polytope of n + 1 vertices in n dimensions. Examples of simplices include a line segment in one-dimensional space, a triangle in two-dimensoinal space, a tetrahedron in three-dimensional space, and so forth.

The method approximates a local optimum of a problem with n variables when the objective function varies smoothly and is unimodal. Typical implementations minimize functions, and we maximize [math]\displaystyle{ f(\mathbf x) }[/math] by minimizing [math]\displaystyle{ - f(\mathbf x) }[/math].

For example, a suspension bridge engineer has to choose how thick each strut, cable, and pier must be. These elements are interdependent, but it is not easy to visualize the impact of changing any specific element. Simulation of such complicated structures is often extremely computationally expensive to run, possibly taking upwards of hours per execution. The Nelder–Mead method requires, in the original variant, no more than two evaluations per iteration, except for the shrink operation described later, which is attractive compared to some other direct-search optimization methods. However, the overall number of iterations to proposed optimum may be high.

Nelder–Mead in n dimensions maintains a set of n + 1 test points arranged as a simplex. It then extrapolates the behavior of the objective function measured at each test point in order to find a new test point and to replace one of the old test points with the new one, and so the technique progresses. The simplest approach 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 a better point. An intuitive explanation of the algorithm from "Numerical Recipes":

The downhill simplex method now takes a series of steps, most steps just moving the point of the simplex where the function is largest (“highest point”) through the opposite face of the simplex to a lower point. These steps are called reflections, and they are constructed to conserve the volume of the simplex (and hence maintain its nondegeneracy). When it can do so, the method expands the simplex in one or another direction to take larger steps. When it reaches a “valley floor”, the method contracts itself in the transverse direction and tries to ooze down the valley. If there is a situation where the simplex is trying to “pass through the eye of a needle”, it contracts itself in all directions, pulling itself in around its lowest (best) point.

Unlike modern optimization methods, the Nelder–Mead heuristic can converge to a non-stationary point, unless the problem satisfies stronger conditions than are necessary for modern methods. Modern improvements over the Nelder–Mead heuristic have been known since 1979.

Many variations exist depending on the actual nature of the problem being solved. A common variant uses a constant-size, small simplex that roughly follows the gradient direction (which gives steepest descent). Visualize a small triangle on an elevation map flip-flopping its way down a valley to a local bottom. This method is also known as the flexible polyhedron method. This, however, tends to perform poorly against the method described in this article because it makes small, unnecessary steps in areas of little interest.

One possible variation of the NM algorithm

(This approximates the procedure in the original Nelder–Mead article.)

Nelder–Mead method applied to the Rosenbrock function

We are trying to minimize the function [math]\displaystyle{ f(\mathbf x) }[/math], where [math]\displaystyle{ \mathbf x \in \mathbb{R}^n }[/math]. Our current test points are [math]\displaystyle{ \mathbf x_1, \ldots, \mathbf x_{n+1} }[/math].

1. Order according to the values at the vertices:

[math]\displaystyle{ f(\mathbf x_1) \leq f(\mathbf x_2) \leq \cdots \leq f(\mathbf x_{n+1}). }[/math]

Check whether method should stop. See Termination (sometimes called "convergence").

2. Calculate [math]\displaystyle{ \mathbf x_o }[/math], the centroid of all points except [math]\displaystyle{ \mathbf x_{n+1} }[/math].

3. Reflection

Compute reflected point [math]\displaystyle{ \mathbf x_r = \mathbf x_o + \alpha (\mathbf x_o - \mathbf x_{n+1}) }[/math] with [math]\displaystyle{ \alpha \gt 0 }[/math].

If the reflected point is better than the second worst, but not better than the best, i.e. [math]\displaystyle{ f(\mathbf x_1) \leq f(\mathbf x_r) \lt f(\mathbf x_n) }[/math],

then obtain a new simplex by replacing the worst point [math]\displaystyle{ \mathbf x_{n+1} }[/math] with the reflected point [math]\displaystyle{ \mathbf x_r }[/math], and go to step 1.

4. Expansion

If the reflected point is the best point so far, [math]\displaystyle{ f(\mathbf x_r) \lt f(\mathbf x_1) }[/math],

then compute the expanded point [math]\displaystyle{ \mathbf x_e = \mathbf x_o + \gamma (\mathbf x_r - \mathbf x_o) }[/math] with [math]\displaystyle{ \gamma \gt 1 }[/math].

If the expanded point is better than the reflected point, [math]\displaystyle{ f(\mathbf x_e) \lt f(\mathbf x_r) }[/math],

then obtain a new simplex by replacing the worst point [math]\displaystyle{ \mathbf x_{n+1} }[/math] with the expanded point [math]\displaystyle{ \mathbf x_e }[/math] and go to step 1;

else obtain a new simplex by replacing the worst point [math]\displaystyle{ \mathbf x_{n+1} }[/math] with the reflected point [math]\displaystyle{ \mathbf x_r }[/math] and go to step 1.

5. Contraction

Here it is certain that [math]\displaystyle{ f(\mathbf x_r) \geq f(\mathbf x_n) }[/math]. (Note that [math]\displaystyle{ \mathbf x_n }[/math] is second or "next" to the worst point.)

If [math]\displaystyle{ f(\mathbf x_r) \lt f(\mathbf x_{n+1}) }[/math],

then compute the contracted point on the outside [math]\displaystyle{ \mathbf x_c = \mathbf x_o + \rho(\mathbf x_{r} - \mathbf x_o) }[/math] with [math]\displaystyle{ 0 \lt \rho \leq 0.5 }[/math].

If the contracted point is better than the reflected point, i.e. [math]\displaystyle{ f(\mathbf x_c) \lt f(\mathbf x_{r}) }[/math],

then obtain a new simplex by replacing the worst point [math]\displaystyle{ \mathbf x_{n+1} }[/math] with the contracted point [math]\displaystyle{ \mathbf x_c }[/math] and go to step 1;

Else go to step 6;

If [math]\displaystyle{ f(\mathbf x_r) \geq f(\mathbf x_{n+1}) }[/math],

then compute the contracted point on the inside [math]\displaystyle{ \mathbf x_c = \mathbf x_o + \rho(\mathbf x_{n+1} - \mathbf x_o) }[/math] with [math]\displaystyle{ 0 \lt \rho \leq 0.5 }[/math].

If the contracted point is better than the worst point, i.e. [math]\displaystyle{ f(\mathbf x_c) \lt f(\mathbf x_{n+1}) }[/math],

then obtain a new simplex by replacing the worst point [math]\displaystyle{ \mathbf x_{n+1} }[/math] with the contracted point [math]\displaystyle{ \mathbf x_c }[/math] and go to step 1;

Else go to step 6;

6. Shrink

Replace all points except the best ([math]\displaystyle{ \mathbf x_1 }[/math]) with

[math]\displaystyle{ \mathbf x_i = \mathbf x_1 + \sigma(\mathbf x_i - \mathbf x_1) }[/math] and go to step 1.

Note: [math]\displaystyle{ \alpha }[/math], [math]\displaystyle{ \gamma }[/math], [math]\displaystyle{ \rho }[/math] and [math]\displaystyle{ \sigma }[/math] are respectively the reflection, expansion, contraction and shrink coefficients. Standard values are [math]\displaystyle{ \alpha = 1 }[/math], [math]\displaystyle{ \gamma = 2 }[/math], [math]\displaystyle{ \rho = 1/2 }[/math] and [math]\displaystyle{ \sigma = 1/2 }[/math].

For the reflection, since [math]\displaystyle{ \mathbf x_{n+1} }[/math] is the vertex with the higher associated value among the vertices, we can expect to find a lower value at the reflection of [math]\displaystyle{ \mathbf x_{n+1} }[/math] in the opposite face formed by all vertices [math]\displaystyle{ \mathbf x_i }[/math] except [math]\displaystyle{ \mathbf x_{n+1} }[/math].

For the expansion, if the reflection point [math]\displaystyle{ \mathbf x_r }[/math] is the new minimum along the vertices, we can expect to find interesting values along the direction from [math]\displaystyle{ \mathbf x_o }[/math] to [math]\displaystyle{ \mathbf x_r }[/math].

Concerning the contraction, if [math]\displaystyle{ f(\mathbf x_r) \gt f(\mathbf x_n) }[/math], we can expect that a better value will be inside the simplex formed by all the vertices [math]\displaystyle{ \mathbf x_i }[/math].

Finally, the shrink handles the rare case that contracting away from the largest point increases [math]\displaystyle{ f }[/math], something that cannot happen sufficiently close to a non-singular minimum. In that case we contract towards the lowest point in the expectation of finding a simpler landscape. However, Nash notes that finite-precision arithmetic can sometimes fail to actually shrink the simplex, and implemented a check that the size is actually reduced.

Initial simplex

The initial simplex is important. Indeed, a too small initial simplex can lead to a local search, consequently the NM can get more easily stuck. So this simplex should depend on the nature of the problem. However, the original article suggested a simplex where an initial point is given as [math]\displaystyle{ \mathbf x_1 }[/math], with the others generated with a fixed step along each dimension in turn. Thus the method is sensitive to scaling of the variables that make up [math]\displaystyle{ \mathbf x }[/math].

Termination

Criteria are needed to break the iterative cycle. Nelder and Mead used the sample standard deviation of the function values of the current simplex. If these fall below some tolerance, then the cycle is stopped and the lowest point in the simplex returned as a proposed optimum. Note that a very "flat" function may have almost equal function values over a large domain, so that the solution will be sensitive to the tolerance. Nash adds the test for shrinkage as another termination criterion. Note that programs terminate, while iterations may converge.

See also

• Derivative-free optimization
• COBYLA
• NEWUOA
• LINCOA
• Nonlinear conjugate gradient method
• Levenberg–Marquardt algorithm
• Broyden–Fletcher–Goldfarb–Shanno or BFGS method
• Differential evolution
• Pattern search (optimization)
• CMA-ES

Further reading

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 978-0-486-43227-4. 
• Coope, I. D.; Price, C. J. (2002). "Positive Bases in Numerical Optimization". Computational Optimization and Applications 21 (2): 169–176. doi:10.1023/A:1013760716801. 
• Gill, Philip E.; Murray, Walter; Wright, Margaret H. (1981). "Methods for Multivariate Non-Smooth Functions". Practical Optimization. New York: Academic Press. pp. 93–96. ISBN 978-0-12-283950-4. https://archive.org/details/practicaloptimiz00gill. 
• Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier. pp. 24–27. ISBN 0-444-00041-0. https://archive.org/details/methodsforuncons0000kowa/page/24. 
• Swann, W. H. (1972). "Direct Search Methods". in Murray, W.. Numerical Methods for Unconstrained Optimization. New York: Academic Press. pp. 13–28. ISBN 978-0-12-512250-4. 

External links

• Nelder–Mead (Downhill Simplex) explanation and visualization with the Rosenbrock banana function
• John Burkardt: Nelder–Mead code in Matlab - note that a variation of the Nelder–Mead method is also implemented by the Matlab function fminsearch.
• Nelder-Mead optimization in Python in the SciPy library.
• nelder-mead - A Python implementation of the Nelder–Mead method
• NelderMead() - A Go/Golang implementation
• SOVA 1.0 (freeware) - Simplex Optimization for Various Applications
• [1] - HillStormer, a practical tool for nonlinear, multivariate and linear constrained Simplex Optimization by Nelder Mead.