overview — An overview of the Nelder-Mead toolbox.
The goal of this toolbox is to provide a Nelder-Mead direct search optimization method. That Nelder-Mead algorithm may be used in the following optimization context :
there is no need to provide the derivatives of the objective function,
the number of parameters is small (up to 10-20),
there are bounds and/or non linear constraints.
This package provides the following components :
neldermead provides various Nelder-Mead variants
and manages for Nelder-Mead specific settings, such as the method to
compute the initial simplex, the specific termination criteria,
fminsearch provides a simplified Nelder-Mead algorithm.
Specific terminations criteria, initial simplex and auxiliary settings are automatically configured.
optimset, optimget provide Scilab
commands to emulate their Matlab counterparts.
optimplotfunccount, optimplotx
and optimplotfval provide plotting features for the
fminsearch function.
nmplot provides a high-level component which
provides directly output pictures for Nelder-Mead algorithm.
The current component is based on the following components
optimbase provides an abstract class for a general
optimization component, including the number of variables, the minimum
and maximum bounds, the number of non linear inequality constraints,
the loggin system, various termination criteria, the cost function,
etc...
optimsimplex provides a class to manage a simplex
made of an arbitrary number of vertices, including the computation of
a simplex by various methods (axes, regular, Pfeffer's, randomized
bounds), the computation of the size by various methods (diameter,
sigma +, sigma-, etc...),
The following is a list of features the Nelder-Mead prototype algorithm currently provides :
Provides 3 algorithms, including
Spendley et al. fixed shaped algorithm,
Nelder-Mead variable shape algorithm,
Box "complex" algorithm managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.
Manage various simplex initializations
initial simplex given by user,
initial simplex computed with a length and along the coordinate axes,
initial regular simplex computed with Spendley et al. formula
initial simplex computed by a small perturbation around the initial guess point
Manage cost function
optionnal additionnal argument
direct communication of the task to perform : cost function or inequality constraints
Manage various termination criteria, including maximum number of iterations, tolerance on function value (relative or absolute),
tolerance on x (relative or absolute),
tolerance on standard deviation of function value (original termination criteria in [3]),
maximum number of evaluations of cost function,
absolute or relative simplex size,
Manage the history of the convergence, including
history of function values,
history of optimum point,
history of simplices,
history of termination criterias,
Provide a plot command which allows to graphically see the history of the simplices toward the optimum,
Provide query features for the status of the optimization process number of iterations, number of function evaluations, status of execution, function value at initial point, function value at optimal point, etc...
Kelley restart based on simplex gradient,
O'Neill restart based on factorial search around optimum,
In the following example, one searches the minimum of the 2D Rosenbrock function. One begins by defining the function "rosenbrock" which computes the Rosenbrock function. The traditionnal initial guess [-1.2 1.0] is used. The initial simplex is computed along the axes with a length equal to 0.1. The Nelder-Mead algorithm with variable simplex size is used. The verbose mode is enabled so that messages are generated during the algorithm. After the optimization is performed, the optimum is retrieved with quiery features.
function y = rosenbrock (x) y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; endfunction nm = neldermead_new (); nm = neldermead_configure(nm,"-x0",[-1.2 1.0]'); nm = neldermead_configure(nm,"-simplex0method","axes"); nm = neldermead_configure(nm,"-simplex0length",0.1); nm = neldermead_configure(nm,"-method","variable"); nm = neldermead_configure(nm,"-verbose",1); nm = neldermead_configure(nm,"-function",rosenbrock); nm = neldermead_search(nm); xopt = neldermead_get(nm,"-xopt"); fopt = neldermead_get(nm,"-fopt"); historyfopt = neldermead_get(nm,"-historyfopt"); iterations = neldermead_get(nm,"-iterations"); historyxopt = neldermead_get(nm,"-historyxopt"); historysimplex = neldermead_get(nm,"-historysimplex"); fx0 = neldermead_get(nm,"-fx0"); status = neldermead_get(nm,"-status"); nm = neldermead_destroy(nm);
“Sequential Application of Simplex Designs in Optimisation and Evolutionary Operation”, Spendley, W. and Hext, G. R. and Himsworth, F. R., American Statistical Association and American Society for Quality, 1962
“A Simplex Method for Function Minimization”, Nelder, J. A. and Mead, R., The Computer Journal, 1965
"A New Method of Constrained Optimization and a Comparison With Other Methods", M. J. Box, The Computer Journal 1965 8(1):42-52, 1965 by British Computer Society
“Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions”, Jeffrey C. Lagarias and James A. Reeds and Margaret H. Wright and Paul E. Wright, SIAM Journal on Optimization, 1998
“Compact numerical methods for computers : linear algebra and function minimisation”, Nash, J. C., Hilger, Bristol, 1979
“Iterative Methods for Optimization”, C. T. Kelley, 1999
“Iterative Methods for Optimization: Matlab Codes”, http://www4.ncsu.edu/~ctk/matlab_darts.html
“Sequential Simplex Optimization: A Technique for Improving Quality and Productivity in Research, Development, and Manufacturing”, Walters, Fred H. and Jr, Lloyd R. and Morgan, Stephen L. and Deming, Stanley N., 1991
“Numerical Recipes in C, Second Edition”, W. H. Press and Saul A. Teukolsky and William T. Vetterling and Brian P. Flannery, 1992
“Detection and Remediation of Stagnation in the Nelder--Mead Algorithm Using a Sufficient Decrease Condition”, SIAM J. on Optimization, Kelley,, C. T., 1999
Matlab – fminsearch , http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/fminsearch.html
GAMS, A19A20 - description, http://gams.nist.gov/serve.cgi/Module/NASHLIB/A19A20/11238/
asa047.f, http://people.sc.fsu.edu/~burkardt/f77_src/asa047/asa047.f
optim1.f, http://www.stat.uconn.edu/~mhchen/survbook/example51/optim1.f
as47,f, http://lib.stat.cmu.edu/apstat/47
“Algorithm AS47 - Function minimization using a simplex procedure, O'Neill, R., 1971, Applied Statistics
include Multi-Directionnal Search algorithm in the release
include parabolic interpolation in the release
provide a neldermead_outputfunction to make nice and easy outputs
provide a stopping feature to the cost function and manage the stop
output argument to the output functions of fminsearch
provide a (quadratic) penalized version of neldermead for
bound constrained problems