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.