Available Optimization Methods

The primary task of Sherpa is to fit a model to a set of observed data, where denotes the model parameters. An optimization method is one that is used to determine the vector of model parameter values, , for which the chosen fit statistic is minimized.

Optimization is complicated because there is no guarantee that, for a given model and dataset, there will not be multiple local fit-statistic minima. Thus Sherpa provides a number of optimization methods, each of which has different advantages and disadvantages. The default optimization method is levmar, which is a robust method for finding the nearest local fit-statistic minimum (but not necessarily the global minimum). The user can change the method using the set_method (S-Lang or Python help) command.

The relative merits of each of the different optimization methods, and accompanying advice for use in Sherpa, are forthcoming.

The following optimization methods are available in Sherpa:

• levmar
• moncar
• neldermead | simplex
• USERMETHOD

levmar

The Levenberg-Marquardt optimization method.

The Levenberg-Marquardt method is an interface to the MINPACK subroutine lmdif to find the local minimum of nonlinear least squares functions of several variables by a modification of the Levenberg-Marquardt algorithm (J.J. More, "The Levenberg Marquardt algorithm: implementation and theory," in Lecture Notes in Mathematics 630: Numerical Analysis, G.A. Watson (Ed.), Springer-Verlag: Berlin, 1978, pp.105-116).

See the 'levmar' ahelp file (S-Lang or Python help) for the available method options.

To set the optimization method to 'levmar' and then confirm the new value:

sherpa> set_method("levmar")   ['set_method("levmar");' S-lang]
sherpa> get_method_name()      ['get_method_name();' S-lang]
'levmar'

moncar

A Monte Carlo search of parameter space.

The Monte Carlo optimization method is an implementation of the differential evolution algorithm.

Differential Evolution

A population of fixed size which contains n-dimensional vectors of (where n is the number of free parameters) are randomly initialized. At each iteration, a new n-dimensional vector is generated by combining vectors from the pool of population, the resulting trial vector is selected if it lowers the objective function. For more details see:

Storn, R. and Price, K. "Differential Evolution: A Simple and Efficient Adaptive Scheme for Global Optimization over Continuous Spaces." J. Global Optimization 11, 341-359, 1997.

or http://www.icsi.berkeley.edu/~storn/code.html

See the 'montecarlo' ahelp file (S-Lang or Python help) for the available method options.

To set the optimization method to 'moncar' and then confirm the new value:

sherpa> set_method("moncar")   ['set_method("moncar");' S-lang]
sherpa> get_method_name()      ['get_method_name();' S-lang]
'moncar'

Nelder-Mead Simplex

Nelder-Mead simplex optimization method.

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 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.

See the 'neldermead' ahelp file (S-Lang or Python help) for the available method options.

To set the optimization method to Nelder-Mead with 'neldermead' or 'simplex', and then confirm the new value:

sherpa> set_method("neldermead")   ['set_method("neldermead");' S-lang]
sherpa> get_method_name()      ['get_method_name();' S-lang]
'neldermead'

sherpa> set_method("simplex")   ['set_method("simplex");' S-lang]
sherpa> get_method_name()      ['get_method_name();' S-lang]
'neldermead'

USERMETHOD

A user-defined method.

It is possible for the user to create and implement his or her own model, own optimization method, and own statistic function within Sherpa. More information on this topic is forthcoming.