summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichael Baudin <michael.baudin@scilab.org>2009-10-05 21:57:48 +0200
committerMichael Baudin <michael.baudin@scilab.org>2009-10-05 21:57:48 +0200
commit5e2e6729fab0b8e212b26daa2ab8252869add7c8 (patch)
treebfbb53e075544525a8d67bcd0a8c79302bbce1a7 /scilab_doc
parentdc8c3a2df5cd66c22ed76ab0f3c348d6a825a164 (diff)
downloadscilab-5e2e6729fab0b8e212b26daa2ab8252869add7c8.zip
scilab-5e2e6729fab0b8e212b26daa2ab8252869add7c8.tar.gz
Transformed figures into pdf. Fixed inconsistency in the notations.
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/chapter-notations.tex23
-rw-r--r--scilab_doc/neldermead/fminsearch-so.idx0
-rw-r--r--scilab_doc/neldermead/fminsearch-so.ilg4
-rw-r--r--scilab_doc/neldermead/fminsearch-so.ind0
-rw-r--r--scilab_doc/neldermead/fminsearch-so.pdfbin0 -> 108029 bytes
-rw-r--r--scilab_doc/neldermead/fminsearch-so.tex86
-rw-r--r--scilab_doc/neldermead/fminsearch.tex180
-rw-r--r--scilab_doc/neldermead/implementations.tex10
-rw-r--r--scilab_doc/neldermead/introduction.tex18
-rw-r--r--scilab_doc/neldermead/macros.tex10
-rw-r--r--scilab_doc/neldermead/mcKinnon-insidecontraction.pdfbin0 -> 17159 bytes
-rw-r--r--scilab_doc/neldermead/mcKinnon-insidecontraction.svg363
-rw-r--r--scilab_doc/neldermead/method-neldermead.tex738
-rw-r--r--scilab_doc/neldermead/method-spendley.tex76
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-inside.pdfbin0 -> 16398 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-inside.pngbin36440 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-inside.svg164
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-outside.pdfbin0 -> 16823 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-outside.pngbin40448 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-outside.svg164
-rw-r--r--scilab_doc/neldermead/nelder-mead-extension.pdfbin0 -> 15560 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-extension.svg148
-rw-r--r--scilab_doc/neldermead/nelder-mead-reflection.pdfbin0 -> 15565 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-reflection.pngbin33907 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-reflection.svg128
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterci.pdfbin0 -> 17146 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterci.pngbin42344 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterci.svg36
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterco.pdfbin0 -> 18075 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterco.pngbin35143 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterco.svg198
-rw-r--r--scilab_doc/neldermead/nelder-mead-steps.pdfbin0 -> 17343 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-steps.pngbin31536 -> 0 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-steps.svg62
-rw-r--r--scilab_doc/neldermead/neldermead-neldermead-so.pdfbin0 -> 558881 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-neldermead-so.tex97
-rw-r--r--scilab_doc/neldermead/neldermead-simplex-so.tex5
-rw-r--r--scilab_doc/neldermead/neldermead-spendley-so.pdfbin308835 -> 301166 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-spendley-so.tex5
-rw-r--r--scilab_doc/neldermead/neldermead.tex6
-rw-r--r--scilab_doc/neldermead/nmbibliography.tex12
-rw-r--r--scilab_doc/neldermead/references.tex53
-rw-r--r--scilab_doc/neldermead/scripts/HanNeumann_roots.sce117
-rw-r--r--scilab_doc/neldermead/scripts/fminsearch_banana.m14
-rw-r--r--scilab_doc/neldermead/scripts/fminsearch_rosenbrock.sce10
-rw-r--r--scilab_doc/neldermead/section-simplex.tex201
46 files changed, 2019 insertions, 909 deletions
diff --git a/scilab_doc/neldermead/chapter-notations.tex b/scilab_doc/neldermead/chapter-notations.tex
new file mode 100644
index 0000000..226bcfe
--- /dev/null
+++ b/scilab_doc/neldermead/chapter-notations.tex
@@ -0,0 +1,23 @@
1\chapter*{Notations}
2
3
4\begin{figure}[h]
5\begin{center}
6\begin{tabular}{|l|l|}
7\hline
8$n$ & number of variables\\
9$\bx=(x_1,x_2,\ldots,x_n)^T \in\RR^n$ & the unknown\\
10$\bx_0\in\RR^n$ & the initial guess\\
11$\bv\in\RR^n$ & a vertex\\
12$S=\{\bv_i\}_{i=1,m}$ & a complex, where $m\geq n+1$ is the number of vertices\\
13$S=\{\bv_i\}_{i=1,n+1}$ & a simplex (with $n+1$ vertices)\\
14$(\bv_i)_j$ & the $j$-th component of the $i$-th vertex\\
15$S_0$& the initial simplex\\
16$S_k$& the simplex at iteration $k$\\
17$f:\RR^n\rightarrow\RR$& the cost function\\
18\hline
19\end{tabular}
20\end{center}
21\caption{Notations used in this document}
22\label{fig-notations}
23\end{figure}
diff --git a/scilab_doc/neldermead/fminsearch-so.idx b/scilab_doc/neldermead/fminsearch-so.idx
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch-so.idx
diff --git a/scilab_doc/neldermead/fminsearch-so.ilg b/scilab_doc/neldermead/fminsearch-so.ilg
new file mode 100644
index 0000000..cea57f1
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch-so.ilg
@@ -0,0 +1,4 @@
1This is makeindex, version 2.14 [02-Oct-2002] (kpathsea + Thai support).
2Scanning input file fminsearch-so.idx...done (0 entries accepted, 0 rejected).
3Nothing written in fminsearch-so.ind.
4Transcript written in fminsearch-so.ilg.
diff --git a/scilab_doc/neldermead/fminsearch-so.ind b/scilab_doc/neldermead/fminsearch-so.ind
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch-so.ind
diff --git a/scilab_doc/neldermead/fminsearch-so.pdf b/scilab_doc/neldermead/fminsearch-so.pdf
new file mode 100644
index 0000000..6604bc16
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/fminsearch-so.tex b/scilab_doc/neldermead/fminsearch-so.tex
new file mode 100644
index 0000000..e364aa9
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch-so.tex
@@ -0,0 +1,86 @@
1\documentclass[12pt]{report}
2
3\include{macros}
4
5\begin{document}
6%% User defined page headers
7\pagestyle{fancyplain}
8\renewcommand{\chaptermark}[1]{\markboth{\chaptername\ \thechapter. #1}{}}
9\renewcommand{\sectionmark}[1]{\markright{\thesection. #1}}
10\lhead[]{\fancyplain{}{\bfseries\leftmark}}
11\rhead[]{\fancyplain{}{\bfseries\thepage}}
12\cfoot{}
13
14%% User defined figure legends
15\makeatletter
16\def\figurename{{\protect\sc \protect\small\bfseries Fig.}}
17\def\f@ffrench{\protect\figurename\space{\protect\small\bf \thefigure}\space}
18\let\fnum@figure\f@ffrench%
19\let\captionORI\caption
20\def\caption#1{\captionORI{\rm\small #1}}
21\makeatother
22
23%% First page
24\thispagestyle{empty}
25{
26\begin{center}
27%% Comment for DVI
28\includegraphics[height=40mm]{scilab_logo}
29\vskip2cm
30
31%% Empty space between the box and the text
32\fboxsep6mm
33%% Box thickness
34\fboxrule1.3pt
35\Huge
36$$\fbox{$
37 \begin{array}{c}
38 \textbf{Nelder-Mead}\\
39 \textbf{User's Manual}\\
40 \textbf{-- The Fminsearch Function --}\\
41 \end{array}
42 $}
43$$
44\end{center}
45
46\vskip1cm
47
48\begin{center}
49\begin{large}
50Micha\"el BAUDIN
51\end{large}
52\end{center}
53
54\vskip2cm
55
56
57\vskip1cm
58
59
60\begin{flushright}
61Version 0.3 \\
62September 2009
63\end{flushright}
64
65
66
67\clearpage
68
69
70\tableofcontents
71
72\include{fminsearch}
73
74\clearpage
75
76%% Bibliography
77
78\addcontentsline{toc}{chapter}{Bibliography}
79\bibliographystyle{plain}
80\bibliography{neldermead}
81
82% Index
83\printindex
84
85\end{document}
86
diff --git a/scilab_doc/neldermead/fminsearch.tex b/scilab_doc/neldermead/fminsearch.tex
new file mode 100644
index 0000000..85dac9f
--- /dev/null
+++ b/scilab_doc/neldermead/fminsearch.tex
@@ -0,0 +1,180 @@
1\chapter{The \scifunction{fminsearch} function}
2
3In this chapter, we analyze the implementation of the \scifunction{fminsearch}
4which is provided in Scilab. In the first part, we describe the specific
5choices of this implementation with respect to the Nelder-Mead algorithm.
6In the second part, we present some numerical experiments which
7allows to check that the feature is behaving as expected, by comparison
8to Matlab's \scifunction{fminsearch}.
9
10\section{\scifunction{fminsearch}'s algorithm}
11
12\subsection{The algorithm}
13
14The algorithm used is the Nelder-Mead algorithm. This corresponds to the
15"variable" value of the "-method" option of the \scifunction{neldermead}.
16The "non greedy" version is used, that is, the expansion point is
17accepted only if it improves over the reflection point.
18
19\subsection{The initial simplex}
20
21The fminsearch algorithm uses a special initial simplex, which is an
22heuristic depending on the initial guess. The strategy chosen by
23fminsearch corresponds to the -simplex0method flag of the neldermead
24component, with the "pfeffer" method. It is associated with the -
25simplex0deltausual = 0.05 and -simplex0deltazero = 0.0075 parameters.
26Pfeffer's method is an heuristic which is presented in "Global
27Optimization Of Lennard-Jones Atomic Clusters" by Ellen Fan \cite{Fan2002}.
28It is due to L. Pfeffer at Stanford. See in the help of optimsimplex for more
29details.
30
31\subsection{The number of iterations}
32
33In this section, we present the default values for the number of
34iterations in fminsearch.
35
36The options input argument is an optionnal data structure which can
37contain the options.MaxIter field. It stores the maximum number of
38iterations. The default value is 200n, where n is the number of
39variables. The factor 200 has not been chosen by chance, but is the
40result of experiments performed against quadratic functions with
41increasing space dimension.
42
43This result is presented in "Effect of dimensionality on the nelder-mead
44simplex method" by Lixing Han and Michael Neumann \cite{HanNeumann2006}. This paper is based
45on Lixing Han's PhD, "Algorithms in Unconstrained Optimization" \cite{Han2000}. The
46study is based on numerical experiment with a quadratic function where
47the number of terms depends on the dimension of the space (i.e. the
48number of variables). Their study shows that the number of iterations
49required to reach the tolerance criteria is roughly 100n. Most
50iterations are based on inside contractions. Since each step of the
51Nelder-Mead algorithm only require one or two function evaluations, the
52number of required function evaluations in this experiment is also
53roughly 100n.
54
55\subsection{The termination criteria}
56
57The algorithm used by \scifunction{fminsearch} uses a particular
58termination criteria, based both on the absolute size of the
59simplex and the difference of the function values in the simplex.
60This termination criteria corresponds to the "-tolssizedeltafvmethod"
61termination criteria of the \scifunction{neldermead} component.
62
63The size of the simplex is computed with the $\sigma-+$ method,
64which corresponds to the "sigmaplus" method of the \scifunction{optimsimplex}
65component. The tolerance associated with this criteria is
66given by the "TolX" parameter of the \scifunction{options} data structure.
67Its default value is 1.e-4.
68
69The function value difference is the difference
70between the highest and the lowest function value in the simplex.
71The tolerance associated with this criteria is given by the
72"TolFun" parameter of the \scifunction{options} data structure.
73Its default value is 1.e-4.
74
75\section{Numerical experiments}
76
77In this section, we analyse the behaviour of Scilab's \scifunction{fminsearch}
78function, by comparison of Matlab's \scifunction{fminsearch}. We especially analyse
79the results of the optimization, so that we can check that the algorithm
80is indeed behaving the same way, even if the implementation is completely
81different. Our test case is based on Rosenbrock's function.
82
83The following Matlab script allows to see the behaviour of Matlab's \scifunction{fminsearch}
84function on Rosenbrock's test case.
85
86\lstset{language=scilabscript}
87\begin{lstlisting}
88format long
89banana = @(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2;
90[x,fval,exitflag,output] = fminsearch(banana,[-1.2, 1])
91output.message
92\end{lstlisting}
93
94When this script is launched in Matlab, the following output is
95produced.
96
97\lstset{language=scilabscript}
98\begin{lstlisting}
99>> format long
100>> banana = @(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2;
101>> [x,fval] = fminsearch(banana,[-1.2, 1])
102>> [x,fval,exitflag,output] = fminsearch(banana,[-1.2, 1])
103x =
104 1.000022021783570 1.000042219751772
105fval =
106 8.177661197416674e-10
107exitflag =
108 1
109output =
110 iterations: 85
111 funcCount: 159
112 algorithm: 'Nelder-Mead simplex direct search'
113 message: [1x194 char]
114>> output.message
115ans =
116Optimization terminated:
117the current x satisfies the termination criteria using
118OPTIONS.TolX of 1.000000e-04
119and F(X) satisfies the convergence criteria using
120OPTIONS.TolFun of 1.000000e-04
121\end{lstlisting}
122
123The following Scilab script allows to solve the problem with Scilab's
124\scifunction{fminsearch}.
125
126\lstset{language=scilabscript}
127\begin{lstlisting}
128format(25)
129function y = banana (x)
130 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
131endfunction
132[x , fval , exitflag , output] = fminsearch ( banana , [-1.2 1] )
133output.message
134\end{lstlisting}
135
136The output associated with this Scilab script is the following.
137
138\lstset{language=scilabscript}
139\begin{lstlisting}
140-->format(25)
141-->function y = banana (x)
142--> y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
143-->endfunction
144-->[x , fval , exitflag , output] = fminsearch ( banana , [-1.2 1] )
145 output =
146 algorithm: "Nelder-Mead simplex direct search"
147 funcCount: 159
148 iterations: 85
149 message: [3x1 string]
150 exitflag =
151 1.
152 fval =
153 0.0000000008177661099387
154 x =
155 1.0000220217835567027009 1.0000422197517710998227
156-->output.message
157 ans =
158
159!Optimization terminated: !
160! !
161!the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-004 !
162! !
163!and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-004 !
164\end{lstlisting}
165
166The result is as close as possible to the result produced
167by Matlab. More specifically :
168\begin{itemize}
169\item the optimum $x$ is the same up to 14 significant digits,
170\item the function value at optimum is the same up to 9 significant digits,
171\item the number of iterations is the same,
172\item the number of function evaluations is the same,
173\item the exit flag is the same,
174\item the content of the output is the same (but the string is not
175display the same way).
176\end{itemize}
177
178
179%TODO : check that the iterations are the same
180
diff --git a/scilab_doc/neldermead/implementations.tex b/scilab_doc/neldermead/implementations.tex
index 150f0ef..2c15246 100644
--- a/scilab_doc/neldermead/implementations.tex
+++ b/scilab_doc/neldermead/implementations.tex
@@ -1,13 +1,13 @@
1\chapter{Implementations of the Nelder-Mead algorithm} 1\chapter{Implementations of the Nelder-Mead algorithm}
2 2
3In the following sections, we analyse the various implementations of the 3In the following sections, we analyze the various implementations of the
4Nelder-Mead algorithm. We analyse the Matlab implementation provided 4Nelder-Mead algorithm. We analyze the Matlab implementation provided
5by the \emph{fminsearch} command. We analyse the matlab algorithm provided by 5by the \emph{fminsearch} command. We analyze the matlab algorithm provided by
6C.T. Kelley and the Scilab port by Y. Collette. We 6C.T. Kelley and the Scilab port by Y. Collette. We
7present the Numerical Recipes implementations. We analyse the O'Neill 7present the Numerical Recipes implementations. We analyze the O'Neill
8fortran 77 implementation "AS47". The Burkardt implementation is also covered. 8fortran 77 implementation "AS47". The Burkardt implementation is also covered.
9The implementation provided in the NAG collection is detailed. 9The implementation provided in the NAG collection is detailed.
10The Nelder-Mead algorithm from the Gnu Scientific Library is analysed. 10The Nelder-Mead algorithm from the Gnu Scientific Library is analyzed.
11 11
12\section{Matlab : fminsearch} 12\section{Matlab : fminsearch}
13 13
diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.tex
index cc4b0a3..e041af1 100644
--- a/scilab_doc/neldermead/introduction.tex
+++ b/scilab_doc/neldermead/introduction.tex
@@ -66,7 +66,7 @@ criteria.
66\item The "fminsearch" component provides a Scilab commands which aims 66\item The "fminsearch" component provides a Scilab commands which aims
67at behaving as Matlab's fminsearch. Specific terminations criteria, 67at behaving as Matlab's fminsearch. Specific terminations criteria,
68initial simplex and auxiliary settings are automatically configured so 68initial simplex and auxiliary settings are automatically configured so
69that the behaviour of Matlab's fminsearch is exactly reproduced. 69that the behavior of Matlab's fminsearch is exactly reproduced.
70\item The "optimset" and "optimget" components provide Scilab commands 70\item The "optimset" and "optimget" components provide Scilab commands
71to emulate their Matlab counterparts. 71to emulate their Matlab counterparts.
72\item The "nmplot" component provides features to 72\item The "nmplot" component provides features to
@@ -168,10 +168,7 @@ is used, which corresponds to the "variable" value of the "-method" option.
168The verbose mode is enabled so that messages are generated during the algorithm. 168The verbose mode is enabled so that messages are generated during the algorithm.
169After the optimization is performed, the optimum is retrieved with quiery features. 169After the optimization is performed, the optimum is retrieved with quiery features.
170 170
171\lstset{language=Scilab} 171\lstset{language=scilabscript}
172\lstset{numbers=left}
173\lstset{basicstyle=\footnotesize}
174\lstset{keywordstyle=\bfseries}
175\begin{lstlisting} 172\begin{lstlisting}
176function y = rosenbrock (x) 173function y = rosenbrock (x)
177 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; 174 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
@@ -193,10 +190,7 @@ nm = neldermead_destroy(nm);
193 190
194This produces the following output. 191This produces the following output.
195 192
196\lstset{language=Scilab} 193\lstset{language=scilabscript}
197\lstset{numbers=left}
198\lstset{basicstyle=\footnotesize}
199\lstset{keywordstyle=\bfseries}
200\begin{lstlisting} 194\begin{lstlisting}
201-->nm = neldermead_search(nm); 195-->nm = neldermead_search(nm);
202Function Evaluation #1 is [24.2] at [-1.2 1] 196Function Evaluation #1 is [24.2] at [-1.2 1]
@@ -314,10 +308,7 @@ and are presented in figure \ref{fig-intro-demos}.
314The following script shows where the demonstration scripts are 308The following script shows where the demonstration scripts are
315available from the Scilab installation directory. 309available from the Scilab installation directory.
316 310
317\lstset{language=Scilab} 311\lstset{language=scilabscript}
318\lstset{numbers=left}
319\lstset{basicstyle=\footnotesize}
320\lstset{keywordstyle=\bfseries}
321\begin{lstlisting} 312\begin{lstlisting}
322-->cd SCI/modules/optimization/demos/neldermead 313-->cd SCI/modules/optimization/demos/neldermead
323 ans = 314 ans =
@@ -361,4 +352,3 @@ a good source of information on how to use the functions.
361 352
362 353
363 354
364
diff --git a/scilab_doc/neldermead/macros.tex b/scilab_doc/neldermead/macros.tex
index 8c9af33..9464b36 100644
--- a/scilab_doc/neldermead/macros.tex
+++ b/scilab_doc/neldermead/macros.tex
@@ -8,6 +8,10 @@
8%% Comment for DVI 8%% Comment for DVI
9\usepackage[pdftex]{graphicx} 9\usepackage[pdftex]{graphicx}
10 10
11%% Index
12\usepackage{makeidx}
13\makeindex
14
11%% Figures formats: jpeg or pdf 15%% Figures formats: jpeg or pdf
12%% Comment for DVI 16%% Comment for DVI
13\DeclareGraphicsExtensions{.jpg,.pdf} 17\DeclareGraphicsExtensions{.jpg,.pdf}
@@ -47,6 +51,8 @@
47\newcommand{\bv}{\mathbf{v}} 51\newcommand{\bv}{\mathbf{v}}
48\newcommand{\bx}{\mathbf{x}} 52\newcommand{\bx}{\mathbf{x}}
49\newcommand{\bl}{\mathbf{l}} 53\newcommand{\bl}{\mathbf{l}}
54\newcommand{\br}{\mathbf{r}}
55\newcommand{\bg}{\mathbf{g}}
50 56
51\usepackage{url} 57\usepackage{url}
52 58
@@ -231,4 +237,8 @@
231\newcommand{\RR}{\mathbb{R}} 237\newcommand{\RR}{\mathbb{R}}
232\newcommand{\CC}{\mathbb{C}} 238\newcommand{\CC}{\mathbb{C}}
233 239
240% For symbol degree
241\DeclareTextSymbol{\degre}{T1}{6}
242
243
234 244
diff --git a/scilab_doc/neldermead/mcKinnon-insidecontraction.pdf b/scilab_doc/neldermead/mcKinnon-insidecontraction.pdf
new file mode 100644
index 0000000..883176b
--- /dev/null
+++ b/scilab_doc/neldermead/mcKinnon-insidecontraction.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/mcKinnon-insidecontraction.svg b/scilab_doc/neldermead/mcKinnon-insidecontraction.svg
new file mode 100644
index 0000000..6ee8589
--- /dev/null
+++ b/scilab_doc/neldermead/mcKinnon-insidecontraction.svg
@@ -0,0 +1,363 @@
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!-- Created with Inkscape (http://www.inkscape.org/) -->
3<svg
4 xmlns:dc="http://purl.org/dc/elements/1.1/"
5 xmlns:cc="http://creativecommons.org/ns#"
6 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
7 xmlns:svg="http://www.w3.org/2000/svg"
8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:xlink="http://www.w3.org/1999/xlink"
10 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
11 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
12 width="690.33319"
13 height="474.34412"
14 id="svg2"
15 sodipodi:version="0.32"
16 inkscape:version="0.46"
17 sodipodi:docname="mcKinnon-insidecontraction.svg"
18 inkscape:output_extension="org.inkscape.output.svg.inkscape"
19 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.shrink.afterci.png"
20 inkscape:export-xdpi="90"
21 inkscape:export-ydpi="90"
22 version="1.0"
23 style="display:inline">
24 <defs
25 id="defs4">
26 <marker
27 inkscape:stockid="Arrow1Lend"
28 orient="auto"
29 refY="0"
30 refX="0"
31 id="Arrow1Lend"
32 style="overflow:visible">
33 <path
34 id="path3318"
35 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
36 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
37 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
38 </marker>
39 <inkscape:perspective
40 sodipodi:type="inkscape:persp3d"
41 inkscape:vp_x="0 : 526.18109 : 1"
42 inkscape:vp_y="0 : 1000 : 0"
43 inkscape:vp_z="744.09448 : 526.18109 : 1"
44 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
45 id="perspective10" />
46 <inkscape:perspective
47 id="perspective3370"
48 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
49 inkscape:vp_z="744.09448 : 526.18109 : 1"
50 inkscape:vp_y="0 : 1000 : 0"
51 inkscape:vp_x="0 : 526.18109 : 1"
52 sodipodi:type="inkscape:persp3d" />
53 </defs>
54 <sodipodi:namedview
55 id="base"
56 pagecolor="#ffffff"
57 bordercolor="#666666"
58 borderopacity="1.0"
59 inkscape:pageopacity="0.0"
60 inkscape:pageshadow="2"
61 inkscape:zoom="0.98994949"
62 inkscape:cx="309.39226"
63 inkscape:cy="206.84932"
64 inkscape:document-units="px"
65 inkscape:current-layer="layer1"
66 showgrid="false"
67 inkscape:window-width="1410"
68 inkscape:window-height="975"
69 inkscape:window-x="1710"
70 inkscape:window-y="14">
71 <inkscape:grid
72 type="xygrid"
73 id="grid3279"
74 visible="true"
75 enabled="true" />
76 </sodipodi:namedview>
77 <metadata
78 id="metadata7">
79 <rdf:RDF>
80 <cc:Work
81 rdf:about="">
82 <dc:format>image/svg+xml</dc:format>
83 <dc:type
84 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
85 </cc:Work>
86 </rdf:RDF>
87 </metadata>
88 <g
89 inkscape:groupmode="layer"
90 id="layer2"
91 inkscape:label="Fond"
92 style="opacity:0.45077718;display:none"
93 transform="translate(48.615517,-37.967144)">
94 <image
95 y="37.967144"
96 x="-48.615517"
97 id="image3372"
98 height="460"
99 width="610"
100 sodipodi:absref="I:\Git-Scilab-Optimization\scilab\scilab_doc\neldermead\mckinnon-history-simplex.png"
101 xlink:href="mckinnon-history-simplex.png" />
102 </g>
103 <g
104 inkscape:groupmode="layer"
105 id="layer3"
106 inkscape:label="IsoValeurs"
107 transform="translate(48.615517,-37.967144)">
108 <path
109 transform="translate(-133.77922,-205.78699)"
110 sodipodi:nodetypes="czzss"
111 id="path3382"
112 d="M 215.34475,710.85644 C 309.91601,732.45675 430.78995,699.50835 491.37545,649.63706 C 550.969,600.58229 565.46584,443.58807 489.88488,381.08838 C 413.80547,318.17651 326.86151,303.01166 222.6887,314.5148 C 157.11139,321.75609 171.24819,700.78468 215.34475,710.85644 z"
113 style="opacity:1;fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1;display:inline" />
114 <path
115 transform="translate(-133.77922,-205.78699)"
116 sodipodi:nodetypes="czzss"
117 id="path3378"
118 d="M 218.3784,683.819 C 292.95956,706.68151 419.31948,645.12109 460.7908,599.91286 C 501.75634,555.25597 499.76424,474.27134 453.10465,423.18679 C 405.80376,371.40013 276.47478,357.25089 219.12629,366.22918 C 176.30935,372.93247 191.64577,675.62423 218.3784,683.819 z"
119 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1;display:inline" />
120 <path
121 transform="translate(-133.77922,-205.78699)"
122 sodipodi:nodetypes="czzss"
123 id="path3281"
124 d="M 223.71438,635.10562 C 310.48804,641.06851 395.87437,615.02173 421.86503,584.26101 C 447.43016,554.00392 459.28269,492.6842 422.95898,449.14974 C 386.13603,405.01693 265.00951,392.95889 220.36467,400.61023 C 187.0324,406.3228 183.92538,632.37141 223.71438,635.10562 z"
125 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1;display:inline" />
126 </g>
127 <g
128 inkscape:label="Simplexes"
129 inkscape:groupmode="layer"
130 id="layer1"
131 transform="translate(-85.163703,-243.75413)"
132 style="display:inline">
133 <text
134 xml:space="preserve"
135 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
136 x="197.9899"
137 y="425.05746"
138 id="text3303"><tspan
139 sodipodi:role="line"
140 id="tspan3305"
141 x="197.9899"
142 y="425.05746"
143 style="font-style:italic;font-weight:normal" /></text>
144 <text
145 xml:space="preserve"
146 style="font-size:40px;font-style:normal;font-weight:bold;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
147 x="189.90868"
148 y="417.98639"
149 id="text3315"><tspan
150 sodipodi:role="line"
151 id="tspan3317"
152 x="189.90868"
153 y="417.98639" /></text>
154 <path
155 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
156 d="M 501.54156,524.60335 L 225.23693,475.44574 L 554.96292,387.75559 L 501.54156,524.60335 z"
157 id="path2423"
158 sodipodi:nodetypes="cccc" />
159 <text
160 xml:space="preserve"
161 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
162 x="136.46864"
163 y="624.44934"
164 id="text3339"><tspan
165 sodipodi:role="line"
166 id="tspan3341"
167 x="136.46864"
168 y="624.44934">R1</tspan></text>
169 <text
170 xml:space="preserve"
171 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
172 x="533.56018"
173 y="378.42715"
174 id="text2438"><tspan
175 sodipodi:role="line"
176 id="tspan2440"
177 x="533.56018"
178 y="378.42715">H</tspan></text>
179 <text
180 xml:space="preserve"
181 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
182 x="203.94423"
183 y="481.67514"
184 id="text2442"><tspan
185 sodipodi:role="line"
186 id="tspan2444"
187 x="203.94423"
188 y="481.67514">L</tspan></text>
189 <text
190 xml:space="preserve"
191 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
192 x="511.85257"
193 y="535.44348"
194 id="text2446"><tspan
195 sodipodi:role="line"
196 id="tspan2448"
197 x="511.85257"
198 y="535.44348">N</tspan></text>
199 <path
200 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
201 d="M 170.6059,611.44637 L 554.67456,388.69752"
202 id="path3226"
203 sodipodi:nodetypes="cc" />
204 <path
205 sodipodi:type="arc"
206 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
207 id="path3247"
208 sodipodi:cx="304.561"
209 sodipodi:cy="367.98383"
210 sodipodi:rx="2.2728431"
211 sodipodi:ry="2.2728431"
212 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
213 transform="translate(-134.83383,244.62513)" />
214 <path
215 sodipodi:type="arc"
216 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
217 id="path3402"
218 sodipodi:cx="304.561"
219 sodipodi:cy="367.98383"
220 sodipodi:rx="2.2728431"
221 sodipodi:ry="2.2728431"
222 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
223 transform="translate(153.57938,76.248576)" />
224 <g
225 id="g3455"
226 transform="translate(-24.285714,68.571429)">
227 <text
228 id="text3238"
229 y="344.7597"
230 x="619.78632"
231 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
232 xml:space="preserve"><tspan
233 y="344.7597"
234 x="619.78632"
235 id="tspan3240"
236 sodipodi:role="line">R = Reflexion</tspan></text>
237 <text
238 id="text3242"
239 y="261.8324"
240 x="619.75543"
241 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
242 xml:space="preserve"><tspan
243 y="261.8324"
244 x="619.75543"
245 id="tspan3244"
246 sodipodi:role="line">H = Highest</tspan></text>
247 <text
248 id="text3246"
249 y="319.74161"
250 x="619.89966"
251 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
252 xml:space="preserve"><tspan
253 y="319.74161"
254 x="619.89966"
255 id="tspan3248"
256 sodipodi:role="line">L = Lowest</tspan></text>
257 <text
258 id="text3250"
259 y="290.78702"
260 x="619.83783"
261 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
262 xml:space="preserve"><tspan
263 y="290.78702"
264 x="619.83783"
265 id="tspan3252"
266 sodipodi:role="line">N = Next to highest</tspan></text>
267 </g>
268 <path
269 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 2;stroke-dashoffset:0;stroke-opacity:1"
270 d="M 226.21509,475.29735 L 502.51972,524.45496 L 172.79373,612.14511 L 226.21509,475.29735 z"
271 id="path3384"
272 sodipodi:nodetypes="cccc" />
273 <path
274 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;display:inline"
275 d="M 501.64942,524.77605 L 225.34479,475.61844 L 458.64221,443.64258 L 501.64942,524.77605 z"
276 id="path3387"
277 sodipodi:nodetypes="cccc" />
278 <path
279 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1;display:inline"
280 d="M 182.76977,394.35687 L 459.0744,443.51448 L 225.77698,475.49034 L 182.76977,394.35687 z"
281 id="path3394"
282 sodipodi:nodetypes="cccc" />
283 <path
284 sodipodi:type="arc"
285 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:inline"
286 id="path3396"
287 sodipodi:cx="304.561"
288 sodipodi:cy="367.98383"
289 sodipodi:rx="2.2728431"
290 sodipodi:ry="2.2728431"
291 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
292 transform="translate(-121.78939,27.490076)" />
293 <text
294 xml:space="preserve"
295 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;display:inline;font-family:Bitstream Vera Sans"
296 x="145.3134"
297 y="398.76273"
298 id="text3399"><tspan
299 sodipodi:role="line"
300 id="tspan3401"
301 x="145.3134"
302 y="398.76273">R2</tspan></text>
303 <path
304 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1;display:inline"
305 d="M 182.1612,395.73154 L 499.55979,524.51578"
306 id="path3407"
307 sodipodi:nodetypes="cc" />
308 <path
309 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1;display:inline"
310 d="M 420.42395,491.59903 L 225.94168,475.77645 L 459.2391,443.80059 L 420.42395,491.59903 z"
311 id="path3429"
312 sodipodi:nodetypes="cccc" />
313 <path
314 sodipodi:type="arc"
315 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:inline"
316 id="path3436"
317 sodipodi:cx="304.561"
318 sodipodi:cy="367.98383"
319 sodipodi:rx="2.2728431"
320 sodipodi:ry="2.2728431"
321 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
322 transform="translate(114.58631,123.95964)" />
323 <path
324 sodipodi:type="arc"
325 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1;display:inline"
326 id="path3465"
327 sodipodi:cx="304.561"
328 sodipodi:cy="367.98383"
329 sodipodi:rx="2.2728431"
330 sodipodi:ry="2.2728431"
331 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
332 transform="translate(-79.397301,150.82872)" />
333 <g
334 id="g4517"
335 transform="translate(-25.714286,20)">
336 <text
337 id="text3992"
338 y="518.53986"
339 x="141.34859"
340 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;display:inline;font-family:Bitstream Vera Sans"
341 xml:space="preserve"><tspan
342 y="518.53986"
343 x="141.34859"
344 id="tspan3994"
345 sodipodi:role="line">X</tspan></text>
346 <text
347 id="text3996"
348 y="509.25412"
349 x="151.3486"
350 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;display:inline;font-family:Bitstream Vera Sans"
351 xml:space="preserve"><tspan
352 y="509.25412"
353 x="151.3486"
354 id="tspan3998"
355 sodipodi:role="line">✶</tspan></text>
356 </g>
357 <path
358 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-opacity:1"
359 d="M 62.857143,317.08718 L 129.28571,307.80147"
360 id="path4000"
361 transform="translate(85.163703,213.86821)" />
362 </g>
363</svg>
diff --git a/scilab_doc/neldermead/method-neldermead.tex b/scilab_doc/neldermead/method-neldermead.tex
index 8e9fd1f..35398c3 100644
--- a/scilab_doc/neldermead/method-neldermead.tex
+++ b/scilab_doc/neldermead/method-neldermead.tex
@@ -3,56 +3,76 @@
3In this chapter, we present Nelder and Mead's \cite{citeulike:3009487} algorithm. 3In this chapter, we present Nelder and Mead's \cite{citeulike:3009487} algorithm.
4We begin by the analysis of the algorithm, which is based on a variable shape simplex. 4We begin by the analysis of the algorithm, which is based on a variable shape simplex.
5Then, we present geometric situations where the various steps of the algorithm 5Then, we present geometric situations where the various steps of the algorithm
6might be used. In the third part, we present the rate of convergence toward the optimum of 6are used. In the third part, we present the rate of convergence toward the optimum of
7the Nelder-Mead algorithm. This part is mainly based on Han and Neumann's paper \cite{HanNeumann2006}, 7the Nelder-Mead algorithm. This part is mainly based on Han and Neumann's paper \cite{HanNeumann2006},
8which is based on a class of quadratic functions with a special initial 8which makes use of a class of quadratic functions with a special initial
9simplex. The core of this chapter is the analysis of several numerical 9simplex. The core of this chapter is the analysis of several numerical
10experiments which have been performed with the neldermead component. 10experiments which have been performed with the neldermead component.
11We analyse the behaviour of the algorithm on quadratic functions and 11We analyze the behavior of the algorithm on quadratic functions and
12present several counter examples where the Nelder-Mead algorithm is 12present several counter examples where the Nelder-Mead algorithm is
13known to fail. 13known to fail.
14 14
15\section{Introduction} 15\section{Introduction}
16 16
17The goal of Nelder and Mead algorithm is to solve the 17In this section, we present the Nelder-Mead algorithm for unconstrained optimization.
18This algorithm is based on the iterative update of a simplex.
19Then we present various geometric situations which might occur
20during the algorithm.
21
22\subsection{Overview}
23
24The goal of the Nelder and Mead algorithm is to solve the
18following unconstrained optimization problem 25following unconstrained optimization problem
19\begin{eqnarray} 26\begin{eqnarray}
20\min f(x) 27\min f(\bx)
21\end{eqnarray} 28\end{eqnarray}
22where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 29where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective
23function $f:\RR^n\rightarrow \RR$. 30function $f:\RR^n\rightarrow \RR$.
24 31
25The Nelder-Mead method is an improvment over the Spendley's et al. 32The Nelder-Mead method is an improvement over the Spendley's et al.
26method with the goal of allowing the simplex to vary in shape. 33method with the goal of allowing the simplex to vary in \emph{shape},
27The Nelder-Mead algorithm makes use of four parameters: the 34and not only in \emph{size}, as in Spendley's et al. algorithm.
28coefficient of reflection $\rho$, expansion $\chi$,
29contraction $\gamma$ and shrinkage $\sigma$.
30When the expansion or contraction steps are performed, the shape
31of the simplex is changed, thus "adapting itself to the
32local landscape" \cite{citeulike:3009487}.
33 35
34These parameters should satisfy the following inequalities \cite{citeulike:3009487,lagarias:112} 36This algorithms is based on the iterative update of
35\begin{eqnarray} 37a \emph{simplex} made of $n+1$ points $S=\{\bv_i\}_{i=1,n+1}$. Each point
36\label{condition-coeffs} 38in the simplex is called a \emph{vertex} and is associated with
37\rho>0, \qquad \chi > 1, \qquad \chi > \rho, \qquad 0<\gamma<1, \qquad \textrm{and} \qquad 0<\sigma<1. 39a function value $f_i=f(\bv_i)$ for $i=1,n+1$.
38\end{eqnarray}
39 40
40The standard values for these coefficients are 41The vertices are sorted by increasing function values so that the
42\emph{best} vertex has index 1 and the \emph{worst} vertex
43has index $n+1$
41\begin{eqnarray} 44\begin{eqnarray}
42\label{standard-coeffs} 45\label{sorted-vertices-fv}
43\rho=1, \qquad \chi =2, \qquad \gamma=\frac{1}{2}, \qquad \textrm{and} \qquad \sigma=\frac{1}{2}. 46f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
44\end{eqnarray} 47\end{eqnarray}
45 48
46In \cite{Kelley1999}, the Nelder-Mead algorithm is presented with 49The $\bv_1$ vertex (resp. the $\bv_{n+1}$ vertex) is called the \emph{best}
47other parameter names, that is $\mu_r = \rho$, $\mu_e = \rho\chi$, $\mu_{ic} = -\gamma$ 50vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest)
48and $\mu_{oc} = \rho\gamma$. These coefficients must satisfy the following 51function value.
49inequality
50 52
53The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices
54where the vertex $\bv_j$ has been
55excluded. This centroid is
51\begin{eqnarray} 56\begin{eqnarray}
52-1 < \mu_{ic} < 0 < \mu_{oc} < \mu_r < \mu_e 57\label{centroid-generalized}
58\overline{\bx} (j) =
59\frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i.
53\end{eqnarray} 60\end{eqnarray}
61The algorithm makes use
62of one coefficient $\rho>0$, called the reflection factor. The standard
63value of this coefficient is $\rho=1$.
64The algorithm attempts to replace some vertex
65$\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$
66to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by
67\begin{eqnarray}
68\label{interpolate-generalized}
69\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j.
70\end{eqnarray}
71
72\subsection{Algorithm}
54 73
55The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}. 74In this section, we analyze the Nelder-Mead algorithm, which
75is presented in figure \ref{algo-neldermead}.
56 76
57\begin{figure}[htbp] 77\begin{figure}[htbp]
58\begin{algorithmic} 78\begin{algorithmic}
@@ -61,9 +81,11 @@ The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}.
61\STATE $S\gets S_0$ 81\STATE $S\gets S_0$
62\WHILE{$\sigma(S)>tol$} 82\WHILE{$\sigma(S)>tol$}
63 \STATE $\overline{x}\gets \overline{x}(n+1)$ 83 \STATE $\overline{x}\gets \overline{x}(n+1)$
64 \STATE $x_r \gets x(\rho,n+1)$, $f_r \gets f(x_r)$ \COMMENT{Reflect} 84 \STATE $x_r \gets x(\rho,n+1)$ \COMMENT{Reflect}
85 \STATE $f_r \gets f(x_r)$
65 \IF {$f_r<f_1$} 86 \IF {$f_r<f_1$}
66 \STATE $x_e \gets x(\rho\chi,n+1)$, $f_e \gets f(x_e)$ \COMMENT{Expand} 87 \STATE $x_e \gets x(\rho\chi,n+1)$ \COMMENT{Expand}
88 \STATE $f_e \gets f(x_e)$
67 \IF {$f_e<f_r$} 89 \IF {$f_e<f_r$}
68 \STATE Accept $x_e$ 90 \STATE Accept $x_e$
69 \ELSE 91 \ELSE
@@ -72,29 +94,109 @@ The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}.
72 \ELSIF {$f_1 \leq f_r < f_n$} 94 \ELSIF {$f_1 \leq f_r < f_n$}
73 \STATE Accept $x_r$ 95 \STATE Accept $x_r$
74 \ELSIF {$f_n \leq f_r < f_{n+1}$} 96 \ELSIF {$f_n \leq f_r < f_{n+1}$}
75 \STATE $x_c \gets x(\rho\gamma,n+1)$, $f_c \gets f(x_c)$ \COMMENT{Outside contraction} 97 \STATE $x_c \gets x(\rho\gamma,n+1)$ \COMMENT{Outside contraction}
98 \STATE $f_c \gets f(x_c)$
76 \IF {$f_c<f_r$} 99 \IF {$f_c<f_r$}
77 \STATE Accept $x_c$ 100 \STATE Accept $x_c$
78 \ELSE 101 \ELSE
79 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink} 102 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink}
80 \STATE Compute the function values at the points $x_i, i=2,n+1$ 103 \STATE Compute $f_i = f(\bv_i)$ for $i=2,n+1$
81 \ENDIF 104 \ENDIF
82 \ELSE 105 \ELSE
83 \STATE $x_c \gets x(-\gamma,n+1)$, $f_c \gets f(x_c)$ \COMMENT{Inside contraction} 106 \STATE $x_c \gets x(-\gamma,n+1)$ \COMMENT{Inside contraction}
107 \STATE $f_c \gets f(x_c)$
84 \IF {$f_c<f_{n+1}$} 108 \IF {$f_c<f_{n+1}$}
85 \STATE Accept $x_c$ 109 \STATE Accept $x_c$
86 \ELSE 110 \ELSE
87 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink} 111 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink}
88 \STATE Compute the function values at the points $x_i, i=2,n+1$ 112 \STATE Compute $f_i = f(\bv_i)$ for $i=2,n+1$
89 \ENDIF 113 \ENDIF
90 \ENDIF 114 \ENDIF
91 \STATE Sort the vertices of $S$ with increasing function values 115 \STATE Sort the vertices of $S$ with increasing function values
92\ENDWHILE 116\ENDWHILE
93\end{algorithmic} 117\end{algorithmic}
94\caption{Nelder-Mead algorithm - standard version} 118\caption{Nelder-Mead algorithm -- Standard version}
95\label{algo-neldermead} 119\label{algo-neldermead}
96\end{figure} 120\end{figure}
97 121
122The Nelder-Mead algorithm makes use of four parameters: the
123coefficient of reflection $\rho$, expansion $\chi$,
124contraction $\gamma$ and shrinkage $\sigma$.
125When the expansion or contraction steps are performed, the shape
126of the simplex is changed, thus "adapting itself to the
127local landscape" \cite{citeulike:3009487}.
128
129These parameters should satisfy the following inequalities \cite{citeulike:3009487,lagarias:112}
130\begin{eqnarray}
131\label{condition-coeffs}
132\rho>0, \qquad \chi > 1, \qquad \chi > \rho, \qquad 0<\gamma<1 \qquad \textrm{and} \qquad 0<\sigma<1.
133\end{eqnarray}
134The standard values for these coefficients are
135\begin{eqnarray}
136\label{standard-coeffs}
137\rho=1, \qquad \chi =2, \qquad \gamma=\frac{1}{2} \qquad \textrm{and} \qquad \sigma=\frac{1}{2}.
138\end{eqnarray}
139
140In \cite{Kelley1999}, the Nelder-Mead algorithm is presented with
141other parameter names, that is $\mu_r = \rho$, $\mu_e = \rho\chi$, $\mu_{ic} = -\gamma$
142and $\mu_{oc} = \rho\gamma$. These coefficients must satisfy the following
143inequality
144\begin{eqnarray}
145-1 < \mu_{ic} < 0 < \mu_{oc} < \mu_r < \mu_e.
146\end{eqnarray}
147
148At each iteration, we compute the centroid
149$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$
150has been excluded. This centroid is
151\begin{eqnarray}
152\label{centroid-worst}
153\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i.
154\end{eqnarray}
155We perform a reflection with respect to the worst vertex $\bv_{n+1}$,
156which creates the reflected point $\bx_r$ defined by
157\begin{eqnarray}
158\label{interpolate-worst}
159\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1}
160\end{eqnarray}
161We then compute the function value of the reflected
162point as $f_r=f(\bx_r)$.
163
164From that point, there are several possibilities, which
165are listed below. Most steps try to replace the
166worst vertex $\bv_{n+1}$ by a better point, which is computed
167depending on the context.
168\begin{itemize}
169\item In the case where $f_r<f_1$, the reflected point $\bx_r$
170were able to improve (i.e. reduce) the function value. In that case, the algorithm
171tries to expand the simplex so that the function value is improved
172even more. The expansion point is computed by
173\begin{eqnarray}
174\bx_e = \bx(\rho\chi,n+1) = (1+\rho\chi)\overline{\bx}(n+1) - \rho\chi \bv_{n+1}
175\end{eqnarray}
176and the function is computed at this point, i.e. we compute
177$f_e = f(\bx_e)$.
178If the expansion point allows to improve the function
179value, the worst vertex
180$\bv_{n+1}$ is rejected from the simplex and the expansion point $\bx_e$
181is accepted. If not, the reflection point $\bx_r$ is accepted.
182\item In the case where $f_1\leq f_r<f_n$, the worst vertex
183$\bv_{n+1}$ is rejected from the simplex and the reflected point $\bx_r$
184is accepted.
185\item In the case where $f_n\leq f_r<f_{n+1}$, we consider the point
186\begin{eqnarray}
187\bx_c = \bx(\rho\gamma,n+1) = (1+\rho\gamma)\overline{\bx}(n+1) - \rho\gamma \bv_{n+1}
188\end{eqnarray}
189is considered. If the point $\bx_c$ is better than the reflection point $\bx_r$,
190then it is accepted. If not, a shrink step is performed, where
191all vertices are moved toward the best vertex $\bv_1$.
192\item In other cases, we consider the point
193\begin{eqnarray}
194\bx_c = \bx(-\gamma,n+1) = (1-\gamma)\overline{\bx}(n+1) + \gamma \bv_{n+1}.
195\end{eqnarray}
196If the point $\bx_c$ is better than the worst vertex $\bx_{n+1}$,
197then it is accepted. If not, a shrink step is performed.
198\end{itemize}
199
98The algorithm from figure \ref{algo-neldermead} is the most 200The algorithm from figure \ref{algo-neldermead} is the most
99popular variant of the Nelder-Mead algorithm. 201popular variant of the Nelder-Mead algorithm.
100But the original paper is based on a "greedy" expansion, where 202But the original paper is based on a "greedy" expansion, where
@@ -104,14 +206,22 @@ This "greedy" version is implemented in AS47 by O'Neill in \cite{O'Neill1971AAF}
104and the corresponding algorithm is presented in figure \ref{algo-neldermead-greedy}. 206and the corresponding algorithm is presented in figure \ref{algo-neldermead-greedy}.
105 207
106\begin{figure}[htbp] 208\begin{figure}[htbp]
209\begin{verbatim}
210[...]
211\end{verbatim}
107\begin{algorithmic} 212\begin{algorithmic}
213 \STATE $\bx_e \gets \bx(\rho\chi,n+1)$ \COMMENT{Expand}
214 \STATE $f_e \gets f(\bx_e)$
108 \IF {$f_e<f_1$} 215 \IF {$f_e<f_1$}
109 \STATE Accept $x_e$ 216 \STATE Accept $\bx_e$
110 \ELSE 217 \ELSE
111 \STATE Accept $x_r$ 218 \STATE Accept $\bx_r$
112 \ENDIF 219 \ENDIF
113\end{algorithmic} 220\end{algorithmic}
114\caption{Nelder-Mead algorithm - greedy version} 221\begin{verbatim}
222[...]
223\end{verbatim}
224\caption{Nelder-Mead algorithm -- Greedy version}
115\label{algo-neldermead-greedy} 225\label{algo-neldermead-greedy}
116\end{figure} 226\end{figure}
117 227
@@ -123,81 +233,90 @@ simplex in the Nelder-Mead algorithm.
123 233
124\begin{figure} 234\begin{figure}
125\begin{center} 235\begin{center}
126\includegraphics[width=10cm]{nelder-mead-steps.png} 236\includegraphics[width=6cm]{nelder-mead-steps.pdf}
127\end{center} 237\end{center}
128\caption{Nelder-Mead simplex moves} 238\caption{Nelder-Mead simplex steps}
129\label{fig-nm-moves} 239\label{fig-nm-moves}
130\end{figure} 240\end{figure}
131 241
132The figure \ref{fig-nm-moves-reflection} 242The figure \ref{fig-nm-moves-reflection}
133through \ref{fig-nm-moves-shrinkafterco} present the 243to \ref{fig-nm-moves-shrinkafterco} present the
134detailed situations when each kind of step occur. 244detailed situations when each type of step occur.
135 245We emphasize that these figures are not the result of
136Obviously, the expansion step is performed when the 246numerical experiments. These figures been created in order
247to illustrate specific points of the algorithm.
248
249\begin{itemize}
250\item Obviously, the expansion step is performed when the
137simplex is far away from the optimum. The direction of 251simplex is far away from the optimum. The direction of
138descent is then followed and the worst vertex is moved 252descent is then followed and the worst vertex is moved
139into that direction. 253into that direction.
140 254\item When the reflection step is performed, the simplex is
141When the reflection step is performed, the simplex is
142getting close to an valley, since the expansion point 255getting close to an valley, since the expansion point
143does not improve. 256does not improve the function value.
144 257\item When the simplex is near the optimum,
145When the simplex is near the optimum,
146the inside and outside contraction steps may be performed, which 258the inside and outside contraction steps may be performed, which
147allow to decrease the size of the simplex. 259allows to decrease the size of the simplex.
148 260The figure \ref{fig-nm-moves-insidecontraction}, which illustrates
149The shrink steps (be it after an outside contraction or an inside 261the inside contraction step, happens in "good" situations.
262As presented in section \ref{section-mcKinnon}, applying
263repeatedly the inside contraction step can transform
264the simplex into a degenerate simplex, which may let the algorithm
265converge to a non stationnary point.
266\item The shrink steps (be it after an outside contraction or an inside
150contraction) occurs only in very special situations. In practical experiments, 267contraction) occurs only in very special situations. In practical experiments,
151shrink steps are rare. 268shrink steps are rare.
269\end{itemize}
152 270
153\begin{figure} 271\begin{figure}
154\begin{center} 272\begin{center}
155\includegraphics[width=10cm]{nelder-mead-reflection.png} 273\includegraphics[width=10cm]{nelder-mead-reflection.pdf}
156\end{center} 274\end{center}
157\caption{Nelder-Mead simplex moves - reflection} 275\caption{Nelder-Mead simplex moves -- Reflection}
158\label{fig-nm-moves-reflection} 276\label{fig-nm-moves-reflection}
159\end{figure} 277\end{figure}
160 278
161\begin{figure} 279\begin{figure}
162\begin{center} 280\begin{center}
163\includegraphics[width=10cm]{nelder-mead-extension.png} 281\includegraphics[width=10cm]{nelder-mead-extension.pdf}
164\end{center} 282\end{center}
165\caption{Nelder-Mead simplex moves - expansion} 283\caption{Nelder-Mead simplex moves -- Expansion}
166\label{fig-nm-moves-expansion} 284\label{fig-nm-moves-expansion}
167\end{figure} 285\end{figure}
168 286
169\begin{figure} 287\begin{figure}
170\begin{center} 288\begin{center}
171\includegraphics[width=10cm]{nelder-mead-contract-inside.png} 289\includegraphics[width=10cm]{nelder-mead-contract-inside.pdf}
172\end{center} 290\end{center}
173\caption{Nelder-Mead simplex moves - inside contraction} 291\caption{Nelder-Mead simplex moves - Inside contraction}
174\label{fig-nm-moves-insidecontraction} 292\label{fig-nm-moves-insidecontraction}
175\end{figure} 293\end{figure}
176 294
177\begin{figure} 295\begin{figure}
178\begin{center} 296\begin{center}
179\includegraphics[width=10cm]{nelder-mead-contract-outside.png} 297\includegraphics[width=10cm]{nelder-mead-contract-outside.pdf}
180\end{center} 298\end{center}
181\caption{Nelder-Mead simplex moves - outside contraction} 299\caption{Nelder-Mead simplex moves -- Outside contraction}
182\label{fig-nm-moves-outsidecontraction} 300\label{fig-nm-moves-outsidecontraction}
183\end{figure} 301\end{figure}
184 302
185\begin{figure} 303\begin{figure}
186\begin{center} 304\begin{center}
187\includegraphics[width=10cm]{nelder-mead-shrink-afterci.png} 305\includegraphics[width=6cm]{nelder-mead-shrink-afterci.pdf}
188\end{center} 306\end{center}
189\caption{Nelder-Mead simplex moves - shrink after inside contraction.} 307\caption{Nelder-Mead simplex moves -- Shrink after inside contraction.}
190\label{fig-nm-moves-shrinkafterci} 308\label{fig-nm-moves-shrinkafterci}
191\end{figure} 309\end{figure}
192 310
193\begin{figure} 311\begin{figure}
194\begin{center} 312\begin{center}
195\includegraphics[width=10cm]{nelder-mead-shrink-afterco.png} 313\includegraphics[width=10cm]{nelder-mead-shrink-afterco.pdf}
196\end{center} 314\end{center}
197\caption{Nelder-Mead simplex moves - shrink after outside contraction} 315\caption{Nelder-Mead simplex moves -- Shrink after outside contraction}
198\label{fig-nm-moves-shrinkafterco} 316\label{fig-nm-moves-shrinkafterco}
199\end{figure} 317\end{figure}
200 318
319
201%\subsection{Termination criteria} 320%\subsection{Termination criteria}
202 321
203%TODO... 322%TODO...
@@ -206,17 +325,17 @@ shrink steps are rare.
206 325
207In this section, we reproduce one result 326In this section, we reproduce one result
208presented by Han and Neumann \cite{HanNeumann2006}, which states 327presented by Han and Neumann \cite{HanNeumann2006}, which states
209the rate of convergence toward the optimum on a class of quadratic functions with a special initial 328the rate of convergence toward the optimum on a class of quadratic
210simplex. 329functions with a special initial simplex.
211Some additionnal results are also presented in the Phd thesis by Lixing Han in 2000 \cite{Han2000}. 330Some additional results are also presented in the Phd thesis by Lixing Han \cite{Han2000}.
212We study a generalized quadratic and use a particular 331We study a generalized quadratic and use a particular
213initial simplex. We show that the vertices follow 332initial simplex. We show that the vertices follow
214a recurrence equation, which is associated with a caracteristic 333a recurrence equation, which is associated with a characteristic
215equation. The study of the roots of these caracteristic equations 334equation. The study of the roots of these characteristic equations
216give an insight of the behaviour of the Nelder-Mead algorithm 335give an insight of the behavior of the Nelder-Mead algorithm
217when the dimension $n$ increases. 336when the dimension $n$ increases.
218 337
219Let us suppose than one wants to minimize the function 338Let us suppose than we want to minimize the function
220\begin{eqnarray} 339\begin{eqnarray}
221\label{hanneumman-quadratic} 340\label{hanneumman-quadratic}
222f(\bx) = x_1^2+\ldots+x_n^2 341f(\bx) = x_1^2+\ldots+x_n^2
@@ -226,137 +345,126 @@ with the initial simplex
226S_0 = \left[\bold{0},\bv^{(0)}_1,\ldots,\bv^{(0)}_n\right] 345S_0 = \left[\bold{0},\bv^{(0)}_1,\ldots,\bv^{(0)}_n\right]
227\end{eqnarray} 346\end{eqnarray}
228With this choice of the initial simplex, the best vertex remains fixed 347With this choice of the initial simplex, the best vertex remains fixed
229at $\bold{0}\in\RR^n$. As the function in equation \ref{hanneumman-quadratic} 348at $\bold{0}=(0,0,\ldots,0)^T\in\RR^n$. As the cost function \ref{hanneumman-quadratic}
230is strictly convex, the Nelder-Mead method never performs 349is strictly convex, the Nelder-Mead method never performs
231the \emph{shrink} step. Therefore, at each iteration, a new simplex 350the \emph{shrink} step. Therefore, at each iteration, a new simplex
232is formed by replacing the worst vertex $\bv^{(k)}_n$, by a 351is formed by replacing the worst vertex $\bv^{(k)}_n$, by a
233new, better vertex. Assume that the Nelder-Mead method 352new, better vertex. Assume that the Nelder-Mead method
234generates a sequence of simplices ${S_k}_{k\geq 0}$ in $\RR^n$, 353generates a sequence of simplices $\{S_k\}_{k\geq 0}$ in $\RR^n$,
235where 354where
236\begin{eqnarray} 355\begin{eqnarray}
237S_k = \left[\bold{0},\bv^{(k)}_1,\ldots,\bv^{(n)}_n\right] 356S_k = \left[\bold{0},\bv^{(k)}_1,\ldots,\bv^{(n)}_n\right]
238\end{eqnarray} 357\end{eqnarray}
239We wish that the sequence of simplices ${S_k}\rightarrow \bold{0}\in\RR^n$ 358We wish that the sequence of simplices $S_k\rightarrow \bold{0}\in\RR^n$
240as $k\rightarrow \infty$. To measure the progress of convergence, 359as $k\rightarrow \infty$. To measure the progress of convergence,
241Han and Neumann use the oriented length of the simplex $S_k$, $\sigma(S_k)$. 360Han and Neumann use the oriented length $\sigma_+(S_k)$ of the simplex $S_k$,
242We say that a sequence of simplices ${S_k}$ converges to the minimizer $\bold{0}\in\RR^n$ 361defined by
362\begin{eqnarray}
363\sigma_+(S) = \max_{i=2,m} \|\bv_i - \bv_1\|_2.
364\end{eqnarray}
365We say that a sequence of simplices $\{S_k\}_{k\geq 0}$ converges to the minimizer $\bold{0}\in\RR^n$
243of the function in equation \ref{hanneumman-quadratic} if 366of the function in equation \ref{hanneumman-quadratic} if
244$\lim_{k\rightarrow \infty} \sigma(S_k) = 0$. 367$\lim_{k\rightarrow \infty} \sigma_+(S_k) = 0$.
245
246We measure the rate of convergence defined by \cite{HanNeumann2006}
247 368
369We measure the rate of convergence defined by
248\begin{eqnarray} 370\begin{eqnarray}
249\label{rho-rate-convergence} 371\label{rho-rate-convergence}
250\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty} 372\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
251\left(\sum_{i=0,k-1} \frac{\sigma(S_{i+1}}{\sigma(S_i}\right)^{1/k} 373\left(\sum_{i=0,k-1} \frac{\sigma(S_{i+1})}{\sigma(S_i)}\right)^{1/k}
252\end{eqnarray} 374\end{eqnarray}
253
254That definition can be viewed as the geometric mean of the ratio of the 375That definition can be viewed as the geometric mean of the ratio of the
255oriented lengths between successive simplices and the minimizer 0. 376oriented lengths between successive simplices and the minimizer 0.
256This definition implies 377This definition implies
257
258\begin{eqnarray} 378\begin{eqnarray}
259\label{rho-rate-convergence2} 379\label{rho-rate-convergence2}
260\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty} 380\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
261\left( \frac{\sigma(S_{k+1}}{\sigma(S_0}\right)^{1/k} 381\left( \frac{\sigma(S_{k+1})}{\sigma(S_0)}\right)^{1/k}
262\end{eqnarray} 382\end{eqnarray}
263 383
264According to the definition, the algorithm is convergent if $0\leq \rho(S_0,n) < 1$. 384According to the definition, the algorithm is convergent if $\rho(S_0,n) < 1$.
265The larger the $\rho(S_0,n)$, the slower the convergence. In particular, the convergence 385The larger the $\rho(S_0,n)$, the slower the convergence. In particular, the convergence
266is very slow when $\rho(S_0,n)$ is close to 1. 386is very slow when $\rho(S_0,n)$ is close to 1.
267The analysis is based on the fact that the Nelder-Mead method generates a sequence of simplices 387The analysis is based on the fact that the Nelder-Mead method generates a sequence of simplices
268in $\RR^n$ satisfying 388in $\RR^n$ satisfying
269
270\begin{eqnarray} 389\begin{eqnarray}
271S_k = \left[\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\right] 390S_k = \left[\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\right],
272\end{eqnarray} 391\end{eqnarray}
273
274where $\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\in\RR^n$ are the vertices 392where $\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\in\RR^n$ are the vertices
275of the $k-th$ simplex, with 393of the $k-th$ simplex, with
276
277\begin{eqnarray} 394\begin{eqnarray}
278f(\bold{0}) < f(\bv^{(k+n-1)} < f(\bv^{(k+1)}) < f(\bv^{(k)}), 395f(\bold{0}) < f\left(\bv^{(k+n-1)}\right) < f\left(\bv^{(k+1)}\right) < f\left(\bv^{(k)}\right),
279\end{eqnarray} 396\end{eqnarray}
280
281for $k\geq 0$. 397for $k\geq 0$.
282 398
283To simplify the analysis, we consider that only one type of step of the Nelder-Mead 399To simplify the analysis, we consider that only one type of step of the Nelder-Mead
284method is applied repeatedly. This allows to establich recurrence equations for the 400method is applied repeatedly. This allows to establish recurrence equations for the
285sucessive simplex vertices. As the shrink step is never used, and the expansion steps is 401successive simplex vertices. As the shrink step is never used, and the expansion steps is
286never used neither (since the best vertex is already at 0), the analysis focuses 402never used neither (since the best vertex is already at 0), the analysis focuses
287on the outside contraction, inside contraction and reflection steps. 403on the outside contraction, inside contraction and reflection steps.
288 404
289The centroid of the $n$ best vertices of $S_k$ is given by 405The centroid of the $n$ best vertices of $S_k$ is given by
290
291\begin{eqnarray} 406\begin{eqnarray}
292\overline{\bold{v}}^{(k)} &=& \frac{1}{n} \sum_{i=1,n-1} \bv^{(k+i)}\\ 407\overline{\bold{v}}^{(k)}
293&=&\frac{1}{n} \left( \bv^{(k+1)} + \ldots + \bv^{(k+n-1)} \right) 408&=&\frac{1}{n} \left( \bv^{(k+1)} + \ldots + \bv^{(k+n-1)} + \bold{0} \right)\\
409&=&\frac{1}{n} \left( \bv^{(k+1)} + \ldots + \bv^{(k+n-1)} \right)\\
410&=& \frac{1}{n} \sum_{i=1,n-1} \bv^{(k+i)} \label{eq-nm-centroid}
294\end{eqnarray} 411\end{eqnarray}
295 412
296\subsection{With default parameters} 413\subsection{With default parameters}
297 414
298In this section, we analyse the roots of the caracteristic 415In this section, we analyze the roots of the characteristic
299equation with \emph{fixed}, standard inside and outside contraction 416equation with \emph{fixed}, standard inside and outside contraction
300coefficients. 417coefficients.
301 418
302\emph{Outside contraction} If the outside contraction step is repeatedly performed 419\emph{Outside contraction} \\
420If the outside contraction step is repeatedly performed
303with $\mu_{oc} = \rho\gamma = \frac{1}{2}$, then 421with $\mu_{oc} = \rho\gamma = \frac{1}{2}$, then
304
305\begin{eqnarray} 422\begin{eqnarray}
306\bv^{(k+n)} = \overline{\bold{v}}^{(k)} 423\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
307+ \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) 424+ \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) .
308\end{eqnarray} 425\end{eqnarray}
309By plugging the definition of the centroid into the previous equality, one 426By plugging the definition of the centroid \ref{eq-nm-centroid} into the previous equality, we
310find the recurrence formula 427find the recurrence formula
311
312\begin{eqnarray} 428\begin{eqnarray}
3132n \bv^{(k+n)} - 3 \bv^{(k+1)} - \ldots - 3 \bv^{(k+n-1)} + n\bv^{(k)} = 0 4292n \bv^{(k+n)} - 3 \bv^{(k+1)} - \ldots - 3 \bv^{(k+n-1)} + n\bv^{(k)} = 0.
314\end{eqnarray} 430\end{eqnarray}
315 431The associated characteristic equation is
316The associated caracteristic equation is
317
318\begin{eqnarray} 432\begin{eqnarray}
319\label{recurrence-oc} 433\label{recurrence-oc}
3202n \mu^n - 3 \mu^{n-1} - \ldots - 3 \mu + n = 0. 4342n \mu^n - 3 \mu^{n-1} - \ldots - 3 \mu + n = 0.
321\end{eqnarray} 435\end{eqnarray}
322 436
323\emph{Inside contraction} If the inside contraction step is repeatedly performed 437\emph{Inside contraction} \\
438If the inside contraction step is repeatedly performed
324with $\mu_{ic} = -\gamma = -\frac{1}{2}$, then 439with $\mu_{ic} = -\gamma = -\frac{1}{2}$, then
325
326\begin{eqnarray} 440\begin{eqnarray}
327\bv^{(k+n)} = \overline{\bold{v}}^{(k)} 441\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
328- \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) 442- \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right).
329\end{eqnarray} 443\end{eqnarray}
330By plugging the definition of the centroid into the previous equality, one 444By plugging the definition of the centroid \ref{eq-nm-centroid} into the previous equality, we
331find the recurrence formula 445find the recurrence formula
332
333\begin{eqnarray} 446\begin{eqnarray}
3342n \bv^{(k+n)} - \bv^{(k+1)} - \ldots - \bv^{(k+n-1)} - n\bv^{(k)} = 0 4472n \bv^{(k+n)} - \bv^{(k+1)} - \ldots - \bv^{(k+n-1)} - n\bv^{(k)} = 0.
335\end{eqnarray} 448\end{eqnarray}
336 449The associated characteristic equation is
337The associated caracteristic equation is
338
339\begin{eqnarray} 450\begin{eqnarray}
340\label{recurrence-ic} 451\label{recurrence-ic}
3412n \mu^n - \mu^{n-1} - \ldots - \mu - n = 0. 4522n \mu^n - \mu^{n-1} - \ldots - \mu - n = 0.
342\end{eqnarray} 453\end{eqnarray}
343 454
344\emph{Reflection} If the reflection step is repeatedly performed 455\emph{Reflection} \\
456If the reflection step is repeatedly performed
345with $\mu_r = \rho = 1$, then 457with $\mu_r = \rho = 1$, then
346
347\begin{eqnarray} 458\begin{eqnarray}
348\bv^{(k+n)} = \overline{\bold{v}}^{(k)} 459\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
349+ \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) 460+ \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right).
350\end{eqnarray} 461\end{eqnarray}
351By plugging the definition of the centroid into the previous equality, one 462By plugging the definition of the centroid \ref{eq-nm-centroid} into the previous equality, we
352find the recurrence formula 463find the recurrence formula
353
354\begin{eqnarray} 464\begin{eqnarray}
355n \bv^{(k+n)} - 2 \bv^{(k+1)} - \ldots - 2 \bv^{(k+n-1)} + n\bv^{(k)} = 0 465n \bv^{(k+n)} - 2 \bv^{(k+1)} - \ldots - 2 \bv^{(k+n-1)} + n\bv^{(k)} = 0.
356\end{eqnarray} 466\end{eqnarray}
357 467The associated characteristic equation is
358The associated caracteristic equation is
359
360\begin{eqnarray} 468\begin{eqnarray}
361\label{recurrence-reflection} 469\label{recurrence-reflection}
362n \mu^n - 2 \mu^{n-1} - \ldots - 2 \mu + n = 0. 470n \mu^n - 2 \mu^{n-1} - \ldots - 2 \mu + n = 0.
@@ -364,12 +472,11 @@ n \mu^n - 2 \mu^{n-1} - \ldots - 2 \mu + n = 0.
364 472
365The recurrence equations \ref{recurrence-oc}, \ref{recurrence-ic} and \ref{recurrence-reflection} 473The recurrence equations \ref{recurrence-oc}, \ref{recurrence-ic} and \ref{recurrence-reflection}
366are linear. Their general solutions are of the form 474are linear. Their general solutions are of the form
367
368\begin{eqnarray} 475\begin{eqnarray}
369\bv^{(k)} = \mu_1^k \bold{a}_1 + \ldots + \mu_n^k \bold{a}_n 476\bv^{(k)} = \mu_1^k \bold{a}_1 + \ldots + \mu_n^k \bold{a}_n,
370\end{eqnarray} 477\end{eqnarray}
371where ${\mu_i}_{i=1,n}$ are the roots of the characteristic equations and 478where $\{\mu_i\}_{i=1,n}$ are the roots of the characteristic equations and
372${\bold{a}_i}_{i=1,n} \in \CC^n$ are independent vectors such that $\bv^{(k)} \in \RR^n$ 479$\{\bold{a}_i\}_{i=1,n} \in \CC^n$ are independent vectors such that $\bv^{(k)} \in \RR^n$
373for all $k\geq 0$. 480for all $k\geq 0$.
374 481
375The analysis by Han and Neumann \cite{HanNeumann2006} gives a 482The analysis by Han and Neumann \cite{HanNeumann2006} gives a
@@ -379,17 +486,14 @@ For $n=2$, the convergence rate is $\frac{\sqrt{2}}{2}\approx 0.7$ with
379a particular choice for the initial simplex. For $n\geq 3$, Han and Neumann \cite{HanNeumann2006} 486a particular choice for the initial simplex. For $n\geq 3$, Han and Neumann \cite{HanNeumann2006}
380perform a numerical analysis of the roots. 487perform a numerical analysis of the roots.
381 488
382In the following Scilab script, one computes the roots of these 3 caracteristic 489In the following Scilab script, we compute the roots of these 3 characteristic
383equations. 490equations.
384 491
385\lstset{language=Scilab} 492\lstset{language=scilabscript}
386\lstset{numbers=left}
387\lstset{basicstyle=\footnotesize}
388\lstset{keywordstyle=\bfseries}
389\begin{lstlisting} 493\begin{lstlisting}
390// 494//
391// computeroots1 -- 495// computeroots1 --
392// Compute the roots of the caracteristic equations of 496// Compute the roots of the characteristic equations of
393// usual Nelder-Mead method. 497// usual Nelder-Mead method.
394// 498//
395function computeroots1 ( n ) 499function computeroots1 ( n )
@@ -402,9 +506,10 @@ function computeroots1 ( n )
402 coeffs(n+1) = 2 * n 506 coeffs(n+1) = 2 * n
403 p=poly(coeffs,"x","coeff") 507 p=poly(coeffs,"x","coeff")
404 disp(p) 508 disp(p)
509 mprintf("Roots :\n");
405 r = roots(p) 510 r = roots(p)
406 for i=1:n 511 for i=1:n
407 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) 512 mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
408 end 513 end
409 // Polynomial for inside contraction : 514 // Polynomial for inside contraction :
410 // - n - x - ... - x^(n-1) + 2n x^(n)= 0 515 // - n - x - ... - x^(n-1) + 2n x^(n)= 0
@@ -415,9 +520,10 @@ function computeroots1 ( n )
415 coeffs(n+1) = 2 * n 520 coeffs(n+1) = 2 * n
416 p=poly(coeffs,"x","coeff") 521 p=poly(coeffs,"x","coeff")
417 disp(p) 522 disp(p)
523 mprintf("Roots :\n");
418 r = roots(p) 524 r = roots(p)
419 for i=1:n 525 for i=1:n
420 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) 526 mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
421 end 527 end
422 // Polynomial for reflection : 528 // Polynomial for reflection :
423 // n - 2x - ... - 2x^(n-1) + n x^(n) = 0 529 // n - 2x - ... - 2x^(n-1) + n x^(n) = 0
@@ -429,75 +535,76 @@ function computeroots1 ( n )
429 p=poly(coeffs,"x","coeff") 535 p=poly(coeffs,"x","coeff")
430 disp(p) 536 disp(p)
431 r = roots(p) 537 r = roots(p)
538 mprintf("Roots :\n");
432 for i=1:n 539 for i=1:n
433 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i))) 540 mprintf("Root #%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
434 end 541 end
435endfunction 542endfunction
436\end{lstlisting} 543\end{lstlisting}
437 544
438If one executes this script with $n=10$, the following 545If we execute the previous script with $n=10$, the following
439output is produced. 546output is produced.
440 547
441\begin{tiny} 548\begin{small}
442\begin{verbatim} 549\begin{verbatim}
443-->computeroots1 ( 10 ) 550-->computeroots1 ( 10 )
444Polynomial for outside contraction : 551Polynomial for outside contraction :
445 552
446 2 3 4 5 6 7 8 9 10 553 2 3 4 5 6 7 8 9 10
447 10 - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x + 20x 554 10 - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x + 20x
448#1/10 |0.5822700+%i*0.7362568|=0.938676 555Roots :
449#2/10 |0.5822700-%i*0.7362568|=0.938676 556Root #1/10 |0.5822700+%i*0.7362568|=0.938676
450#3/10 |-0.5439060+%i*0.7651230|=0.938747 557Root #2/10 |0.5822700-%i*0.7362568|=0.938676
451#4/10 |-0.5439060-%i*0.7651230|=0.938747 558Root #3/10 |-0.5439060+%i*0.7651230|=0.938747
452#5/10 |0.9093766+%i*0.0471756|=0.910599 559Root #4/10 |-0.5439060-%i*0.7651230|=0.938747
453#6/10 |0.9093766-%i*0.0471756|=0.910599 560Root #5/10 |0.9093766+%i*0.0471756|=0.910599
454#7/10 |0.0191306+%i*0.9385387|=0.938734 561Root #6/10 |0.9093766-%i*0.0471756|=0.910599
455#8/10 |0.0191306-%i*0.9385387|=0.938734 562Root #7/10 |0.0191306+%i*0.9385387|=0.938734
456#9/10 |-0.8918713+%i*0.2929516|=0.938752 563Root #8/10 |0.0191306-%i*0.9385387|=0.938734
457#10/10 |-0.8918713-%i*0.2929516|=0.938752 564Root #9/10 |-0.8918713+%i*0.2929516|=0.938752
565Root #10/10 |-0.8918713-%i*0.2929516|=0.938752
458Polynomial for inside contraction : 566Polynomial for inside contraction :
459 567
460 2 3 4 5 6 7 8 9 10 568 2 3 4 5 6 7 8 9 10
461 - 10 - x - x - x - x - x - x - x - x - x + 20x 569 - 10 - x - x - x - x - x - x - x - x - x + 20x
462#1/10 |0.7461586+%i*0.5514088|=0.927795 570Roots :
463#2/10 |0.7461586-%i*0.5514088|=0.927795 571Root #1/10 |0.7461586+%i*0.5514088|=0.927795
464#3/10 |-0.2879931+%i*0.8802612|=0.926175 572Root #2/10 |0.7461586-%i*0.5514088|=0.927795
465#4/10 |-0.2879931-%i*0.8802612|=0.926175 573Root #3/10 |-0.2879931+%i*0.8802612|=0.926175
466#5/10 |-0.9260704|=0.926070 574Root #4/10 |-0.2879931-%i*0.8802612|=0.926175
467#6/10 |0.9933286|=0.993329 575Root #5/10 |-0.9260704|=0.926070
468#7/10 |0.2829249+%i*0.8821821|=0.926440 576Root #6/10 |0.9933286|=0.993329
469#8/10 |0.2829249-%i*0.8821821|=0.926440 577Root #7/10 |0.2829249+%i*0.8821821|=0.926440
470#9/10 |-0.7497195+%i*0.5436596|=0.926091 578Root #8/10 |0.2829249-%i*0.8821821|=0.926440
471#10/10 |-0.7497195-%i*0.5436596|=0.926091 579Root #9/10 |-0.7497195+%i*0.5436596|=0.926091
580Root #10/10 |-0.7497195-%i*0.5436596|=0.926091
472Polynomial for reflection : 581Polynomial for reflection :
473 582
474 2 3 4 5 6 7 8 9 10 583 2 3 4 5 6 7 8 9 10
475 10 - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x + 10x 584 10 - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x + 10x
476#1/10 |0.6172695+%i*0.7867517|=1.000000 585Roots :
477#2/10 |0.6172695-%i*0.7867517|=1.000000 586Root #1/10 |0.6172695+%i*0.7867517|=1.000000
478#3/10 |-0.5801834+%i*0.8144859|=1.000000 587Root #2/10 |0.6172695-%i*0.7867517|=1.000000
479#4/10 |-0.5801834-%i*0.8144859|=1.000000 588Root #3/10 |-0.5801834+%i*0.8144859|=1.000000
480#5/10 |0.9946011+%i*0.1037722|=1.000000 589Root #4/10 |-0.5801834-%i*0.8144859|=1.000000
481#6/10 |0.9946011-%i*0.1037722|=1.000000 590Root #5/10 |0.9946011+%i*0.1037722|=1.000000
482#7/10 |0.0184670+%i*0.9998295|=1.000000 591Root #6/10 |0.9946011-%i*0.1037722|=1.000000
483#8/10 |0.0184670-%i*0.9998295|=1.000000 592Root #7/10 |0.0184670+%i*0.9998295|=1.000000
484#9/10 |-0.9501543+%i*0.3117800|=1.000000 593Root #8/10 |0.0184670-%i*0.9998295|=1.000000
485#10/10 |-0.9501543-%i*0.3117800|=1.000000 594Root #9/10 |-0.9501543+%i*0.3117800|=1.000000
595Root #10/10 |-0.9501543-%i*0.3117800|=1.000000
486\end{verbatim} 596\end{verbatim}
487\end{tiny} 597\end{small}
488 598
489The following Scilab script allows to compute the minimum and 599The following Scilab script allows to compute the minimum and
490the maximum of the modulus of the roots. 600the maximum of the modulus of the roots.
491The "e" option of the "roots" command has been used to force the 601The "e" option of the "roots" command has been used to force the
492use of the eigenvalues of the companion matrix as the computationnal 602use of the eigenvalues of the companion matrix as the computational
493method. The default algorithm, based on the Jenkins-Traub Rpoly 603method. The default algorithm, based on the Jenkins-Traub Rpoly
494method is generating a convergence error and cannot be used 604method is generating a convergence error and cannot be used
495in this case. 605in this case.
496 606
497\lstset{language=Scilab} 607\lstset{language=scilabscript}
498\lstset{numbers=left}
499\lstset{basicstyle=\footnotesize}
500\lstset{keywordstyle=\bfseries}
501\begin{lstlisting} 608\begin{lstlisting}
502function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n ) 609function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n )
503 // Polynomial for outside contraction : 610 // Polynomial for outside contraction :
@@ -537,9 +644,9 @@ function drawfigure1 ( nbmax )
537 end 644 end
538 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] ) 645 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] )
539 f = gcf(); 646 f = gcf();
540 f.children.title.text = "Nelder-Mead caracteristic equation roots"; 647 f.children.title.text = "Nelder-Mead characteristic equation roots";
541 f.children.x_label.text = "Number of variables (n)"; 648 f.children.x_label.text = "Number of variables (n)";
542 f.children.y_label.text = "Roots of the caracteristic equation"; 649 f.children.y_label.text = "Roots of the characteristic equation";
543 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]); 650 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]);
544 f.children.children(1).legend_location="in_lower_right"; 651 f.children.children(1).legend_location="in_lower_right";
545 for i = 1:4 652 for i = 1:4
@@ -557,13 +664,13 @@ The minimum and maximum roots of the inside contraction ("ic" in the table) and
557outside contraction ("oc" in the table) steps are 664outside contraction ("oc" in the table) steps are
558presented in table \ref{table-nm-roots-table}. These 665presented in table \ref{table-nm-roots-table}. These
559roots are presented graphically in figure \ref{fig-nm-roots}. 666roots are presented graphically in figure \ref{fig-nm-roots}.
560One can see that the roots converge toward 1 when $n\rightarrow \infty$. 667We see that the roots start from 0.5 when $n=1$ and
561 668converge rapidly toward 1 when $n\rightarrow \infty$.
562 669
563\begin{figure}[htbp] 670\begin{figure}[htbp]
564\begin{center} 671\begin{center}
565\begin{tiny} 672\begin{tiny}
566\begin{tabular}{|l|l||l|l|l|} 673\begin{tabular}{|l|l|l|l|l|}
567\hline 674\hline
568$n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{ic}$ & $\max_{i=1,n}\mu_i^{ic}$ \\ 675$n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{ic}$ & $\max_{i=1,n}\mu_i^{ic}$ \\
569\hline 676\hline
@@ -623,7 +730,7 @@ $n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{
623\end{tabular} 730\end{tabular}
624\end{tiny} 731\end{tiny}
625\end{center} 732\end{center}
626\caption{Roots of the caracteristic equations of the Nelder-Mead method with standard 733\caption{Roots of the characteristic equations of the Nelder-Mead method with standard
627coefficients. (Some results are not displayed to make the table fit the page).} 734coefficients. (Some results are not displayed to make the table fit the page).}
628\label{table-nm-roots-table} 735\label{table-nm-roots-table}
629\end{figure} 736\end{figure}
@@ -632,60 +739,56 @@ coefficients. (Some results are not displayed to make the table fit the page).}
632\begin{center} 739\begin{center}
633\includegraphics[width=10cm]{neldermead-roots.png} 740\includegraphics[width=10cm]{neldermead-roots.png}
634\end{center} 741\end{center}
635\caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with standard 742\caption{Modulus of the roots of the characteristic equations of the Nelder-Mead method with standard
636coefficients -- R-max-IC is the maximum of the modulus of the root of the Inside Contraction steps} 743coefficients -- R-max-IC is the maximum of the modulus of the root of the Inside Contraction steps}
637\label{fig-nm-roots} 744\label{fig-nm-roots}
638\end{figure} 745\end{figure}
639 746
640\subsection{With variable parameters} 747\subsection{With variable parameters}
641 748
642In this section, we analyse the roots of the caracteristic 749In this section, we analyze the roots of the characteristic
643equation with \emph{variable} inside and outside contraction 750equation with \emph{variable} inside and outside contraction
644coefficients. 751coefficients.
645 752
646\emph{Outside contraction} If the outside contraction step is repeatedly performed 753\emph{Outside contraction} \\
647with variable $\mu_{oc} > 0$, then 754If the outside contraction step is repeatedly performed
648 755with variable $\mu_{oc} \in }0,\mu_r[$, then
649\begin{eqnarray} 756\begin{eqnarray}
650\bv^{(k+n)} &=& \overline{\bold{v}}^{(k)} 757\bv^{(k+n)} &=& \overline{\bold{v}}^{(k)}
651+ \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\ 758+ \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\
652&=& (1 + \mu_{oc} ) \overline{\bold{v}}^{(k)} - \mu_{oc} \bv^{(k)} 759&=& (1 + \mu_{oc} ) \overline{\bold{v}}^{(k)} - \mu_{oc} \bv^{(k)}
653\end{eqnarray} 760\end{eqnarray}
654By plugging the definition of the centroid into the previous equality, one 761By plugging the definition of the centroid into the previous equality, we
655find the recurrence formula 762find the recurrence formula
656
657\begin{eqnarray} 763\begin{eqnarray}
658n \bv^{(k+n)} - (1 + \mu_{oc} ) \bv^{(k+1)} - \ldots - (1 + \mu_{oc} ) \bv^{(k+n-1)} + n\mu_{oc}\bv^{(k)} = 0 764n \bv^{(k+n)} - (1 + \mu_{oc} ) \bv^{(k+1)} - \ldots - (1 + \mu_{oc} ) \bv^{(k+n-1)} + n\mu_{oc}\bv^{(k)} = 0
659\end{eqnarray} 765\end{eqnarray}
660 766
661The associated caracteristic equation is 767The associated characteristic equation is
662
663\begin{eqnarray} 768\begin{eqnarray}
664\label{recurrence-variable} 769\label{recurrence-variable}
665n \mu^n - (1 + \mu_{oc} ) \mu^{n-1} - \ldots - (1 + \mu_{oc} ) \mu + n \mu_{oc} = 0. 770n \mu^n - (1 + \mu_{oc} ) \mu^{n-1} - \ldots - (1 + \mu_{oc} ) \mu + n \mu_{oc} = 0.
666\end{eqnarray} 771\end{eqnarray}
667 772
668\emph{Inside contraction} We suppose that the inside contraction step is repeatedly performed 773\emph{Inside contraction} \\
669with $-1 < \mu_{ic} < 0$. The caracteristic equation is the same as \ref{recurrence-variable}, 774We suppose that the inside contraction step is repeatedly performed
775with $-1 < \mu_{ic} < 0$. The characteristic equation is the same as \ref{recurrence-variable},
670but it is here studied in the range $\mu_{ic}\in]-1, 0[$. 776but it is here studied in the range $\mu_{ic}\in]-1, 0[$.
671 777
672To study the convergence of the method, one simply have 778To study the convergence of the method, we simply have
673to study the roots of equation \ref{recurrence-variable}, where 779to study the roots of equation \ref{recurrence-variable}, where
674the range $]-1,0[$ corresponds to the inside contraction (with $-1/2$ 780the range $]-1,0[$ corresponds to the inside contraction (with $-1/2$
675as the standard value) and where the range $]0,\mu_r[$ corresponds to the outside contraction (with $1/2$ 781as the standard value) and where the range $]0,\mu_r[$ corresponds to the outside contraction (with $1/2$
676as the standard value). 782as the standard value).
677 783
678In the following Scilab script, one computes the minimum and 784In the following Scilab script, we compute the minimum and
679maximum root of the caracteristic equation, with $n$ fixed. 785maximum root of the characteristic equation, with $n$ fixed.
680 786
681\lstset{language=Scilab} 787\lstset{language=scilabscript}
682\lstset{numbers=left}
683\lstset{basicstyle=\footnotesize}
684\lstset{keywordstyle=\bfseries}
685\begin{lstlisting} 788\begin{lstlisting}
686// 789//
687// rootsvariable -- 790// rootsvariable --
688// Compute roots of the caracteristic equation 791// Compute roots of the characteristic equation
689// of Nelder-Mead with variable coefficient mu. 792// of Nelder-Mead with variable coefficient mu.
690// Polynomial for outside/inside contraction : 793// Polynomial for outside/inside contraction :
691// n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0 794// n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0
@@ -715,9 +818,9 @@ function drawfigure_variable ( n , nmumax )
715 plot2d ( mutable , [ rmintable' , rmaxtable' ] ) 818 plot2d ( mutable , [ rmintable' , rmaxtable' ] )
716 f = gcf(); 819 f = gcf();
717 pause 820 pause
718 f.children.title.text = "Nelder-Mead caracteristic equation roots"; 821 f.children.title.text = "Nelder-Mead characteristic equation roots";
719 f.children.x_label.text = "Contraction coefficient"; 822 f.children.x_label.text = "Contraction coefficient";
720 f.children.y_label.text = "Roots of the caracteristic equation"; 823 f.children.y_label.text = "Roots of the characteristic equation";
721 captions(f.children.children.children,["R-max","R-min"]); 824 captions(f.children.children.children,["R-max","R-min"]);
722 f.children.children(1).legend_location="in_lower_right"; 825 f.children.children(1).legend_location="in_lower_right";
723 for i = 1:2 826 for i = 1:2
@@ -731,7 +834,7 @@ endfunction
731\end{lstlisting} 834\end{lstlisting}
732 835
733The figure \ref{fig-nm-roots-variable} presents the minimum 836The figure \ref{fig-nm-roots-variable} presents the minimum
734and maximum modulus of the roots of the caracteristic equation 837and maximum modulus of the roots of the characteristic equation
735with $n=10$. The result is that when $\mu_{oc}$ is close to 0, the 838with $n=10$. The result is that when $\mu_{oc}$ is close to 0, the
736minimum root has a modulus close to 0. The maximum root remains close to 839minimum root has a modulus close to 0. The maximum root remains close to
7371, whatever the value of the contraction coefficient. 8401, whatever the value of the contraction coefficient.
@@ -749,18 +852,34 @@ experiment.
749\begin{center} 852\begin{center}
750\includegraphics[width=10cm]{neldermead-roots-variable.png} 853\includegraphics[width=10cm]{neldermead-roots-variable.png}
751\end{center} 854\end{center}
752\caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with variable 855\caption{Modulus of the roots of the characteristic equations of the Nelder-Mead method with variable
753contraction coefficient and $n=10$ -- R-max is the maximum of the modulus of the root of the 856contraction coefficient and $n=10$ -- R-max is the maximum of the modulus of the root of the
754caracteristic equation} 857characteristic equation}
755\label{fig-nm-roots-variable} 858\label{fig-nm-roots-variable}
756\end{figure} 859\end{figure}
757 860
758
759
760\section{Numerical experiments} 861\section{Numerical experiments}
761 862
762In this section, we present some numerical experiments 863In this section, we present some numerical experiments
763with the Nelder-Mead algorithm. 864with the Nelder-Mead algorithm.
865The two first numerical experiments involve simple quadratic functions.
866These experiments allows to see the difference between
867Spendley's et al. algorithm and the Nelder-Mead algorithm.
868We then present several experiments taken from the bibliography.
869The O'Neill experiments \cite{O'Neill1971AAF} are performed in order
870to check that our algorithm is a correct implementation.
871We then present several numerical experiments where the Nelder-Mead
872does not converge properly.
873We analyze the Mc Kinnon counter example
874from \cite{589109}. We show the behavior of the
875Nelder-Mead simplex method for a family of examples which cause the
876method to converge to a non stationnary point.
877We analyze the counter examples presented by Han in his Phd thesis \cite{Han2000}.
878In these experiments, the Nelder-Mead algorithm degenerates by applying repeatedly
879the inside contraction step.
880We also reproduce numerical experiments extracted from Torczon's Phd Thesis
881\cite{Torczon89multi-directionalsearch}, where Virginia Torczon
882presents the multi-directional direct search algorithm.
764 883
765\subsection{Quadratic function} 884\subsection{Quadratic function}
766 885
@@ -783,7 +902,7 @@ The numerical results are presented in table \ref{fig-nm-numexp1-table}.
783 902
784\begin{figure}[htbp] 903\begin{figure}[htbp]
785\begin{center} 904\begin{center}
786\begin{tiny} 905%\begin{tiny}
787\begin{tabular}{|l|l|} 906\begin{tabular}{|l|l|}
788\hline 907\hline
789Iterations & 65 \\ 908Iterations & 65 \\
@@ -795,7 +914,7 @@ Computed $x^\star$ & $(7.3e-10 , -2.5e-9)$\\
795Computed $f(x^\star)$ & $8.7e-18$\\ 914Computed $f(x^\star)$ & $8.7e-18$\\
796\hline 915\hline
797\end{tabular} 916\end{tabular}
798\end{tiny} 917%\end{tiny}
799\end{center} 918\end{center}
800\caption{Numerical experiment with Nelder-Mead method on the quadratic function 919\caption{Numerical experiment with Nelder-Mead method on the quadratic function
801$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$} 920$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$}
@@ -806,7 +925,7 @@ $f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$}
806The various simplices generated during the iterations are 925The various simplices generated during the iterations are
807presented in figure \ref{fig-nm-numexp1-historysimplex}. 926presented in figure \ref{fig-nm-numexp1-historysimplex}.
808The method use reflections in the early iterations. Then there 927The method use reflections in the early iterations. Then there
809is no possible improvment using reflections and shrinking is necessary. 928is no possible improvement using reflections and shrinking is necessary.
810 929
811\begin{figure} 930\begin{figure}
812\begin{center} 931\begin{center}
@@ -857,7 +976,7 @@ We set the maximum number of function evaluations to 400.
857The initial simplex is computed from the coordinate axis and the unit length. 976The initial simplex is computed from the coordinate axis and the unit length.
858 977
859The numerical results are presented in table \ref{fig-nm-numexp2-table}, 978The numerical results are presented in table \ref{fig-nm-numexp2-table},
860where the experiment is presented for $a=100$. One can check that the 979where the experiment is presented for $a=100$. We can check that the
861number of function evaluation (161 function evaluations) is much lower than the number 980number of function evaluation (161 function evaluations) is much lower than the number
862for the fixed shape Spendley et al. method (400 function evaluations) 981for the fixed shape Spendley et al. method (400 function evaluations)
863and that the function value at optimum is very accurate ($f(x^\star)\approx 1.e-17$ 982and that the function value at optimum is very accurate ($f(x^\star)\approx 1.e-17$
@@ -865,7 +984,7 @@ compared to Spendley's et al. $f(x^\star) \approx 0.08$).
865 984
866\begin{figure}[h] 985\begin{figure}[h]
867\begin{center} 986\begin{center}
868\begin{tiny} 987%\begin{tiny}
869\begin{tabular}{|l|l|l|} 988\begin{tabular}{|l|l|l|}
870\hline 989\hline
871& Nelder-Mead & Spendley et al.\\ 990& Nelder-Mead & Spendley et al.\\
@@ -880,7 +999,7 @@ Computed $x^\star$ & $(2.e-10, -3.e-9)$& $(0.001,0.2)$\\
880Computed $f(x^\star)$ & $1.e-17$ & $0.08$\\ 999Computed $f(x^\star)$ & $1.e-17$ & $0.08$\\
881\hline 1000\hline
882\end{tabular} 1001\end{tabular}
883\end{tiny} 1002%\end{tiny}
884\end{center} 1003\end{center}
885\caption{Numerical experiment with Nelder-Mead method on a badly scaled quadratic function. 1004\caption{Numerical experiment with Nelder-Mead method on a badly scaled quadratic function.
886The variable shape Nelder-Mead algorithm improves the accuracy of the result compared 1005The variable shape Nelder-Mead algorithm improves the accuracy of the result compared
@@ -888,16 +1007,16 @@ to the fixed shaped Spendley et al. method.}
888\label{fig-nm-numexp2-table} 1007\label{fig-nm-numexp2-table}
889\end{figure} 1008\end{figure}
890 1009
891In figure \ref{fig-nm-numexp2-scaling}, we analyse the 1010In figure \ref{fig-nm-numexp2-scaling}, we analyze the
892behaviour of the method with respect to scaling. 1011behavior of the method with respect to scaling.
893We check that the method behave very smoothly, with a very 1012We check that the method behave very smoothly, with a very
894small number of additionnal function evaluations when the 1013small number of additional function evaluations when the
895scaling deteriorates. This shows how much the Nelder-Mead algorithms 1014scaling deteriorates. This shows how much the Nelder-Mead algorithms
896improves over the Spendley et al. method. 1015improves over Spendley's et al. method.
897 1016
898\begin{figure}[htbp] 1017\begin{figure}[htbp]
899\begin{center} 1018\begin{center}
900\begin{tiny} 1019%\begin{tiny}
901\begin{tabular}{|l|l|l|l|} 1020\begin{tabular}{|l|l|l|l|}
902\hline 1021\hline
903$a$ & Function evaluations & Computed $f(x^\star)$ & Computed $x^\star$\\ 1022$a$ & Function evaluations & Computed $f(x^\star)$ & Computed $x^\star$\\
@@ -908,7 +1027,7 @@ $1000.0$ & 165 & $1.0e-17$ & $(-1.e-010 9.e-10)$\\
908$10000.0$ & 167 & $3.0e-17$ & $(5.0e-11,-1.0e-10)$ \\ 1027$10000.0$ & 167 & $3.0e-17$ & $(5.0e-11,-1.0e-10)$ \\
909\hline 1028\hline
910\end{tabular} 1029\end{tabular}
911\end{tiny} 1030%\end{tiny}
912\end{center} 1031\end{center}
913\caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function} 1032\caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function}
914\label{fig-nm-numexp2-scaling} 1033\label{fig-nm-numexp2-scaling}
@@ -937,7 +1056,7 @@ experiment for $n=1,19$.
937During the iterations, no shrink steps are performed. The 1056During the iterations, no shrink steps are performed. The
938algorithm performs reflections, inside and outside contractions. 1057algorithm performs reflections, inside and outside contractions.
939The figure \ref{fig-nm-numexp3-steps} shows the detailed sequence of 1058The figure \ref{fig-nm-numexp3-steps} shows the detailed sequence of
940iterations for $n=10$. One can see that there is no general 1059iterations for $n=10$. We see that there is no general
941pattern for the iterations. One can check, however, that there 1060pattern for the iterations. One can check, however, that there
942are never no more than $n$ consecutive reflection steps, which is 1061are never no more than $n$ consecutive reflection steps, which is
943as expected. After one or more contractions, the reflection 1062as expected. After one or more contractions, the reflection
@@ -947,7 +1066,7 @@ vertices are moved in at most $n$ reflection steps.
947 1066
948\begin{figure}[htbp] 1067\begin{figure}[htbp]
949\begin{center} 1068\begin{center}
950\begin{tiny} 1069%\begin{tiny}
951\begin{verbatim} 1070\begin{verbatim}
952I I I I I I I I I I I I I I I I I I I I R R R R R R R R R R R R R I O 1071I I I I I I I I I I I I I I I I I I I I R R R R R R R R R R R R R I O
953R R R R R R R R R R R R R I R I I R I R O I I I I R I R I I R O I R R 1072R R R R R R R R R R R R R I R I I R I R O I I I I R I R I I R O I R R
@@ -968,7 +1087,7 @@ R I I R I I R R R R R O R R R I R R R R I R I R R I R I I R R I I R R
968I I I I R R R R R R R R R I R R O R R R R R O I I I I R I I R O I I R 1087I I I I R R R R R R R R R I R R O R R R R R O I I I I R I I R O I I R
969R R R R I I I R R 1088R R R R I I I R R
970\end{verbatim} 1089\end{verbatim}
971\end{tiny} 1090%\end{tiny}
972\end{center} 1091\end{center}
973\caption{Numerical experiment with Nelder-Mead method on a generalized 1092\caption{Numerical experiment with Nelder-Mead method on a generalized
974quadratic function - steps of the algorithm : I = inside contraction, O = outside contraction, 1093quadratic function - steps of the algorithm : I = inside contraction, O = outside contraction,
@@ -981,12 +1100,12 @@ the kind of steps performed during the iterations for $n=1,19$.
981It appears that the number of shrink steps and expansion steps is zero, as expected. 1100It appears that the number of shrink steps and expansion steps is zero, as expected.
982More interesting is that the number of reflection is 1101More interesting is that the number of reflection is
983larger than the number of inside contraction when $n$ 1102larger than the number of inside contraction when $n$
984is large. The number of outside contraction is allways 1103is large. The number of outside contraction is always
985the smallest in this case. 1104the smallest in this case.
986 1105
987\begin{figure}[htbp] 1106\begin{figure}[htbp]
988\begin{center} 1107\begin{center}
989\begin{tiny} 1108%\begin{tiny}
990\begin{tabular}{|l|l|l|l|l|l|} 1109\begin{tabular}{|l|l|l|l|l|l|}
991\hline 1110\hline
992$n$ & \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\ 1111$n$ & \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\
@@ -1013,21 +1132,21 @@ $n$ & \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\
101319 & 767 & 0 & 480 & 48 & 0\\ 113219 & 767 & 0 & 480 & 48 & 0\\
1014\hline 1133\hline
1015\end{tabular} 1134\end{tabular}
1016\end{tiny} 1135%\end{tiny}
1017\end{center} 1136\end{center}
1018\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function -- number 1137\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function -- number
1019and kinds of steps performed} 1138and kinds of steps performed}
1020\label{fig-nm-numexp3-nbsteps} 1139\label{fig-nm-numexp3-nbsteps}
1021\end{figure} 1140\end{figure}
1022 1141
1023One can check that the number of function evaluations 1142We check that the number of function evaluations
1024increases approximately linearily with the dimension of the problem in 1143increases approximately linearly with the dimension of the problem in
1025figure \ref{fig-nm-numexp3-fvn}. A rough rule of thumb is that, for $n=1,19$, 1144figure \ref{fig-nm-numexp3-fvn}. A rough rule of thumb is that, for $n=1,19$,
1026the number of function evaluations is equal to $100n$. 1145the number of function evaluations is equal to $100n$.
1027 1146
1028\begin{figure}[htbp] 1147\begin{figure}[htbp]
1029\begin{center} 1148\begin{center}
1030\begin{tiny} 1149%\begin{tiny}
1031\begin{tabular}{|l|l|l|l|} 1150\begin{tabular}{|l|l|l|l|}
1032\hline 1151\hline
1033$n$ & Function evaluations & Iterations & $\rho(S_0,n)$\\ 1152$n$ & Function evaluations & Iterations & $\rho(S_0,n)$\\
@@ -1053,7 +1172,7 @@ $n$ & Function evaluations & Iterations & $\rho(S_0,n)$\\
105319 & 1843 & 1296 & 0.98584701106083183\\ 117219 & 1843 & 1296 & 0.98584701106083183\\
1054\hline 1173\hline
1055\end{tabular} 1174\end{tabular}
1056\end{tiny} 1175%\end{tiny}
1057\end{center} 1176\end{center}
1058\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function} 1177\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function}
1059\label{fig-nm-numexp3-dimension} 1178\label{fig-nm-numexp3-dimension}
@@ -1153,11 +1272,11 @@ The table \ref{fig-nm-oneill-table} presents the results which were
1153computed by O'Neill compared with our software. 1272computed by O'Neill compared with our software.
1154For most experiments, the results are very close in terms of 1273For most experiments, the results are very close in terms of
1155number of function evaluations. 1274number of function evaluations.
1156The problem \#4 exhibits a completely different behaviour than the 1275The problem \#4 exhibits a completely different behavior than the
1157results presented by O'Neill. For us, the maximum number of function evaluations 1276results presented by O'Neill. For us, the maximum number of function evaluations
1158is reached (i.e. 1000 function evaluations), whereas for O'Neill, the algorithm 1277is reached (i.e. 1000 function evaluations), whereas for O'Neill, the algorithm
1159is restarted and gives the result with 474 function evaluations. 1278is restarted and gives the result with 474 function evaluations.
1160We did not find any explanation for this behaviour. A possible cause of 1279We did not find any explanation for this behavior. A possible cause of
1161difference may be the floating point system which are different and may 1280difference may be the floating point system which are different and may
1162generate different simplices in the algorithms. 1281generate different simplices in the algorithms.
1163Although the CPU times cannot be 1282Although the CPU times cannot be
@@ -1169,7 +1288,7 @@ and the problems 3 and 4 were solved in 22.25 seconds.
1169 1288
1170\begin{figure}[htbp] 1289\begin{figure}[htbp]
1171\begin{center} 1290\begin{center}
1172\begin{tiny} 1291%\begin{tiny}
1173\begin{tabular}{|l|l|l|l|l|l|l|} 1292\begin{tabular}{|l|l|l|l|l|l|l|}
1174\hline 1293\hline
1175Author & Problem & Function & No. of Restarts & Function Value & Iterations & CPU\\ 1294Author & Problem & Function & No. of Restarts & Function Value & Iterations & CPU\\
@@ -1188,71 +1307,72 @@ O'Neill & 4 & 474 & 1 & 3.80 e-7 & ? & ? \\
1188Baudin & 4 & 999 & 0 & 5.91 e-9 & 676 & - \\ 1307Baudin & 4 & 999 & 0 & 5.91 e-9 & 676 & - \\
1189\hline 1308\hline
1190\end{tabular} 1309\end{tabular}
1191\end{tiny} 1310%\end{tiny}
1192\end{center} 1311\end{center}
1193\caption{Numerical experiment with Nelder-Mead method on O'Neill test cases - O'Neill results and our results} 1312\caption{Numerical experiment with Nelder-Mead method on O'Neill test cases - O'Neill results and our results}
1194\label{fig-nm-oneill-table} 1313\label{fig-nm-oneill-table}
1195\end{figure} 1314\end{figure}
1196 1315
1197\subsection{Convergence to a non stationnary point} 1316\subsection{Convergence to a non stationnary point}
1317\label{section-mcKinnon}
1198 1318
1199In this section, we analyse the Mc Kinnon counter example 1319In this section, we analyze the Mc Kinnon counter example
1200from \cite{589109}. We show the behavior of the 1320from \cite{589109}. We show the behavior of the
1201Nelder-Mead simplex method for a family of examples which cause the 1321Nelder-Mead simplex method for a family of examples which cause the
1202method to converge to a nonstationnary point. 1322method to converge to a non stationnary point.
1203 1323
1204Consider a simplex in two dimensions with vertices at 0 (i.e. the origin), 1324Consider a simplex in two dimensions with vertices at 0 (i.e. the origin),
1205$v^{(n+1)}$ and $v^{(n)}$. Assume that 1325$\bv^{(n+1)}$ and $\bv^{(n)}$. Assume that
1206 1326
1207\begin{eqnarray} 1327\begin{eqnarray}
1208\label{mckinnon-sortedfv} 1328\label{mckinnon-sortedfv}
1209f(0) < f(v^{(n+1)}) < f(v^{(n)}). 1329f(0) < f(\bv^{(n+1)}) < f(\bv^{(n)}).
1210\end{eqnarray} 1330\end{eqnarray}
1211 1331
1212The centroid of the simplex is $\overline{v} = v^{(n+1)}/2$, the midpoint 1332The centroid of the simplex is $\overline{\bv} = \bv^{(n+1)}/2$, the midpoint
1213of the line joining the best and second vertex. The refected 1333of the line joining the best and second vertex. The reflected
1214point is then computed as 1334point is then computed as
1215 1335
1216\begin{eqnarray} 1336\begin{eqnarray}
1217\label{mckinnon-reflection} 1337\label{mckinnon-reflection}
1218r^{(n)} = \overline{v} + \rho ( \overline{v} - v^{(n)} ) = v^{(n+1)} - v^{(n)} 1338\br^{(n)} = \overline{\bv} + \rho ( \overline{\bv} - \bv^{(n)} )
1339= \bv^{(n+1)} - \bv^{(n)}
1219\end{eqnarray} 1340\end{eqnarray}
1220 1341
1221Assume that the reflection point $r^{(n)}$ is rejected, i.e. that 1342Assume that the reflection point $\br^{(n)}$ is rejected, i.e. that
1222$f(v^{(n)}) < f(r^{(n)})$. In this case, the inside contraction 1343$f(\bv^{(n)}) < f(\br^{(n)})$. In this case, the inside contraction
1223step is taken and the point $v^{(n+2)}$ is computed using the 1344step is taken and the point $\bv^{(n+2)}$ is computed using the
1224reflection factor $-\gamma = -1/2$ so that 1345reflection factor $-\gamma = -1/2$ so that
1225 1346
1226\begin{eqnarray} 1347\begin{eqnarray}
1227\label{mckinnon-insidecontraction} 1348\label{mckinnon-insidecontraction}
1228v^{(n+2)} = \overline{v} - \gamma ( \overline{v} - v^{(n)} ) = \frac{1}{4} v^{(n+1)} - \frac{1}{2} v^{(n)} 1349\bv^{(n+2)} = \overline{\bv} -
1350\gamma ( \overline{\bv} - \bv^{(n)} )
1351= \frac{1}{4} \bv^{(n+1)} - \frac{1}{2} \bv^{(n)}
1229\end{eqnarray} 1352\end{eqnarray}
1230 1353
1231Assume then that the inside contraction point is accepted, i.e. $f(v^{(n+2)}) < f(v^{(n+1)})$. 1354Assume then that the inside contraction point is accepted, i.e. $f(\bv^{(n+2)}) < f(\bv^{(n+1)})$.
1232If this sequence of steps repeats, the simplices are subject to the 1355If this sequence of steps repeats, the simplices are subject to the
1233following linear reccurence formula 1356following linear recurrence formula
1234 1357
1235\begin{eqnarray} 1358\begin{eqnarray}
1236\label{mckinnon-reccurence} 1359\label{mckinnon-reccurence}
12374 v^{(n+2)} - v^{(n+1)} + 2 v^{(n)} = 0 13604 \bv^{(n+2)} - \bv^{(n+1)} + 2 \bv^{(n)} = 0
1238\end{eqnarray} 1361\end{eqnarray}
1239 1362
1240Their general solutions are of the form 1363Their general solutions are of the form
1241 1364
1242\begin{eqnarray} 1365\begin{eqnarray}
1243v^{(n)} = \lambda_1^k a_1 + \lambda_2^k a_2 1366\bv^{(n)} = \lambda_1^k a_1 + \lambda_2^k a_2
1244\end{eqnarray} 1367\end{eqnarray}
1245where ${\lambda_i}_{i=1,2}$ are the roots of the characteristic equation and 1368where ${\lambda_i}_{i=1,2}$ are the roots of the characteristic equation and
1246${a_i}_{i=1,2} \in \RR^n$. 1369${a_i}_{i=1,2} \in \RR^n$.
1247The caracteristic equation is 1370The characteristic equation is
1248
1249\begin{eqnarray} 1371\begin{eqnarray}
1250\label{mckinnon-caracequation} 1372\label{mckinnon-caracequation}
12514 \lambda^2 - \lambda + 2 \lambda = 0 13734 \lambda^2 - \lambda + 2 \lambda = 0
1252\end{eqnarray} 1374\end{eqnarray}
1253
1254and has the roots 1375and has the roots
1255
1256\begin{eqnarray} 1376\begin{eqnarray}
1257\label{mckinnon-roots} 1377\label{mckinnon-roots}
1258\lambda_1 = \frac{1 + \sqrt{33}}{8}\approx 0.84307, 1378\lambda_1 = \frac{1 + \sqrt{33}}{8}\approx 0.84307,
@@ -1260,25 +1380,23 @@ and has the roots
1260\end{eqnarray} 1380\end{eqnarray}
1261 1381
1262After Mc Kinnon has presented the computation of the roots of the 1382After Mc Kinnon has presented the computation of the roots of the
1263caracteristic equation, he presents a special initial simplex 1383characteristic equation, he presents a special initial simplex
1264for which the simplices degenerates because of repeated failure by inside 1384for which the simplices degenerates because of repeated failure by inside
1265contraction (RFIC in his article). Consider the initial simplex with 1385contraction (RFIC in his article). Consider the initial simplex with
1266vertices $v^{(0)} = (1,1)$ and $v^{(1)} = (\lambda_1,\lambda_2)$ and 1386vertices $\bv^{(0)} = (1,1)$ and $\bv^{(1)} = (\lambda_1,\lambda_2)$ and
1267$0$. If follows that the particular solution for these initial 1387$0$. If follows that the particular solution for these initial
1268conditions is $v^{(n)} = (\lambda_1^n,\lambda_2^n)$. 1388conditions is $\bv^{(n)} = (\lambda_1^n,\lambda_2^n)$.
1269
1270Consider the function $f(x,y)$ given by
1271 1389
1390Consider the function $f(x_1,x_2)$ given by
1272\begin{eqnarray} 1391\begin{eqnarray}
1273\label{mckinnon-function} 1392\label{mckinnon-function}
1274f(x,y) &=& \theta \phi |x|^\tau + y + y^2, \qquad x\leq 0,\\ 1393f(x_1,x_2) &=& \theta \phi |x_1|^\tau + x_2 + x_2^2, \qquad x_1\leq 0,\\
1275&=&\theta x^\tau + y + y^2, \qquad x\geq 0. 1394&=&\theta x_1^\tau + x_2 + x_2^2, \qquad x_1\geq 0.
1276\end{eqnarray} 1395\end{eqnarray}
1277
1278where $\theta$ and $\phi$ are positive constants. Note that $(0,-1)$ 1396where $\theta$ and $\phi$ are positive constants. Note that $(0,-1)$
1279is a descent direction from the origin $(0,0)$ and that f is stricly convex 1397is a descent direction from the origin $(0,0)$ and that f is stricly convex
1280provided $\tau>1$. $f$ has continuous first derivatives if $\tau>1$, continuous second 1398provided $\tau>1$. $f$ has continuous first derivatives if $\tau>1$, continuous second
1281derivatives if $\tau>2$ and continous third derivatives if $\tau>3$. 1399derivatives if $\tau>2$ and continuous third derivatives if $\tau>3$.
1282 1400
1283Mc Kinnon computed the conditions on $\theta,\phi$ and $\tau$ 1401Mc Kinnon computed the conditions on $\theta,\phi$ and $\tau$
1284so that the function values are ordered as expected, i.e. so that the 1402so that the function values are ordered as expected, i.e. so that the
@@ -1290,16 +1408,17 @@ for $\tau=3$, $\theta=6$ and $\phi = 400$.
1290 1408
1291We consider here the more regular case $\tau=3$, $\theta=6$ 1409We consider here the more regular case $\tau=3$, $\theta=6$
1292and $\phi = 400$, i.e. the function is defined by 1410and $\phi = 400$, i.e. the function is defined by
1293
1294\begin{eqnarray} 1411\begin{eqnarray}
1295\label{mckinnon-function3} 1412\label{mckinnon-function3}
1296f(x,y) &=& - 2400 x^3 + y + y^2, \qquad x\leq 0, \\ 1413f(x_1,x_2) &=& - 2400 x_1^3 + x_2 + x_2^2, \qquad x_1\leq 0, \\
1297&=& 6 x^3 + y + y^2, \qquad x\geq 0. 1414&=& 6 x_1^3 + x_2 + x_2^2, \qquad x_1\geq 0.
1298\end{eqnarray} 1415\end{eqnarray}
1299 1416
1300The figure \ref{fig-nm-numexp-mckinnon} shows the contour plot of this function and the first 1417The figure \ref{fig-nm-numexp-mckinnon} shows the contour plot of this function and the first
1301steps of the Nelder-Mead method. 1418steps of the Nelder-Mead method.
1302 1419The global minimum is located at $(0,-1/2)$.
1420Notice that the simplex degenerates to the
1421point $(0,0)$, which is a non stationnary point.
1303 1422
1304\begin{figure} 1423\begin{figure}
1305\begin{center} 1424\begin{center}
@@ -1310,6 +1429,23 @@ a non stationnary point}
1310\label{fig-nm-numexp-mckinnon} 1429\label{fig-nm-numexp-mckinnon}
1311\end{figure} 1430\end{figure}
1312 1431
1432The figure \ref{fig-nm-numexp-mckinnon-detail} presents the first steps
1433of the algorithm in this numerical experiment. Because of the
1434particular shape of the contours of the function, the reflected
1435point is always worse that the worst vertex $\bx_{n+1}$. This
1436leads to the inside contraction step. The vertices constructed
1437by Mc Kinnon are so that the situation loops without end.
1438
1439\begin{figure}
1440\begin{center}
1441\includegraphics[width=10cm]{mcKinnon-insidecontraction.pdf}
1442\end{center}
1443\caption{Nelder-Mead numerical experiment -- Detail of the first steps.
1444The simplex converges to a non stationnary point, after repeated
1445inside contractions.}
1446\label{fig-nm-numexp-mckinnon-detail}
1447\end{figure}
1448
1313\subsection{Han counter examples} 1449\subsection{Han counter examples}
1314 1450
1315In his Phd thesis \cite{Han2000}, Han presents two counter examples 1451In his Phd thesis \cite{Han2000}, Han presents two counter examples
@@ -1319,15 +1455,14 @@ the inside contraction step.
1319\subsubsection{First counter example} 1455\subsubsection{First counter example}
1320 1456
1321The first counter example is based on the function 1457The first counter example is based on the function
1322
1323\begin{eqnarray} 1458\begin{eqnarray}
1324\label{han-function1} 1459\label{han-function1}
1325f(x,y) &=& x^2 + y ( y + 2 ) ( y - 0.5 ) ( y - 2 ) 1460f(x_1,x_2) &=& x_1^2 + x_2 ( x_2 + 2 ) ( x_2 - 0.5 ) ( x_2 - 2 )
1326\end{eqnarray} 1461\end{eqnarray}
1327 1462
1328This function is nonconvex, bounded below and has bounded level 1463This function is nonconvex, bounded below and has bounded level
1329sets. The initial simplex is chosen as $S_0 = [(0.,-1),(0,1),(1,0)]$. 1464sets. The initial simplex is chosen as $S_0 = [(0.,-1),(0,1),(1,0)]$.
1330Han prooves that the Nelder-Mead algorithm generates a sequence of simplices 1465Han proves that the Nelder-Mead algorithm generates a sequence of simplices
1331$S_k = [(0.,-1),(0,1),(\frac{1}{2^k},0)]$. 1466$S_k = [(0.,-1),(0,1),(\frac{1}{2^k},0)]$.
1332 1467
1333The figure \ref{fig-nm-numexp-han1} presents the isovalues and the 1468The figure \ref{fig-nm-numexp-han1} presents the isovalues and the
@@ -1347,24 +1482,32 @@ a non stationnary point}
1347\subsubsection{Second counter example} 1482\subsubsection{Second counter example}
1348 1483
1349The second counter example is based on the function 1484The second counter example is based on the function
1350
1351\begin{eqnarray} 1485\begin{eqnarray}
1352\label{han-function2} 1486\label{han-function2}
1353f(x,y) &=& x^2 + \rho(y) 1487f(x_1,x_2) &=& x_1^2 + \rho(x_2)
1354\end{eqnarray} 1488\end{eqnarray}
1355where $\rho$ is a continuous convex function with bounded level 1489where $\rho$ is a continuous convex function with bounded level
1356sets which satisfies 1490sets defined by
1357\begin{eqnarray} 1491\begin{eqnarray}
1358\label{han-function2-rho} 1492\label{han-function2-rho}
1359\rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\ 1493\left\{
1360& \geq & 0, \qquad \textrm{if} \qquad |y|> 1. 1494\begin{array}{ll}
1495\rho(x_2) =0, &\qquad \textrm{if} \qquad |x_2|\leq 1, \\
1496\rho(x_2)\geq 0, &\qquad \textrm{if} \qquad |x_2|> 1.
1497\end{array}
1498\right.
1361\end{eqnarray} 1499\end{eqnarray}
1362The example given by Han for such a $\rho$ function is 1500The example given by Han for such a $\rho$ function is
1363\begin{eqnarray} 1501\begin{eqnarray}
1364\label{han-function2-rho2} 1502\label{han-function2-rho2}
1365\rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\ 1503\rho(x_2) =
1366& = & y - 1, \qquad \textrm{if} \qquad y> 1, \\ 1504\left\{
1367& = & -y - 1, \qquad \textrm{if} \qquad y < -1. 1505\begin{array}{ll}
15060, &\qquad \textrm{if} \qquad |x_2|\leq 1, \\
1507x_2 - 1, &\qquad \textrm{if} \qquad x_2> 1, \\
1508-x_2 - 1, &\qquad \textrm{if} \qquad x_2 < -1.
1509\end{array}
1510\right.
1368\end{eqnarray} 1511\end{eqnarray}
1369 1512
1370The initial simplex is chosen as $S_0 = [(0.,1/2),(0,-1/2),(1,0)]$. 1513The initial simplex is chosen as $S_0 = [(0.,1/2),(0,-1/2),(1,0)]$.
@@ -1391,11 +1534,11 @@ into a degenerate simplex, by applying repeated inside contractions.
1391\subsection{Torczon's numerical experiments} 1534\subsection{Torczon's numerical experiments}
1392 1535
1393In her Phd Thesis \cite{Torczon89multi-directionalsearch}, Virginia Torczon 1536In her Phd Thesis \cite{Torczon89multi-directionalsearch}, Virginia Torczon
1394presents the multi-directionnal direct search algorithm. In order to analyse the 1537presents the multi-directional direct search algorithm. In order to analyze the
1395performances of her new algorithm, she presents some interesting numerical 1538performances of her new algorithm, she presents some interesting numerical
1396experiments with the Nelder-Mead algorithm. 1539experiments with the Nelder-Mead algorithm.
1397These numerical experiments are based on the collection of test problems \cite{355943}, 1540These numerical experiments are based on the collection of test problems \cite{355943},
1398published in the ACM by Moré, Garbow and Hillstrom in 1981. 1541published in the ACM by Mor\'e, Garbow and Hillstrom in 1981.
1399These test problems are associated with varying number of variables. 1542These test problems are associated with varying number of variables.
1400In her Phd, Torczon presents numerical experiments with $n$ from 8 1543In her Phd, Torczon presents numerical experiments with $n$ from 8
1401to 40. 1544to 40.
@@ -1403,16 +1546,15 @@ The stopping rule is based on the relative size of the simplex.
1403The angle between the descent direction (given by the worst point and the centroid), and the 1546The angle between the descent direction (given by the worst point and the centroid), and the
1404gradient of the function is computed when the algorithm is stopped. 1547gradient of the function is computed when the algorithm is stopped.
1405Torczon shows that, when the tolerance on the relative simplex size is decreased, the 1548Torczon shows that, when the tolerance on the relative simplex size is decreased, the
1406angle converges toward 90°. This fact is observed even for moderate 1549angle converges toward 90 \degre. This fact is observed even for moderate
1407number of dimensions. 1550number of dimensions.
1408 1551
1409In this section, we try to reproduce Torczon numerical experiments. 1552In this section, we try to reproduce Torczon numerical experiments.
1410 1553
1411All experiments are associated with the following sum of squares cost function 1554All experiments are associated with the following sum of squares cost function
1412
1413\begin{eqnarray} 1555\begin{eqnarray}
1414\label{torzcon-sumofsquares} 1556\label{torzcon-sumofsquares}
1415f(x) &=& \sum_{i=1,m} f_i(x)^2, 1557f(\bx) &=& \sum_{i=1,m} f_i(\bx)^2,
1416\end{eqnarray} 1558\end{eqnarray}
1417where $m\geq 1$ is the number of functions $f_i$ in the problem. 1559where $m\geq 1$ is the number of functions $f_i$ in the problem.
1418 1560
@@ -1421,9 +1563,9 @@ simplex and is the following
1421 1563
1422\begin{eqnarray} 1564\begin{eqnarray}
1423\label{torzcon-stopping} 1565\label{torzcon-stopping}
1424\frac{1}{\Delta} \max_{i=1,n} \|v_i^k - v_0^k\| \leq \epsilon, 1566\frac{1}{\Delta} \max_{i=2,n+1} \|\bv_i - \bv_1\| \leq \epsilon,
1425\end{eqnarray} 1567\end{eqnarray}
1426where $\Delta = \max( 1 , \|v_0^k\| )$. Decreasing the value of 1568where $\Delta = \max( 1 , \|\bv_1\| )$. Decreasing the value of
1427$\epsilon$ allows to get smaller simplex sizes. 1569$\epsilon$ allows to get smaller simplex sizes.
1428 1570
1429\subsubsection{Penalty \#1} 1571\subsubsection{Penalty \#1}
@@ -1431,21 +1573,22 @@ The first test function is the \emph{Penalty \#1} function :
1431 1573
1432\begin{eqnarray} 1574\begin{eqnarray}
1433\label{torzcon-sumofsquares-case1} 1575\label{torzcon-sumofsquares-case1}
1434f_i(x) &=& \sqrt{1.e-5}(x_i - 1), \qquad i=1,n\\ 1576f_i(\bx) &=& \sqrt{1.e-5}(x_i - 1), \qquad i=1,n\\
1435f_{n+1} & = & -\frac{1}{4} + \sum_{j=1,n} x_j^2. 1577f_{n+1} & = & -\frac{1}{4} + \sum_{j=1,n} x_j^2.
1436\end{eqnarray} 1578\end{eqnarray}
1437 1579
1438The initial guess is given by $x_0 = (x_{0,j})_{j=1,n}$ and 1580The initial guess is given by $\bx_0 = ((\bx_0)_1 , (\bx_0)_2, \ldots , (\bx_0)_n)^T$ and
1439$x_{0,j} = j$ for $j=1,n$. 1581$(\bx_0)_j = j$ for $j=1,n$.
1440 1582
1441The problem given by 1583The problem given by
1442Moré, Garbow and Hillstrom in \cite{355943} is associated with 1584Mor\'e, Garbow and Hillstrom in \cite{355943} is associated with
1443the size $n=4$. The value of the cost function at the initial guess 1585the size $n=4$. The value of the cost function at the initial guess
1444$x_0 = (1,2,3,4)$ is $f(x_0) = 885.063$. The value of the function 1586$\bx_0 = (1,2,3,4)^T$ is $f(\bx_0) = 885.063$. The value of the function
1445at the optimum is given in \cite{355943} as $f(x^\star) = 2.24997d-5$. 1587at the optimum is given in \cite{355943} as $f(\bx^\star) = 2.24997d-5$.
1588% TODO : what is the optimum ?
1446 1589
1447Torzcon shows an experiment with the Penalty \#1 test case and $n=8$. 1590Torzcon shows an experiment with the Penalty \#1 test case and $n=8$.
1448For this particular case, the initial function value is $f(x_0) = 4.151406e4$. 1591For this particular case, the initial function value is $f(\bx_0) = 4.151406.10^4$.
1449The figure \ref{fig-nm-torczon-table} presents the results of these 1592The figure \ref{fig-nm-torczon-table} presents the results of these
1450experiments. The number of function evaluations is not the same 1593experiments. The number of function evaluations is not the same
1451so that we can conclude that the algorithm may be different 1594so that we can conclude that the algorithm may be different
@@ -1454,10 +1597,10 @@ explain why the number of function evaluations is so different.
1454 1597
1455\begin{figure}[htbp] 1598\begin{figure}[htbp]
1456\begin{center} 1599\begin{center}
1457\begin{tiny} 1600%\begin{tiny}
1458\begin{tabular}{|l|l|l|l|l|} 1601\begin{tabular}{|l|l|l|l|l|}
1459\hline 1602\hline
1460Author & Step & $f(v_0^star)$ & Function & Angle ($,^{\circ}$)\\ 1603Author & Step & $f(\bv_1^\star)$ & Function & Angle (\degre)\\
1461& Tolerance & & Evaluations & \\ 1604& Tolerance & & Evaluations & \\
1462\hline 1605\hline
1463Torzcon & 1.e-1 & 7.0355e-5 & 1605 & 89.396677792198 \\ 1606Torzcon & 1.e-1 & 7.0355e-5 & 1605 & 89.396677792198 \\
@@ -1476,7 +1619,7 @@ Torzcon & 1.e-5 & 6.2912e-5 & 3750 & 89.999931862232 \\
1476Baudin & 1.e-5 & 7.427212e-5 & 4626 & 89.999990 \\ 1619Baudin & 1.e-5 & 7.427212e-5 & 4626 & 89.999990 \\
1477\hline 1620\hline
1478\end{tabular} 1621\end{tabular}
1479\end{tiny} 1622%\end{tiny}
1480\end{center} 1623\end{center}
1481\caption{Numerical experiment with Nelder-Mead method on Torczon test cases - 1624\caption{Numerical experiment with Nelder-Mead method on Torczon test cases -
1482Torczon results and our results} 1625Torczon results and our results}
@@ -1484,16 +1627,16 @@ Torczon results and our results}
1484\end{figure} 1627\end{figure}
1485 1628
1486The figure \ref{fig-nm-numexp-torczon1} presents the 1629The figure \ref{fig-nm-numexp-torczon1} presents the
1487angle between the gradient of the function $-g_k$ and the search 1630angle between the gradient of the function $-\bg_k$ and the search
1488direction $x_c - x_h$, where $x_c$ is the centroid of the best 1631direction $\bx_c - \bx_h$, where $\bx_c$ is the centroid of the best
1489points and $x_h$ is the worst (or high) vertex. 1632vertices and $\bx_h$ is the worst (or high) vertex.
1490 1633
1491\begin{figure} 1634\begin{figure}
1492\begin{center} 1635\begin{center}
1493\includegraphics[width=10cm]{torczon_test1_angle.png} 1636\includegraphics[width=10cm]{torczon_test1_angle.png}
1494\end{center} 1637\end{center}
1495\caption{Nelder-Mead numerical experiment -- Penalty \#1 function -- 1638\caption{Nelder-Mead numerical experiment -- Penalty \#1 function --
1496One can see that the angle between the gradient and the search direction 1639We see that the angle between the gradient and the search direction
1497is very close to $90^{\circ}$, especially for large number of iterations.} 1640is very close to $90^{\circ}$, especially for large number of iterations.}
1498\label{fig-nm-numexp-torczon1} 1641\label{fig-nm-numexp-torczon1}
1499\end{figure} 1642\end{figure}
@@ -1508,9 +1651,8 @@ The main advantage of the Nelder-Mead algorithm over Spendley et al.
1508algorithm is that the shape of the simplex is dynamically updated. 1651algorithm is that the shape of the simplex is dynamically updated.
1509That allows to get a reasonably fast convergence rate on badly scaled 1652That allows to get a reasonably fast convergence rate on badly scaled
1510quadratics, or more generally when the cost function is made 1653quadratics, or more generally when the cost function is made
1511of a sharp valley. Nevertheless, the behaviour of the algorithm when the 1654of a sharp valley. Nevertheless, the behavior of the algorithm when the
1512dimension of the problem increases is disappointing : the more there are 1655dimension of the problem increases is disappointing : the more there are
1513variables, the more the algorithm is slow. In general, it is expected 1656variables, the more the algorithm is slow. In general, it is expected
1514that the number of function evaluations is roughly equal to $100n$. 1657that the number of function evaluations is roughly equal to $100n$.
1515 1658
1516
diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex
index 06224dd..62a9df1 100644
--- a/scilab_doc/neldermead/method-spendley.tex
+++ b/scilab_doc/neldermead/method-spendley.tex
@@ -6,10 +6,10 @@ unconstrained optimization.
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 in the behaviour 9numerical experiments which allow to get some insight in the behavior
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 behavior of the algorithm
13when the number of variables increases. 13when the number of variables increases.
14 14
15\section{Introduction} 15\section{Introduction}
@@ -32,10 +32,10 @@ following unconstrained optimization problem
32where $\bx\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 35This algorithms is based on the iterative update of
36a \emph{simplex} made of $n+1$ points $S=\{\bx_i\}_{i=1,n+1}$. Each point 36a \emph{simplex} made of $n+1$ points $S=\{\bv_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)$ for $i=1,n+1$. 38a function value $f_i=f(\bv_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
@@ -45,32 +45,32 @@ has index $n+1$
45f_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}.
46\end{eqnarray} 46\end{eqnarray}
47 47
48The $\bx_1$ vertex (resp. the $\bx_{n+1}$ vertex) is called the \emph{best} 48The $\bv_1$ vertex (resp. the $\bv_{n+1}$ vertex) is called the \emph{best}
49vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest) 49vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest)
50function value. As we are going to see, the \emph{next-to-worst} vertex $\bx_n$ has a 50function value. As we are going to see, the \emph{next-to-worst} vertex $\bv_n$ has a
51special role in this algorithm. 51special role in this algorithm.
52 52
53The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices 53The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices
54where the vertex $\bx_j$ has been 54where the vertex $\bv_j$ has been
55excluded. This centroid is 55excluded. This centroid is
56\begin{eqnarray} 56\begin{eqnarray}
57\label{centroid-generalized} 57\label{centroid-generalized}
58\overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bx_i. 58\overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i.
59\end{eqnarray} 59\end{eqnarray}
60The algorithm makes use 60The algorithm makes use
61of one coefficient $\rho>0$, called the reflection factor. The standard 61of one coefficient $\rho>0$, called the reflection factor. The standard
62value of this coefficient is $\rho=1$. 62value of this coefficient is $\rho=1$.
63The algorithm attemps to replace some vertex 63The algorithm attempts to replace some vertex
64$\bx_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bx_j$ 64$\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$
65to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by 65to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by
66\begin{eqnarray} 66\begin{eqnarray}
67\label{interpolate-generalized} 67\label{interpolate-generalized}
68\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bx_j. 68\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j.
69\end{eqnarray} 69\end{eqnarray}
70 70
71\subsection{Algorithm} 71\subsection{Algorithm}
72 72
73In this section, we analyse Spendley's et al algorithm, which 73In this section, we analyze Spendley's et al algorithm, which
74is presented in figure \ref{algo-spendley}. 74is presented in figure \ref{algo-spendley}.
75 75
76\begin{figure}[htbp] 76\begin{figure}[htbp]
@@ -91,51 +91,51 @@ is presented in figure \ref{algo-spendley}.
91 \IF {$f_r^\prime<f_{n+1}$} 91 \IF {$f_r^\prime<f_{n+1}$}
92 \STATE Accept $\bx_r^\prime$ 92 \STATE Accept $\bx_r^\prime$
93 \ELSE 93 \ELSE
94 \STATE Compute the points $\bx_i=\bx_1 + \sigma (\bx_i - \bx_1)$, $i=2,n+1$ \COMMENT{Shrink} 94 \STATE Compute the vertices $\bv_i=\bv_1 + \sigma (\bv_i - \bv_1)$ for $i=2,n+1$ \COMMENT{Shrink}
95 \STATE Compute $f_i = f(\bx_i), i=2,n+1$ 95 \STATE Compute $f_i = f(\bv_i)$ for $i=2,n+1$
96 \ENDIF 96 \ENDIF
97 \ENDIF 97 \ENDIF
98 \STATE Sort the vertices of $S$ with increasing function values 98 \STATE Sort the vertices of $S$ with increasing function values
99\ENDWHILE 99\ENDWHILE
100\end{algorithmic} 100\end{algorithmic}
101\caption{Spendley et al. algorithm} 101\caption{Spendley's et al. algorithm}
102\label{algo-spendley} 102\label{algo-spendley}
103\end{figure} 103\end{figure}
104 104
105The first step of the algorithm is based on the centroid 105At each iteration, we compute the centroid
106$\overline{\bx} (n+1)$ where the worst vertex $\bx_{n+1}$ 106$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$
107has been excluded. This centroid is 107has been excluded. This centroid is
108\begin{eqnarray} 108\begin{eqnarray}
109\label{centroid-worst} 109\label{centroid-worst}
110\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bx_i. 110\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i.
111\end{eqnarray} 111\end{eqnarray}
112We perform a reflection with respect to the worst vertex $\bx_{n+1}$, 112We perform a reflection with respect to the worst vertex $\bv_{n+1}$,
113which creates the reflected point $\bx_r$ defined by 113which creates the reflected point $\bx_r$ defined by
114\begin{eqnarray} 114\begin{eqnarray}
115\label{interpolate-worst} 115\label{interpolate-worst}
116\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bx_{n+1} 116\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1}
117\end{eqnarray} 117\end{eqnarray}
118 118
119We then compute the function value of the reflected 119We then compute the function value of the reflected
120point as $f_r=f(\bx_r)$. If the function value $f_r$ is better than the worst function 120point as $f_r=f(\bx_r)$. If the function value $f_r$ is better than the worst function
121value $f_{n+1}$, i.e. if $f_r < f_{n+1}$, then the worst point $\bx_{n+1}$ is rejected from the 121value $f_{n+1}$, i.e. if $f_r < f_{n+1}$, then the worst vertex $\bv_{n+1}$ is rejected from the
122simplex and the reflected point $\bx_r$ is accepted. If the reflection point 122simplex and the reflected point $\bx_r$ is accepted. If the reflection point
123does not improve the function value $f_{n+1}$, we consider the centroid 123does not improve the function value $f_{n+1}$, we consider the centroid
124$\overline{\bx} (n)$, i.e. the centroid where the vertex $\bx_n$ has been excluded. 124$\overline{\bx} (n)$, i.e. the centroid where the next-to-worst vertex $\bv_n$ has been excluded.
125We then consider the reflected vertex $\bx_r^\prime$, computed from the 125We then consider the reflected point $\bx_r^\prime$, computed from the
126next-to-worst vertex $\bx_n$ and the centroid $\overline{\bx} (n)$. 126next-to-worst vertex $\bv_n$ and the centroid $\overline{\bx} (n)$.
127We compute the function value $f_r^\prime = f(\bx_r^\prime)$. If the function 127We compute the function value $f_r^\prime = f(\bx_r^\prime)$. If the function
128value $f_r^\prime$ improves over the worst function value $f_{n+1}$, the new reflection vertex 128value $f_r^\prime$ improves over the worst function value $f_{n+1}$, then
129the worst vertex $\bv_{n+1}$ is rejected from the simplex and the new reflection point
129$\bx_r^\prime$ is accepted. 130$\bx_r^\prime$ is accepted.
130 131
131At that point of the algorithm, neither the reflection with respect to 132At that point of the algorithm, neither the reflection with respect to
132$\bx_{n+1}$ nor the reflection with respect to $\bx_n$ were able to improve over 133$\bv_{n+1}$ nor the reflection with respect to $\bv_n$ were able to improve over
133the worst function value $f_{n+1}$. 134the worst function value $f_{n+1}$.
134Therefore, the algorithm shrinks the simplex toward the best vertex $\bx_1$. 135Therefore, the algorithm shrinks the simplex toward the best vertex $\bv_1$.
135That last step uses the shrink coefficient $0<\sigma<1$. The standard 136That last step uses the shrink coefficient $0<\sigma<1$. The standard
136value for this coefficient is $\sigma=\frac{1}{2}$. 137value for this coefficient is $\sigma=\frac{1}{2}$.
137 138
138
139\subsection{Geometric analysis} 139\subsection{Geometric analysis}
140 140
141The figure \ref{fig-spendley-moves} presents the various 141The figure \ref{fig-spendley-moves} presents the various
@@ -245,7 +245,7 @@ with Spendley's et al. algorithm.
245The first numerical experiments involves one quadratic function 245The first numerical experiments involves one quadratic function
246in 2 dimensions. The second experiment is based on a 246in 2 dimensions. The second experiment is based on a
247badly scaled quadratic in 2 dimension. In the third experiment, 247badly scaled quadratic in 2 dimension. In the third experiment,
248we analyse the behaviour of the algorithm with respect to the 248we analyze the behavior of the algorithm with respect to the
249number of variables. 249number of variables.
250 250
251\subsection{Quadratic function} 251\subsection{Quadratic function}
@@ -263,11 +263,11 @@ with respect to the size of the initial simplex
263\end{eqnarray} 263\end{eqnarray}
264The oriented length $\sigma_+(S)$ is defined by 264The oriented length $\sigma_+(S)$ is defined by
265\begin{eqnarray} 265\begin{eqnarray}
266\sigma_+(S) = \max_{i=2,n+1} \|\bx_i - \bx_1\|_2 266\sigma_+(S) = \max_{i=2,n+1} \|\bv_i - \bv_1\|_2
267\end{eqnarray} 267\end{eqnarray}
268where $\|.\|_2$ is the euclidian norm defined by 268where $\|.\|_2$ is the euclidian norm defined by
269\begin{eqnarray} 269\begin{eqnarray}
270\|\bx\|_2 = \sum_{i=1,n}(x^j)^2. 270\|\bx\|_2 = \sum_{i=1,n}x_i^2.
271\end{eqnarray} 271\end{eqnarray}
272 272
273The initial simplex is a regular simplex with length unity. 273The initial simplex is a regular simplex with length unity.
@@ -324,7 +324,7 @@ The various simplices generated during the iterations are
324presented in figure \ref{fig-spendley-numexp1-historysimplex}. 324presented in figure \ref{fig-spendley-numexp1-historysimplex}.
325The method use reflections in the early iterations. Then there 325The method use reflections in the early iterations. Then there
326is no possible improvement using reflections and shrinking is necessary. 326is no possible improvement using reflections and shrinking is necessary.
327That behaviour is an illustration of the discretization which has already 327That behavior is an illustration of the discretization which has already
328been discussed. 328been discussed.
329 329
330\begin{figure} 330\begin{figure}
@@ -407,7 +407,7 @@ nm = nmplot_destroy(nm);
407The numerical results are presented in table \ref{fig-spendley-numexp1-table}, 407The numerical results are presented in table \ref{fig-spendley-numexp1-table},
408where the experiment is presented for $a=100$. One can check that the 408where the experiment is presented for $a=100$. One can check that the
409number of function evaluation is equal to its maximum limit, even if the value of the 409number of function evaluation is equal to its maximum limit, even if the value of the
410function at optimum is very inacurate ($f(x^\star) \approx 0.08$). 410function at optimum is very inaccurate ($f(x^\star) \approx 0.08$).
411 411
412\begin{figure}[h] 412\begin{figure}[h]
413\begin{center} 413\begin{center}
@@ -434,7 +434,7 @@ Computed $f(x^\star)$ & $0.08$\\
434The various simplices generated during the iterations are 434The various simplices generated during the iterations are
435presented in figure \ref{fig-spendley-numexp2-historysimplex}. 435presented in figure \ref{fig-spendley-numexp2-historysimplex}.
436The method use reflections in the early iterations. Then there 436The method use reflections in the early iterations. Then there
437is no possible improvment using reflections and shrinking is necessary. 437is no possible improvement using reflections and shrinking is necessary.
438But the shrinking makes the simplex very small so that a large number of 438But the shrinking makes the simplex very small so that a large number of
439iterations are necessary to improve the function value. 439iterations are necessary to improve the function value.
440This is a limitation of the method, which is based on a simplex 440This is a limitation of the method, which is based on a simplex
@@ -448,8 +448,8 @@ which can vary its size, but not its shape.
448\label{fig-spendley-numexp2-historysimplex} 448\label{fig-spendley-numexp2-historysimplex}
449\end{figure} 449\end{figure}
450 450
451In figure \ref{fig-spendley-numexp2-scaling}, we analyse the 451In figure \ref{fig-spendley-numexp2-scaling}, we analyze the
452behaviour of the method with respect to scaling. 452behavior of the method with respect to scaling.
453We check that the method behave poorly when the scaling is 453We check that the method behave poorly when the scaling is
454bad. The convergence speed is slower and slower and impractical 454bad. The convergence speed is slower and slower and impractical
455when $a>10$ 455when $a>10$
@@ -644,7 +644,7 @@ The figure \ref{fig-sp-numexp3-dimension} presents the number of function
644evaluations depending on the number of variables. 644evaluations depending on the number of variables.
645 645
646One can see that the number of function evaluations 646One can see that the number of function evaluations
647increases approximately linearily with the dimension of the problem in 647increases approximately linearly with the dimension of the problem in
648figure \ref{fig-sp-numexp3-fvn}. A rough rule of thumb is that, for $n=1,20$, 648figure \ref{fig-sp-numexp3-fvn}. A rough rule of thumb is that, for $n=1,20$,
649the number of function evaluations is equal to $30n$. 649the number of function evaluations is equal to $30n$.
650This test is in fact the best that we can expect from this algorithm : since 650This test is in fact the best that we can expect from this algorithm : since
diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.pdf b/scilab_doc/neldermead/nelder-mead-contract-inside.pdf
new file mode 100644
index 0000000..2291d00
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.png b/scilab_doc/neldermead/nelder-mead-contract-inside.png
deleted file mode 100644
index 2411847..0000000
--- a/scilab_doc/neldermead/nelder-mead-contract-inside.png
+++ /dev/null
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.svg b/scilab_doc/neldermead/nelder-mead-contract-inside.svg
index cd756ed..1aee216 100644
--- a/scilab_doc/neldermead/nelder-mead-contract-inside.svg
+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.svg
@@ -8,8 +8,8 @@
8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm" 11 width="809.82587"
12 height="297mm" 12 height="397.0213"
13 id="svg2" 13 id="svg2"
14 sodipodi:version="0.32" 14 sodipodi:version="0.32"
15 inkscape:version="0.46" 15 inkscape:version="0.46"
@@ -17,21 +17,22 @@
17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-inside.png" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-inside.png"
19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90"
21 version="1.0">
21 <defs 22 <defs
22 id="defs4"> 23 id="defs4">
23 <marker 24 <marker
24 inkscape:stockid="Arrow1Lend" 25 inkscape:stockid="Arrow1Lend"
25 orient="auto" 26 orient="auto"
26 refY="0.0" 27 refY="0"
27 refX="0.0" 28 refX="0"
28 id="Arrow1Lend" 29 id="Arrow1Lend"
29 style="overflow:visible;"> 30 style="overflow:visible">
30 <path 31 <path
31 id="path3318" 32 id="path3318"
32 d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " 33 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
33 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;" 34 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" /> 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
35 </marker> 36 </marker>
36 <inkscape:perspective 37 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d" 38 sodipodi:type="inkscape:persp3d"
@@ -49,15 +50,15 @@
49 inkscape:pageopacity="0.0" 50 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2" 51 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949" 52 inkscape:zoom="0.98994949"
52 inkscape:cx="303.93521" 53 inkscape:cx="423.78725"
53 inkscape:cy="730.24376" 54 inkscape:cy="283.81813"
54 inkscape:document-units="px" 55 inkscape:document-units="px"
55 inkscape:current-layer="layer1" 56 inkscape:current-layer="layer1"
56 showgrid="false" 57 showgrid="false"
57 inkscape:window-width="1280" 58 inkscape:window-width="1280"
58 inkscape:window-height="975" 59 inkscape:window-height="975"
59 inkscape:window-x="0" 60 inkscape:window-x="1777"
60 inkscape:window-y="22" /> 61 inkscape:window-y="14" />
61 <metadata 62 <metadata
62 id="metadata7"> 63 id="metadata7">
63 <rdf:RDF> 64 <rdf:RDF>
@@ -72,7 +73,8 @@
72 <g 73 <g
73 inkscape:label="Calque 1" 74 inkscape:label="Calque 1"
74 inkscape:groupmode="layer" 75 inkscape:groupmode="layer"
75 id="layer1"> 76 id="layer1"
77 transform="translate(-51.823231,-103.31687)">
76 <text 78 <text
77 xml:space="preserve" 79 xml:space="preserve"
78 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 80 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
@@ -95,7 +97,7 @@
95 x="189.90868" 97 x="189.90868"
96 y="417.98639" /></text> 98 y="417.98639" /></text>
97 <path 99 <path
98 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 100 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
99 d="M 322.74455,355.90788 L 321.20143,215.83654 L 425.66339,316.03476 L 322.74455,355.90788 z" 101 d="M 322.74455,355.90788 L 321.20143,215.83654 L 425.66339,316.03476 L 322.74455,355.90788 z"
100 id="path2423" 102 id="path2423"
101 sodipodi:nodetypes="cccc" /> 103 sodipodi:nodetypes="cccc" />
@@ -140,12 +142,12 @@
140 x="432.05054" 142 x="432.05054"
141 y="308.15915">N</tspan></text> 143 y="308.15915">N</tspan></text>
142 <path 144 <path
143 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 145 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
144 d="M 435.46343,438.97454 L 322.53305,356.33396 L 425.47979,316.37352 L 435.46343,438.97454 z" 146 d="M 435.46343,438.97454 L 322.53305,356.33396 L 425.47979,316.37352 L 435.46343,438.97454 z"
145 id="path2454" 147 id="path2454"
146 sodipodi:nodetypes="cccc" /> 148 sodipodi:nodetypes="cccc" />
147 <path 149 <path
148 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 150 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
149 d="M 435.60634,439.45686 L 321.21202,216.07873" 151 d="M 435.60634,439.45686 L 321.21202,216.07873"
150 id="path3226" 152 id="path3226"
151 sodipodi:nodetypes="cc" /> 153 sodipodi:nodetypes="cc" />
@@ -176,7 +178,7 @@
176 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-163.52526,97.403636)" /> 178 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-163.52526,97.403636)" />
177 <path 179 <path
178 sodipodi:type="arc" 180 sodipodi:type="arc"
179 style="fill:none;stroke:#000000;stroke-width:0.44742242;stroke-miterlimit:4;stroke-dasharray:0.44742241, 1.78968964;stroke-dashoffset:0;stroke-opacity:1" 181 style="fill:none;stroke:#000000;stroke-width:0.48342219;stroke-miterlimit:4;stroke-dasharray:0.48342218, 1.93368873;stroke-dashoffset:0;stroke-opacity:1"
180 id="path3230" 182 id="path3230"
181 sodipodi:cx="375.77673" 183 sodipodi:cx="375.77673"
182 sodipodi:cy="472.02954" 184 sodipodi:cy="472.02954"
@@ -186,7 +188,7 @@
186 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-802.48459,-155.5446)" /> 188 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-802.48459,-155.5446)" />
187 <path 189 <path
188 sodipodi:type="arc" 190 sodipodi:type="arc"
189 style="fill:none;stroke:#000000;stroke-width:0.24033611;stroke-miterlimit:4;stroke-dasharray:0.2403361, 0.96134438;stroke-dashoffset:0;stroke-opacity:1" 191 style="fill:none;stroke:#000000;stroke-width:0.25967363;stroke-miterlimit:4;stroke-dasharray:0.25967363, 1.03869451;stroke-dashoffset:0;stroke-opacity:1"
190 id="path3232" 192 id="path3232"
191 sodipodi:cx="375.77673" 193 sodipodi:cx="375.77673"
192 sodipodi:cy="472.02954" 194 sodipodi:cy="472.02954"
@@ -215,7 +217,7 @@
215 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 217 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
216 transform="translate(130.81219,71.517787)" /> 218 transform="translate(130.81219,71.517787)" />
217 <path 219 <path
218 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 220 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
219 d="M 351.27869,273.43734 L 322.83401,355.3091 L 425.69409,316.40214 L 351.27869,273.43734 z" 221 d="M 351.27869,273.43734 L 322.83401,355.3091 L 425.69409,316.40214 L 351.27869,273.43734 z"
220 id="path3396" 222 id="path3396"
221 sodipodi:nodetypes="cccc" /> 223 sodipodi:nodetypes="cccc" />
@@ -239,73 +241,77 @@
239 sodipodi:ry="2.2728431" 241 sodipodi:ry="2.2728431"
240 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 242 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
241 transform="translate(47.474606,-93.13708)" /> 243 transform="translate(47.474606,-93.13708)" />
242 <text
243 xml:space="preserve"
244 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
245 x="542.25177"
246 y="445.54333"
247 id="text3238"><tspan
248 sodipodi:role="line"
249 id="tspan3240"
250 x="542.25177"
251 y="445.54333">R = Reflexion</tspan></text>
252 <g 244 <g
253 id="g2431" 245 id="g3198"
254 transform="translate(-3.1011179e-5,-1.0874309e-4)"> 246 transform="translate(139.40105,-235.36554)">
255 <text 247 <text
256 id="text3242" 248 id="text3238"
257 y="356.25449" 249 y="445.54333"
258 x="542.22089" 250 x="542.25177"
259 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 251 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
260 xml:space="preserve"><tspan 252 xml:space="preserve"><tspan
261 y="356.25449" 253 y="445.54333"
254 x="542.25177"
255 id="tspan3240"
256 sodipodi:role="line">R = Reflexion</tspan></text>
257 <g
258 transform="translate(-3.1011179e-5,-1.0874309e-4)"
259 id="g2431">
260 <text
261 xml:space="preserve"
262 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
262 x="542.22089" 263 x="542.22089"
263 id="tspan3244" 264 y="356.25449"
264 sodipodi:role="line">H = Highest</tspan></text> 265 id="text3242"><tspan
265 </g> 266 sodipodi:role="line"
266 <text 267 id="tspan3244"
267 xml:space="preserve" 268 x="542.22089"
268 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 269 y="356.25449">H = Highest</tspan></text>
269 x="542.36511" 270 </g>
270 y="418.40466" 271 <text
271 id="text3246"><tspan 272 id="text3246"
272 sodipodi:role="line" 273 y="418.40466"
273 id="tspan3248"
274 x="542.36511" 274 x="542.36511"
275 y="418.40466">L = Lowest</tspan></text> 275 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
276 <text 276 xml:space="preserve"><tspan
277 xml:space="preserve" 277 y="418.40466"
278 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 278 x="542.36511"
279 x="542.30328" 279 id="tspan3248"
280 y="387.3295" 280 sodipodi:role="line">L = Lowest</tspan></text>
281 id="text3250"><tspan 281 <text
282 sodipodi:role="line" 282 id="text3250"
283 id="tspan3252" 283 y="387.3295"
284 x="542.30328" 284 x="542.30328"
285 y="387.3295">N = Next to highest</tspan></text> 285 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
286 <text 286 xml:space="preserve"><tspan
287 xml:space="preserve" 287 y="387.3295"
288 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 288 x="542.30328"
289 x="543.91089" 289 id="tspan3252"
290 y="472.68198" 290 sodipodi:role="line">N = Next to highest</tspan></text>
291 id="text3439"><tspan 291 <text
292 sodipodi:role="line" 292 id="text3439"
293 id="tspan3441" 293 y="472.68198"
294 x="543.91089"
295 y="472.68198">Ci = Contraction </tspan><tspan
296 sodipodi:role="line"
297 x="543.91089" 294 x="543.91089"
298 y="499.06259" 295 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
299 id="tspan3443"> (inside)</tspan></text> 296 xml:space="preserve"><tspan
300 <text 297 y="472.68198"
301 xml:space="preserve" 298 x="543.91089"
302 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 299 id="tspan3441"
303 x="543.71509" 300 sodipodi:role="line">Ci = Contraction </tspan><tspan
304 y="530.39539" 301 id="tspan3443"
305 id="text2435"><tspan 302 y="499.06259"
306 sodipodi:role="line" 303 x="543.91089"
307 id="tspan2437" 304 sodipodi:role="line"> (inside)</tspan></text>
305 <text
306 id="text2435"
307 y="530.39539"
308 x="543.71509" 308 x="543.71509"
309 y="530.39539">f(R) &gt;= f(H)</tspan></text> 309 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
310 xml:space="preserve"><tspan
311 y="530.39539"
312 x="543.71509"
313 id="tspan2437"
314 sodipodi:role="line">f(R) ≥ f(H)</tspan></text>
315 </g>
310 </g> 316 </g>
311</svg> 317</svg>
diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.pdf b/scilab_doc/neldermead/nelder-mead-contract-outside.pdf
new file mode 100644
index 0000000..d294af6
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.png b/scilab_doc/neldermead/nelder-mead-contract-outside.png
deleted file mode 100644
index fe38040..0000000
--- a/scilab_doc/neldermead/nelder-mead-contract-outside.png
+++ /dev/null
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.svg b/scilab_doc/neldermead/nelder-mead-contract-outside.svg
index fb5200d..e9fc83c 100644
--- a/scilab_doc/neldermead/nelder-mead-contract-outside.svg
+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.svg
@@ -8,8 +8,8 @@
8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm" 11 width="837.6604"
12 height="297mm" 12 height="503.00317"
13 id="svg2" 13 id="svg2"
14 sodipodi:version="0.32" 14 sodipodi:version="0.32"
15 inkscape:version="0.46" 15 inkscape:version="0.46"
@@ -17,21 +17,22 @@
17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-outside.png" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-outside.png"
19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90"
21 version="1.0">
21 <defs 22 <defs
22 id="defs4"> 23 id="defs4">
23 <marker 24 <marker
24 inkscape:stockid="Arrow1Lend" 25 inkscape:stockid="Arrow1Lend"
25 orient="auto" 26 orient="auto"
26 refY="0.0" 27 refY="0"
27 refX="0.0" 28 refX="0"
28 id="Arrow1Lend" 29 id="Arrow1Lend"
29 style="overflow:visible;"> 30 style="overflow:visible">
30 <path 31 <path
31 id="path3318" 32 id="path3318"
32 d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " 33 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
33 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;" 34 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" /> 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
35 </marker> 36 </marker>
36 <inkscape:perspective 37 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d" 38 sodipodi:type="inkscape:persp3d"
@@ -49,15 +50,15 @@
49 inkscape:pageopacity="0.0" 50 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2" 51 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949" 52 inkscape:zoom="0.98994949"
52 inkscape:cx="207.44335" 53 inkscape:cx="533.6731"
53 inkscape:cy="636.62322" 54 inkscape:cy="336.53587"
54 inkscape:document-units="px" 55 inkscape:document-units="px"
55 inkscape:current-layer="layer1" 56 inkscape:current-layer="layer1"
56 showgrid="false" 57 showgrid="false"
57 inkscape:window-width="1280" 58 inkscape:window-width="1533"
58 inkscape:window-height="975" 59 inkscape:window-height="975"
59 inkscape:window-x="0" 60 inkscape:window-x="1798"
60 inkscape:window-y="22" /> 61 inkscape:window-y="10" />
61 <metadata 62 <metadata
62 id="metadata7"> 63 id="metadata7">
63 <rdf:RDF> 64 <rdf:RDF>
@@ -72,7 +73,8 @@
72 <g 73 <g
73 inkscape:label="Calque 1" 74 inkscape:label="Calque 1"
74 inkscape:groupmode="layer" 75 inkscape:groupmode="layer"
75 id="layer1"> 76 id="layer1"
77 transform="translate(-33.845178,-66.596157)">
76 <text 78 <text
77 xml:space="preserve" 79 xml:space="preserve"
78 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 80 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
@@ -95,7 +97,7 @@
95 x="189.90868" 97 x="189.90868"
96 y="417.98639" /></text> 98 y="417.98639" /></text>
97 <path 99 <path
98 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" 100 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
99 d="M 272.74455,335.90788 L 271.20143,195.83654 L 375.66339,296.03476 L 272.74455,335.90788 z" 101 d="M 272.74455,335.90788 L 271.20143,195.83654 L 375.66339,296.03476 L 272.74455,335.90788 z"
100 id="path2423" 102 id="path2423"
101 sodipodi:nodetypes="cccc" /> 103 sodipodi:nodetypes="cccc" />
@@ -140,12 +142,12 @@
140 x="386.09116" 142 x="386.09116"
141 y="295.73529">N</tspan></text> 143 y="295.73529">N</tspan></text>
142 <path 144 <path
143 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 145 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
144 d="M 385.46343,418.97454 L 272.53305,336.33396 L 375.47979,296.37352 L 385.46343,418.97454 z" 146 d="M 385.46343,418.97454 L 272.53305,336.33396 L 375.47979,296.37352 L 385.46343,418.97454 z"
145 id="path2454" 147 id="path2454"
146 sodipodi:nodetypes="cccc" /> 148 sodipodi:nodetypes="cccc" />
147 <path 149 <path
148 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 150 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
149 d="M 385.89222,419.74019 L 270.60234,196.65251" 151 d="M 385.89222,419.74019 L 270.60234,196.65251"
150 id="path3226" 152 id="path3226"
151 sodipodi:nodetypes="cc" /> 153 sodipodi:nodetypes="cc" />
@@ -171,7 +173,7 @@
171 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-801.7703,-126.25889)" /> 173 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-801.7703,-126.25889)" />
172 <path 174 <path
173 sodipodi:type="arc" 175 sodipodi:type="arc"
174 style="fill:none;stroke:#000000;stroke-width:0.24033611;stroke-miterlimit:4;stroke-dasharray:0.2403361, 0.96134438;stroke-dashoffset:0;stroke-opacity:1" 176 style="fill:none;stroke:#000000;stroke-width:0.25967363;stroke-miterlimit:4;stroke-dasharray:0.25967363, 1.03869451;stroke-dashoffset:0;stroke-opacity:1"
175 id="path3232" 177 id="path3232"
176 sodipodi:cx="375.77673" 178 sodipodi:cx="375.77673"
177 sodipodi:cy="472.02954" 179 sodipodi:cy="472.02954"
@@ -181,7 +183,7 @@
181 transform="matrix(3.3350534,-1.9254939,1.9254939,3.3350534,-1804.8322,-522.25569)" /> 183 transform="matrix(3.3350534,-1.9254939,1.9254939,3.3350534,-1804.8322,-522.25569)" />
182 <path 184 <path
183 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.92553139;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.9255314, 3.7021256;stroke-dashoffset:0;stroke-opacity:1" 185 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.92553139;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.9255314, 3.7021256;stroke-dashoffset:0;stroke-opacity:1"
184 d="M 46.429775,338.61979 C 129.63836,188.0964 361.50049,88.059116 501.73967,87.124191" 186 d="M 34.307944,325.48781 C 143.7805,193.14716 369.58171,87.048967 489.61784,73.992208"
185 id="path3292" 187 id="path3292"
186 sodipodi:nodetypes="cc" /> 188 sodipodi:nodetypes="cc" />
187 <text 189 <text
@@ -210,7 +212,7 @@
210 d="M 426.28436,472.02954 A 50.507626,18.687822 0 1 1 325.26911,472.02954 A 50.507626,18.687822 0 1 1 426.28436,472.02954 z" 212 d="M 426.28436,472.02954 A 50.507626,18.687822 0 1 1 325.26911,472.02954 A 50.507626,18.687822 0 1 1 426.28436,472.02954 z"
211 transform="matrix(5.7171128,-3.3007765,3.3007765,5.7171128,-3358.0596,-1127.1779)" /> 213 transform="matrix(5.7171128,-3.3007765,3.3007765,5.7171128,-3358.0596,-1127.1779)" />
212 <path 214 <path
213 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 215 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
214 d="M 358.75333,367.91758 L 273.09708,335.78462 L 375.2862,296.32926 L 358.75333,367.91758 z" 216 d="M 358.75333,367.91758 L 273.09708,335.78462 L 375.2862,296.32926 L 358.75333,367.91758 z"
215 id="path3237" 217 id="path3237"
216 sodipodi:nodetypes="cccc" /> 218 sodipodi:nodetypes="cccc" />
@@ -244,69 +246,73 @@
244 sodipodi:ry="2.2728431" 246 sodipodi:ry="2.2728431"
245 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 247 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z"
246 transform="translate(80.812192,51.517787)" /> 248 transform="translate(80.812192,51.517787)" />
247 <text 249 <g
248 xml:space="preserve" 250 id="g3198"
249 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 251 transform="translate(199.00005,-352.54324)">
250 x="492.50925" 252 <text
251 y="524.6214" 253 id="text3238"
252 id="text3238"><tspan 254 y="524.6214"
253 sodipodi:role="line"
254 id="tspan3240"
255 x="492.50925" 255 x="492.50925"
256 y="524.6214">R = Reflexion</tspan></text> 256 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
257 <text 257 xml:space="preserve"><tspan
258 xml:space="preserve" 258 y="524.6214"
259 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 259 x="492.50925"
260 x="492.47833" 260 id="tspan3240"
261 y="434.24643" 261 sodipodi:role="line">R = Reflexion</tspan></text>
262 id="text3242"><tspan 262 <text
263 sodipodi:role="line" 263 id="text3242"
264 id="tspan3244" 264 y="434.24643"
265 x="492.47833" 265 x="492.47833"
266 y="434.24643">H = Highest</tspan></text> 266 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
267 <text 267 xml:space="preserve"><tspan
268 xml:space="preserve" 268 y="434.24643"
269 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 269 x="492.47833"
270 x="492.62259" 270 id="tspan3244"
271 y="497.1207" 271 sodipodi:role="line">H = Highest</tspan></text>
272 id="text3246"><tspan 272 <text
273 sodipodi:role="line" 273 id="text3246"
274 id="tspan3248" 274 y="497.1207"
275 x="492.62259" 275 x="492.62259"
276 y="497.1207">L = Lowest</tspan></text> 276 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
277 <text 277 xml:space="preserve"><tspan
278 xml:space="preserve" 278 y="497.1207"
279 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 279 x="492.62259"
280 x="492.56076" 280 id="tspan3248"
281 y="465.68356" 281 sodipodi:role="line">L = Lowest</tspan></text>
282 id="text3250"><tspan 282 <text
283 sodipodi:role="line" 283 id="text3250"
284 id="tspan3252" 284 y="465.68356"
285 x="492.56076" 285 x="492.56076"
286 y="465.68356">N = Next to highest</tspan></text> 286 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
287 <text 287 xml:space="preserve"><tspan
288 xml:space="preserve" 288 y="465.68356"
289 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 289 x="492.56076"
290 x="494.16833" 290 id="tspan3252"
291 y="552.12207" 291 sodipodi:role="line">N = Next to highest</tspan></text>
292 id="text3259"><tspan 292 <text
293 sodipodi:role="line" 293 id="text3259"
294 id="tspan3261" 294 y="552.12207"
295 x="494.16833" 295 x="494.16833"
296 y="552.12207">Co = Contraction </tspan><tspan 296 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
297 sodipodi:role="line" 297 xml:space="preserve"><tspan
298 x="494.16833" 298 y="552.12207"
299 y="578.50269" 299 x="494.16833"
300 id="tspan3263"> (outside)</tspan></text> 300 id="tspan3261"
301 <text 301 sodipodi:role="line">Co = Contraction </tspan><tspan
302 xml:space="preserve" 302 id="tspan3263"
303 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 303 y="578.50269"
304 x="493.97253" 304 x="494.16833"
305 y="610.19745" 305 sodipodi:role="line"> (outside)</tspan></text>
306 id="text2586"><tspan 306 <text
307 sodipodi:role="line" 307 id="text2586"
308 id="tspan2588" 308 y="610.19745"
309 x="493.97253" 309 x="493.97253"
310 y="610.19745">f(N)&lt;=f(R)&lt;f(H)</tspan></text> 310 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
311 xml:space="preserve"><tspan
312 y="610.19745"
313 x="493.97253"
314 id="tspan2588"
315 sodipodi:role="line">f(N)≤f(R)&lt;f(H)</tspan></text>
316 </g>
311 </g> 317 </g>
312</svg> 318</svg>
diff --git a/scilab_doc/neldermead/nelder-mead-extension.pdf b/scilab_doc/neldermead/nelder-mead-extension.pdf
new file mode 100644
index 0000000..7d6de4f
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-extension.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-extension.svg b/scilab_doc/neldermead/nelder-mead-extension.svg
index 893a1ba..d69765b 100644
--- a/scilab_doc/neldermead/nelder-mead-extension.svg
+++ b/scilab_doc/neldermead/nelder-mead-extension.svg
@@ -8,30 +8,31 @@
8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm" 11 width="760.96051"
12 height="297mm" 12 height="516.25098"
13 id="svg2" 13 id="svg2"
14 sodipodi:version="0.32" 14 sodipodi:version="0.32"
15 inkscape:version="0.46" 15 inkscape:version="0.46"
16 sodipodi:docname="nelder.mead.extension.svg" 16 sodipodi:docname="nelder-mead-extension.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.extension.png" 18 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.extension.png"
19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90"
21 version="1.0">
21 <defs 22 <defs
22 id="defs4"> 23 id="defs4">
23 <marker 24 <marker
24 inkscape:stockid="Arrow1Lend" 25 inkscape:stockid="Arrow1Lend"
25 orient="auto" 26 orient="auto"
26 refY="0.0" 27 refY="0"
27 refX="0.0" 28 refX="0"
28 id="Arrow1Lend" 29 id="Arrow1Lend"
29 style="overflow:visible;"> 30 style="overflow:visible">
30 <path 31 <path
31 id="path3318" 32 id="path3318"
32 d="M 0.0,0.0 L 5.0,-5.0 L -12.5,0.0 L 5.0,5.0 L 0.0,0.0 z " 33 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
33 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;" 34 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" /> 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
35 </marker> 36 </marker>
36 <inkscape:perspective 37 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d" 38 sodipodi:type="inkscape:persp3d"
@@ -48,16 +49,16 @@
48 borderopacity="1.0" 49 borderopacity="1.0"
49 inkscape:pageopacity="0.0" 50 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2" 51 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949" 52 inkscape:zoom="0.7"
52 inkscape:cx="241.7257" 53 inkscape:cx="330.2877"
53 inkscape:cy="610.56309" 54 inkscape:cy="311.45737"
54 inkscape:document-units="px" 55 inkscape:document-units="px"
55 inkscape:current-layer="layer1" 56 inkscape:current-layer="layer1"
56 showgrid="false" 57 showgrid="false"
57 inkscape:window-width="1280" 58 inkscape:window-width="1280"
58 inkscape:window-height="975" 59 inkscape:window-height="975"
59 inkscape:window-x="0" 60 inkscape:window-x="1769"
60 inkscape:window-y="22" /> 61 inkscape:window-y="21" />
61 <metadata 62 <metadata
62 id="metadata7"> 63 id="metadata7">
63 <rdf:RDF> 64 <rdf:RDF>
@@ -72,7 +73,8 @@
72 <g 73 <g
73 inkscape:label="Calque 1" 74 inkscape:label="Calque 1"
74 inkscape:groupmode="layer" 75 inkscape:groupmode="layer"
75 id="layer1"> 76 id="layer1"
77 transform="translate(-73.241138,-175.12971)">
76 <text 78 <text
77 xml:space="preserve" 79 xml:space="preserve"
78 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 80 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
@@ -95,7 +97,7 @@
95 x="189.90868" 97 x="189.90868"
96 y="417.98639" /></text> 98 y="417.98639" /></text>
97 <path 99 <path
98 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:none" 100 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
99 d="M 219.20646,335.90788 L 217.66334,195.83654 L 322.12531,296.03476 L 219.20646,335.90788 z" 101 d="M 219.20646,335.90788 L 217.66334,195.83654 L 322.12531,296.03476 L 219.20646,335.90788 z"
100 id="path2423" 102 id="path2423"
101 sodipodi:nodetypes="cccc" /> 103 sodipodi:nodetypes="cccc" />
@@ -150,18 +152,18 @@
150 x="395.74493" 152 x="395.74493"
151 y="513.42316">E</tspan></text> 153 y="513.42316">E</tspan></text>
152 <path 154 <path
153 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:0.528,1.584;stroke-dashoffset:0" 155 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
154 d="M 331.92535,418.97454 L 218.99497,336.33396 L 321.94171,296.37352 L 331.92535,418.97454 z" 156 d="M 331.92535,418.97454 L 218.99497,336.33396 L 321.94171,296.37352 L 331.92535,418.97454 z"
155 id="path2454" 157 id="path2454"
156 sodipodi:nodetypes="cccc" /> 158 sodipodi:nodetypes="cccc" />
157 <path 159 <path
158 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:0.528;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:0.528, 1.584;stroke-dashoffset:0;stroke-opacity:1" 160 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1, 3;stroke-dashoffset:0;stroke-opacity:1"
159 d="M 386.39729,523.7859 L 217.92647,196.33127" 161 d="M 386.39729,523.7859 L 217.92647,196.33127"
160 id="path3226" 162 id="path3226"
161 sodipodi:nodetypes="cc" /> 163 sodipodi:nodetypes="cc" />
162 <path 164 <path
163 sodipodi:type="arc" 165 sodipodi:type="arc"
164 style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:1,4.00000001;stroke-dashoffset:0;stroke-opacity:1" 166 style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:1, 4.00000001;stroke-dashoffset:0;stroke-opacity:1"
165 id="path3228" 167 id="path3228"
166 sodipodi:cx="375.77673" 168 sodipodi:cx="375.77673"
167 sodipodi:cy="472.02954" 169 sodipodi:cy="472.02954"
@@ -171,7 +173,7 @@
171 transform="matrix(0.8660254,-0.5,0.5,0.8660254,-152.3352,348.10297)" /> 173 transform="matrix(0.8660254,-0.5,0.5,0.8660254,-152.3352,348.10297)" />
172 <path 174 <path
173 sodipodi:type="arc" 175 sodipodi:type="arc"
174 style="fill:none;stroke:#000000;stroke-width:0.44742241;stroke-miterlimit:4;stroke-dasharray:0.44742241,1.78968964;stroke-dashoffset:0;stroke-opacity:1" 176 style="fill:none;stroke:#000000;stroke-width:0.44742242;stroke-miterlimit:4;stroke-dasharray:0.44742241, 1.78968964;stroke-dashoffset:0;stroke-opacity:1"
175 id="path3230" 177 id="path3230"
176 sodipodi:cx="375.77673" 178 sodipodi:cx="375.77673"
177 sodipodi:cy="472.02954" 179 sodipodi:cy="472.02954"
@@ -181,7 +183,7 @@
181 transform="matrix(1.9355879,-1.1175122,1.1175122,1.9355879,-842.70542,74.802419)" /> 183 transform="matrix(1.9355879,-1.1175122,1.1175122,1.9355879,-842.70542,74.802419)" />
182 <path 184 <path
183 sodipodi:type="arc" 185 sodipodi:type="arc"
184 style="fill:none;stroke:#000000;stroke-width:0.2403361;stroke-miterlimit:4;stroke-dasharray:0.2403361,0.96134438;stroke-dashoffset:0;stroke-opacity:1" 186 style="fill:none;stroke:#000000;stroke-width:0.24033611;stroke-miterlimit:4;stroke-dasharray:0.2403361, 0.96134438;stroke-dashoffset:0;stroke-opacity:1"
185 id="path3232" 187 id="path3232"
186 sodipodi:cx="375.77673" 188 sodipodi:cx="375.77673"
187 sodipodi:cy="472.02954" 189 sodipodi:cy="472.02954"
@@ -190,67 +192,71 @@
190 d