summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichaŽl Baudin <michael.baudin@scilab.org>2009-10-02 11:47:32 +0200
committerMichaŽl Baudin <michael.baudin@scilab.org>2009-10-02 11:47:32 +0200
commitf2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d (patch)
tree5932000f730d00b774a7fd8883f2916ec414c854 /scilab_doc
parentdd87ade6726805c65775028c97b9b45e0e60d80b (diff)
parente9e36c37b07e407827d95ebb62243b2eef696593 (diff)
downloadscilab-f2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d.zip
scilab-f2b0c4b9e01b9d13b0a6218d79ddb6f3e0fa0e5d.tar.gz
Updated Spendley's chapter
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/introduction.tex8
-rw-r--r--scilab_doc/neldermead/method-spendley.tex110
-rw-r--r--scilab_doc/neldermead/neldermead-introduction-so.pdfbin286702 -> 286698 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-spendley-so.pdfbin323141 -> 322977 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.bib2
5 files changed, 62 insertions, 58 deletions
diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.tex
index 11b20ef..cc4b0a3 100644
--- a/scilab_doc/neldermead/introduction.tex
+++ b/scilab_doc/neldermead/introduction.tex
@@ -32,9 +32,9 @@ vertices.
32The goal of this toolbox is to provide a Nelder-Mead (1965) direct search optimization method to solve the 32The goal of this toolbox is to provide a Nelder-Mead (1965) direct search optimization method to solve the
33following unconstrained optimization problem 33following unconstrained optimization problem
34\begin{eqnarray} 34\begin{eqnarray}
35\min f(x) 35\min f(\bx)
36\end{eqnarray} 36\end{eqnarray}
37where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 37where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective
38function $f:\RR^n\rightarrow \RR$. 38function $f:\RR^n\rightarrow \RR$.
39In order to solve the unconstrained optimization problem, the Nelder-Mead 39In order to solve the unconstrained optimization problem, the Nelder-Mead
40algorithm uses a variable shape simplex. The toolbox also provide Spendley's et al. 40algorithm uses a variable shape simplex. The toolbox also provide Spendley's et al.
@@ -43,9 +43,9 @@ by Nelder and Mead was designed as an improvement on Spendley's et al. algorithm
43The Box complex algorithm \cite{Box1965} (1965), which is an extension of Spendley's et al. algorithm, solves the 43The Box complex algorithm \cite{Box1965} (1965), which is an extension of Spendley's et al. algorithm, solves the
44following constrained problem 44following constrained problem
45\begin{eqnarray} 45\begin{eqnarray}
46&&\min f(x)\\ 46&&\min f(\bx)\\
47&&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\ 47&&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\
48&&g_j(x)\geq 0, \qquad j = 1, m\\ 48&&g_j(\bx)\geq 0, \qquad j = 1, m\\
49\end{eqnarray} 49\end{eqnarray}
50where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower 50where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower
51and upper bounds of the variables. 51and upper bounds of the variables.
diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex
index c8d58a0..b099261 100644
--- a/scilab_doc/neldermead/method-spendley.tex
+++ b/scilab_doc/neldermead/method-spendley.tex
@@ -1,12 +1,12 @@
1\chapter{Spendley's et al. method} 1\chapter{Spendley's et al. method}
2 2
3In this section, we present Spendley's et al. algorithm \cite{Spendley1962} for 3In this chapter, we present Spendley's et al. algorithm \cite{Spendley1962} for
4unconstrained optimization. 4unconstrained optimization.
5 5
6We begin by presenting a global overview of the algorithm. 6We begin by presenting a global overview of the algorithm.
7Then we present various geometric situations which might occur 7Then we present various geometric situations which might occur
8during the algorithm. In the second section, we present several 8during the algorithm. In the second section, we present several
9numerical experiments which allow to get some insight of the behaviour 9numerical experiments which allow to get some insight in the behaviour
10of the algorithm on some simple situations. The two first cases 10of the algorithm on some simple situations. The two first cases
11are involving only 2 variables and are based on a quadratic function. 11are involving only 2 variables and are based on a quadratic function.
12The last numerical experiment explores the behaviour of the algorith 12The last numerical experiment explores the behaviour of the algorith
@@ -22,93 +22,88 @@ Then we present various geometric situations which might occur
22during the algorithm. This allows to understand when exactly a reflection 22during the algorithm. This allows to understand when exactly a reflection
23or a shrink is performed in practice. 23or a shrink is performed in practice.
24 24
25\subsection{Algorithm} 25\subsection{Overview}
26 26
27The goal of Spendley's et al. algorithm is to solve the 27The goal of Spendley's et al. algorithm is to solve the
28following unconstrained optimization problem 28following unconstrained optimization problem
29\begin{eqnarray} 29\begin{eqnarray}
30\min f(x) 30\min f(\bx)
31\end{eqnarray} 31\end{eqnarray}
32where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 32where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective
33function $f:\RR^n\rightarrow \RR$. 33function $f:\RR^n\rightarrow \RR$.
34 34
35The simplex algorithms are based on the iterative update of 35The simplex algorithms are based on the iterative update of
36a \emph{simplex} made of $n+1$ points $S=\{x_i\}_{i=1,n+1}$. Each point 36a \emph{simplex} made of $n+1$ points $S=\{\bx_i\}_{i=1,n+1}$. Each point
37in the simplex is called a \emph{vertex} and is associated with 37in the simplex is called a \emph{vertex} and is associated with
38a function value $f_i=f(x_i), i=1,n+1$. 38a function value $f_i=f(x_i)$ for $i=1,n+1$.
39 39
40The vertices are sorted by increasing function values so that the 40The vertices are sorted by increasing function values so that the
41\emph{best} vertex has index 1 and the \emph{worst} vertex 41\emph{best} vertex has index 1 and the \emph{worst} vertex
42has index $n+1$ 42has index $n+1$
43
44\begin{eqnarray} 43\begin{eqnarray}
45\label{sorted-vertices-fv} 44\label{sorted-vertices-fv}
46f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 45f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
47\end{eqnarray} 46\end{eqnarray}
48 47
49The \emph{next-to-worst} vertex with index $n$ has a 48The $\bx_1$ vertex (resp. the $\bx_{n+1}$ vertex) is called the \emph{best}
50special role in simplex algorithms. 49vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest)
51 50function value. As we are going to see, the \emph{next-to-worst} vertex $\bx_n$ has a
52The centroid of the simplex is the center of the vertices 51special role in this algorithm.
53where the vertex with index $j=1,n+1$ has been
54excluded
55 52
53The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices
54where the vertex $\bx_j$ has been
55excluded. This centroid is
56\begin{eqnarray} 56\begin{eqnarray}
57\label{centroid-generalized} 57\label{centroid-generalized}
58\overline{x} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j}x_i 58\overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bx_i.
59\end{eqnarray}
60
61The first move of the algorithm is based on the centroid
62where the worst vertex with index $j=n+1$ has been excluded
63
64\begin{eqnarray}
65\label{centroid-worst}
66\overline{x} (n+1) = \frac{1}{n} \sum_{i=1,n}x_i
67\end{eqnarray} 59\end{eqnarray}
68 60The algorithm makes use
69The algorithm attemps to replace one vertex 61of one coefficient $\rho>0$, called the reflection factor. The standard
70$x_j$ by a new point $x(\mu,j)$ between the centroid 62value of this coefficient is $\rho=1$.
71$\overline{x}$ and the vertex $x_j$ and defined by 63The algorithm attemps to replace some vertex
64$\bx_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bx_j$
65to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by
72\begin{eqnarray} 66\begin{eqnarray}
73\label{interpolate-generalized} 67\label{interpolate-generalized}
74x(\mu,j) = (1+\mu)\overline{x}(j) - \mu x_j 68\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bx_j.
75\end{eqnarray} 69\end{eqnarray}
76 70
77The Spendley et al. \cite{Spendley1962} algorithm makes use 71\subsection{Algorithm}
78of one coefficient, the reflection $\rho>0$. The standard
79value of this coefficient is $\rho=1$.
80
81The first move of the algorithm is based on the reflection
82with respect to the worst point $x_{n+1}$ so that the reflection point is
83computed by
84 72
73The first step of the algorithm is based on the centroid
74where the worst vertex $\bx_{n+1}$ has been excluded. This centroid
75$\overline{\bx} (n+1)$ is
76\begin{eqnarray}
77\label{centroid-worst}
78\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bx_i.
79\end{eqnarray}
80This step is a reflection with respect to the worst vertex $\bx_{n+1}$ so that the
81reflected point $\bx_r$ is defined by
85\begin{eqnarray} 82\begin{eqnarray}
86\label{interpolate-worst} 83\label{interpolate-worst}
87x(\rho,n+1) = (1+\rho)\overline{x}(n+1) - \rho x_{n+1} 84\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bx_{n+1}
88\end{eqnarray} 85\end{eqnarray}
89 86
90The algorithm first computes the reflection point 87We then compute the function value of the reflected
91with respect to the worst point excluded with $x_r=x(\rho,n+1)$ 88point $f_r=f(\bx_r)$. If the function value $f_r$ is better than the worst function
92and evaluates the function value of the reflection 89value $f_{n+1}$, i.e. if $f_r < f_{n+1}$, then the worst point $\bx_{n+1}$ is rejected from the
93point $f_r=f(x_r)$. If that value $f_r$ is better than the worst function 90simplex and the reflected point $\bx_r$ is accepted. If the reflection point
94value $f_{n+1}$, the worst point $x_{n+1}$ is rejected from the 91does not improve the function value $f_{n+1}$, we consider the centroid
95simplex and the reflection point $x_r$ is accepted. If the reflection point 92$\overline{\bx} (n)$, i.e. the centroid where the vertex $\bx_n$ has been excluded.
96does not improves, the next-to-worst point $x_n$ is reflected and the 93We then consider the reflected vertex $\bx_r^\prime$, computed from the
97function is evaluated at the new reflected point. If the function 94next-to-worst vertex $\bx_n$ and the centroid $\overline{\bx} (n)$.
98value improves over the worst function value $f_{n+1}$, the new reflection point is 95We compute the function value $f_r^\prime = f(\bx_r^\prime)$. If the function
99accepted. 96value $f_r^\prime$ improves over the worst function value $f_{n+1}$, the new reflection vertex
97$\bx_r^\prime$ is accepted.
100 98
101At that point of the algorithm, neither the reflection with respect to 99At that point of the algorithm, neither the reflection with respect to
102$x_{n+1}$ nor the reflection with respect to $x_n$ has improved. 100$\bx_{n+1}$ nor the reflection with respect to $\bx_n$ were able to improve over
103The algorithm therefore shrinks the simplex toward the best point. 101the worst function value $f_{n+1}$.
102Therefore, the algorithm shrinks the simplex toward the best vertex $\bx_1$.
104That last step uses the shrink coefficient $0<\sigma<1$. The standard 103That last step uses the shrink coefficient $0<\sigma<1$. The standard
105value for this coefficient is $\sigma=\frac{1}{2}$. 104value for this coefficient is $\sigma=\frac{1}{2}$.
106 105
107Spendley's et al. algorithm is presented in figure \ref{algo-spendley}. 106Spendley's et al. algorithm is presented in figure \ref{algo-spendley}.
108The figure \ref{fig-spendley-moves} presents the various
109moves of the Spendley et al. algorithm. It is obvious from the
110picture that the algorithm explores a pattern which is
111entirely determined from the initial simplex.
112 107
113\begin{figure}[htbp] 108\begin{figure}[htbp]
114\begin{algorithmic} 109\begin{algorithmic}
@@ -139,8 +134,10 @@ entirely determined from the initial simplex.
139 134
140\subsection{Geometric analysis} 135\subsection{Geometric analysis}
141 136
142The figure \ref{fig-spendley-moves} presents the various moves of the 137The figure \ref{fig-spendley-moves} presents the various
143simplex in the Spendley et al. algorithm. 138moves of the Spendley et al. algorithm. It is obvious from the
139picture that the algorithm explores a pattern which is
140entirely determined from the initial simplex.
144 141
145\begin{figure} 142\begin{figure}
146\begin{center} 143\begin{center}
@@ -199,6 +196,11 @@ optimum is searched.
199 196
200%% TODO... 197%% TODO...
201 198
199%% \subsection{General features of the algorithm}
200
201%% TODO...
202
203
202\section{Numerical experiments} 204\section{Numerical experiments}
203 205
204In this section, we present some numerical experiments 206In this section, we present some numerical experiments
diff --git a/scilab_doc/neldermead/neldermead-introduction-so.pdf b/scilab_doc/neldermead/neldermead-introduction-so.pdf
index c2bf429..16beed5 100644
--- a/scilab_doc/neldermead/neldermead-introduction-so.pdf
+++ b/scilab_doc/neldermead/neldermead-introduction-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead-spendley-so.pdf b/scilab_doc/neldermead/neldermead-spendley-so.pdf
index ecb3671..70b6ca5 100644
--- a/scilab_doc/neldermead/neldermead-spendley-so.pdf
+++ b/scilab_doc/neldermead/neldermead-spendley-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead.bib b/scilab_doc/neldermead/neldermead.bib
index a92538f..384ad54 100644
--- a/scilab_doc/neldermead/neldermead.bib
+++ b/scilab_doc/neldermead/neldermead.bib
@@ -261,6 +261,8 @@ publisher= {}}
261 author = {Box, M. J.}, 261 author = {Box, M. J.},
262 journal = {The Computer Journal}, 262 journal = {The Computer Journal},
263 pages = {42--52}, 263 pages = {42--52},
264 volume = {8},
265 number = {1},
264 title = {A New Method of Constrained Optimization and a Comparison With Other Methods}, 266 title = {A New Method of Constrained Optimization and a Comparison With Other Methods},
265 year = {1965 } 267 year = {1965 }
266} 268}