It is an optimization algorithm named after the developers of the technique, John Nelder and Roger Mead.
The algorithm was described in their 1965 paper titled “A Simplex Method For Function Minimization” and has become a standard and widely used technique for function optimization.
It is appropriate for one-dimensional or multidimensional functions with numerical inputs.
Nelder-Mead is a pattern search optimization algorithm, which means it does not require or use function gradient information and is appropriate for optimization problems where the gradient of the function is unknown or cannot be reasonably computed.
It is often used for multidimensional nonlinear function optimization problems, although it can get stuck in local optima.
Practical performance of the Nelder–Mead algorithm is often reasonable, though stagnation has been observed to occur at nonoptimal points. Restarting can be used when stagnation is detected.
— Page 239, Numerical Optimization, 2006.
A starting point must be provided to the algorithm, which may be the endpoint of another global optimization algorithm or a random point drawn from the domain.
Given that the algorithm may get stuck, it may benefit from multiple restarts with different starting points.
The Nelder-Mead simplex method uses a simplex to traverse the space in search of a minimum.
— Page 105, Algorithms for Optimization, 2019.
The algorithm works by using a shape structure (called a simplex) composed of n + 1 points (vertices), where n is the number of input dimensions to the function.
For example, on a two-dimensional problem that may be plotted as a surface, the shape structure would be composed of three points represented as a triangle.
The Nelder-Mead method uses a series of rules that dictate how the simplex is updated based on evaluations of the objective function at its vertices.
— Page 106, Algorithms for Optimization, 2019.
The points of the shape structure are evaluated and simple rules are used to decide how to move the points of the shape based on their relative evaluation. This includes operations such as “reflection,” “expansion,” “contraction,” and “shrinkage” of the simplex shape on the surface of the objective function.
In a single iteration of the Nelder–Mead algorithm, we seek to remove the vertex with the worst function value and replace it with another point with a better value. The new point is obtained by reflecting, expanding, or contracting the simplex along the line joining the worst vertex with the centroid of the remaining vertices. If we cannot find a better point in this manner, we retain only the vertex with the best function value, and we shrink the simplex by moving all other vertices toward this value.
— Page 238, Numerical Optimization, 2006.
The search stops when the points converge on an optimum, when a minimum difference between evaluations is observed, or when a maximum number of function evaluations are performed.