Simplex method

Under the name simplex method one understands a minimizing algorithm for general non-linear functions, due basically to Nelder and Mead Nelder65. More precisely, this is called the downhill simplex method.

The simplex method is an efficient iterative algorithm to solve unconstrained minimization problems numerically for several but not too many variables. Quick convergence and intelligent choice of linearization of the function to be minimized are non-trivial key elements in general minimization algorithms. The simplex method does not use derivatives, analytic or numeric. It attempts to enclose the minimum inside an irregular volume defined by a simplex (= an n-dimensional convex volume bounded by (n-1)-dimensional hyperplanes and defined by n + 1 linearly independent corners, e.g. a tetrahedron for n = 3). The simplex size is continuously changed and mostly diminished, so that finally it is small enough to contain the minimum with the desired accuracy. The operations of changing the simplex optimally with respect to the minimal/maximal function values found at the corners of the simplex are contraction, expansion and reflection, each determining new simplex corner points by linear combinations of selected existing corner points. The details of the method are explained in Nelder65; the method is usually embedded in standard minimizing packages.

A mathematical discussion of the downhill simplex method and of a (quite different) simplex method used in linear programming problems, is found in Press95.