Does the algorithm need gradients?

No. Its usual form uses objective-function values at candidate points.

Does it always find the best possible solution?

No. It can miss better regions and has known convergence limitations.

How many vertices does a two-parameter simplex have?

Three. In general, n parameters require n + 1 simplex vertices.

AI Glossary / Computer vision and multimodal AI / Intermediate

Downhill simplex

Definition

Downhill simplex is a derivative-free optimization method commonly referring to the Nelder - Mead algorithm. It searches for a low value of an objective function by moving and reshaping a set of candidate points called a simplex. It uses function evaluations rather than gradients and does not guarantee finding the global minimum.

What it means

An optimization problem asks which input settings make a chosen score as small as possible. For example, two image-alignment parameters might be adjusted to reduce a mismatch score between images.

In two dimensions, a simplex is a triangle containing three candidate points. In three dimensions, it is a tetrahedron with four. In n dimensions, it has n + 1 vertices. The algorithm compares the objective values at those vertices and proposes new points based on their relative performance.

The name can be misleading. This is different from the simplex method for linear programming, and its simplex is not a probability distribution. It is a geometric set used to organize a direct search through parameter space.

How it works

Choose an initial point and construct a nondegenerate simplex around it. Its size and orientation affect which parameter changes are explored first, so variable scaling matters.

Evaluate the objective at every vertex and order the vertices from better to worse. The method uses the centroid of the better vertices to propose a reflected replacement for the worst vertex.

Depending on the resulting objective value, it may expand the move, contract it, or shrink the simplex toward the best vertex. These operations allow the search region to move and change size without explicitly calculating a gradient.

Stop according to criteria such as small changes in vertex positions and objective values, or a limit on evaluations. Check the result rather than interpreting a stopping message as proof of optimality. The method can stagnate, depend strongly on initialization, or converge to an unsuitable point on some problems.

Three practical examples

1. Image alignment: A prototype adjusts a small number of transformation parameters to reduce a measured image mismatch.

2. Simulation tuning: An engineer searches a low-dimensional set of simulator settings when derivatives are unavailable or inconvenient.

3. Experimental comparison: A researcher uses a direct-search baseline to compare against gradient-based optimization on a manageable objective.

Think of it this way

Think of three scouts on a landscape comparing their elevations and repositioning their triangle to seek lower ground. They infer promising directions from the heights they observe instead of measuring the slope directly.

The analogy is limited because objective landscapes can have many dimensions, numerical noise, or discontinuities. Also, a triangle that becomes very small is not necessarily sitting at the lowest point, or even at a true local minimum.

Worked example

Take the objective f(x, y) = x squared + y squared. Start with vertices A = (1, 0), B = (0, 1), and C = (2, 2).

Their objective values are 1, 1, and 8, so C is the worst vertex. The centroid of A and B is M = (0.5, 0.5). Using a standard reflection coefficient of 1, reflect C through M: R = 2M - C = (-1, -1). Its objective value is 2.

In a common Nelder - Mead decision rule, this reflected point is better than the worst value but not better than the second-worst value, so an outside contraction is considered. With contraction coefficient 0.5, the candidate is M + 0.5(R - M) = (-0.25, -0.25).

Its objective value is 0.125, which is better than the reflected value, so the contracted point replaces C. This is one illustrative iteration, not a full optimization run. The true minimum of this teaching function is zero at (0, 0), which the iteration has not yet reached.

Illustrative case study

Fictional case study: AlignLab tunes horizontal and vertical offsets for a pair of scanned labels. A downhill-simplex search reduces its mismatch score from one starting configuration but gives a different result from another.

The team inspects the objective and finds repeated printed patterns that create several attractive alignments. It tests multiple starts, improves the score's use of distinctive image regions, and checks the final transformation visually and numerically.

This fictional case illustrates local-search limitations. It does not claim that multiple starts guarantee the correct alignment or that the algorithm is the most efficient choice for every registration problem.

Common misconceptions and mistakes

Do not confuse downhill simplex with linear-programming simplex. They solve different formulations using different mechanisms.

Do not interpret derivative-free as assumption-free. Objective noise, parameter scaling, dimensionality, and initialization still affect behavior.

Do not assume every iteration simply moves downhill along a slope. The method evaluates geometric proposals and makes decisions from their function values.

Do not treat a small simplex or small objective change as proof of a global optimum. Stopping criteria describe numerical progress, not a universal mathematical guarantee.

Business use

Downhill simplex can be a convenient option for small optimization problems when a score can be evaluated but derivatives are unavailable. It is often straightforward to prototype, making it useful for comparisons and exploratory tuning.

Teams should measure the number and cost of objective evaluations, test sensitivity to the initial simplex, and scale parameters sensibly. Compare against alternatives when reliable gradients exist or when the dimension grows. Report the achieved objective and validation evidence separately from the solver's termination status so stakeholders understand what was actually established.

Check your understanding

Why is a shrinking simplex not sufficient evidence that the search found a true minimum?

Answer: The vertices can become close together because the method stagnated or followed an unfavorable path. Their proximity alone does not establish the objective's optimality conditions.

Related terms

Derivative-free optimization
Objective function
Gradient descent
Image registration
Nelder–Mead method
local minimum
parameter scaling

Learn next

Learn local versus global optimization next, then compare Nelder - Mead with a gradient-based method on a simple two-dimensional objective. Plot the evaluations and vary the starting point to see how search behavior changes.

Sources

SciPy, minimize with Nelder–Mead: primary software documentation consulted for simplex initialization and stopping controls. https://docs.scipy.org/doc/scipy/reference/optimize.minimize-neldermead.html

Lagarias, Poonen, and Wright, Convergence of the restricted Nelder–Mead algorithm in two dimensions: primary research abstract consulted for convergence scope and limitations. The iteration and fictional case above are original. https://arxiv.org/abs/1104.0350

Previous: Doubly robust off-policy evaluation Next: Downward refinement property