neldermead

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:

• Jeffrey C. Lagarias, James A. Reeds, Margaret H. Wright, Paul E. Wright "Convergence Properties of the Nelder-Mead Simplex Algorithm in Low Dimensions", SIAM Journal on Optimization,Vol. 9, No. 1 (1998), pages 112-147. http://citeseer.ist.psu.edu/3996.html
• Wright, M. H. (1996) "Direct Search Methods: Once Scorned, Now Respectable" in Numerical Analysis 1995 (Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis) (D.F. Griffiths and G.A. Watson, eds.), 191-208, Addison Wesley Longman, Harlow, United Kingdom. http://citeseer.ist.psu.edu/155516.html

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 unavalaible, 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 cirteria intended to relfect 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

• ftol - the function tolerance to terminate the search for the minimum; default is sqrt( DBL_EPSILON ) ~ 1.19209289551e-07, where DBL_EPSILON is the smallest number x such that 1.0 != 1.0 + x.
• maxfev - the maximum number of function evaluations; default is 1024 * n (number of free parameters).
• scale - the scale size of the initial simplex; see the option initsimplex for more details.
• initsimplex - dictates how the non-degenerate initial simplex is to be constructed. Default is 0; see the "cases for initsimplex" section below for details.
• finalsimplex - at each iteration, a combination of one of the following stopping criteria is tested to see if the simplex has converged or not. Full details are in the "cases for finalsimplex" section below.
• step - a list of length n (number of free parameters) to initialize the simplex; see the option initsimplex for details. The default value is step=[0.4, 0.4, .... 0.4] where n = length( step ).
• seed - the seed for the random number generator; see the option initsimplex for more details. The default value is 7151.
• iquad - boolean which indicates whether a fit to a quadratic surface is done. If iquad is set to one (the default) then a fit to a quadratic surface is done; if iquad is set to 0 then the quadratic surface fit is not done. If the fit to the quadratic surface is not positive semi-definitive, then the search terminated prematurely. The code to fit the quadratic surface was written by D. E. Shaw, CSIRO, Division of Mathematics & Statistics, with amendments by R. W. M. Wedderburn, Rothamsted Experimental Station, and Alan Miller, CSIRO, Division of Mathematics & Statistics. See also Nelder & Mead, The Computer Journal 7 (1965), 308-313.
• verbose - the amount of information to print about the fit progress. Default is 0 (no output).

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:

    x_i   = x_(user_supplied_i) + step_size_i * e_i ; 1 <= i <= n
                             i
where step_size_i  = random( 1.0e-3, scale ) * step_i,
      step_i is the ith element of the option step,
      random( 1.0e-3, scale ) is a random number from 1.0e-3 to scale,
      and e_i is the unit vector. 


if initsimplex == 1:

Then x_(user_supplied) is one of the vertices of the simplex.

The other n vertices are:
              
             { x_(user_supplied_j) + pn,   if i - 1 != j
             {      
    x    =   {			  
     i,j     {			  
             { x_(user_supplied_j) + qn,   otherwise

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

where pn = scale * ( sqrt( n + 1 ) - 1 + npar ) / ( n * sqrt(2) )
      qn = scale * ( 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:

• case 0: same as case a
• case 1: case a, case b and case c have to be met
• case 2: case a and either case b or case c have to be met.

finalsimplex values

• if finalsimplex = 0 then convergence is assumed if case 1 is met.
• finalsimplex = 1 then convergence is assumed if case 2 is met.
• finalsimplex = 2 then convergence is assumed if case 0 is met at two consecutive iterations.
• finalsimplex = 3 then convergence is assumed if case 0 then case 1 are met on two consecutive iterations.
• finalsimplex = 4 then convergence is assumed if case 0 then case 1 then case 0 are met on three consecutive iterations.
• finalsimplex = 5 then convergence is assumed if case 0 then case 1 then case 0 are met on three consecutive iterations.
• finalsimplex = 6 then convergence is assumed if case 1 then case 1 then case 0 are met on three consecutive iterations.
• finalsimplex = 7 then convergence is assumed if case 2 then case 1 then case 0 are met on three consecutive iterations.
• finalsimplex = 8 then convergence is assumed if case 0 then case 2 then case 0 are met on three consecutive iterations.
• finalsimplex = 9 then convergence is assumed if case 0 then case 1 then case 1 are met on three consecutive iterations.
• finalsimplex = 10 then convergence is assumed if case 0 then case 2 then case 1 are met on three consecutive iterations.
• finalsimplex = 11 then convergence is assumed if case 1 then case 1 then case 1 are met on three consecutive iterations.
• finalsimplex = 12 then convergence is assumed if case 1 then case 2 then case 1 are met on three consecutive iterations.
• finalsimplex = 13 then convergence is assumed if case 2 then case 1 then case 1 are met on three consecutive iterations.
• else convergence is assumed if case 2 then case 2 then case 2 are met on three consecutive iterations.