Nelder-Mead

Imagine you are blindfolded on a hilly landscape and want to reach the lowest valley. You cannot see the slope — you can only measure the altitude at the exact spot where you stand. How do you navigate?

That is the core challenge of derivative-free optimization: minimizing a function when its gradient is unknown, expensive to compute, or too noisy to trust. The scenario is more common than it sounds — engineering simulations, drug-dosing models, machine-learning hyperparameter tuning, and countless physical experiments live in this blind-hiker regime.

In 1965, statisticians John Nelder and Roger Mead published a beautifully simple answer: send a small team of hikers carrying a deformable triangle. Each hiker stands at a corner and reports their altitude. The triangle then reshapes — reflecting the worst corner over the opposite edge, expanding if the reflected spot is even better, or contracting toward the best corner if the terrain gets difficult. Over many steps the triangle homes in on a valley floor.

This shape is called a simplex (the generalization of a triangle to any number of dimensions: a tetrahedron in 3D, and so on). The method asks for nothing but the ability to evaluate the function at a point — no formula, no derivative, no gradient descent.

The canvas below shows a 2D landscape as a contour map. The three colored dots are the corners of the simplex — the worst corner (red), the second-worst (orange), and the best (green). Press Step to apply one Nelder-Mead operation, or Run to animate until convergence.

<div class="controls">
  <button id="btnStep" type="button">{{btn_step}}</button>
  <button id="btnRun"  type="button">{{btn_run}}</button>
  <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  <span class="info" id="info">{{step_zero}}</span>
</div>
<canvas id="canvas" width="380" height="320"></canvas>
<div class="legend">
  <span class="dot worst"></span> {{legend_worst}} &nbsp;
  <span class="dot second"></span> {{legend_second}} &nbsp;
  <span class="dot best"></span> {{legend_best}}
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #f4f7fa; }
.controls { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; padding: .5rem 0 .4rem; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }
.info { font-size: .88rem; color: #444; margin-left: .3rem; }
canvas { display: block; border-radius: 10px; border: 1px solid #cdd9e3;
         background: #fff; max-width: 100%; }
.legend { font-size: .8rem; color: #555; margin-top: .4rem; display: flex; align-items: center; gap: .2rem; }
.dot { display: inline-block; width: 11px; height: 11px; border-radius: 50%; }
.dot.worst  { background: #e63946; }
.dot.second { background: #f4a261; }
.dot.best   { background: #2a9d8f; }

// Code not found

Watch how the triangle reflects away from hills, expands when it finds a promising direction, and contracts when it is trapped near a ridge. After enough steps the simplex shrinks to a tiny dot at the minimum.

Nelder-Mead's elegance hides a theoretical embarrassment.

• No general convergence guarantee. For functions of more than one variable, there is no theorem guaranteeing that Nelder-Mead reaches even a local minimum. McKinnon (1998) constructed explicit counterexamples where the simplex converges to a non-stationary point — a spot that is not a minimum — on a perfectly smooth function.
• Yet it works in practice. For low-dimensional problems (roughly n ≤ 10), with moderately smooth objectives, the method almost always converges and does so quickly. Decades of practitioners trust it precisely because gradients are hard while function evaluations are cheap.
• No free lunch. Nelder-Mead fits squarely in the world of non-convex optimization: there is no algorithm that can guarantee finding the global minimum of an arbitrary function. The simplex may converge to a local minimum or even a saddle point, especially in high dimensions.
• Complexity per iteration is $O(n)$ evaluations (at most one new function evaluation per step), making each iteration cheap — but the number of iterations needed grows quickly with dimension, and convergence slows dramatically beyond about 10 variables.
• Restart heuristics partially rescue the method: shrink the simplex, perturb it, and restart. Modern variants (COBYLA, BOBYQA, NEWUOA) fix many of the pathological cases while preserving the gradient-free spirit.

The status of Nelder-Mead is thus unusual: a method proven to fail on adversarial inputs, yet proven indispensable in practice. It occupies the same pragmatic space as many heuristics in non-convex optimization — you use it because the alternative (computing gradients) is worse.

"Minimize this function, but I cannot give you the gradient" is one of the most common requests in applied science, and Nelder-Mead is often the first tool to reach for:

• Pharmacokinetics and pharmacodynamics: fitting drug-concentration curves to patient data requires optimizing nonlinear models where analytical derivatives are impractical. Nelder-Mead has been a standard tool here since the 1970s.
• Engineering design: aerodynamic shape optimization, antenna tuning, and circuit parameter fitting all involve expensive black-box simulations. A single evaluation may take minutes; gradients are not available.
• Machine-learning hyperparameter search: choosing learning rates, regularization constants, and architecture sizes is a black-box problem. Nelder-Mead works well for small numbers of hyperparameters.
• Statistics and maximum-likelihood estimation: the optim() function in R uses Nelder-Mead by default; SciPy's minimize defaults to it when no gradient is supplied. Millions of statistical models are fitted this way every day.
• Robotics and control: tuning PID gains on a physical robot, where each trial takes time and gradients are not computable, is a classic Nelder-Mead use case.

Whenever an experiment, simulation, or black-box system needs to be tuned and derivatives are out of reach, the Nelder-Mead simplex is almost certainly in the toolbox. Its spirit — explore with a flexible shape, shrink toward what works — also echoes in modern methods like Bayesian optimization and evolution strategies.

Nelder-Mead is a paradox in algorithm design: theoretically fragile, practically unbeatable in its niche.

Published in 1965, it offers no guarantee of reaching a local minimum on functions of more than one variable. McKinnon showed it can converge to the wrong point entirely. Yet sixty years later it remains the default optimizer in R, SciPy, MATLAB, and countless scientific pipelines — because the alternative of computing gradients is often impossible, not just inconvenient.

The simplex's secret is its physical intuition. It samples the landscape at a few points, reads which direction is uphill by comparison, and deforms away from it. No calculus. No matrix inversions. Just geometry and a handful of function calls.

When you next reach for scipy.optimize.minimize without specifying a gradient, the Nelder-Mead simplex will quietly deploy its three-point triangle and start feeling its way downhill — imperfect by proof, indispensable in practice.