next up previous contents
Next: Simulated Annealing Up: Global Optimization Previous: Global Optimization

Simplex Algorithm

 

The Simplex algorithm is an elegant method for function minimization which, though not strictly `global' (in the sense that it searches all parameter space), is able to crawl out of some local minima to find better minima. It requires only function evaluations, not derivatives, but unlike Powell's method (2.4.1) it neither uses line minimizations nor builds an implicit model of the derivative structure of the function. This makes it the method of choice for noisy functions. Though slower than Powell's, it is more robust.

A simplex is the geometrical figure in n dimensions consisting of n+1 vertices. In 2-D it is a triangle, in 3-D a tetrahedron. The Simplex Algorithm for minimization takes such a set of n+1 points and attempts to move them into a minimum. The simplex formed from the points should be non-degenerate, it should have a non-zero volume. If your initial guess is the other n points of the simplex can be initialized as where are unit vectors ().

The algorithm then takes a series of steps. It will either

The overall effect is for the simplex to crawl around the parameter space, creeping down valleys and shrinking to get to the very bottom of narrow valleys. Details are given in [6].



Bob Fisher
Fri Mar 28 14:12:50 GMT 1997