Nelder-Mead (SciPy)

Downhill Simplex Method

← Back to Optimizer Competition
Nelder-Mead (Nelder & Mead, 1965) maintains a simplex of n + 1 vertices in n-dimensional space and updates it each iteration via reflection, expansion, contraction, or shrinkage moves. HumpDay's NelderMead is a faithful pure-Python port of scipy's implementation — same canonical coefficients (ρ=1, χ=2, ψ=σ=½), same simplex-initialization rules, same convergence test on simplex spread — wrapped in a restart layer that reseeds the simplex when it converges, rather than stopping.

HumpDay's Nelder-Mead at a glance

  • Coefficients: ρ=1 (reflection), χ=2 (expansion), ψ=½ (contraction), σ=½ (shrinkage) — scipy's defaults.
  • Simplex init: from a seed point x0, the remaining vertices perturb one coordinate at a time by 1 + nonzdelt (or zdelt if the coordinate is zero).
  • Convergence: xatol = fatol = 1e-12, tightened from scipy's default 1e-4 so the algorithm uses the full budget where the landscape permits.
  • Restart on collapse: when the simplex meets the convergence test, instead of terminating we reseed and continue. This is HumpDay's own heuristic. The first simplex is built around a uniform draw from [0.3, 0.7]n; restarts then alternate between intensification (reseed around the current best) and diversification (a fresh uniform draw from the whole cube). Each simplex uses a different nonzdelt from the schedule [0.05, 0.15, 0.30, 0.10, 0.50, 0.20] so the new simplex isn't a scaled copy of the collapsed one.

Why restart matters

McKinnon (1998, SIAM J. Optim. 9(1), 148–158, DOI) constructed a family of strictly convex functions of two variables on which vanilla Nelder-Mead converges to a non-stationary point: repeated inside contractions collapse the simplex onto a line orthogonal to the steepest-descent direction. Kelley (1999, SIAM J. Optim. 10(1), 43–55, DOI) proposed a sufficient-decrease test that detects this kind of stagnation and, when the test fails, an oriented restart: a smaller simplex with orthogonal edges, oriented by an approximate descent direction from the current best point. HumpDay's restart layer is not Kelley's procedure. It has no sufficient-decrease test and no oriented simplex; it fires on the ordinary convergence test above and reseeds as described there. Its practical purpose is the budget. A converged simplex stops and hands back whatever evaluations remain: on a two-dimensional sphere with a 200-evaluation budget, scipy's default tolerance of 1e-4 stops it after roughly 50–70 evaluations, and even 1e-12 stops it after roughly 160–190. The restart layer spends the remainder, alternately around the best point found and somewhere new.

Interactive 3D Visualization

See Nelder-Mead in action on 3D optimization surfaces:

Loading 3D visualization...

Requires WebGL support

Instructions: Choose a test function and algorithm, then click Start to watch the step-by-step optimization process.

Auto-selection metadata. Consulted by humpday.minimize() when picking a default algorithm.
  • Overhead tier 1: light (~100µs/iter). Eligible when measured eval_time ≥ 10 µs.
  • Dimensional cap: n_dim ≤ 20 — simplex degenerates past ~20 dims.
  • Minimum trials: 10 — baseline minimum.

Implementation Details

Component Details Links
Original Algorithm John Nelder & Roger Mead
Simplex-based direct search method
Uses geometric transformations of n+1 vertices
Published: 1965 		Paper
Reference Implementation scipy.optimize Nelder-Mead
scipy's Fortran-backed simplex method.
Reference: scipy.optimize.minimize(method='Nelder-Mead') 		SciPy Docs
HumpDay Python HumpDay NelderMead
Pure-Python simplex method, faithful to scipy's parameters and convergence test.
No required dependencies.
File: humpday/optimizers/scipy_algorithms.py 		Source
HumpDay JavaScript Browser NelderMead
Mirrors the Python port.
Class: NelderMead 		JS Port

Performance Characteristics

  • Best for: Low-dimensional black-box objectives where the simplex moves can navigate the surface without curvature information.
  • Worst for: High dimensions — simplex moves degenerate past ~10-20 dimensions because the relevant geometry becomes too thin.
  • Per iteration: 1 reflection eval; possibly 1 expansion or 1-2 contraction evals; rarely n+1 shrinkage evals.
  • Relative to scipy.optimize Nelder-Mead at n_trials=200, n_dim=2: ties across sphere, Rosenbrock, and Ackley — algorithmically identical, differs only in the interpreter tax. See SOTA status for the live numbers.

Educational Resources

Algorithm Visualization

The Nelder-Mead method is one of the most visually intuitive optimization algorithms. The simplex (triangle in 2D) moves through the parameter space by:

  • Reflection: Mirror the worst point across the centroid
  • Expansion: If reflection improves, try going further
  • Contraction: If reflection fails, contract toward the best point
  • Shrinkage: If all else fails, shrink the entire simplex