Nelder-Mead method

:See simplex algorithm for the numerical solution of the linear programming problem.

Related Topics:
Simplex algorithm - Numerical - Linear programming

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The Nelder-Mead method or Simplex method or downhill simplex method is a commonly used nonlinear regression algorithm. It is due to Nelder & Mead (1965) and is a numerical method for solving many-dimensional problems, belonging to the more general class of search algorithms.

Related Topics:
Nelder-Mead method - Algorithm - Numerical method - Problem - Search algorithm

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The method uses the concept of a simplex, which is a polytope of N + 1 vertices in N dimensions; a line segment on a line, a triangle on a plane, a tetrahedron in three-dimensional space and so forth.

Related Topics:
Simplex - Polytope - Tetrahedron

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The method finds an optimum solution to a problem with N variables when the solution varies smoothly from one point in the N-dimensional solution space to the neighboring points. For example, a 2-dimensional map showing the elevation of a piece of land or the depth of a pool of oil, or optimizing the outcome of an experiment where many conditions are varied over some known range. With an elevation map, simple inspection shows the answer to the question of the highest elevations; thus illustrating that the usefulness of the simplex method lies in cases where the value at various points is hard to come by, and an exhaustive search is infeasible.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

A computer program to use the simplex method to automatically find an optimum is typically of the form: (1) choose N + 1 points, (2) find the values (if unknown) at those points (the elevation, depth, speed, cost, execution time ... whatever is being optimized), (3) stop if we found a good enough value (by any of several criteria), else choose a new point closer to the other points (typically by half) in place of the worst valued point (creating a new smaller simplex), (4) go to step (2).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Many variations exist depending on the actual nature of problem being solved. The most common, perhaps, is to use a constant size small simplex that climbs local gradients to local maximums. Visualize a small triangle on an elevation map flip flopping its way up a hill to a local peak.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~