NelderMead

class sherpa.optmethods.NelderMead(name='simplex')

Bases: OptMethod

Nelder-Mead Simplex optimization method.

The Nelder-Mead Simplex algorithm, devised by J.A. Nelder and R. Mead [1], is a direct search method of optimization for finding a local minimum of an objective function of several variables. The implementation of the Nelder-Mead Simplex algorithm is a variation of the algorithm outlined in [2] and [3]. As noted, 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.”

ftol

The function tolerance to terminate the search for the minimum; the default is sqrt(DBL_EPSILON) ~ 1.19209289551e-07, where DBL_EPSILON is the smallest number x such that 1.0 != 1.0 + x.

Type:

number

maxfev

The maximum number of function evaluations; the default value of None means to use 1024 * n, where n is the number of free parameters.

Type:

int or None

initsimplex

Dictates how the non-degenerate initial simplex is to be constructed. Default is 0; see the “cases for initsimplex” section below for details.

Type:

int

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.

Type:

int

step

A list of length n (number of free parameters) to initialize the simplex; see the initsimplex for details. The default of None means to use a step of 0.4 for each free parameter.

Type:

array of number or None

iquad

A boolean flag which indicates whether a fit to a quadratic surface is done. If iquad is set to 1 (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 [1].

Type:

int

verbose

The amount of information to print during the fit. The default is 0, which means no output.

Type:

int

reflect

When a parameter exceeds a limit should the parameter be reflected, so moved back within bounds (True, the default) or should the model evaluation return DBL_MAX, causing the current set of parameters to be excluded from the simplex.

Type:

bool

Notes

The initsimplex option determines how the non-degenerate initial simplex is to be constructed:

• when initsimplex is 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 is 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 and:

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

The finalsimplex option determines whether the simplex has converged:

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

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

• case b (if the standard deviation 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.

The finalsimplex value controls which of these criteria need to hold:

• if finalsimplex=0 then convergence is assumed if case 1 is met.

• if finalsimplex=1 then convergence is assumed if case 2 is met.

• if finalsimplex=2 then convergence is assumed if case 0 is met at two consecutive iterations.

• if finalsimplex=3 then convergence is assumed if case 0 then case 1 are met on two consecutive iterations.

• if finalsimplex=4 then convergence is assumed if case 0 then case 1 then case 0 are met on three consecutive iterations.

• if finalsimplex=5 then convergence is assumed if case 0 then case 1 then case 0 are met on three consecutive iterations.

• if finalsimplex=6 then convergence is assumed if case 1 then case 1 then case 0 are met on three consecutive iterations.

• if finalsimplex=7 then convergence is assumed if case 2 then case 1 then case 0 are met on three consecutive iterations.

• if finalsimplex=8 then convergence is assumed if case 0 then case 2 then case 0 are met on three consecutive iterations.

• if finalsimplex=9 then convergence is assumed if case 0 then case 1 then case 1 are met on three consecutive iterations.

• if finalsimplex=10 then convergence is assumed if case 0 then case 2 then case 1 are met on three consecutive iterations.

• if finalsimplex=11 then convergence is assumed if case 1 is met on three consecutive iterations.

• if finalsimplex=12 then convergence is assumed if case 1 then case 2 then case 1 are met on three consecutive iterations.

• if finalsimplex=13 then convergence is assumed if case 2 then case 1 then case 1 are met on three consecutive iterations.

• otherwise convergence is assumed if case 2 is met on three consecutive iterations.

References

[1] (1,2)

“A simplex method for function minimization”, J.A. Nelder and R. Mead (Computer Journal, 1965, vol 7, pp 308-313) https://doi.org/10.1093%2Fcomjnl%2F7.4.308

[2]

“Convergence Properties of the Nelder-Mead Simplex Algorithm in Low Dimensions”, Jeffrey C. Lagarias, James A. Reeds, Margaret H. Wright, Paul E. Wright , SIAM Journal on Optimization, Vol. 9, No. 1 (1998), pages 112-147. http://citeseer.ist.psu.edu/3996.html

[3]

“Direct Search Methods: Once Scorned, Now Respectable” Wright, M. H. (1996) 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

Attributes Summary

default_config

The default settings for the optimiser.

Methods Summary

fit(statfunc, pars, parmins, parmaxes[, ...])

Run the optimiser.

Attributes Documentation

default_config

The default settings for the optimiser.

Methods Documentation

fit(statfunc, pars, parmins, parmaxes, statargs=(), statkwargs=None)

Run the optimiser.

Changed in version 4.16.0: The statkwargs argument now defaults to None rather than {}.

Parameters:

• statfunc (function) – Given a list of parameter values as the first argument and, as the remaining positional arguments, statargs and statkwargs as keyword arguments, return the statistic value.

• pars (sequence) – The start position of the model parameter values.

• parmins (sequence) – The minimum allowed values for each model parameter. This must match the length of pars.

• parmaxes (sequence) – The maximum allowed values for each model parameter. This must match the length of pars.

• statargs (optional) – Additional positional arguments to send to statfunc.

• statkwargs (dict, optional) – Additional keyword arguments to send to statfunc.

Returns:

newpars – The tuple contains: boolean indicating whether the optimization succeeded or not, the best fit parameters as a NumPy array, the statistic value at the best-fit location, a string message indicating the status, and a dictionary containing information about the optimisation (this depends on the optimiser).

Return type:

tuple