What if you can tell whether one answer is better than another, but you cannot reliably calculate a gradient? Nelder–Mead is one of the clearest algorithms for learning how optimisation can proceed from comparisons alone. It maintains a small geometric shape called a simplex, evaluates the objective function at its vertices, and repeatedly moves that shape toward lower values.
This article teaches the method as a Learning Hall progression: first see the geometry, then trace the decision rules, then implement the algorithm, and finally examine the numerical and engineering conditions that determine whether it is a sensible professional choice. It complements the broader Numerical Optimisation Algorithms article rather than replacing it.
Quick Read
- Nelder–Mead minimises a scalar objective without requiring derivatives.
- In n dimensions it keeps n + 1 vertices: a line segment in 1D, a triangle in 2D, a tetrahedron in 3D.
- Each iteration ranks the vertices, computes the centroid of the better vertices, then tries reflection, expansion, contraction or shrinkage.
- The algorithm is simple and useful, but it is not a universal optimiser: scaling, dimensionality, noise, local minima and stopping criteria matter.
- Professionally, treat function evaluations as the expensive resource and validate convergence rather than trusting a success flag blindly.
1. Beginner Level: A Triangle That Learns Where Downhill Is
Imagine a landscape where height represents cost. You cannot see the slope, but you may stand at a few locations and read their heights. In two variables, Nelder–Mead places a triangle on this landscape. Suppose its three vertices have objective values 3, 5 and 12. The point scoring 12 is the worst. A reasonable first move is to push that bad corner through the opposite side of the triangle and test the reflected point.
If reflection produces a much better value, the algorithm tries going farther in the same direction: expansion. If reflection is disappointing, it tries a shorter move: contraction. If even contraction fails, the simplex shrinks toward its best vertex. The algorithm therefore behaves like a cautious geometric search: explore when evidence is encouraging, retreat when it is not, and reduce the search scale when necessary.
2. The Five Objects You Must Keep Straight
- Vertices: the current candidate points.
- Objective values: the score at each vertex; lower is better for minimisation.
- Best, second-worst and worst: the ranking that drives the branch logic.
- Centroid: the average of all vertices except the worst.
- Move coefficients: reflection, expansion, contraction and shrink parameters.
A common source of confusion is that the centroid does not include the worst point. The algorithm is asking: “Where is the centre of the part of the simplex that is currently doing reasonably well?” The worst point is then moved relative to that centre.
3. The Four Moves
Let c be the centroid of every vertex except the worst vertex xw. With the classic coefficients α = 1, γ = 2, ρ = 1/2 and σ = 1/2, the moves can be understood geometrically.
- Reflection: try xr = c + α(c − xw). This mirrors the worst point across the centroid.
- Expansion: if reflection is exceptionally good, try farther along that direction: xe = c + γ(xr − c).
- Contraction: if reflection is poor, test a point closer to the centroid.
- Shrink: keep the best vertex and move every other vertex toward it by the shrink factor σ.
The important learning target is not memorising four formulas. It is understanding the decision pattern: rank → centre → probe → judge → enlarge or retreat.
4. A Worked Two-Dimensional Example
Consider f(x, y) = (x − 2)² + (y + 1)². Its minimum is at (2, −1), but pretend we do not know that. Start with three vertices A = (0, 0), B = (1, 0), C = (0, 1).
- f(A) = 5
- f(B) = 2
- f(C) = 8
C is worst. The centroid of A and B is c = (0.5, 0). Reflection gives xr = (1, −1). Its value is 1, better than the current best value 2, so expansion is worth testing. Expansion gives xe = (1.5, −2), whose value is 1.25. Reflection was better, so we keep the reflected point rather than the expanded one. One iteration has already moved the simplex toward the basin containing the optimum.
This is a useful tracing exercise because the algorithm does not “know” the formula’s gradient. All direction emerges from comparing sampled values.
5. Pseudocode
build n + 1 vertices
repeat:
sort vertices by objective value
best = first
worst = last
centroid = average(all except worst)
reflected = reflect(worst across centroid)
if reflected is better than best:
expanded = expand beyond reflected
keep better of expanded and reflected
else if reflected is better than second-worst:
replace worst with reflected
else:
contracted = contract toward centroid
if contracted improves the relevant bad point:
replace worst with contracted
else:
shrink every non-best vertex toward best
until simplex size and objective spread are small enough6. A Readable Python Implementation
import numpy as np
def nelder_mead(f, simplex, tol_x=1e-8, tol_f=1e-10, max_iter=5000):
simplex = np.asarray(simplex, dtype=float).copy()
n = simplex.shape[1]
if simplex.shape != (n + 1, n):
raise ValueError("simplex must have shape (n+1, n)")
alpha, gamma, rho, sigma = 1.0, 2.0, 0.5, 0.5
values = np.array([f(x) for x in simplex], dtype=float)
for iteration in range(max_iter):
order = np.argsort(values)
simplex = simplex[order]
values = values[order]
diameter = np.max(np.linalg.norm(simplex[1:] - simplex[0], axis=1))
spread = np.max(np.abs(values - values[0]))
if diameter <= tol_x and spread <= tol_f:
return simplex[0], values[0], iteration
centroid = simplex[:-1].mean(axis=0)
worst = simplex[-1]
xr = centroid + alpha * (centroid - worst)
fr = f(xr)
if fr < values[0]:
xe = centroid + gamma * (xr - centroid)
fe = f(xe)
if fe < fr:
simplex[-1], values[-1] = xe, fe
else:
simplex[-1], values[-1] = xr, fr
elif fr < values[-2]:
simplex[-1], values[-1] = xr, fr
else:
if fr < values[-1]:
xc = centroid + rho * (xr - centroid)
fc = f(xc)
if fc <= fr:
simplex[-1], values[-1] = xc, fc
continue
else:
xc = centroid + rho * (worst - centroid)
fc = f(xc)
if fc < values[-1]:
simplex[-1], values[-1] = xc, fc
continue
best = simplex[0].copy()
for i in range(1, n + 1):
simplex[i] = best + sigma * (simplex[i] - best)
values[i] = f(simplex[i])
order = np.argsort(values)
return simplex[order[0]], values[order[0]], max_iterFor learning, this explicit version is valuable because every branch is visible. In production work, prefer a mature numerical library unless you have a reason to own the implementation.
7. What “Correctness” Means Here
Nelder–Mead is unlike binary search, where we can prove that an invariant always preserves the target interval and derive a clean logarithmic bound. The algorithm has a deterministic update rule, but its global convergence behaviour is more delicate. There are known examples where Nelder–Mead can converge to non-stationary points, and convergence theory depends on the exact variant and assumptions.
So the professional habit is to separate three claims: the code followed the Nelder–Mead rules, the run terminated according to a numerical criterion, and the returned point is genuinely an acceptable solution to the optimisation problem. Those are not identical statements.
8. Complexity: Count Function Evaluations First
Each iteration performs vector operations that are roughly linear in the dimension, but objective evaluations usually dominate. A normal iteration may need one or two new evaluations; a shrink can require evaluations at every non-best vertex. Unlike gradient methods, there is no general iteration bound that makes “Nelder–Mead is O(…)” a useful one-line description of the full optimisation task.
If one objective evaluation launches a simulation, trains a model, runs a laboratory surrogate, or solves another numerical system, then the engineering budget should be expressed in function evaluations, not only wall-clock iterations.
9. Failure Modes That Strong Learners Should Test
- Poor scaling: one variable ranges near 10⁻⁶ while another ranges near 10⁶; simplex geometry becomes awkward.
- Bad initial simplex: vertices are too close, too large, nearly degenerate, or placed in an unhelpful basin.
- Noise: small value differences may reflect measurement noise rather than genuine improvement.
- High dimension: the simplex has n + 1 vertices and the method can become inefficient.
- Local minima: a successful local run does not prove global optimality.
- Bounds: naive clipping can distort the search geometry.
- Weak stopping rules: small objective spread can occur on a flat plateau even when the point is not satisfactory.
10. Professional-Level Practice
In a professional workflow, scale variables before optimisation, record every objective evaluation, use explicit evaluation budgets, inspect both the simplex diameter and objective-value spread, and consider restarts from different initial points. If gradients are reliable, compare against gradient-based alternatives. If the objective is noisy or expensive, consider whether a method designed for that regime is more appropriate.
Current SciPy documentation exposes Nelder–Mead through scipy.optimize.minimize, including controls for the initial simplex, iteration and evaluation limits, parameter tolerances, bounds and adaptive coefficients. SciPy notes that its bound handling clips simplex vertices; that detail matters when interpreting constrained behaviour. The adaptive parameter option is based on Gao and Han’s dimension-dependent coefficients.
11. A Four-Stage Learning Route
- Beginner: move a triangle by hand on a contour plot and label best/worst vertices.
- Intermediate: trace the branch logic for reflection, expansion, contraction and shrinkage.
- Advanced: implement the algorithm with numerical stopping rules and diagnostic logging.
- Professional: compare implementations, scale variables, test restarts, measure evaluation cost, and verify whether another optimiser gives a more defensible solution.
12. Practice Problems
- Trace one full iteration on f(x, y) = x² + 4y² from a triangle of your choice.
- Change the scale of y by a factor of 1000 and observe how the search changes.
- Add random noise to the objective and test whether the stopping rule becomes unreliable.
- Compare classic and adaptive coefficients on dimensions 2, 10 and 50.
- Run five random restarts on the Rosenbrock function and compare evaluation counts.
- Explain why “terminated successfully” is not the same as “found the global minimum.”
13. Sources and Further Reading
- Nelder & Mead (1965), A Simplex Method for Function Minimization.
- SciPy optimisation documentation.
- Gao & Han, adaptive Nelder–Mead parameters.
- Scholarpedia: Nelder–Mead algorithm.
- Recent review of Nelder–Mead convergence questions.
- Programming education research on subgoal-labelled worked examples.
- Worked examples and metacognitive scaffolding in programming.
Final idea: Nelder–Mead is valuable not because it removes the need to think about optimisation, but because it makes the act of searching visible. The simplex is a moving record of what the algorithm has tried, what it currently trusts, and how strongly the evidence supports the next move.
