Contents - Index


Nelder-Mead Simplex Method

 

The Nelder-Mead Simplex method uses a variation of the Nelder Mead simplex method (1965) is used to minimize a function of multiple variables without derivatives.  The algorithm is described by Press et al. (1989).  A brief description is as follows:  

 

The algorithm uses N + 1 test points (where N is the number of dimensions (i.e., degrees of freedom), which is called a simplex. For example, a two-dimensional problem uses a triangle as its simplex.  All of the points of the simplex are evaluated. The objective function is determined at each point.  The worst point in the simplex is then thrown out and a new point is found by reflecting away from the worst point about the axis formed by the other test points. This process is repeated until one of the stopping criteria are met.  The objective function of the best point is taken to be the optimum.

 

Press et al. (1989) indicate that Nelder-Mead algorithm is not as successful as others, for example, the Conjugate Directions Method or the Variable Metric Method, provided by EES.  This conclusion is perhaps true for an unconstrained optimization.  However, the effectiveness of all of these algorithms is affected by the constraint and, for some problems, the Nelder-Mead seems to be more robust in this situation.

 

The algorithm uses as one of its points, the current values of the independent variables.  The remaining N points are chosen randomly from a range within the lower and upper bounds of each variable.  Because of the random starting points, you may not see the same results with successive runs.  If an optimum is not found, try running the optimization again.  Reducing the bounds will also increase the success of finding an optimum.

 

The Relative Convergence Tolerance provided by the user is taken to be the difference in successive values of the objective function.  The search will terminate if this difference is smaller than the specified tolerance.

 

References:

Nelder, J.A. and Mead, R., (1965) Computer Journal, Vol. 7., p. 308

 

Press, W.H., Flannery, B.P, Teukolsky, S.A., and Vetterling, W.T., "Numerical Recipes in Pascal", 1989, Cambridge University Press, section 10.4.

 

 

Min/Max