Nelder–Mead Method

Nelder–Mead method, also known as the downhill simplex method or amoeba method, is a direct-search, derivative-free numerical optimization algorithm in computation and algorithms and applied statistics, published by John A. Nelder and Roger Mead in 1965 as an adaptive extension of the fixed-step simplex design of Spendley, Hext, and Himsworth (1962). Given an unconstrained objective function f : ℝⁿ → ℝ whose analytical derivatives are unavailable, noisy, discontinuous, or expensive to evaluate, the Nelder–Mead algorithm maintains a non-degenerate geometric simplex—the convex hull of n + 1 vertices {x₁, x₂, …, x_n+1} in ℝⁿ (a triangle in ℝ², a tetrahedron in ℝ³, similar to a single cell of a Delaunay triangulation).

At each iteration, the algorithm orders the vertices by their function values f(x₁) ≤ f(x₂) ≤ ⋯ ≤ f(x_n+1) and replaces the worst vertex x_n+1 by reflecting, expanding, or contracting it through the centroid x̄ of the remaining n best vertices, or by shrinking the simplex toward x₁. Unlike George Dantzig's linear-programming simplex algorithm—which walks along vertices of a polyhedral feasible region—the Nelder–Mead downhill simplex moves across unconstrained ℝⁿ using 1 or 2 function evaluations per step and zero derivatives, in contrast to gradient descent, Newton's method, and the Broyden–Fletcher–Goldfarb–Shanno algorithm.

At the start of an iteration, the n + 1 vertices of the current simplex Δ_k are sorted so that:

f(x₁) ≤ f(x₂) ≤ ⋯ ≤ f(x_n) ≤ f(x_n+1),

where x₁ is the best vertex, x_n is the second-worst ("next-to-worst") vertex, and x_n+1 is the worst vertex. Next, the algorithm computes the centroid x̄ of the n best vertices (excluding x_n+1):

x̄ = (1 / n) ∑_i=1ⁿ x_i.

All trial points lie along the line passing through x_n+1 and x̄, parameterized by four standard scalar coefficients (Nelder & Mead, 1965): reflection α = 1, expansion γ = 2, contraction ρ = 1/2, and shrink σ = 1/2 (satisfying α > 0, γ > 1, γ > α, and 0 < ρ, σ < 1).

The Five Decision Rules per Iteration

1. Reflection: Compute the reflected point x_r = x̄ + α(x̄ − x_n+1). If f(x₁) ≤ f(x_r) < f(x_n) (meaning x_r is better than the second-worst vertex x_n, though not better than the current best x₁), accept x_r in place of x_n+1 and terminate the iteration.
2. Expansion: If f(x_r) < f(x₁) (the reflection produced a new overall best point), probe further in this promising direction by computing the expanded point x_e = x̄ + γ(x_r − x̄). If f(x_e) < f(x_r), accept x_e; otherwise accept x_r (a "greedy minimization" rule).
3. Outside Contraction: If f(x_n) ≤ f(x_r) < f(x_n+1), compute the outside contracted point x_oc = x̄ + ρ(x_r − x̄). If f(x_oc) ≤ f(x_r), accept x_oc; otherwise proceed to Step 5 (Shrink).
4. Inside Contraction: If f(x_r) ≥ f(x_n+1) (the reflected point is even worse than x_n+1), compute the inside contracted point x_ic = x̄ − ρ(x̄ − x_n+1). If f(x_ic) < f(x_n+1), accept x_ic; otherwise proceed to Step 5 (Shrink).
5. Shrink (Homothety): When both reflection and contraction fail to improve upon x_n+1, contract all n non-best vertices halfway toward the best vertex x₁:

x_i ← x₁ + σ(x_i − x₁) for i = 2, 3, …, n + 1.

In practice, shrink steps are rare on smooth functions (Lagarias et al., 1998 proved that shrink steps never occur on uniformly convex functions in 1D and 2D with standard parameters), so almost every iteration costs 1 or 2 function evaluations.

Lagarias–Reeds–Wright–Wright Convergence Analysis and McKinnon's 1998 Counterexample

For more than three decades after 1965, Nelder–Mead was widely used across science without general convergence proofs. In 1998, Jeffrey C. Lagarias, James A. Reeds, Margaret H. Wright, and Paul E. Wright proved that in dimension n = 1, the Nelder–Mead method converges to the minimizer for any uniformly convex function, and in dimension n = 2, the simplex diameter converges to zero for uniformly convex functions with bounded level sets.

In the same year, however, Kenneth I. M. McKinnon constructed a family of smooth, uniformly convex two-dimensional functions—including one with a positive-definite Hessian everywhere—on which the standard Nelder–Mead simplex repeatedly performs inside contractions perpendicular to the steepest descent direction. The triangles become progressively more elongated and degenerate, causing all three vertices to converge to a non-stationary point where the gradient ∇f(x) ≠ 0.

Safeguarding and Adaptive High-Dimensional Parameters (Gao–Han)

To prevent McKinnon-type simplex flattening and ensure convergence to a stationary point, two remedies are widely adopted:

1. Kelley's Oriented Restart and Torczon's Multidirectional Search (MDS): C. T. Kelley (1999) introduced a sufficient-decrease test tied to the simplex gradient condition number: whenever the simplex becomes flat relative to step progress, it is re-initialized as a right-angled coordinate frame around x₁. Virginia Torczon's Multidirectional Search (MDS) reflects and expands all n non-best edges through x₁ simultaneously, preserving the angles of the initial simplex at every step and ensuring convergence on continuously differentiable functions.
2. Gao–Han Dimension-Adaptive Parameters (2012): As dimension n grows beyond n = 10, fixed parameters (α = 1, γ = 2, ρ = 1/2, σ = 1/2) cause the centroid x̄ of n vertices to weight each vertex by only 1/n, flattening the simplex along the reflection axis. Fuchang Gao and Lixing Han (2012) derived dimension-dependent parameters that preserve simplex interior angles in ℝⁿ:

α = 1, γ = 1 + 2/n, ρ = 0.75 − 1/(2n), σ = 1 − 1/n, which serves as the adaptive option in MATLAB's fminsearch and SciPy's optimize module.

How does the Nelder–Mead simplex method differ from Dantzig's simplex algorithm?

Despite sharing the geometric word simplex, the two algorithms solve different problems: George Dantzig's simplex algorithm (1947) is an algebraic solver for linear programming (optimizing a linear objective subject to linear inequality constraints by pivoting between vertices of a polyhedron), whereas the Nelder–Mead method (1965) is a derivative-free heuristic for unconstrained nonlinear optimization of black-box functions—such as tuning hyperparameters of a particle filter or Kalman filter.

Why should Nelder–Mead be restarted after initial convergence?

Because the simplex can lose rank and flatten into a subspace along curved valleys, building a fresh orthogonal simplex around the converged vertex x and running a second pass verifies that x is a true local minimum in all n coordinate directions.

1. Nelder, J. A., & Mead, R. (1965). A simplex method for function minimization. The Computer Journal, 7(4), 308–313. https://doi.org/10.1093/comjnl/7.4.308
2. Lagarias, J. C., Reeds, J. A., Wright, M. H., & Wright, P. E. (1998). Convergence properties of the Nelder–Mead simplex method in low dimensions. SIAM Journal on Optimization, 9(1), 112–147. https://doi.org/10.1137/S1052623496303470
3. McKinnon, K. I. M. (1998). Convergence of the Nelder–Mead simplex method to a nonstationary point. SIAM Journal on Optimization, 9(1), 148–158. https://doi.org/10.1137/S1052623496303482
4. Gao, F., & Han, L. (2012). Implementing the Nelder–Mead simplex algorithm with adaptive parameters. Computational Optimization and Applications, 51(1), 259–277. https://doi.org/10.1007/s10589-010-9329-3