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.