Last modified: December 2013

URL: http://cxc.harvard.edu/sherpa/ahelp/neldermead.html
Jump to: Description · Example · Bugs · See Also


AHELP for CIAO 4.11 Sherpa v1

neldermead

Context: methods

Synopsis

Nelder-Mead Simplex optimization method

Description

The Nelder-Mead Simplex algorithm, devised by J.A. Nelder and R. Mead (Computer Journal, 1965, vol 7, pp 308-313), is a direct search method of optimization for finding local minimum of an objective function of several variables. The implementation of Nelder-Mead Simplex algorithm is a variation of the algorithm outlined in the following two papers:

As noted in the paper, terminating the simplex is not a simple task:

"For any non-derivative method, the issue of termination is problematical as well as highly sensitive to problem scaling. Since gradient information is unavailable, it is provably impossible to verify closeness to optimality simply by sampling f at a finite number of points. Most implementations of direct search methods terminate based on two criteria intended to reflect the progress of the algorithm: either the function values at the vertices are close, or the simplex has become very small."

"Either form of termination-close function values or a small simplex-can be misleading for badly scaled functions."

Method Options

Cases for initsimplex

The option initsimplex (default is 0 ) dictates how the non-degenerate initial simplex is to be constructed:

if initsimplex == 0:

Then x_(user_supplied) is one of the vertices of the simplex. 
The other n vertices are:

    for ( int i = 0; i < n; ++i ) {
    for ( int j = 0; j < n; ++j )
      x[ i + 1 ][ j ] = x_[ j ];
      x[ i + 1 ][ i ] = x_[ i ] + step[ i ];
      }

where step[i] is the ith element of the option step.

if initsimplex == 1:

Then x_(user_supplied) is one of the vertices of the simplex. 
The other n vertices are:

                    { x_[j] + pn,   if i - 1 != j
                    {
        x[i][j]  =  {
                    {
                    { x_[j] + qn,   otherwise

    for 1 <= i <= n, 0 <= j < n

    where pn = ( sqrt( n + 1 ) - 1 + n ) / ( n * sqrt(2) )
          qn = ( sqrt( n + 1 ) - 1 ) / ( n * sqrt(2) )

Cases for finalsimplex

At each iteration, a combination of one of the following stopping criteria is tested to see if the simplex has converged or not.

case a (if the max length of the simplex small enough):

      max(    | x_i - x_0 | ) <= ftol max( 1, | x_0  | )
   1 <= i <= n

case b (if the std dev of the simplex is < ftol):
     
     	n           -   2
       ===   ( f  - f ) 
       \        i                    2
       /     -----------     <=  ftol
       ====   sqrt( n )	
       i = 0

case c (if the function values are close enough):

   f_0  < f_(n-1)     within ftol

The combination of the above stopping criteria are:

finalsimplex values


Example

sherpa> set_method("neldermead")
sherpa> get_method_name()
'neldermead'
sherpa> set_method("simplex")
sherpa> get_method_name()
'neldermead'

Set the optimization method and then confirm the new value. This method may be set by either "neldermead" or "simplex".


Bugs

See the bugs pages on the Sherpa website for an up-to-date listing of known bugs.

See Also

methods
gridsearch, levmar, list_iter_methods, list_methods, moncar, set_method, set_method_opt
statistics
set_sampler_opt