# The Nelder–Mead algorithm¶

The Nelder–Mead algorithm [NM65] attempts to minimize a
goal function \(f : \mathbb{R}^n \to \mathbb{R}\) of an unconstrained
optimization problem.
As it only evaluates function values, but no derivatives, the Nelder–Mead
algorithm is a *direct search method* [KLT03].
Although the method generally lacks rigorous convergence properties
[LRWW98][PCB02], in practice the first few
iterations often yield satisfactory results [SN09].
Typically, each iteration evaluates the goal function only once or twice
[SS04], which is why the Nelder–Mead algorithm is
comparatively fast if goal function evaluation is the computational bottleneck
[SN09].

## The algorithm¶

Nelder & Mead [NM65] refined a simplex method by Spendley et al.
[SHH62].
A simplex is the generalization of triangles in \(\mathbb{R}^2\) to
\(n\) dimensions: in \(\mathbb{R}^n\), a simplex is the convex hull of
\(n+1\) vertices \(x_0, \ldots, x_n \in \mathbb{R}^n\).
Starting with an initial simplex, the algorithm attempts to decrease the
function values \(f_i := f(x_i)\) at the vertices by a sequence of
elementary transformations of the simplex along the local landscape.
The algorithm *succeeds* when the simplex is sufficiently small (*domain
convergence test*), and/or when the function values \(f_i\) are
sufficiently close (*function-value convergence test*).
The algorithm *fails* when it did not succeed after a given number of
iterations or function evaluations.
See Singer & Nead [SN09] and references therein for a
complete description of the algorithm and the simplex transformations.

## Uncertainties in parameter estimation¶

For parameter estimation, Spendley et al. [SHH62] and Nelder & Mead [NM65] provide a method to estimate the uncertainties. Fitting a quadratic surface to the vertices and the midpoints of the edges of the final simplex yields an estimate for the variance–covariance matrix. The variance–covariance matrix is \(\mathbf{Q} \mathbf{B}^{-1} \mathbf{Q}^T\) as originally given by Nelder & Mead [NM65], despite the erratum on the original paper. The errors are the square roots of the diagonal terms [BR03].

## Implementation¶

Scientific Python [JOP1–][Oli07] implements the
Nelder–Mead method for the `scipy.optimize.minimize()`

function.
Note that this implementation only returns the vertex with the lowest function
value, but not the whole final simplex.