The Nelder-Mead Component
6/11/2009
Updated 27/04/2010
In this page, we present the main features of the Nelder-Mead component in Scilab, starting from v5.2. The goal of this page is to be an introduction to Scilab's Nelder-Mead User Manual, which is provided at the end of this document.
The goal of this component 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 component has been proposed in SEP #21: SEP_21_neldermead.odt.
On this base, Scilab now provides the function "fminsearch", which is able to reproduce Matlab's fminsearch.
Overview
The following is a list of features the Nelder-Mead prototype algorithm currently provides :
- 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...
- Spendley et al. fixed shaped algorithm,
- Kelley restart based on simplex gradient,
- O'Neill restart based on factorial search around optimum,
- Box method managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.
Nelder-Mead User's Manual
In this section, we present the Nelder-Mead User's Manual.
Abstract
In this document, we present the Nelder-Mead component provided in Scilab. The introduction gives a brief overview of the optimization features of the component and present an introductory example. Then we present some theory associated with the simplex, a geometric concept which is central in the Nelder-Mead algorithm. We present several method to compute an initial simplex. Then we present Spendley's et al. fixed shape unconstrained optimization algorithm. Several numerical experiments are provided, which shows how this algorithm performs on well-scaled and badly scaled quadratics. In the final section, we present the Nelder-Mead variable shape unconstrained optimization algorithm. Several numerical experiments are presented, where some of these are counter examples, that is cases where the algorithms fails to converge on a stationnary point. In the appendix of this document, the interested reader will find a bibliography of simplex-based algorithms, along with an analysis of the various implementations which are available in several programming languages.
The User's Manual is a 130 pages document provided in pdf format.
v0.5, updated 27/04/2010 : neldermead.pdf
This document is maintained in the Scilab forge at :
http://forge.scilab.org/index.php/p/docneldermead/
The latest pdf version is available at :
http://forge.scilab.org/index.php/p/docneldermead/downloads/
The LaTeX source is provided under the terms of the Creative Commons Attribution-ShareAlike 3.0 Unported License :