1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

\chapter{Introduction}
The NelderMead simplex algorithm, published in 1965, is an enormously
popular search method for multidimensional unconstrained optimization.
The NelderMead algorithm should not be confused with the (probably)
more famous simplex algorithm of Dantzig for linear programming. The
NelderMead algorithm is especially popular in the fields of chemistry,
chemical engineering, and medicine. Two measures of the ubiquity of the
NelderMead algorithm are that it appears in the bestselling handbook
Numerical Recipes and in Matlab. In \cite{Torczon89multidirectionalsearch},
Virginia Torczon writes : "Margaret Wright has stated that over
fifty percent of the calls received by the support group for the NAG
software library concerned the version of the NelderMead
simplex algorithm to be found in that library". No derivative of the cost function is
required, which makes the algorithm interesting for noisy problems.
The NelderMead algorithm falls in the more general class of direct
search algorithms. These methods use values of $f$ taken from a set of
sample points and use that information to continue the sampling. The
NelderMead algorithm maintains a simplex which are approximations of an
optimal point. The vertices are sorted according to the objective
function values. The algorithm attemps to replace the worst vertex with
a new point, which depends on the worst point and the centre of the best
vertices.
The goal of this toolbox is to provide a NelderMead direct search optimization method to solve the
following unconstrained optimization problem
\begin{eqnarray}
\min f(x)
\end{eqnarray}
where $x\in \RR^n$ where $n$ is the number of optimization parameters.
The Box complex algorithm, which is an extension of NelderMead's algorithm, solves the
following constrained problem
\begin{eqnarray}
&&\min f(x)\\
&&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\
&&g_j(x)\geq 0, \qquad j = 1, m\\
\end{eqnarray}
where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower
and upper bounds of the variables.
The NelderMead algorithm may be used in the following optimization context :
\begin{itemize}
\item there is no need to provide the derivatives of the objective function,
\item the number of parameters is small (up to 1020),
\item there are bounds and/or non linear constraints.
\end{itemize}
The internal design of the system is based on the following components :
\begin{itemize}
\item "neldermead" provides various NelderMead variants and manages for NelderMead specific settings, such as the method to compute the initial simplex, the specific termination criteria,
\item "fminsearch" provides a Scilab commands which aims at behaving as Matlab's fminsearch. Specific terminations criteria, initial simplex and auxiliary settings are automatically configured so that the behaviour of Matlab's fminsearch is exactly reproduced.
\item "optimset", "optimget" provides Scilab commands to emulate their Matlab counterparts.
\item "nmplot" provides a highlevel component which provides directly output pictures for NelderMead algorithm.
\end{itemize}
The current toolbox is based on (and therefore requires) the following toolboxes
\begin{itemize}
\item "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...
\item "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...),
\end{itemize}
The following is a list of features the NelderMead prototype algorithm currently provides :
\begin{itemize}
\item Manage various simplex initializations
\begin{itemize}
\item initial simplex given by user,
\item initial simplex computed with a length and along the coordinate axes,
\item initial regular simplex computed with Spendley et al. formula
\item initial simplex computed by a small perturbation around the initial guess point
\end{itemize}
\item Manage cost function
\begin{itemize}
\item optionnal additionnal argument
\item direct communication of the task to perform : cost function or inequality constraints
\end{itemize}
\item Manage various termination criteria, including maximum number of iterations, tolerance on function value (relative or absolute),
\begin{itemize}
\item tolerance on x (relative or absolute),
\item tolerance on standard deviation of function value (original termination criteria in [3]),
\item maximum number of evaluations of cost function,
\item absolute or relative simplex size,
\end{itemize}
\item Manage the history of the convergence, including
\begin{itemize}
\item history of function values,
\item history of optimum point,
\item history of simplices,
\item history of termination criterias,
\end{itemize}
\item Provide a plot command which allows to graphically see the history of the simplices toward the optimum,
\item 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...
\item Spendley et al. fixed shaped algorithm,
\item Kelley restart based on simplex gradient,
\item O'Neill restart based on factorial search around optimum,
\item Boxlike method managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.
\end{itemize}
