summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichaŽl Baudin <michael.baudin@scilab.org>2009-09-02 13:47:05 +0200
committerMichaŽl Baudin <michael.baudin@scilab.org>2009-09-02 13:47:05 +0200
commit7b08f99e44382044485bdf80ba765b761d07a798 (patch)
treec9ffdddcf6f42517dfa2e6a5339a341bdc32688d /scilab_doc
parentdb9a0eb89f79225c200cf4e132626d98b1f4b0ec (diff)
downloadscilab-7b08f99e44382044485bdf80ba765b761d07a798.zip
scilab-7b08f99e44382044485bdf80ba765b761d07a798.tar.gz
Added manual for neldermead
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/Makefile31
-rw-r--r--scilab_doc/neldermead/acknowledgments.tex11
-rw-r--r--scilab_doc/neldermead/compute.roots.sce186
-rw-r--r--scilab_doc/neldermead/conclusion.tex27
-rw-r--r--scilab_doc/neldermead/han1-history-simplex.pngbin0 -> 7826 bytes
-rw-r--r--scilab_doc/neldermead/han2-history-simplex.pngbin0 -> 9992 bytes
-rw-r--r--scilab_doc/neldermead/implementations.tex225
-rw-r--r--scilab_doc/neldermead/installation-directories.pngbin0 -> 7872 bytes
-rw-r--r--scilab_doc/neldermead/installation.tex159
-rw-r--r--scilab_doc/neldermead/introduction.tex97
-rw-r--r--scilab_doc/neldermead/mckinnon-history-simplex.pngbin0 -> 10992 bytes
-rw-r--r--scilab_doc/neldermead/method-neldermead.tex1494
-rw-r--r--scilab_doc/neldermead/method-spendley.tex495
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-inside.pngbin0 -> 36440 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-inside.svg311
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-outside.pngbin0 -> 40448 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-contract-outside.svg312
-rw-r--r--scilab_doc/neldermead/nelder-mead-extension.pngbin0 -> 35182 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-extension.svg293
-rw-r--r--scilab_doc/neldermead/nelder-mead-reflection.pngbin0 -> 33907 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-reflection.svg301
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterci.pngbin0 -> 42344 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterci.svg314
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterco.pngbin0 -> 35143 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-shrink-afterco.svg306
-rw-r--r--scilab_doc/neldermead/nelder-mead-steps.pngbin0 -> 31536 bytes
-rw-r--r--scilab_doc/neldermead/nelder-mead-steps.svg356
-rw-r--r--scilab_doc/neldermead/neldermead-dimension-nfevals.pngbin0 -> 12140 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-dimension-rho.pngbin0 -> 11013 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-roots-variable.pngbin0 -> 4265 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-roots.pngbin0 -> 4977 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.bib464
-rw-r--r--scilab_doc/neldermead/neldermead.pdfbin0 -> 951124 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.tex172
-rw-r--r--scilab_doc/neldermead/nmbibliography.tex399
-rw-r--r--scilab_doc/neldermead/overview.tex74
-rw-r--r--scilab_doc/neldermead/quad2-spendley-simplexcontours.pngbin0 -> 18444 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-nm-history-logfopt.pngbin0 -> 12858 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-nm-history-sigma.pngbin0 -> 10614 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-nm-simplexcontours.pngbin0 -> 32449 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-spendley-history-logfopt.pngbin0 -> 11971 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-spendley-history-sigma.pngbin0 -> 9722 bytes
-rw-r--r--scilab_doc/neldermead/quad2bis-spendley-simplexcontours.pngbin0 -> 32301 bytes
-rw-r--r--scilab_doc/neldermead/references.tex53
-rw-r--r--scilab_doc/neldermead/scilab_logo.jpgbin0 -> 20150 bytes
-rw-r--r--scilab_doc/neldermead/section-simplex.tex102
-rw-r--r--scilab_doc/neldermead/spendley-dimension-nfevals.pngbin0 -> 11047 bytes
-rw-r--r--scilab_doc/neldermead/spendley-dimension-rho.pngbin0 -> 12711 bytes
-rw-r--r--scilab_doc/neldermead/spendley-steps-reflect.pngbin0 -> 23005 bytes
-rw-r--r--scilab_doc/neldermead/spendley-steps-reflect.svg228
-rw-r--r--scilab_doc/neldermead/spendley-steps-reflect2.pngbin0 -> 30191 bytes
-rw-r--r--scilab_doc/neldermead/spendley-steps-reflect2.svg258
-rw-r--r--scilab_doc/neldermead/spendley-steps-shrink.pngbin0 -> 33070 bytes
-rw-r--r--scilab_doc/neldermead/spendley-steps-shrink.svg258
-rw-r--r--scilab_doc/neldermead/spendley-steps.pngbin0 -> 22149 bytes
-rw-r--r--scilab_doc/neldermead/spendley-steps.svg283
-rw-r--r--scilab_doc/neldermead/torczon_test1_angle.pngbin0 -> 8333 bytes
-rw-r--r--scilab_doc/neldermead/validation.tex11
58 files changed, 7220 insertions, 0 deletions
diff --git a/scilab_doc/neldermead/Makefile b/scilab_doc/neldermead/Makefile
new file mode 100644
index 0000000..85dc7ca
--- /dev/null
+++ b/scilab_doc/neldermead/Makefile
@@ -0,0 +1,31 @@
1#!/bin/sh
2
3RAPPORT = neldermead
4
5pdf:
6 pdflatex ${RAPPORT}
7 #bibtex ${RAPPORT}
8 #pdflatex ${RAPPORT}
9 #pdflatex ${RAPPORT}
10
11dvi:
12 latex ${RAPPORT}
13 bibtex ${RAPPORT}
14 latex ${RAPPORT}
15
16clean:
17 rm -f *.aux
18 rm -f *.bbl
19 rm -f *.blg
20 rm -f *.log
21 rm -f *.out
22 rm -f *.toc
23
24ortho:
25 ispell -t ${RAPPORT}.tex
26
27distclean:
28 make clean
29 rm -f ${RAPPORT}.pdf
30 rm -f ${RAPPORT}.dvi
31
diff --git a/scilab_doc/neldermead/acknowledgments.tex b/scilab_doc/neldermead/acknowledgments.tex
new file mode 100644
index 0000000..8603990
--- /dev/null
+++ b/scilab_doc/neldermead/acknowledgments.tex
@@ -0,0 +1,11 @@
1\chapter{Acknowledgments}
2
3I would like to thank Vincent Couvert,
4the team manager for Scilab releases, for his support
5during the development of this software. I would like to thank
6Serge Steer, INRIA researcher, for his comments and the discussions
7on this subject. Professor Han, Associate Professor of Mathematics in the
8University of Michigan-Flint University was kind enough to send me a copy
9of his Phd and I would like to thank him for that.
10
11
diff --git a/scilab_doc/neldermead/compute.roots.sce b/scilab_doc/neldermead/compute.roots.sce
new file mode 100644
index 0000000..5c5bd77
--- /dev/null
+++ b/scilab_doc/neldermead/compute.roots.sce
@@ -0,0 +1,186 @@
1//
2// compute.roots.sce --
3// Compute the roots of the caracteristic equation of Nelder-Mead algorithm.
4// Reproduce the results by Han & Neuman.
5//
6// Copyright 2008-2009 Michael Baudin
7//
8//
9// computeroots1 --
10// Compute the roots of the caracteristic equations of
11// usual Nelder-Mead method.
12//
13function computeroots1 ( n )
14 // Polynomial for outside contraction :
15 // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0
16 mprintf("Polynomial for outside contraction :\n");
17 coeffs = zeros(1,n+1);
18 coeffs(1) = n
19 coeffs(2:n) = -3
20 coeffs(n+1) = 2 * n
21 p=poly(coeffs,"x","coeff")
22 disp(p)
23 r = roots(p)
24 for i=1:n
25 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
26 end
27 // Polynomial for inside contraction :
28 // - n - x - ... - x^(n-1) + 2n x^(n)= 0
29 mprintf("Polynomial for inside contraction :\n");
30 coeffs = zeros(1,n+1);
31 coeffs(1) = -n
32 coeffs(2:n) = -1
33 coeffs(n+1) = 2 * n
34 p=poly(coeffs,"x","coeff")
35 disp(p)
36 r = roots(p)
37 for i=1:n
38 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
39 end
40 // Polynomial for reflection :
41 // n - 2x - ... - 2x^(n-1) + n x^(n) = 0
42 mprintf("Polynomial for reflection :\n");
43 coeffs = zeros(1,n+1);
44 coeffs(1) = n
45 coeffs(2:n) = -2
46 coeffs(n+1) = n
47 p=poly(coeffs,"x","coeff")
48 disp(p)
49 r = roots(p)
50 for i=1:n
51 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
52 end
53endfunction
54function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n )
55 // Polynomial for outside contraction :
56 // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0
57 coeffs = zeros(1,n+1);
58 coeffs(1) = n
59 coeffs(2:n) = -3
60 coeffs(n+1) = 2 * n
61 p=poly(coeffs,"x","coeff")
62 r = roots(p , "e")
63 rminoc = min(abs(r))
64 rmaxoc = max(abs(r))
65 // Polynomial for inside contraction :
66 // - n - x - ... - x^(n-1) + 2n x^(n)= 0
67 coeffs = zeros(1,n+1);
68 coeffs(1) = -n
69 coeffs(2:n) = -1
70 coeffs(n+1) = 2 * n
71 p=poly(coeffs,"x","coeff")
72 r = roots(p , "e")
73 rminic = min(abs(r))
74 rmaxic = max(abs(r))
75 mprintf("%d & %f & %f & %f & %f\\\\\n", n, rminoc, rmaxoc, rminic, rmaxic)
76endfunction
77
78function drawfigure1 ( nbmax )
79 rminoctable = zeros(1,nbmax)
80 rmaxoctable = zeros(1,nbmax)
81 rminictable = zeros(1,nbmax)
82 rmaxictable = zeros(1,nbmax)
83 for n = 1 : nbmax
84 [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n )
85 rminoctable ( n ) = rminoc
86 rmaxoctable ( n ) = rmaxoc
87 rminictable ( n ) = rminic
88 rmaxictable ( n ) = rmaxic
89 end
90 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] )
91 f = gcf();
92 pause
93 f.children.title.text = "Nelder-Mead caracteristic equation roots";
94 f.children.x_label.text = "Number of variables (n)";
95 f.children.y_label.text = "Roots of the caracteristic equation";
96 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]);
97 f.children.children(1).legend_location="in_lower_right";
98 for i = 1:4
99 mypoly = f.children.children(2).children(i);
100 mypoly.foreground=i;
101 mypoly.line_style=i;
102 end
103 xs2png(0,"neldermead-roots.png");
104endfunction
105
106//
107// computeroots2 --
108// Compute the roots of the caracteristic equations of
109// baudin Nelder-Mead method, when the xbar is xlow.
110//
111function computeroots2 ( n )
112 // Polynomial for outside contraction :
113 // 1 - 3x^(n-1) + 2 x^(n) = 0
114 mprintf("Polynomial for outside contraction :\n");
115 coeffs = zeros(1,n+1);
116 coeffs(1) = 1
117 coeffs(n) = -3
118 coeffs(n+1) = 2
119 p=poly(coeffs,"x","coeff")
120 disp(p)
121 r = roots(p)
122 for i=1:n
123 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
124 end
125 // Polynomial for inside contraction :
126 // - 1 - x^(n-1) + 2 x^(n)= 0
127 mprintf("Polynomial for inside contraction :\n");
128 coeffs = zeros(1,n+1);
129 coeffs(1) = -1
130 coeffs(n) = -1
131 coeffs(n+1) = 2
132 p=poly(coeffs,"x","coeff")
133 disp(p)
134 r = roots(p)
135 for i=1:n
136 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
137 end
138 // Polynomial for reflection :
139 // ???
140endfunction
141
142//
143// rootsvariable --
144// Compute roots of the caracteristic equation
145// of Nelder-Mead with variable coefficient mu.
146// Polynomial for outside/inside contraction :
147// n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0
148//
149function [rmin , rmax] = rootsvariable ( n , mu )
150 coeffs = zeros(1,n+1);
151 coeffs(1) = n * mu
152 coeffs(2:n) = -(1+mu)
153 coeffs(n+1) = n
154 p=poly(coeffs,"x","coeff")
155 r = roots(p , "e")
156 rmin = min(abs(r))
157 rmax = max(abs(r))
158 mprintf("%f & %f & %f\\\\\n", mu, rmin, rmax)
159endfunction
160
161function drawfigure_variable ( n , nmumax )
162 rmintable = zeros(1,nmumax)
163 rmaxtable = zeros(1,nmumax)
164 mutable = linspace ( -1 , 1 , nmumax )
165 for index = 1 : nmumax
166 mu = mutable ( index )
167 [rmin , rmax ] = rootsvariable ( n , mu )
168 rmintable ( index ) = rmin
169 rmaxtable ( index ) = rmax
170 end
171 plot2d ( mutable , [ rmintable' , rmaxtable' ] )
172 f = gcf();
173 pause
174 f.children.title.text = "Nelder-Mead caracteristic equation roots";
175 f.children.x_label.text = "Contraction coefficient";
176 f.children.y_label.text = "Roots of the caracteristic equation";
177 captions(f.children.children.children,["R-max","R-min"]);
178 f.children.children(1).legend_location="in_lower_right";
179 for i = 1:2
180 mypoly = f.children.children(2).children(i);
181 mypoly.foreground=i;
182 mypoly.line_style=i;
183 end
184 xs2png(0,"neldermead-roots-variable.png");
185endfunction
186
diff --git a/scilab_doc/neldermead/conclusion.tex b/scilab_doc/neldermead/conclusion.tex
new file mode 100644
index 0000000..e9880a9
--- /dev/null
+++ b/scilab_doc/neldermead/conclusion.tex
@@ -0,0 +1,27 @@
1\chapter{Conclusion}
2
3That tool might be extended in future releases so that it provides the following features :
4\begin{itemize}
5\item Kelley restart based on simplex gradient [9],
6\item C-based implementation (a prototype is provided in appendix B),
7\item parallel implementation of the DIRECT algorithm,
8\item implementation of the Hook-Jeeves and Multidimensional Search methods [9]
9\item parallel implementation of the Nelder-Mead algorithm. See for example [21].
10?This paper generalizes the widely used Nelder and Mead (Comput J
117:308?313, 1965) simplex algorithm to parallel processors. Unlike most
12previous parallelization methods, which are based on parallelizing the
13tasks required to compute a specific objective function given a vector
14of parameters, our parallel simplex algorithm uses parallelization at
15the parameter level. Our parallel simplex algorithm assigns to each
16processor a separate vector of parameters corresponding to a point on a
17simplex. The processors then conduct the simplex search steps for an
18improved point, communicate the results, and a new simplex is formed.
19The advantage of this method is that our algorithm is generic and can be
20applied, without re-writing computer code, to any optimization problem
21which the non-parallel Nelder?Mead is applicable. The method is also
22easily scalable to any degree of parallelization up to the number of
23parameters. In a series of Monte Carlo experiments, we show that this
24parallel simplex method yields computational savings in some experiments
25up to three times the number of processors.?
26\end{itemize}
27
diff --git a/scilab_doc/neldermead/han1-history-simplex.png b/scilab_doc/neldermead/han1-history-simplex.png
new file mode 100644
index 0000000..8cb57aa
--- /dev/null
+++ b/scilab_doc/neldermead/han1-history-simplex.png
Binary files differ
diff --git a/scilab_doc/neldermead/han2-history-simplex.png b/scilab_doc/neldermead/han2-history-simplex.png
new file mode 100644
index 0000000..8273f9a
--- /dev/null
+++ b/scilab_doc/neldermead/han2-history-simplex.png
Binary files differ
diff --git a/scilab_doc/neldermead/implementations.tex b/scilab_doc/neldermead/implementations.tex
new file mode 100644
index 0000000..150f0ef
--- /dev/null
+++ b/scilab_doc/neldermead/implementations.tex
@@ -0,0 +1,225 @@
1\chapter{Implementations of the Nelder-Mead algorithm}
2
3In the following sections, we analyse the various implementations of the
4Nelder-Mead algorithm. We analyse the Matlab implementation provided
5by the \emph{fminsearch} command. We analyse the matlab algorithm provided by
6C.T. Kelley and the Scilab port by Y. Collette. We
7present the Numerical Recipes implementations. We analyse the O'Neill
8fortran 77 implementation "AS47". The Burkardt implementation is also covered.
9The implementation provided in the NAG collection is detailed.
10The Nelder-Mead algorithm from the Gnu Scientific Library is analysed.
11
12\section{Matlab : fminsearch}
13
14The Matlab command fminsearch implements the Nelder-Mead algorithm \cite{MatlabFminsearch}.
15It provides features such as
16\begin{itemize}
17\item maximum number of function evaluations,
18\item maximum number of iterations,
19\item termination tolerance on the function value,
20\item termination tolerance on $x$,
21\item output command to display the progress of the algorithm.
22\end{itemize}
23
24\section{Kelley and the Nelder-Mead algorithm}
25
26C.T. Kelley has written a book \cite{Kelley1999} on optimization method and devotes a
27complete chapter to direct search algorithms, especially the Nelder-Mead
28algorithm. Kelley provides in \cite{KelleyMethodsOptimizationMatlabCodes}
29the Matlab implementation of the
30Nelder-Mead algorithm. That implementation uses the restart strategy
31that Kelley has published in \cite{589283} and which improves the possible
32stagnation of the algorithm on non local optimization points. No tests
33are provided.
34
35The following is extracted from the README provided with these
36algorithms.
37
38\begin{verbatim}
39These files are current as of December 9, 1998.
40
41-----------------
42
43MATLAB/FORTRAN software for Iterative Methods for Optimization
44
45by C. T. Kelley
46
47These M-files are implementations of the algorithms from the book
48"Iterative Methods for Optimization", to be published by SIAM,
49by C. T. Kelley. The book, which describes the algorithms, is available
50from SIAM (service@siam.org). These files can be modified for non-commercial
51purposes provided that the authors:
52
53C. T. Kelley for all MATLAB codes,
54P. Gilmore and T. D. Choi for iffco.f
55J. M. Gablonsky for DIRECT
56
57are acknowledged and clear comment lines are inserted
58that the code has been changed. The authors assume no no responsibility
59for any errors that may exist in these routines.
60
61Questions, comments, and bug reports should be sent to
62
63Professor C. T. Kelley
64Department of Mathematics, Box 8205
65North Carolina State University
66Raleigh, NC 27695-8205
67
68(919) 515-7163
69(919) 515-3798 (FAX)
70
71Tim_Kelley@ncsu.edu
72
73\end{verbatim}
74
75
76From Scilab's point of view, that ?licence? is a problem since it
77prevents the use of the source for commercial purposes.
78
79\section{Nelder-Mead Scilab Toolbox : Lolimot}
80
81The Lolimot project by Yann Collette provide two Scilab-based Nelder-
82Mead implementations \cite{LolimotColletteURL}. The first implementation is a Scilab port of
83the Kelley script. The licence problem is therefore not solved by this
84script. The second implementation \cite{NelderMeadColletteURL} implements the restart strategy
85by Kelley. No tests are provided.
86
87\section{Numerical Recipes}
88
89The Numerical Recipes \cite{NumericalRecipes} provides the C source code of an
90implementation of the Nelder-Mead algorithm. Of course, this is a
91copyrighted material which cannot be included in Scilab.
92
93\section{NASHLIB : A19}
94
95Nashlib is a collection of Fortran subprograms from "Compact Numerical
96Methods for Computers; Linear Algebra and Function Minimisation, " by
97J.C. Nash. The subprograms are written without many of the extra
98features usually associated with commercial mathematical software, such
99as extensive error checking, and are most useful for those applications
100where small program size is particularly important. The license is
101public domain.
102
103Nahslib includes one implementation of the Nelder-Mead algorithm \cite{GAMS-A19A20-Desc},
104\cite{GAMS-A19A20-Source}. It is written in fortran 77. The coding style is "goto"-based and
105may not be easy to maintain.
106
107\section{O'Neill implementations}
108
109The paper \cite{O'Neill1971AAF} by R. O'Neil in the journal of Applied Statistics
110presents a fortran 77 implementation of the Nelder-Mead algorithm. The
111source code itself is available in \cite{O'NeillAS47}. Many of the following
112implementations are based on this primary source code. We were not able
113to get the paper \cite{O'Neill1971AAF} itself.
114
115On his website, John Burkardt gives a fortran 77 source code of the
116Nelder-Mead algorithm \cite{Burkardtasa047}. The following are the comments in the header
117of the source code.
118
119\begin{verbatim}
120
121c Discussion:
122c
123c This routine seeks the minimum value of a user-specified function.
124c
125c Simplex function minimisation procedure due to Nelder+Mead(1965),
126c as implemented by O'Neill(1971, Appl.Statist. 20, 338-45), with
127c subsequent comments by Chambers+Ertel(1974, 23, 250-1), Benyon(1976,
128c 25, 97) and Hill(1978, 27, 380-2)
129c
130c The function to be minimized must be defined by a function of
131c the form
132c
133c function fn ( x, f )
134c double precision fn
135c double precision x(*)
136c
137c and the name of this subroutine must be declared EXTERNAL in the
138c calling routine and passed as the argument FN.
139c
140c This routine does not include a termination test using the
141c fitting of a quadratic surface.
142c
143c Modified:
144c
145c 27 February 2008
146c
147c Author:
148c
149c FORTRAN77 version by R ONeill
150c Modifications by John Burkardt
151
152\end{verbatim}
153
154The "Bayesian Survival Analysis" book by Joseph G. Ibrahim, Ming-Hui
155Chen, and Debajyoti Sinha provides in \cite{SurvivalBookOptim} a fortran 77 implementation
156of the Nelder-Mead algorithm. The following is the header of the source
157code.
158
159\begin{verbatim}
160c Simplex function minimisation procedure due to Nelder+Mead(1965),
161c as implemented by O'Neill(1971, Appl.Statist. 20, 338-45), with
162c subsequent comments by Chambers+Ertel(1974, 23, 250-1), Benyon(1976,
163c 25, 97) and Hill(1978, 27, 380-2)
164\end{verbatim}
165
166The O'Neill implementation uses a restart procedure which is
167based on a local axis by axis search for the optimality of the
168computed optimum.
169
170\section{Burkardt implementations}
171
172John Burkardt gives several implementations of the Nelder-Mead
173algorithm
174\begin{itemize}
175\item in fortran 77 \cite{Burkardtasa047}
176\item in Matlab by Jeff Borggaard \cite{BurkardtNelderMeadMatlab}.
177\end{itemize}
178
179\section{NAG Fortran implementation}
180
181The NAG Fortran library provides the E04CCF/E04CCA routines \cite{NAGE04CCF} which
182implements the simplex optimization method.
183E04CCA is a version of E04CCF that has additional parameters
184in order to make it safe for use in multithreaded applications.
185As mentioned in the documentation, "The method tends to be slow, but it
186is robust and therefore very useful for functions that are subject to inaccuracies.".
187The termination criteria is based on the standard deviation of the function
188values of the simplex.
189
190The specification of the cost function for E04CCA is:
191\begin{verbatim}
192SUBROUTINE FUNCT ( N, XC, FC, IUSER, RUSER)
193\end{verbatim}
194where IUSER and RUSER and integer and double precision array, which allow the
195user to supply information to the cost function.
196An output routine, called MONIT is called once every iteration in E04CCF/E04CCA.
197It can be used to print out the current values of any selection of its parameters
198but must not be used to change the values of the parameters.
199
200\section{GSL implementation}
201
202The Gnu Scientific Library provides two Nelder-Mead implementations.
203The authors are Tuomo Keskitalo, Ivo Alxneit and Brian Gough.
204The size of the simplex is the root mean square sum of length of vectors
205from simplex center to corner points.
206The termination criteria is based on the size of the simplex.
207
208The C implementation of the minimization algorithm is original.
209The communication is direct, in the sense that the specific optimization
210algorithm calls back the cost function.
211A specific optimization implementation provides four functions : "alloc", "free", "iterate"
212and "set". A generic optimizer is created by connecting it to a specific optimizer.
213The user must write the loop over the iterations, making successive calls
214to the generic "iterate" function, which, in turns, calls the specific "iterate"
215associated with the specific optimization algorithm.
216
217The cost function can be provided as three function pointers
218\begin{itemize}
219\item the cost function $f$,
220\item the gradient $g$,
221\item both the cost function and the gradient.
222\end{itemize}
223Some additional parameters can be passed to these functions.
224
225
diff --git a/scilab_doc/neldermead/installation-directories.png b/scilab_doc/neldermead/installation-directories.png
new file mode 100644
index 0000000..c70b1cb
--- /dev/null
+++ b/scilab_doc/neldermead/installation-directories.png
Binary files differ
diff --git a/scilab_doc/neldermead/installation.tex b/scilab_doc/neldermead/installation.tex
new file mode 100644
index 0000000..66cd62f
--- /dev/null
+++ b/scilab_doc/neldermead/installation.tex
@@ -0,0 +1,159 @@
1\chapter{Installation}
2
3In this section, we present the installation process for the toolbox.
4We present the steps which are required to have a running version of the
5toolbox and presents the several checks which can be performed before
6using the toolbox.
7
8\section{Architecture of the directories}
9
10We suppose that the archive has been unpacked in the "neldermead"
11directory. The following is a short list of the steps which are
12required to setup the toolbox.
13
14\begin{enumerate}
15\item build the toolbox : run the \emph{neldermead/builder.sce} script to
16create the binaries of the library, create the binaries
17for the gateway, generate the documentation
18\item load the toolbox : run the \emph{neldermead/loader.sce} script to
19load all commands and setup the documentation
20\item setup the startup configuration file of your Scilab system so that the toolbox is
21known at startup (see below for details),
22\item run the unit tests : run the \emph{neldermead/runtests.sce} script to
23perform all unit tests and check that the toolbox is OK
24\item run the demos : run the \emph{neldermead/rundemos.sce} script to
25run all demonstration scripts and get a quick interactive
26overview of its features
27\end{enumerate}
28
29The easiest way to setup your Scilab system is to configure the
30startup configuration file so that the toolboxes are known immediately
31at startup. The directory where this file is located is stored in the
32Scilab variable \emph{SCIHOME}.
33On my Linux system, the Scilab 5.1 startup file is located
34in \emph{/home/myname/.Scilab/scilab-5.1/.scilab}. On my Windows system, the Scilab 5.1 startup file is located
35in \emph{C:/Users/myname/AppData/Roaming/Scilab/scilab-5.1/.scilab}.
36This file is a regular Scilab script which is automatically
37loaded at Scilab's startup. If that file does not already
38exist, create it. Copy the following lines into the \emph{.scilab} file
39and configure the path to the toolboxes, stored in the \emph{SCILABTBX} variable.
40
41\begin{verbatim}
42ilib(0);
43SCILABTBX="/home/myname/mytoolboxes";
44exec(SCILABTBX + filesep() + 'optimbase'+ filesep() + 'loader.sce');
45exec(SCILABTBX + filesep() + 'optimsimplex'+ filesep() + 'loader.sce');
46exec(SCILABTBX + filesep() + 'neldermead'+ filesep() + 'loader.sce');
47\end{verbatim}
48
49The figure \ref{installation:builder.sce} presents the messages
50which are generated when the builder of the toolbox is launched.
51
52\begin{figure}[htbp]
53\begin{small}
54\begin{verbatim}
55-->cd neldermead/
56 ans =
57 /media/disk/SVN-Scilab/neldermead
58-->exec builder.sce
59-->// ====================================================================
60-->// Copyright INRIA 2008-2009
61-->// Allan CORNET
62-->// Simon LIPP
63-->// Michael Baudin
64-->// This file is released into the public domain
65-->// ====================================================================
66-->mode(-1);
67Building macros...
68-- Cr√ation de [neldermeadlib] (Macros) --
69genlib: Traitement du fichier: nmplot_display.sci
70[...]
71genlib: Traitement du fichier: nmplot_configure.sci
72genlib: Regenere noms et librairie
73Building help...
74Construit le document principal dans /media/disk/SVN-Scilab/neldermead/help/en_US
75Construction du fichier manuel [javaHelp] dans /media/disk/SVN-Scilab/neldermead/help/en_US. (Veuillez patienter ... cela peut prendre un certain temps)
76Generating loader.sce...
77\end{verbatim}
78\end{small}
79\caption{Launch of the builder}
80\label{installation:builder.sce}
81\end{figure}
82
83The figure \ref{installation:loader.sce} presents the messages
84which are generated when the loader of the toolbox is launched.
85
86\begin{figure}[htbp]
87\begin{small}
88\begin{verbatim}
89->exec loader.sce
90
91-->// ====================================================================
92-->// generated by builder.sce
93-->// Copyright INRIA 2008
94-->// ====================================================================
95-->try
96--> getversion('scilab');
97-->catch
98--> warning('Scilab 5.0 or more is required.');
99--> return;
100-->end;
101-->// ====================================================================
102-->root_tlbx = get_absolute_file_path('loader.sce');
103-->exec(root_tlbx+'etc\'+'neldermead.start');
104 Start Nelder-Mead Toolbox
105 Load macros from :
106 /media/disk/SVN-Scilab/neldermead/macros/
107 Load help
108-->// ====================================================================
109-->clear root_tlbx;
110-->// ====================================================================
111\end{verbatim}
112\end{small}
113\caption{Launch of the loader}
114\label{installation:loader.sce}
115\end{figure}
116
117The figure \ref{installation:runtests.sce} presents the messages
118which are generated when the unit tests script of the toolbox is launched.
119
120\begin{figure}[htbp]
121\begin{verbatim}
122-->exec D:\Baudin\ProjetScilab\toolboxes\neldermead\runtests.sce
123-->TODO ...
124\end{verbatim}
125\caption{Launch of the unit tests script}
126\label{installation:runtests.sce}
127\end{figure}
128
129
130\section{Configuration}
131
132The directories which are provided in the toolbox
133are presented in figure \ref{installation:neldermeaddirectory}.
134
135\begin{figure}[htbp]
136\begin{center}
137\includegraphics[height=5cm]{installation-directories.png}
138\end{center}
139\caption{Architecture of the toolbox}
140\label{installation:neldermeaddirectory}
141\end{figure}
142
143This is an overview of the content of these directories :
144\begin{itemize}
145\item \emph{neldermead/demos} : demonstration scripts
146\item \emph{neldermead/doc} : the Scilab Enhancement Proposal \#21, about Nelder-Mead algorithm
147\item \emph{neldermead/doc/usermanual} : the \LaTeX sources of this manual
148\item \emph{neldermead/etc} : startup and shutdow scripts for the toolbox
149\item \emph{neldermead/help/en\_US/scilab\_en\_US\_help} : html pages of the help
150\item \emph{neldermead/jar} : java archive for the help
151\item \emph{neldermead/macros} : Scilab macros files *.sci
152\item \emph{neldermead/tests} : tests
153\item \emph{neldermead/tests/nonreg\_tests} : tests after some bug has been identified
154\item \emph{neldermead/tests/unit\_tests} : unit tests
155\end{itemize}
156
157\section{Tests}
158
159
diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.tex
new file mode 100644
index 0000000..303ef25
--- /dev/null
+++ b/scilab_doc/neldermead/introduction.tex
@@ -0,0 +1,97 @@
1\chapter{Introduction}
2
3The Nelder-Mead simplex algorithm, published in 1965, is an enormously
4popular search method for multidimensional unconstrained optimization.
5The Nelder-Mead algorithm should not be confused with the (probably)
6more famous simplex algorithm of Dantzig for linear programming. The
7Nelder-Mead algorithm is especially popular in the fields of chemistry,
8chemical engineering, and medicine. Two measures of the ubiquity of the
9Nelder-Mead algorithm are that it appears in the best-selling handbook
10Numerical Recipes and in Matlab. In \cite{Torczon89multi-directionalsearch},
11Virginia Torczon writes : "Margaret Wright has stated that over
12fifty percent of the calls received by the support group for the NAG
13software library concerned the version of the Nelder-Mead
14simplex algorithm to be found in that library". No derivative of the cost function is
15required, which makes the algorithm interesting for noisy problems.
16
17The Nelder-Mead algorithm falls in the more general class of direct
18search algorithms. These methods use values of $f$ taken from a set of
19sample points and use that information to continue the sampling. The
20Nelder-Mead algorithm maintains a simplex which are approximations of an
21optimal point. The vertices are sorted according to the objective
22function values. The algorithm attemps to replace the worst vertex with
23a new point, which depends on the worst point and the centre of the best
24vertices.
25
26The goal of this toolbox is to provide a Nelder-Mead direct search optimization method to solve the
27following unconstrained optimization problem
28\begin{eqnarray}
29\min f(x)
30\end{eqnarray}
31where $x\in \RR^n$ where $n$ is the number of optimization parameters.
32The Box complex algorithm, which is an extension of Nelder-Mead's algorithm, solves the
33following constrained problem
34\begin{eqnarray}
35&&\min f(x)\\
36&&\ell_i \leq x_i \leq u_i, \qquad i = 1,n\\
37&&g_j(x)\geq 0, \qquad j = 1, m\\
38\end{eqnarray}
39where $m$ is the number of nonlinear, positive constraints and $\ell_i,u_i\in \RR^n$ are the lower
40and upper bounds of the variables.
41
42The Nelder-Mead algorithm may be used in the following optimization context :
43\begin{itemize}
44\item there is no need to provide the derivatives of the objective function,
45\item the number of parameters is small (up to 10-20),
46\item there are bounds and/or non linear constraints.
47\end{itemize}
48
49The internal design of the system is based on the following components :
50\begin{itemize}
51\item "neldermead" provides various Nelder-Mead variants and manages for Nelder-Mead specific settings, such as the method to compute the initial simplex, the specific termination criteria,
52\item "fminsearch" provides a Scilab commands which aims at behaving as Matlab's fminsearch. Specific terminations criteria, initial simplex and auxiliary settings are automatically configured so that the behaviour of Matlab's fminsearch is exactly reproduced.
53\item "optimset", "optimget" provides Scilab commands to emulate their Matlab counterparts.
54\item "nmplot" provides a high-level component which provides directly output pictures for Nelder-Mead algorithm.
55\end{itemize}
56The current toolbox is based on (and therefore requires) the following toolboxes
57\begin{itemize}
58\item "optimbase" provides an abstract class for a general optimization component, including the number of variables, the minimum and maximum bounds, the number of non linear inequality constraints, the loggin system, various termination criteria, the cost function, etc...
59\item "optimsimplex" provides a class to manage a simplex made of an arbitrary number of vertices, including the computation of a simplex by various methods (axes, regular, Pfeffer's, randomized bounds), the computation of the size by various methods (diameter, sigma +, sigma-, etc...),
60\end{itemize}
61
62The following is a list of features the Nelder-Mead prototype algorithm currently provides :
63\begin{itemize}
64\item Manage various simplex initializations
65 \begin{itemize}
66 \item initial simplex given by user,
67 \item initial simplex computed with a length and along the coordinate axes,
68 \item initial regular simplex computed with Spendley et al. formula
69 \item initial simplex computed by a small perturbation around the initial guess point
70 \end{itemize}
71\item Manage cost function
72 \begin{itemize}
73 \item optionnal additionnal argument
74 \item direct communication of the task to perform : cost function or inequality constraints
75 \end{itemize}
76\item Manage various termination criteria, including maximum number of iterations, tolerance on function value (relative or absolute),
77 \begin{itemize}
78 \item tolerance on x (relative or absolute),
79 \item tolerance on standard deviation of function value (original termination criteria in [3]),
80 \item maximum number of evaluations of cost function,
81 \item absolute or relative simplex size,
82 \end{itemize}
83\item Manage the history of the convergence, including
84 \begin{itemize}
85 \item history of function values,
86 \item history of optimum point,
87 \item history of simplices,
88 \item history of termination criterias,
89 \end{itemize}
90\item Provide a plot command which allows to graphically see the history of the simplices toward the optimum,
91\item Provide query features for the status of the optimization process number of iterations, number of function evaluations, status of execution, function value at initial point, function value at optimal point, etc...
92\item Spendley et al. fixed shaped algorithm,
93\item Kelley restart based on simplex gradient,
94\item O'Neill restart based on factorial search around optimum,
95\item Box-like method managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.
96\end{itemize}
97
diff --git a/scilab_doc/neldermead/mckinnon-history-simplex.png b/scilab_doc/neldermead/mckinnon-history-simplex.png
new file mode 100644
index 0000000..a1f81b7
--- /dev/null
+++ b/scilab_doc/neldermead/mckinnon-history-simplex.png
Binary files differ
diff --git a/scilab_doc/neldermead/method-neldermead.tex b/scilab_doc/neldermead/method-neldermead.tex
new file mode 100644
index 0000000..22529dc
--- /dev/null
+++ b/scilab_doc/neldermead/method-neldermead.tex
@@ -0,0 +1,1494 @@
1\chapter{Nelder-Mead method}
2
3\section{Analysis}
4
5The Nelder-Mead method is an improvment over the Spendley's et al.
6method with the goal of allowing the simplex to vary in shape.
7The Nelder-Mead algorithm makes use of four parameters : the
8coefficient of reflection $\rho$, expansion $\chi$,
9contraction $\gamma$ and shrinkage $\sigma$.
10When the expansion or contraction steps are performed, the shape
11of the simplex is changed, thus "adapting itself to the
12local landscape" \cite{citeulike:3009487}.
13
14These parameters should satisfy the following inequalities \cite{citeulike:3009487,lagarias:112}
15\begin{eqnarray}
16\label{condition-coeffs}
17\rho>0, \qquad \chi > 1, \qquad \chi > \rho, \qquad 0<\gamma<1, \qquad \textrm{and} \qquad 0<\sigma<1.
18\end{eqnarray}
19
20The standard values for these coefficients are
21\begin{eqnarray}
22\label{standard-coeffs}
23\rho=1, \qquad \chi =2, \qquad \gamma=\frac{1}{2}, \qquad \textrm{and} \qquad \sigma=\frac{1}{2}.
24\end{eqnarray}
25
26In \cite{Kelley1999}, the Nelder-Mead algorithm is presented with
27other parameter names, that is $\mu_r = \rho$, $\mu_e = \rho\chi$, $\mu_{ic} = -\gamma$
28and $\mu_{oc} = \rho\gamma$. These coefficients must satisfy the following
29inequality
30
31\begin{eqnarray}
32-1 < \mu_{ic} < 0 < \mu_{oc} < \mu_r < \mu_e
33\end{eqnarray}
34
35The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}.
36
37\begin{figure}[htbp]
38\begin{algorithmic}
39\STATE Compute an initial simplex $S_0$
40\STATE Sorts the vertices $S_0$ with increasing function values
41\STATE $S\gets S_0$
42\WHILE{$\sigma(S)>tol$}
43 \STATE $\overline{x}\gets \overline{x}(n+1)$
44 \STATE $x_r \gets x(\rho,n+1)$, $f_r \gets f(x_r)$ \COMMENT{Reflect}
45 \IF {$f_r<f_1$}
46 \STATE $x_e \gets x(\rho\chi,n+1)$, $f_e \gets f(x_e)$ \COMMENT{Expand}
47 \IF {$f_e<f_r$}
48 \STATE Accept $x_e$
49 \ELSE
50 \STATE Accept $x_r$
51 \ENDIF
52 \ELSIF {$f_1 \leq f_r < f_n$}
53 \STATE Accept $x_r$
54 \ELSIF {$f_n \leq f_r < f_{n+1}$}
55 \STATE $x_c \gets x(\rho\gamma,n+1)$, $f_c \gets f(x_c)$ \COMMENT{Outside contraction}
56 \IF {$f_c<f_r$}
57 \STATE Accept $x_c$
58 \ELSE
59 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink}
60 \STATE Compute the function values at the points $x_i, i=2,n+1$
61 \ENDIF
62 \ELSE
63 \STATE $x_c \gets x(-\gamma,n+1)$, $f_c \gets f(x_c)$ \COMMENT{Inside contraction}
64 \IF {$f_c<f_{n+1}$}
65 \STATE Accept $x_c$
66 \ELSE
67 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink}
68 \STATE Compute the function values at the points $x_i, i=2,n+1$
69 \ENDIF
70 \ENDIF
71 \STATE Sort the vertices of $S$ with increasing function values
72\ENDWHILE
73\end{algorithmic}
74\caption{Nelder-Mead algorithm - standard version}
75\label{algo-neldermead}
76\end{figure}
77
78The algorithm from figure \ref{algo-neldermead} is the most
79popular variant of the Nelder-Mead algorithm.
80But the original paper is based on a "greedy" expansion, where
81the expansion point is accepted if it is better than the
82best point (and not if it is better than the reflection point).
83This "greedy" version is implemented in AS47 by O'Neill in \cite{O'Neill1971AAF}
84and the corresponding algorithm is presented in figure \ref{algo-neldermead-greedy}.
85
86\begin{figure}[htbp]
87\begin{algorithmic}
88 \IF {$f_e<f_1$}
89 \STATE Accept $x_e$
90 \ELSE
91 \STATE Accept $x_r$
92 \ENDIF
93\end{algorithmic}
94\caption{Nelder-Mead algorithm - greedy version}
95\label{algo-neldermead-greedy}
96\end{figure}
97
98
99\section{Geometric analysis}
100
101The figure \ref{fig-nm-moves} presents the various moves of the
102simplex in the Nelder-Mead algorithm.
103
104\begin{figure}
105\begin{center}
106\includegraphics[width=10cm]{nelder-mead-steps.png}
107\end{center}
108\caption{Nelder-Mead simplex moves}
109\label{fig-nm-moves}
110\end{figure}
111
112The figure \ref{fig-nm-moves-reflection}
113through \ref{fig-nm-moves-shrinkafterco} present the
114detailed situations when each kind of step occur.
115
116Obviously, the expansion step is performed when the
117simplex is far away from the optimum. The direction of
118descent is then followed and the worst vertex is moved
119into that direction.
120
121When the reflection step is performed, the simplex is
122getting close to an valley, since the expansion point
123does not improve.
124
125When the simplex is near the optimum,
126the inside and outside contraction steps may be performed, which
127allow to decrease the size of the simplex.
128
129The shrink steps (be it after an outside contraction or an inside
130contraction) occurs only in very special situations. In practical experiments,
131shrink steps are rare.
132
133\begin{figure}
134\begin{center}
135\includegraphics[width=10cm]{nelder-mead-reflection.png}
136\end{center}
137\caption{Nelder-Mead simplex moves - reflection}
138\label{fig-nm-moves-reflection}
139\end{figure}
140
141\begin{figure}
142\begin{center}
143\includegraphics[width=10cm]{nelder-mead-extension.png}
144\end{center}
145\caption{Nelder-Mead simplex moves - expansion}
146\label{fig-nm-moves-expansion}
147\end{figure}
148
149\begin{figure}
150\begin{center}
151\includegraphics[width=10cm]{nelder-mead-contract-inside.png}
152\end{center}
153\caption{Nelder-Mead simplex moves - inside contraction}
154\label{fig-nm-moves-insidecontraction}
155\end{figure}
156
157\begin{figure}
158\begin{center}
159\includegraphics[width=10cm]{nelder-mead-contract-outside.png}
160\end{center}
161\caption{Nelder-Mead simplex moves - outside contraction}
162\label{fig-nm-moves-outsidecontraction}
163\end{figure}
164
165\begin{figure}
166\begin{center}
167\includegraphics[width=10cm]{nelder-mead-shrink-afterci.png}
168\end{center}
169\caption{Nelder-Mead simplex moves - shrink after inside contraction.}
170\label{fig-nm-moves-shrinkafterci}
171\end{figure}
172
173\begin{figure}
174\begin{center}
175\includegraphics[width=10cm]{nelder-mead-shrink-afterco.png}
176\end{center}
177\caption{Nelder-Mead simplex moves - shrink after outside contraction}
178\label{fig-nm-moves-shrinkafterco}
179\end{figure}
180
181\subsection{Termination criteria}
182
183TODO...
184
185\section{Convergence on a quadratic}
186
187In this section, we reproduce one result
188presented by Han and Neumann \cite{HanNeumann2006}, which states
189the rate of convergence toward the optimum on a class of quadratic functions with a special initial
190simplex.
191See also the Phd by Lixing Han in 2000 \cite{Han2000}.
192We study a generalized quadratic and use a particular
193initial simplex. We show that the vertices follow
194a recurrence equation, which is associated with a caracteristic
195equation. The study of the roots of these caracteristic equations
196give an insight of the behaviour of the Nelder-Mead algorithm
197when the dimension $n$ increases.
198
199Let us suppose than one wants to minimize the function
200\begin{eqnarray}
201\label{hanneumman-quadratic}
202f(\bx) = x_1^2+\ldots+x_n^2
203\end{eqnarray}
204with the initial simplex
205\begin{eqnarray}
206S_0 = \left[\bold{0},\bv^{(0)}_1,\ldots,\bv^{(0)}_n\right]
207\end{eqnarray}
208With this choice of the initial simplex, the best vertex remains fixed
209at $\bold{0}\in\RR^n$. As the function in equation \ref{hanneumman-quadratic}
210is strictly convex, the Nelder-Mead method never performs
211the \emph{shrink} step. Therefore, at each iteration, a new simplex
212is formed by replacing the worst vertex $\bv^{(k)}_n$, by a
213new, better vertex. Assume that the Nelder-Mead method
214generates a sequence of simplices ${S_k}_{k\geq 0}$ in $\RR^n$,
215where
216\begin{eqnarray}
217S_k = \left[\bold{0},\bv^{(k)}_1,\ldots,\bv^{(n)}_n\right]
218\end{eqnarray}
219We wish that the sequence of simplices ${S_k}\rightarrow \bold{0}\in\RR^n$
220as $k\rightarrow \infty$. To measure the progress of convergence,
221Han and Neumann use the oriented length of the simplex $S_k$, $\sigma(S_k)$.
222We say that a sequence of simplices ${S_k}$ converges to the minimizer $\bold{0}\in\RR^n$
223of the function in equation \ref{hanneumman-quadratic} if
224$\lim_{k\rightarrow \infty} \sigma(S_k) = 0$.
225
226We measure the rate of convergence defined by \cite{HanNeumann2006}
227
228\begin{eqnarray}
229\label{rho-rate-convergence}
230\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
231\left(\sum_{i=0,k-1} \frac{\sigma(S_{i+1}}{\sigma(S_i}\right)^{1/k}
232\end{eqnarray}
233
234That definition can be viewed as the geometric mean of the ratio of the
235oriented lengths between successive simplices and the minimizer 0.
236This definition implies
237
238\begin{eqnarray}
239\label{rho-rate-convergence2}
240\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
241\left( \frac{\sigma(S_{k+1}}{\sigma(S_0}\right)^{1/k}
242\end{eqnarray}
243
244According to the definition, the algorithm is convergent if $0\leq \rho(S_0,n) < 1$.
245The larger the $\rho(S_0,n)$, the slower the convergence. In particular, the convergence
246is very slow when $\rho(S_0,n)$ is close to 1.
247The analysis is based on the fact that the Nelder-Mead method generates a sequence of simplices
248in $\RR^n$ satisfying
249
250\begin{eqnarray}
251S_k = \left[\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\right]
252\end{eqnarray}
253
254where $\bold{0},\bv^{(k+n-1)},\ldots,\bv^{(k+1)},\bv^{(k)}\in\RR^n$ are the vertices
255of the $k-th$ simplex, with
256
257\begin{eqnarray}
258f(\bold{0}) < f(\bv^{(k+n-1)} < f(\bv^{(k+1)}) < f(\bv^{(k)}),
259\end{eqnarray}
260
261for $k\geq 0$.
262
263To simplify the analysis, we consider that only one type of step of the Nelder-Mead
264method is applied repeatedly. This allows to establich recurrence equations for the
265sucessive simplex vertices. As the shrink step is never used, and the expansion steps is
266never used neither (since the best vertex is already at 0), the analysis focuses
267on the outside contraction, inside contraction and reflection steps.
268
269The centroid of the $n$ best vertices of $S_k$ is given by
270
271\begin{eqnarray}
272\overline{\bold{v}}^{(k)} &=& \frac{1}{n} \sum_{i=1,n-1} \bv^{(k+i)}\\
273&=&\frac{1}{n} \left( \bv^{(k+1)} + \ldots + \bv^{(k+n-1)} \right)
274\end{eqnarray}
275
276\subsection{With default parameters}
277
278In this section, we analyse the roots of the caracteristic
279equation with \emph{fixed}, standard inside and outside contraction
280coefficients.
281
282\emph{Outside contraction} If the outside contraction step is repeatedly performed
283with $\mu_{oc} = \rho\gamma = \frac{1}{2}$, then
284
285\begin{eqnarray}
286\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
287+ \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right)
288\end{eqnarray}
289By plugging the definition of the centroid into the previous equality, one
290find the recurrence formula
291
292\begin{eqnarray}
2932n \bv^{(k+n)} - 3 \bv^{(k+1)} - \ldots - 3 \bv^{(k+n-1)} + n\bv^{(k)} = 0
294\end{eqnarray}
295
296The associated caracteristic equation is
297
298\begin{eqnarray}
299\label{recurrence-oc}
3002n \mu^n - 3 \mu^{n-1} - \ldots - 3 \mu + n = 0.
301\end{eqnarray}
302
303\emph{Inside contraction} If the inside contraction step is repeatedly performed
304with $\mu_{ic} = -\gamma = -\frac{1}{2}$, then
305
306\begin{eqnarray}
307\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
308- \frac{1}{2} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right)
309\end{eqnarray}
310By plugging the definition of the centroid into the previous equality, one
311find the recurrence formula
312
313\begin{eqnarray}
3142n \bv^{(k+n)} - \bv^{(k+1)} - \ldots - \bv^{(k+n-1)} - n\bv^{(k)} = 0
315\end{eqnarray}
316
317The associated caracteristic equation is
318
319\begin{eqnarray}
320\label{recurrence-ic}
3212n \mu^n - \mu^{n-1} - \ldots - \mu - n = 0.
322\end{eqnarray}
323
324\emph{Reflection} If the reflection step is repeatedly performed
325with $\mu_r = \rho = 1$, then
326
327\begin{eqnarray}
328\bv^{(k+n)} = \overline{\bold{v}}^{(k)}
329+ \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right)
330\end{eqnarray}
331By plugging the definition of the centroid into the previous equality, one
332find the recurrence formula
333
334\begin{eqnarray}
335n \bv^{(k+n)} - 2 \bv^{(k+1)} - \ldots - 2 \bv^{(k+n-1)} + n\bv^{(k)} = 0
336\end{eqnarray}
337
338The associated caracteristic equation is
339
340\begin{eqnarray}
341\label{recurrence-reflection}
342n \mu^n - 2 \mu^{n-1} - \ldots - 2 \mu + n = 0.
343\end{eqnarray}
344
345The recurrence equations \ref{recurrence-oc}, \ref{recurrence-ic} and \ref{recurrence-reflection}
346are linear. Their general solutions are of the form
347
348\begin{eqnarray}
349\bv^{(k)} = \mu_1^k \bold{a}_1 + \ldots + \mu_n^k \bold{a}_n
350\end{eqnarray}
351where ${\mu_i}_{i=1,n}$ are the roots of the characteristic equations and
352${\bold{a}_i}_{i=1,n} \in \CC^n$ are independent vectors such that $\bv^{(k)} \in \RR^n$
353for all $k\geq 0$.
354
355The analysis by Han and Neumann \cite{HanNeumann2006} gives a
356deep understanding of the convergence rate for this particular
357situation. For $n=1$, they show that the convergence rate is $\frac{1}{2}$.
358For $n=2$, the convergence rate is $\frac{\sqrt{2}}{2}\approx 0.7$ with
359a particular choice for the initial simplex. For $n\geq 3$, Han and Neumann \cite{HanNeumann2006}
360perform a numerical analysis of the roots.
361
362In the following Scilab script, one computes the roots of these 3 caracteristic
363equations.
364
365\lstset{language=Scilab}
366\lstset{numbers=left}
367\lstset{basicstyle=\footnotesize}
368\lstset{keywordstyle=\bfseries}
369\begin{lstlisting}
370//
371// computeroots1 --
372// Compute the roots of the caracteristic equations of
373// usual Nelder-Mead method.
374//
375function computeroots1 ( n )
376 // Polynomial for outside contraction :
377 // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0
378 mprintf("Polynomial for outside contraction :\n");
379 coeffs = zeros(1,n+1);
380 coeffs(1) = n
381 coeffs(2:n) = -3
382 coeffs(n+1) = 2 * n
383 p=poly(coeffs,"x","coeff")
384 disp(p)
385 r = roots(p)
386 for i=1:n
387 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
388 end
389 // Polynomial for inside contraction :
390 // - n - x - ... - x^(n-1) + 2n x^(n)= 0
391 mprintf("Polynomial for inside contraction :\n");
392 coeffs = zeros(1,n+1);
393 coeffs(1) = -n
394 coeffs(2:n) = -1
395 coeffs(n+1) = 2 * n
396 p=poly(coeffs,"x","coeff")
397 disp(p)
398 r = roots(p)
399 for i=1:n
400 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
401 end
402 // Polynomial for reflection :
403 // n - 2x - ... - 2x^(n-1) + n x^(n) = 0
404 mprintf("Polynomial for reflection :\n");
405 coeffs = zeros(1,n+1);
406 coeffs(1) = n
407 coeffs(2:n) = -2
408 coeffs(n+1) = n
409 p=poly(coeffs,"x","coeff")
410 disp(p)
411 r = roots(p)
412 for i=1:n
413 mprintf("#%d/%d |%s|=%f\n", i, length(r),string(r(i)),abs(r(i)))
414 end
415endfunction
416\end{lstlisting}
417
418If one executes this script with $n=10$, the following
419output is produced.
420
421\begin{tiny}
422\begin{verbatim}
423-->computeroots1 ( 10 )
424Polynomial for outside contraction :
425
426 2 3 4 5 6 7 8 9 10
427 10 - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x + 20x
428#1/10 |0.5822700+%i*0.7362568|=0.938676
429#2/10 |0.5822700-%i*0.7362568|=0.938676
430#3/10 |-0.5439060+%i*0.7651230|=0.938747
431#4/10 |-0.5439060-%i*0.7651230|=0.938747
432#5/10 |0.9093766+%i*0.0471756|=0.910599
433#6/10 |0.9093766-%i*0.0471756|=0.910599
434#7/10 |0.0191306+%i*0.9385387|=0.938734
435#8/10 |0.0191306-%i*0.9385387|=0.938734
436#9/10 |-0.8918713+%i*0.2929516|=0.938752
437#10/10 |-0.8918713-%i*0.2929516|=0.938752
438Polynomial for inside contraction :
439
440 2 3 4 5 6 7 8 9 10
441 - 10 - x - x - x - x - x - x - x - x - x + 20x
442#1/10 |0.7461586+%i*0.5514088|=0.927795
443#2/10 |0.7461586-%i*0.5514088|=0.927795
444#3/10 |-0.2879931+%i*0.8802612|=0.926175
445#4/10 |-0.2879931-%i*0.8802612|=0.926175
446#5/10 |-0.9260704|=0.926070
447#6/10 |0.9933286|=0.993329
448#7/10 |0.2829249+%i*0.8821821|=0.926440
449#8/10 |0.2829249-%i*0.8821821|=0.926440
450#9/10 |-0.7497195+%i*0.5436596|=0.926091
451#10/10 |-0.7497195-%i*0.5436596|=0.926091
452Polynomial for reflection :
453
454 2 3 4 5 6 7 8 9 10
455 10 - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x + 10x
456#1/10 |0.6172695+%i*0.7867517|=1.000000
457#2/10 |0.6172695-%i*0.7867517|=1.000000
458#3/10 |-0.5801834+%i*0.8144859|=1.000000
459#4/10 |-0.5801834-%i*0.8144859|=1.000000
460#5/10 |0.9946011+%i*0.1037722|=1.000000
461#6/10 |0.9946011-%i*0.1037722|=1.000000
462#7/10 |0.0184670+%i*0.9998295|=1.000000
463#8/10 |0.0184670-%i*0.9998295|=1.000000
464#9/10 |-0.9501543+%i*0.3117800|=1.000000
465#10/10 |-0.9501543-%i*0.3117800|=1.000000
466\end{verbatim}
467\end{tiny}
468
469The following Scilab script allows to compute the minimum and
470the maximum of the modulus of the roots.
471The "e" option of the "roots" command has been used to force the
472use of the eigenvalues of the companion matrix as the computationnal
473method. The default algorithm, based on the Jenkins-Traub Rpoly
474method is generating a convergence error and cannot be used
475in this case.
476
477\lstset{language=Scilab}
478\lstset{numbers=left}
479\lstset{basicstyle=\footnotesize}
480\lstset{keywordstyle=\bfseries}
481\begin{lstlisting}
482function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n )
483 // Polynomial for outside contraction :
484 // n - 3x - ... - 3x^(n-1) + 2n x^(n) = 0
485 coeffs = zeros(1,n+1);
486 coeffs(1) = n
487 coeffs(2:n) = -3
488 coeffs(n+1) = 2 * n
489 p=poly(coeffs,"x","coeff")
490 r = roots(p , "e")
491 rminoc = min(abs(r))
492 rmaxoc = max(abs(r))
493 // Polynomial for inside contraction :
494 // - n - x - ... - x^(n-1) + 2n x^(n)= 0
495 coeffs = zeros(1,n+1);
496 coeffs(1) = -n
497 coeffs(2:n) = -1
498 coeffs(n+1) = 2 * n
499 p=poly(coeffs,"x","coeff")
500 r = roots(p , "e")
501 rminic = min(abs(r))
502 rmaxic = max(abs(r))
503 mprintf("%d & %f & %f & %f & %f\\\\\n", n, rminoc, rmaxoc, rminic, rmaxic)
504endfunction
505
506function drawfigure1 ( nbmax )
507 rminoctable = zeros(1,nbmax)
508 rmaxoctable = zeros(1,nbmax)
509 rminictable = zeros(1,nbmax)
510 rmaxictable = zeros(1,nbmax)
511 for n = 1 : nbmax
512 [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n )
513 rminoctable ( n ) = rminoc
514 rmaxoctable ( n ) = rmaxoc
515 rminictable ( n ) = rminic
516 rmaxictable ( n ) = rmaxic
517 end
518 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] )
519 f = gcf();
520 f.children.title.text = "Nelder-Mead caracteristic equation roots";
521 f.children.x_label.text = "Number of variables (n)";
522 f.children.y_label.text = "Roots of the caracteristic equation";
523 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]);
524 f.children.children(1).legend_location="in_lower_right";
525 for i = 1:4
526 mypoly = f.children.children(2).children(i);
527 mypoly.foreground=i;
528 mypoly.line_style=i;
529 end
530 xs2png(0,"neldermead-roots.png");
531endfunction
532\end{lstlisting}
533
534For the reflection characteristic equation, the roots all have
535a unity modulus.
536The minimum and maximum roots of the inside contraction ("ic" in the table) and
537outside contraction ("oc" in the table) steps are
538presented in table \ref{table-nm-roots-table}. These
539roots are presented graphically in figure \ref{fig-nm-roots}.
540One can see that the roots converge toward 1 when $n\rightarrow \infty$.
541
542
543\begin{figure}[htbp]
544\begin{center}
545\begin{tiny}
546\begin{tabular}{|l|l||l|l|l|}
547\hline
548$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}$ \\
549\hline
5501 & 0.500000 & 0.500000 & 0.500000 & 0.500000\\
5512 & 0.707107 & 0.707107 & 0.593070 & 0.843070\\
5523 & 0.776392 & 0.829484 & 0.734210 & 0.927534\\
5534 & 0.817185 & 0.865296 & 0.802877 & 0.958740\\
5545 & 0.844788 & 0.888347 & 0.845192 & 0.973459\\
5556 & 0.864910 & 0.904300 & 0.872620 & 0.981522\\
5567 & 0.880302 & 0.916187 & 0.892043 & 0.986406\\
5578 & 0.892487 & 0.925383 & 0.906346 & 0.989584\\
5589 & 0.902388 & 0.932736 & 0.917365 & 0.991766\\
55910 & 0.910599 & 0.938752 & 0.926070 & 0.993329\\
56011 & 0.917524 & 0.943771 & 0.933138 & 0.994485\\
56112 & 0.923446 & 0.948022 & 0.938975 & 0.995366\\
56213 & 0.917250 & 0.951672 & 0.943883 & 0.996051\\
56314 & 0.912414 & 0.954840 & 0.948062 & 0.996595\\
56415 & 0.912203 & 0.962451 & 0.951666 & 0.997034\\
56516 & 0.913435 & 0.968356 & 0.954803 & 0.997393\\
56617 & 0.915298 & 0.972835 & 0.957559 & 0.997691\\
56718 & 0.917450 & 0.976361 & 0.959999 & 0.997940\\
56819 & 0.919720 & 0.979207 & 0.962175 & 0.998151\\
56920 & 0.922013 & 0.981547 & 0.964127 & 0.998331\\
57021 & 0.924279 & 0.983500 & 0.965888 & 0.998487\\
57122 & 0.926487 & 0.985150 & 0.967484 & 0.998621\\
57223 & 0.928621 & 0.986559 & 0.968938 & 0.998738\\
57324 & 0.930674 & 0.987773 & 0.970268 & 0.998841\\
57425 & 0.932640 & 0.988826 & 0.971488 & 0.998932\\
57526 & 0.934520 & 0.989747 & 0.972613 & 0.999013\\
57627 & 0.936316 & 0.990557 & 0.973652 & 0.999085\\
57728 & 0.938030 & 0.991274 & 0.974616 & 0.999149\\
57829 & 0.939666 & 0.991911 & 0.975511 & 0.999207\\
57930 & 0.941226 & 0.992480 & 0.976346 & 0.999259\\
58031 & 0.942715 & 0.992991 & 0.977126 & 0.999306\\
58132 & 0.944137 & 0.993451 & 0.977856 & 0.999348\\
58233 & 0.945495 & 0.993867 & 0.978540 & 0.999387\\
58334 & 0.946793 & 0.994244 & 0.979184 & 0.999423\\
58435 & 0.948034 & 0.994587 & 0.979791 & 0.999455\\
58536 & 0.949222 & 0.994900 & 0.980363 & 0.999485\\
58637 & 0.950359 & 0.995187 & 0.980903 & 0.999513\\
58738 & 0.951449 & 0.995450 & 0.981415 & 0.999538\\
58839 & 0.952494 & 0.995692 & 0.981900 & 0.999561\\
58940 & 0.953496 & 0.995915 & 0.982360 & 0.999583\\
59045 & 0.957952 & 0.996807 & 0.984350 & 0.999671\\
59150 & 0.961645 & 0.997435 & 0.985937 & 0.999733\\
59255 & 0.964752 & 0.997894 & 0.987232 & 0.999779\\
59360 & 0.967399 & 0.998240 & 0.988308 & 0.999815\\
59465 & 0.969679 & 0.998507 & 0.989217 & 0.999842\\
59570 & 0.971665 & 0.998718 & 0.989995 & 0.999864\\
59675 & 0.973407 & 0.998887 & 0.990669 & 0.999881\\
59780 & 0.974949 & 0.999024 & 0.991257 & 0.999896\\
59885 & 0.976323 & 0.999138 & 0.991776 & 0.999908\\
59990 & 0.977555 & 0.999233 & 0.992236 & 0.999918\\
60095 & 0.978665 & 0.999313 & 0.992648 & 0.999926\\
601100 & 0.979671 & 0.999381 & 0.993018 & 0.999933\\
602\hline
603\end{tabular}
604\end{tiny}
605\end{center}
606\caption{Roots of the caracteristic equations of the Nelder-Mead method with standard
607coefficients. (Some results are not displayed to make the table fit the page).}
608\label{table-nm-roots-table}
609\end{figure}
610
611\begin{figure}
612\begin{center}
613\includegraphics[width=10cm]{neldermead-roots.png}
614\end{center}
615\caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with standard
616coefficients -- R-max-IC is the maximum of the modulus of the root of the Inside Contraction steps}
617\label{fig-nm-roots}
618\end{figure}
619
620\subsection{With variable parameters}
621
622In this section, we analyse the roots of the caracteristic
623equation with \emph{variable} inside and outside contraction
624coefficients.
625
626\emph{Outside contraction} If the outside contraction step is repeatedly performed
627with variable $\mu_{oc} > 0$, then
628
629\begin{eqnarray}
630\bv^{(k+n)} &=& \overline{\bold{v}}^{(k)}
631+ \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\
632&=& (1 + \mu_{oc} ) \overline{\bold{v}}^{(k)} - \mu_{oc} \bv^{(k)}
633\end{eqnarray}
634By plugging the definition of the centroid into the previous equality, one
635find the recurrence formula
636
637\begin{eqnarray}
638n \bv^{(k+n)} - (1 + \mu_{oc} ) \bv^{(k+1)} - \ldots - (1 + \mu_{oc} ) \bv^{(k+n-1)} + n\mu_{oc}\bv^{(k)} = 0
639\end{eqnarray}
640
641The associated caracteristic equation is
642
643\begin{eqnarray}
644\label{recurrence-variable}
645n \mu^n - (1 + \mu_{oc} ) \mu^{n-1} - \ldots - (1 + \mu_{oc} ) \mu + n \mu_{oc} = 0.
646\end{eqnarray}
647
648\emph{Inside contraction} We suppose that the inside contraction step is repeatedly performed
649with $-1 < \mu_{ic} < 0$. The caracteristic equation is the same as \ref{recurrence-variable},
650but it is here studied in the range $\mu_{ic}\in]-1, 0[$.
651
652To study the convergence of the method, one simply have
653to study the roots of equation \ref{recurrence-variable}, where
654the range $]-1,0[$ corresponds to the inside contraction (with $-1/2$
655as the standard value) and where the range $]0,\mu_r[$ corresponds to the outside contraction (with $1/2$
656as the standard value).
657
658In the following Scilab script, one computes the minimum and
659maximum root of the caracteristic equation, with $n$ fixed.
660
661\lstset{language=Scilab}
662\lstset{numbers=left}
663\lstset{basicstyle=\footnotesize}
664\lstset{keywordstyle=\bfseries}
665\begin{lstlisting}
666//
667// rootsvariable --
668// Compute roots of the caracteristic equation
669// of Nelder-Mead with variable coefficient mu.
670// Polynomial for outside/inside contraction :
671// n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0
672//
673function [rmin , rmax] = rootsvariable ( n , mu )
674 coeffs = zeros(1,n+1);
675 coeffs(1) = n * mu
676 coeffs(2:n) = -(1+mu)
677 coeffs(n+1) = n
678 p=poly(coeffs,"x","coeff")
679 r = roots(p , "e")
680 rmin = min(abs(r))
681 rmax = max(abs(r))
682 mprintf("%f & %f & %f\\\\\n", mu, rmin, rmax)
683endfunction
684
685function drawfigure_variable ( n , nmumax )
686 rmintable = zeros(1,nmumax)
687 rmaxtable = zeros(1,nmumax)
688 mutable = linspace ( -1 , 1 , nmumax )
689 for index = 1 : nmumax
690 mu = mutable ( index )
691 [rmin , rmax ] = rootsvariable ( n , mu )
692 rmintable ( index ) = rmin
693 rmaxtable ( index ) = rmax
694 end
695 plot2d ( mutable , [ rmintable' , rmaxtable' ] )
696 f = gcf();
697 pause
698 f.children.title.text = "Nelder-Mead caracteristic equation roots";
699 f.children.x_label.text = "Contraction coefficient";
700 f.children.y_label.text = "Roots of the caracteristic equation";
701 captions(f.children.children.children,["R-max","R-min"]);
702 f.children.children(1).legend_location="in_lower_right";
703 for i = 1:2
704 mypoly = f.children.children(2).children(i);
705 mypoly.foreground=i;
706 mypoly.line_style=i;
707 end
708 xs2png(0,"neldermead-roots-variable.png");
709endfunction
710
711\end{lstlisting}
712
713The figure \ref{fig-nm-roots-variable} presents the minimum
714and maximum modulus of the roots of the caracteristic equation
715with $n=10$. The result is that when $\mu_{oc}$ is close to 0, the
716minimum root has a modulus close to 0. The maximum root remains close to
7171, whatever the value of the contraction coefficient.
718This result would mean that either modifying the contraction
719coefficient has no effect (because the maximum modulus of the roots
720is close to 1) or diminishing the contraction coefficient should
721improve the convergence speed (because the minimum modulus of the
722roots gets closer to 0). This is the expected result because
723the more the contraction coefficient is close to 0, the more the new
724vertex is close to 0, which is, in our particular situation, the
725global minimizer. No general conclusion can be drawn from this single
726experiment.
727
728\begin{figure}
729\begin{center}
730\includegraphics[width=10cm]{neldermead-roots-variable.png}
731\end{center}
732\caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with variable
733contraction coefficient and $n=10$ -- R-max is the maximum of the modulus of the root of the
734caracteristic equation}
735\label{fig-nm-roots-variable}
736\end{figure}
737
738\section{Numerical experiments}
739
740In this section, we present some numerical experiments
741with the Nelder-Mead algorithm.
742
743\subsection{Quadratic function}
744
745The function we try to minimize is the following quadratic
746in 2 dimensions
747
748\begin{eqnarray}
749f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2
750\end{eqnarray}
751
752The stopping criteria is based on the relative size of the simplex
753with respect to the size of the initial simplex
754
755\begin{eqnarray}
756\sigma(S) < tol \times \sigma(S_0)
757\end{eqnarray}
758
759The initial simplex is computed from the coordinate axis and the unit length.
760The numerical results are presented in table \ref{fig-nm-numexp1-table}.
761
762\begin{figure}[htbp]
763\begin{center}
764\begin{tiny}
765\begin{tabular}{|l|l|}
766\hline
767Iterations & 65 \\
768Function Evaluations & 127 \\
769$x_0$ & $(2.0,2.0)$ \\
770Relative tolerance on simplex size & $10^{-8}$ \\
771Exact $x^\star$ & $(0.,0.)$\\
772Computed $x^\star$ & $(7.3e-10 , -2.5e-9)$\\
773Computed $f(x^\star)$ & $8.7e-18$\\
774\hline
775\end{tabular}
776\end{tiny}
777\end{center}
778\caption{Numerical experiment with Nelder-Mead method on the quadratic function
779$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$}
780\label{fig-nm-numexp1-table}
781\end{figure}
782
783
784The various simplices generated during the iterations are
785presented in figure \ref{fig-nm-numexp1-historysimplex}.
786The method use reflections in the early iterations. Then there
787is no possible improvment using reflections and shrinking is necessary.
788
789\begin{figure}
790\begin{center}
791\includegraphics[width=10cm]{quad2bis-nm-simplexcontours.png}
792\end{center}
793\caption{Nelder-Mead numerical experiment -- history of simplex}
794\label{fig-nm-numexp1-historysimplex}
795\end{figure}
796
797The figure \ref{fig-nm-numexp1-sigma} presents the history of the oriented
798length of the simplex. The length is updated at each iteration, which
799generates a continuous evolution of the length, compared to the
800step-by-step evolution of the simplex with the Spendley et al. algorithm.
801
802\begin{figure}
803\begin{center}
804\includegraphics[width=10cm]{quad2bis-nm-history-sigma.png}
805\end{center}
806\caption{Nelder-Mead numerical experiment -- history of length of simplex}
807\label{fig-nm-numexp1-sigma}
808\end{figure}
809
810The convergence is quite fast in this case, since less than 60 iterations
811allow to get a function value lower than $10^{-15}$, as shown in
812figure \ref{fig-nm-numexp1-logfopt}.
813
814\begin{figure}
815\begin{center}
816\includegraphics[width=10cm]{quad2bis-nm-history-logfopt.png}
817\end{center}
818\caption{Nelder-Mead numerical experiment -- history of logarithm of function}
819\label{fig-nm-numexp1-logfopt}
820\end{figure}
821
822\subsection{Badly scaled quadratic function}
823
824The function we try to minimize is the following quadratic
825in 2 dimensions
826\begin{eqnarray}
827\label{quadratic-nm-function2}
828f(x_1,x_2) = a x_1^2 + x_2^2,
829\end{eqnarray}
830where $a>0$ is a chosen scaling parameter.
831The more $a$ is large, the more difficult the problem is
832to solve with the simplex algorithm.
833
834We set the maximum number of function evaluations to 400.
835The initial simplex is computed from the coordinate axis and the unit length.
836
837The numerical results are presented in table \ref{fig-nm-numexp2-table},
838where the experiment is presented for $a=100$. One can check that the
839number of function evaluation (161 function evaluations) is much lower than the number
840for the fixed shape Spendley et al. method (400 function evaluations)
841and that the function value at optimum is very accurate ($f(x^\star)\approx 1.e-17$
842compared to Spendley's et al. $f(x^\star) \approx 0.08$).
843
844\begin{figure}[h]
845\begin{center}
846\begin{tiny}
847\begin{tabular}{|l|l|l|}
848\hline
849& Nelder-Mead & Spendley et al.\\
850\hline
851Iterations & 83 & 340 \\
852Function Evaluations & 161 & 400 \\
853$a$ & $100.0$ & - \\
854$x_0$ & $(10.0,10.0)$ & - \\
855Relative tolerance on simplex size & - \\
856Exact $x^\star$ & $(0.,0.)$ & -\\
857Computed $x^\star$ & $(2.e-10, -3.e-9)$& $(0.001,0.2)$\\
858Computed $f(x^\star)$ & $1.e-17$ & $0.08$\\
859\hline
860\end{tabular}
861\end{tiny}
862\end{center}
863\caption{Numerical experiment with Nelder-Mead method on a badly scaled quadratic function.
864The variable shape Nelder-Mead algorithm improves the accuracy of the result compared
865to the fixed shaped Spendley et al. method.}
866\label{fig-nm-numexp2-table}
867\end{figure}
868
869In figure \ref{fig-nm-numexp2-scaling}, we analyse the
870behaviour of the method with respect to scaling.
871We check that the method behave very smoothly, with a very
872small number of additionnal function evaluations when the
873scaling deteriorates. This shows how much the Nelder-Mead algorithms
874improves over the Spendley et al. method.
875
876\begin{figure}[htbp]
877\begin{center}
878\begin{tiny}
879\begin{tabular}{|l|l|l|l|}
880\hline
881$a$ & Function evaluations & Computed $f(x^\star)$ & Computed $x^\star$\\
882$1.0$ & 139 & $8.0e-18$ & $(2.e-9 -1.e-9)$\\
883$10.0$ & 151 & $7.0e-17$ & $(5.e-10 2.e-9)$\\
884$100.0$ & 161 & $1.0e-17$ & $(2.e-10 -3.e-9)$ \\
885$1000.0$ & 165 & $1.0e-17$ & $(-1.e-010 9.e-10)$\\
886$10000.0$ & 167 & $3.0e-17$ & $(5.0e-11,-1.0e-10)$ \\
887\hline
888\end{tabular}
889\end{tiny}
890\end{center}
891\caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function}
892\label{fig-nm-numexp2-scaling}
893\end{figure}
894
895\subsection{Sensitivity to dimension}
896
897In this section, we try to reproduce the result
898presented by Han and Neumann \cite{HanNeumann2006}, which shows that the
899convergence rate of the Nelder-Mead algorithms rapidly
900deteriorates when the number of variables increases.
901The function we try to minimize is the following quadratic
902in n-dimensions
903\begin{eqnarray}
904\label{quadratic-function3}
905f(\bold{x}) = \sum_{i=1,n} x_i^2.
906\end{eqnarray}
907
908The initial simplex is computed from the coordinate axis and the unit length.
909The initial guess is at 0 so that the first vertex is the origin ;
910this vertex is never updated during the iterations.
911
912The figure \ref{fig-nm-numexp3-dimension} presents the results of this
913experiment for $n=1,19$.
914
915During the iterations, no shrink steps are performed. The
916algorithm performs reflections, inside and outside contractions.
917The figure \ref{fig-nm-numexp3-steps} shows the detailed sequence of
918iterations for $n=10$. One can see that there is no general
919pattern for the iterations. One can check, however, that there
920are never no more than $n$ consecutive reflection steps, which is
921as expected. After one or more contractions, the reflection
922steps move the worst vertices toward better function values.
923But there are only $n+1$ vertices so that the $n$ worst
924vertices are moved in at most $n$ reflection steps.
925
926\begin{figure}[htbp]
927\begin{center}
928\begin{tiny}
929\begin{verbatim}
930I 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
931R 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
932R R I R I R I R R R R R R R I R R R R I R I I R I R I I I R R I I I R
933R R I R R I R R R R R R I R I R R R R R I R R O R R I O I O R R R R I
934I I O R I R R R R R R I I I R R I I R R R O R I I R R R I R I I O I R
935I R R O I I R R R R I R R O I R R O R I R I R I R R I R I R R R I I I
936I I O R R R R I I I R R R I I I R R R I I I I R R R R I I R R R R I R
937R R I O I R R I I R R R R O I R I I R R R R R R O R R R O I R R I I I
938I O R I I I R I I I I R R I I R R I R R R R R R I R R I I R R O R I I
939O R I R O O R O I I R I I I R I I R R R R R R R R R R R R I R R O I R
940I O I R I I I I R I I R I I R I R O R I O R I R I R R R O R I R R R I
941I R I R R R I R I R R R R I I R R I R R R R I I R R R R I I R I R I I
942O I R I I R R R R R R R R I O I R R I I I R I R I I I I R R R R I R R
943I R I R R R R I I R R R I I I I R I I I I R I R R I R I O R R R I R I
944O I R R I I R R I R R R R O R R R R I O R R R I R I I I I R I R R R R
945R 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
946I 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
947R R R R I I I R R
948\end{verbatim}
949\end{tiny}
950\end{center}
951\caption{Numerical experiment with Nelder-Mead method on a generalized
952quadratic function - steps of the algorithm : I = inside contraction, O = outside contraction,
953R = reflection, S = shrink}
954\label{fig-nm-numexp3-steps}
955\end{figure}
956
957The figure \ref{fig-nm-numexp3-nbsteps} presents the number and
958the kind of steps performed during the iterations for $n=1,19$.
959It appears that the number of shrink steps and expansion steps is zero, as expected.
960More interesting is that the number of reflection is
961larger than the number of inside contraction when $n$
962is large. The number of outside contraction is allways
963the smallest in this case.
964
965\begin{figure}[htbp]
966\begin{center}
967\begin{tiny}
968\begin{tabular}{|l|l|l|l|l|l|}
969\hline
970$n$ & \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\
971 & & & Contractions & Contractions & \\
972\hline
9731 & 0 & 0 & 27 & 0 & 0\\
9742 & 0 & 0 & 5 & 49 & 0\\
9753 & 54 & 0 & 45 & 36 & 0\\
9764 & 93 & 0 & 74 & 34 & 0\\
9775 & 123 & 0 & 101 & 33 & 0\\
9786 & 170 & 0 & 122 & 41 & 0\\
9797 & 202 & 0 & 155 & 35 & 0\\
9808 & 240 & 0 & 178 & 41 & 0\\
9819 & 267 & 0 & 205 & 40 & 0\\
98210 & 332 & 0 & 234 & 38 & 0\\
98311 & 381 & 0 & 267 & 36 & 0\\
98412 & 476 & 0 & 299 & 32 & 0\\
98513 & 473 & 0 & 316 & 42 & 0\\
98614 & 545 & 0 & 332 & 55 & 0\\
98715 & 577 & 0 & 372 & 41 & 0\\
98816 & 635 & 0 & 396 & 46 & 0\\
98917 & 683 & 0 & 419 & 52 & 0\\
99018 & 756 & 0 & 445 & 55 & 0\\
99119 & 767 & 0 & 480 & 48 & 0\\
992\hline
993\end{tabular}
994\end{tiny}
995\end{center}
996\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function -- number
997and kinds of steps performed}
998\label{fig-nm-numexp3-nbsteps}
999\end{figure}
1000
1001One can check that the number of function evaluations
1002increases approximately linearily with the dimension of the problem in
1003figure \ref{fig-nm-numexp3-fvn}. A rough rule of thumb is that, for $n=1,19$,
1004the number of function evaluations is equal to $100n$.
1005
1006\begin{figure}[htbp]
1007\begin{center}
1008\begin{tiny}
1009\begin{tabular}{|l|l|l|l|}
1010\hline
1011$n$ & Function evaluations & Iterations & $\rho(S_0,n)$\\
1012\hline
10131 & 56 & 28 & 0.5125321059829373\\
10142 & 111 & 55 & 0.71491052830553248\\
10153 & 220 & 136 & 0.87286283470760984\\
10164 & 314 & 202 & 0.91247307800713973\\
10175 & 397 & 258 & 0.93107793607270162\\
10186 & 503 & 334 & 0.94628781077508028\\
10197 & 590 & 393 & 0.95404424343636474\\
10208 & 687 & 460 & 0.96063768057900478\\
10219 & 767 & 513 & 0.96471820169933631\\
102210 & 887 & 605 & 0.97000569588245511\\
102311 & 999 & 685 & 0.97343652480535203\\
102412 & 1151 & 808 & 0.97745310525741003\\
102513 & 1203 & 832 & 0.97803465666405531\\
102614 & 1334 & 933 & 0.98042500139065414\\
102715 & 1419 & 991 & 0.98154526298964495\\
102816 & 1536 & 1078 & 0.98305435726547608\\
102917 & 1643 & 1155 & 0.98416149958157839\\
103018 & 1775 & 1257 & 0.98544909490809807\\
103119 & 1843 & 1296 & 0.98584701106083183\\
1032\hline
1033\end{tabular}
1034\end{tiny}
1035\end{center}
1036\caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function}
1037\label{fig-nm-numexp3-dimension}
1038\end{figure}
1039
1040\begin{figure}
1041\begin{center}
1042\includegraphics[width=10cm]{neldermead-dimension-nfevals.png}
1043\end{center}
1044\caption{Nelder-Mead numerical experiment -- number of function evaluations
1045depending on the number of variables}
1046\label{fig-nm-numexp3-fvn}
1047\end{figure}
1048
1049The figure \ref{fig-nm-numexp3-rho} presents the rate of convergence
1050depending on the number of variables. The figure shows that
1051the rate of convergence rapidly gets close to 1 when the number
1052of variables increases. That shows that the rate of convergence
1053is slower and slower as the number of variables increases, as
1054explained by Han \& Neumann.
1055
1056\begin{figure}
1057\begin{center}
1058\includegraphics[width=10cm]{neldermead-dimension-rho.png}
1059\end{center}
1060\caption{Nelder-Mead numerical experiment -- rate of convergence
1061depending on the number of variables}
1062\label{fig-nm-numexp3-rho}
1063\end{figure}
1064
1065\subsection{O'Neill test cases}
1066
1067In this section, we present the results by O'Neill, who
1068implemented a fortran 77 version of the Nelder-Mead algorithm
1069\cite{O'Neill1971AAF}.
1070
1071The O'Neill implementation of the Nelder-Mead algorithm has the following
1072particularities
1073\begin{itemize}
1074\item the initial simplex is computed from the axes and a (single) length,
1075\item the stopping rule is based on variance (not standard deviation) of function value,
1076\item the expansion is greedy, i.e. the expansion point is accepted if it is better than the lower point,
1077\item an automatic restart is performed if a factorial test shows that the
1078computed optimum is greater than a local point computed with a relative
1079epsilon equal to 1.e-3.
1080\end{itemize}
1081
1082The following tests are presented by O'Neill :
1083
1084\begin{itemize}
1085\item Rosenbrock's parabolic valley \cite{citeulike:1903787}
1086\begin{eqnarray}
1087\label{nm-oneill-rosenbrock}
1088f(x_1,x_2) = 100(x_2 - x_1^2)^2 + (1-x_1)^2
1089\end{eqnarray}
1090with starting point $(x_1,x_2) = (-1.2,1.0)$
1091\item Powell's quartic function \cite{Powell08011962}
1092\begin{eqnarray}
1093\label{nm-oneill-powell}
1094f(x_1,x_2,x_3,x_4) = (x_1 + 10x_2)^2 + 5 ( x_3 - x_4)^2 + (x_2 - 2x_3)^4 + 10 (x_1 - x_4)^4
1095\end{eqnarray}
1096with starting point $(x_1,x_2,x_3,x_4) = (3,-1,0,1)$
1097\item Fletcher and Powell's helical valley \cite{R.Fletcher08011963}
1098\begin{eqnarray}
1099\label{nm-oneill-fletcherpowell}
1100f(x_1,x_2,x_3) = 100\left(x_3 + 10\theta(x_1,x_2)\right)^2
1101+ \left(\sqrt{x_1^2 + x_2^2} - 1\right)^2 + x_3^2
1102\end{eqnarray}
1103where
1104\begin{eqnarray}
1105\label{nm-oneill-fletcherpowelltheta}
11062\pi \theta(x_1,x_2) &=& \arctan(x_2,x_1), x_1>0\\
1107&=& \pi + \arctan(x_2,x_1), x_1<0\\
1108\end{eqnarray}
1109with starting point $(x_1,x_2,x_3) = (-1,0,0)$. Note
1110that since $\arctan(0/0)$ is not defined neither
1111the function $f$ on the line $(0,0,x_3)$. This line is excluded
1112by assigning a very large value to the function.
1113\item the sum of powers
1114\begin{eqnarray}
1115\label{nm-oneill-powers}
1116f(x_1,\ldots,x_{10}) = \sum_{i=1,10} x_i^4
1117\end{eqnarray}
1118with starting point $(x_1,\ldots,x_{10}) = (1,\ldots,1)$
1119\end{itemize}
1120
1121The parameters are set to
1122
1123\begin{itemize}
1124\item $REQMIN=10^{-16}$, the absolute tolerance on the variance of the function
1125values in the simplex,
1126\item $STEP = 1.0$, the absolute side length of the initial simplex,
1127\item $ICOUNT$, the maximum number of function evaluations.
1128\end{itemize}
1129
1130The table \ref{fig-nm-oneill-table} presents the results which were
1131computed by O'Neill compared with our software.
1132For most experiments, the results are very close in terms of
1133number of function evaluations.
1134The problem \#4 exhibits a completely different behaviour than the
1135results presented by O'Neill. For us, the maximum number of function evaluations
1136is reached (i.e. 1000 function evaluations), whereas for O'Neill, the algorithm
1137is restarted and gives the result with 474 function evaluations.
1138We did not find any explanation for this behaviour. A possible cause of
1139difference may be the floating point system which are different and may
1140generate different simplices in the algorithms.
1141Although the CPU times cannot be
1142compared (the article is dated 1972 !), let's mention
1143that the numerical experiment were performed by O'Neill
1144on a ICL 4-50 where the two problem 1 and 2 were solved in 3.34 seconds
1145and the problems 3 and 4 were solved in 22.25 seconds.
1146
1147
1148\begin{figure}[htbp]
1149\begin{center}
1150\begin{tiny}
1151\begin{tabular}{|l|l|l|l|l|l|l|}
1152\hline
1153Author & Problem & Function & No. of Restarts & Function Value & Iterations & CPU\\
1154& & Evaluations & & & & Time \\
1155\hline
1156O'Neill & 1 & 148 & 0 & 3.19 e-9 & ? & ? \\
1157Baudin & 1 & 149 & 0 & 1.15 e-7 & 79 & 0.238579 \\
1158\hline
1159O'Neill & 2 & 209 & 0 & 7.35 e-8 & ? & ? \\
1160Baudin & 2 & 224 & 0 & 1.07 e-8 & 126 & 0.447958 \\
1161\hline
1162O'Neill & 3 & 250 & 0 & 5.29 e-9 & ? & ? \\
1163Baudin & 3 & 255 & 0 & 4.56 e-8 & 137 & 0.627493 \\
1164\hline
1165O'Neill & 4 & 474 & 1 & 3.80 e-7 & ? & ? \\
1166Baudin & 4 & 999 & 0 & 5.91 e-9 & 676 & - \\
1167\hline
1168\end{tabular}
1169\end{tiny}
1170\end{center}
1171\caption{Numerical experiment with Nelder-Mead method on O'Neill test cases - O'Neill results and our results}
1172\label{fig-nm-oneill-table}
1173\end{figure}
1174
1175\subsection{Convergence to a non stationnary point}
1176
1177In this section, we analyse the Mc Kinnon counter example
1178from \cite{589109}. We show the behavior of the
1179Nelder-Mead simplex method for a family of examples which cause the
1180method to converge to a nonstationnary point.
1181
1182Consider a simplex in two dimensions with vertices at 0 (i.e. the origin),
1183$v^{(n+1)}$ and $v^{(n)}$. Assume that
1184
1185\begin{eqnarray}
1186\label{mckinnon-sortedfv}
1187f(0) < f(v^{(n+1)}) < f(v^{(n)}).
1188\end{eqnarray}
1189
1190The centroid of the simplex is $\overline{v} = v^{(n+1)}/2$, the midpoint
1191of the line joining the best and second vertex. The refected
1192point is then computed as
1193
1194\begin{eqnarray}
1195\label{mckinnon-reflection}
1196r^{(n)} = \overline{v} + \rho ( \overline{v} - v^{(n)} ) = v^{(n+1)} - v^{(n)}
1197\end{eqnarray}
1198
1199Assume that the reflection point $r^{(n)}$ is rejected, i.e. that
1200$f(v^{(n)}) < f(r^{(n)})$. In this case, the inside contraction
1201step is taken and the point $v^{(n+2)}$ is computed using the
1202reflection factor $-\gamma = -1/2$ so that
1203
1204\begin{eqnarray}
1205\label{mckinnon-insidecontraction}
1206v^{(n+2)} = \overline{v} - \gamma ( \overline{v} - v^{(n)} ) = \frac{1}{4} v^{(n+1)} - \frac{1}{2} v^{(n)}
1207\end{eqnarray}
1208
1209Assume then that the inside contraction point is accepted, i.e. $f(v^{(n+2)}) < f(v^{(n+1)})$.
1210If this sequence of steps repeats, the simplices are subject to the
1211following linear reccurence formula
1212
1213\begin{eqnarray}
1214\label{mckinnon-reccurence}
12154 v^{(n+2)} - v^{(n+1)} + 2 v^{(n)} = 0
1216\end{eqnarray}
1217
1218Their general solutions are of the form
1219
1220\begin{eqnarray}
1221v^{(n)} = \lambda_1^k a_1 + \lambda_2^k a_2
1222\end{eqnarray}
1223where ${\lambda_i}_{i=1,2}$ are the roots of the characteristic equation and
1224${a_i}_{i=1,2} \in \RR^n$.
1225The caracteristic equation is
1226
1227\begin{eqnarray}
1228\label{mckinnon-caracequation}
12294 \lambda^2 - \lambda + 2 \lambda = 0
1230\end{eqnarray}
1231
1232and has the roots
1233
1234\begin{eqnarray}
1235\label{mckinnon-roots}
1236\lambda_1 = \frac{1 + \sqrt{33}}{8}\approx 0.84307,
1237\qquad \lambda_2 = \frac{1 - \sqrt{33}}{8} \approx -0.59307
1238\end{eqnarray}
1239
1240After Mc Kinnon has presented the computation of the roots of the
1241caracteristic equation, he presents a special initial simplex
1242for which the simplices degenerates because of repeated failure by inside
1243contraction (RFIC in his article). Consider the initial simplex with
1244vertices $v^{(0)} = (1,1)$ and $v^{(1)} = (\lambda_1,\lambda_2)$ and
1245$0$. If follows that the particular solution for these initial
1246conditions is $v^{(n)} = (\lambda_1^n,\lambda_2^n)$.
1247
1248Consider the function $f(x,y)$ given by
1249
1250\begin{eqnarray}
1251\label{mckinnon-function}
1252f(x,y) &=& \theta \phi |x|^\tau + y + y^2, \qquad x\leq 0,\\
1253&=&\theta x^\tau + y + y^2, \qquad x\geq 0.
1254\end{eqnarray}
1255
1256where $\theta$ and $\phi$ are positive constants. Note that $(0,-1)$
1257is a descent direction from the origin $(0,0)$ and that f is stricly convex
1258provided $\tau>1$. $f$ has continuous first derivatives if $\tau>1$, continuous second
1259derivatives if $\tau>2$ and continous third derivatives if $\tau>3$.
1260
1261Mc Kinnon computed the conditions on $\theta,\phi$ and $\tau$
1262so that the function values are ordered as expected, i.e. so that the
1263reflection step is rejected and the inside contraction is accepted.
1264Examples of values which makes these equations hold are as follows :
1265for $\tau=1$, $\theta=15$ and $\phi = 10$,
1266for $\tau=2$, $\theta=6$ and $\phi = 60$ and
1267for $\tau=3$, $\theta=6$ and $\phi = 400$.
1268
1269We consider here the more regular case $\tau=3$, $\theta=6$
1270and $\phi = 400$, i.e. the function is defined by
1271
1272\begin{eqnarray}
1273\label{mckinnon-function3}
1274f(x,y) &=& - 2400 x^3 + y + y^2, \qquad x\leq 0, \\
1275&=& 6 x^3 + y + y^2, \qquad x\geq 0.
1276\end{eqnarray}
1277
1278The figure \ref{fig-nm-numexp-mckinnon} shows the contour plot of this function and the first
1279steps of the Nelder-Mead method.
1280
1281
1282\begin{figure}
1283\begin{center}
1284\includegraphics[width=10cm]{mckinnon-history-simplex.png}
1285\end{center}
1286\caption{Nelder-Mead numerical experiment -- Mc Kinnon example for convergence toward
1287a non stationnary point}
1288\label{fig-nm-numexp-mckinnon}
1289\end{figure}
1290
1291\subsection{Han counter examples}
1292
1293In his Phd thesis \cite{Han2000}, Han presents two counter examples
1294in which the Nelder-Mead algorithm degenerates by applying repeatedly
1295the inside contraction step.
1296
1297\subsubsection{First counter example}
1298
1299The first counter example is based on the function
1300
1301\begin{eqnarray}
1302\label{han-function1}
1303f(x,y) &=& x^2 + y ( y + 2 ) ( y - 0.5 ) ( y - 2 )
1304\end{eqnarray}
1305
1306This function is nonconvex, bounded below and has bounded level
1307sets. The initial simplex is chosen as $S_0 = [(0.,-1),(0,1),(1,0)]$.
1308Han prooves that the Nelder-Mead algorithm generates a sequence of simplices
1309$S_k = [(0.,-1),(0,1),(\frac{1}{2^k},0)]$.
1310
1311The figure \ref{fig-nm-numexp-han1} presents the isovalues and the
1312simplices during the steps of the Nelder-Mead algorithm.
1313Note that the limit simplex contains no minimizer of the function.
1314The failure is caused by repeated inside contractions.
1315
1316\begin{figure}
1317\begin{center}
1318\includegraphics[width=10cm]{han1-history-simplex.png}
1319\end{center}
1320\caption{Nelder-Mead numerical experiment -- Han example \#1 for convergence toward
1321a non stationnary point}
1322\label{fig-nm-numexp-han1}
1323\end{figure}
1324
1325\subsubsection{Second counter example}
1326
1327The second counter example is based on the function
1328
1329\begin{eqnarray}
1330\label{han-function2}
1331f(x,y) &=& x^2 + \rho(y)
1332\end{eqnarray}
1333where $\rho$ is a continuous convex function with bounded level
1334sets which satisfies
1335\begin{eqnarray}
1336\label{han-function2-rho}
1337\rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\
1338& \geq & 0, \qquad \textrm{if} \qquad |y|> 1.
1339\end{eqnarray}
1340The example given by Han for such a $\rho$ function is
1341\begin{eqnarray}
1342\label{han-function2-rho2}
1343\rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\
1344& = & y - 1, \qquad \textrm{if} \qquad y> 1, \\
1345& = & -y - 1, \qquad \textrm{if} \qquad y < -1.
1346\end{eqnarray}
1347
1348The initial simplex is chosen as $S_0 = [(0.,1/2),(0,-1/2),(1,0)]$.
1349Han prooves that the Nelder-Mead algorithm generates a sequence of simplices
1350$S_k = [(0.,1/2),(0,-1/2),(\frac{1}{2^k},0)]$.
1351
1352The figure \ref{fig-nm-numexp-han2} presents the isovalues and the
1353simplices during the steps of the Nelder-Mead algorithm.
1354The failure is caused by repeated inside contractions.
1355
1356\begin{figure}
1357\begin{center}
1358\includegraphics[width=10cm]{han2-history-simplex.png}
1359\end{center}
1360\caption{Nelder-Mead numerical experiment -- Han example \#2 for convergence toward
1361a non stationnary point}
1362\label{fig-nm-numexp-han2}
1363\end{figure}
1364
1365These two examples of non convergence show that the Nelder-Mead method may unreliable.
1366They also reveal that the Nelder-Mead method can generate simplices which collapse
1367into a degenerate simplex, by applying repeated inside contractions.
1368
1369\subsection{Torczon's numerical experiments}
1370
1371In her Phd Thesis \cite{Torczon89multi-directionalsearch}, Virginia Torczon
1372presents the multi-directionnal direct search algorithm. In order to analyse the
1373performances of her new algorithm, she presents some interesting numerical
1374experiments with the Nelder-Mead algorithm.
1375These numerical experiments are based on the collection of test problems \cite{355943},
1376published in the ACM by Moré, Garbow and Hillstrom in 1981.
1377These test problems are associated with varying number of variables.
1378In her Phd, Torczon presents numerical experiments with $n$ from 8
1379to 40.
1380The stopping rule is based on the relative size of the simplex.
1381The angle between the descent direction (given by the worst point and the centroid), and the
1382gradient of the function is computed when the algorithm is stopped.
1383Torczon shows that, when the tolerance on the relative simplex size is decreased, the
1384angle converges toward 90¬į. This fact is observed even for moderate
1385number of dimensions.
1386
1387In this section, we try to reproduce Torczon numerical experiments.
1388
1389All experiments are associated with the following sum of squares cost function
1390
1391\begin{eqnarray}
1392\label{torzcon-sumofsquares}
1393f(x) &=& \sum_{i=1,m} f_i(x)^2,
1394\end{eqnarray}
1395where $m\geq 1$ is the number of functions $f_i$ in the problem.
1396
1397The stopping criteria is based on the relative size of the
1398simplex and is the following
1399
1400\begin{eqnarray}
1401\label{torzcon-stopping}
1402\frac{1}{\Delta} \max_{i=1,n} \|v_i^k - v_0^k\| \leq \epsilon,
1403\end{eqnarray}
1404where $\Delta = \max( 1 , \|v_0^k\| )$. Decreasing the value of
1405$\epsilon$ allows to get smaller simplex sizes.
1406
1407\subsubsection{Penalty \#1}
1408The first test function is the \emph{Penalty \#1} function :
1409
1410\begin{eqnarray}
1411\label{torzcon-sumofsquares-case1}
1412f_i(x) &=& \sqrt{1.e-5}(x_i - 1), \qquad i=1,n\\
1413f_{n+1} & = & -\frac{1}{4} + \sum_{j=1,n} x_j^2.
1414\end{eqnarray}
1415
1416The initial guess is given by $x_0 = (x_{0,j})_{j=1,n}$ and
1417$x_{0,j} = j$ for $j=1,n$.
1418
1419The problem given by
1420Moré, Garbow and Hillstrom in \cite{355943} is associated with
1421the size $n=4$. The value of the cost function at the initial guess
1422$x_0 = (1,2,3,4)$ is $f(x_0) = 885.063$. The value of the function
1423at the optimum is given in \cite{355943} as $f(x^\star) = 2.24997d-5$.
1424
1425Torzcon shows an experiment with the Penalty \#1 test case and $n=8$.
1426For this particular case, the initial function value is $f(x_0) = 4.151406e4$.
1427The figure \ref{fig-nm-torczon-table} presents the results of these
1428experiments. The number of function evaluations is not the same
1429so that we can conclude that the algorithm may be different
1430variants of the Nelder-Mead algorithms. We were not able to
1431explain why the number of function evaluations is so different.
1432
1433\begin{figure}[htbp]
1434\begin{center}
1435\begin{tiny}
1436\begin{tabular}{|l|l|l|l|l|}
1437\hline
1438Author & Step & $f(v_0^star)$ & Function & Angle ($,^{\circ}$)\\
1439& Tolerance & & Evaluations & \\
1440\hline
1441Torzcon & 1.e-1 & 7.0355e-5 & 1605 & 89.396677792198 \\
1442Baudin & 1.e-1 & 8.2272e-5 & 530 & 87.7654 \\
1443\hline
1444Torzcon & 1.e-2 & 6.2912e-5 & 1605 & 89.935373548613 \\
1445Baudin & 1.e-2 & 7.4854e-5 & 1873 & 89.9253 \\
1446\hline
1447Torzcon & 1.e-3 & 6.2912e-5 & 3600 & 89.994626919197 \\
1448Baudin & 1.e-3 & 7.4815e-5 & 2135 & 90.0001 \\
1449\hline
1450Torzcon & 1.e-4 & 6.2912e-5 & 3670 & 89.999288284747 \\
1451Baudin & 1.e-4 & 7.481546e-5 & 2196 & 89.9991 \\
1452\hline
1453Torzcon & 1.e-5 & 6.2912e-5 & 3750 & 89.999931862232 \\
1454Baudin & 1.e-5 & 7.427212e-5 & 4626 & 89.999990 \\
1455\hline
1456\end{tabular}
1457\end{tiny}
1458\end{center}
1459\caption{Numerical experiment with Nelder-Mead method on Torczon test cases -
1460Torczon results and our results}
1461\label{fig-nm-torczon-table}
1462\end{figure}
1463
1464The figure \ref{fig-nm-numexp-torczon1} presents the
1465angle between the gradient of the function $-g_k$ and the search
1466direction $x_c - x_h$, where $x_c$ is the centroid of the best
1467points and $x_h$ is the worst (or high) vertex.
1468
1469\begin{figure}
1470\begin{center}
1471\includegraphics[width=10cm]{torczon_test1_angle.png}
1472\end{center}
1473\caption{Nelder-Mead numerical experiment -- Penalty \#1 function --
1474One can see that the angle between the gradient and the search direction
1475is very close to $90^{\circ}$, especially for large number of iterations.}
1476\label{fig-nm-numexp-torczon1}
1477\end{figure}
1478
1479The numerical experiment shows that the conditioning of the matrix
1480of simplex direction has an increasing condition number. This corresponds to the
1481fact that the simplex is increasingly distorted.
1482
1483\section{Conclusion}
1484
1485The main advantage of the Nelder-Mead algorithm over Spendley et al.
1486algorithm is that the shape of the simplex is dynamically updated.
1487That allows to get a reasonably fast convergence rate on badly scaled
1488quadratics, or more generally when the cost function is made
1489of a sharp valley. Nevertheless, the behaviour of the algorithm when the
1490dimension of the problem increases is disappointing : the more there are
1491variables, the more the algorithm is slow. In general, it is expected
1492that the number of function evaluations is roughly equal to $100n$.
1493
1494
diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex
new file mode 100644
index 0000000..335f142
--- /dev/null
+++ b/scilab_doc/neldermead/method-spendley.tex
@@ -0,0 +1,495 @@
1\chapter{Spendley's et al. method}
2
3\section{Analysis}
4
5The simplex algorithms are based on the iterative update of
6a \emph{simplex} made of $n+1$ points $S={x_i}_{i=1,n+1}$. Each point
7in the simplex is called a \emph{vertex} and is associated with
8a function value $f_i=f(x_i), i=1,n+1$.
9
10The vertices are sorted by increasing function values so that the
11\emph{best} vertex has index 1 and the \emph{worst} vertex
12has index $n+1$
13
14\begin{eqnarray}
15\label{sorted-vertices-fv}
16f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
17\end{eqnarray}
18
19The \emph{next-to-worst} vertex with index $n$ has a
20special role in simplex algorithms.
21
22The centroid of the simplex is the center of the vertices
23where the vertex with index $j=1,n+1$ has been
24excluded
25
26\begin{eqnarray}
27\label{centroid-generalized}
28\overline{x} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j}x_i
29\end{eqnarray}
30
31The first move of the algorithm is based on the centroid
32where the worst vertex with index $j=n+1$ has been excluded
33
34\begin{eqnarray}
35\label{centroid-worst}
36\overline{x} (n+1) = \frac{1}{n} \sum_{i=1,n}x_i
37\end{eqnarray}
38
39The algorithm attemps to replace one vertex
40$x_j$ by a new point $x(\mu,j)$ between the centroid
41$\overline{x}$ and the vertex $x_j$ and defined by
42\begin{eqnarray}
43\label{interpolate-generalized}
44x(\mu,j) = (1+\mu)\overline{x}(j) - \mu x_j
45\end{eqnarray}
46
47The Spendley et al. \cite{Spendley1962} algorithm makes use
48of one coefficient, the reflection $\rho>0$. The standard
49value of this coefficient is $\rho=1$.
50
51The first move of the algorithm is based on the reflection
52with respect to the worst point $x_{n+1}$ so that the reflection point is
53computed by
54
55\begin{eqnarray}
56\label{interpolate-worst}
57x(\rho,n+1) = (1+\rho)\overline{x}(n+1) - \rho x_{n+1}
58\end{eqnarray}
59
60The algorithm first computes the reflection point
61with respect to the worst point excluded with $x_r=x(\rho,n+1)$
62and evaluates the function value of the reflection
63point $f_r=f(x_r)$. If that value $f_r$ is better than the worst function
64value $f_{n+1}$, the worst point $x_{n+1}$ is rejected from the
65simplex and the reflection point $x_r$ is accepted. If the reflection point
66does not improves, the next-to-worst point $x_n$ is reflected and the
67function is evaluated at the new reflected point. If the function
68value improves over the worst function value $f_{n+1}$, the new reflection point is
69accepted.
70
71At that point of the algorithm, neither the reflection with respect to
72$x_{n+1}$ nor the reflection with respect to $x_n$ has improved.
73The algorithm therefore shrinks the simplex toward the best point.
74That last step uses the shrink coefficient $0<\sigma<1$. The standard
75value for this coefficient is $\sigma=\frac{1}{2}$.
76
77Spendley's et al. algorithm is presented in figure \ref{algo-spendley}.
78The figure \ref{fig-spendley-moves} presents the various
79moves of the Spendley et al. algorithm. It is obvious from the
80picture that the algorithm explores a pattern which is
81entirely determined from the initial simplex.
82
83\begin{figure}[htbp]
84\begin{algorithmic}
85\STATE Compute an initial simplex $S_0$
86\STATE Sorts the vertices $S_0$ with increasing function values
87\STATE $S\gets S_0$
88\WHILE{$\sigma(S)>tol$}
89 \STATE $\overline{x}\gets \overline{x}(n+1)$
90 \STATE $x_r \gets x(\rho,n+1)$, $f_r \gets f(x_r)$ \COMMENT{Reflect with respect to worst}
91 \IF {$f_r<f_{n+1}$}
92 \STATE Accept $x_r$
93 \ELSE
94 \STATE $\overline{x}\gets \overline{x}(n)$
95 \STATE $x_r \gets x(\rho,n)$, $f_r \gets f(x_r)$ \COMMENT{Reflect with respect to next-to-worst}
96 \IF {$f_r<f_{n+1}$}
97 \STATE Accept $x_r$
98 \ELSE
99 \STATE Compute the points $x_i=x_1 + \sigma (x_i - x_1)$, $i=2,n+1$ \COMMENT{Shrink}
100 \STATE Compute the function values at the points $x_i, i=2,n+1$
101 \ENDIF
102 \ENDIF
103 \STATE Sort the vertices of $S$ with increasing function values
104\ENDWHILE
105\end{algorithmic}
106\caption{Spendley et al. algorithm}
107\label{algo-spendley}
108\end{figure}
109
110\section{Geometric analysis}
111
112The figure \ref{fig-spendley-moves} presents the various moves of the
113simplex in the Spendley et al. algorithm.
114
115\begin{figure}
116\begin{center}
117\includegraphics[width=10cm]{spendley-steps.png}
118\end{center}
119\caption{Spendley et al. simplex moves}
120\label{fig-spendley-moves}
121\end{figure}
122
123The various situations in which these moves are chosen are
124presented in figures \ref{fig-spendley-moves-reflect}, \ref{fig-spendley-moves-reflect2}
125and \ref{fig-spendley-moves-shrink}.
126
127The basic move is the reflection step, presented in figure
128\ref{fig-spendley-moves-reflect} and \ref{fig-spendley-moves-reflect2}.
129These two figures shows that the Spendley et al.
130algorithm is based on a discretization of the parameter space.
131The optimum is searched on that grid, which is based on regular simplices.
132When no move is possible to improve the situation on that grid,
133a shrink step is necessary, as presented in figure \ref{fig-spendley-moves-shrink}.
134
135\begin{figure}
136\begin{center}
137\includegraphics[width=10cm]{spendley-steps-reflect.png}
138\end{center}
139\caption{Spendley et al. simplex moves - reflection with respect to highest point}
140\label{fig-spendley-moves-reflect}
141\end{figure}
142
143\begin{figure}
144\begin{center}
145\includegraphics[width=10cm]{spendley-steps-reflect2.png}
146\end{center}
147\caption{Spendley et al. simplex moves - reflection with respect to next-to-highest point.
148It may happen that the next iteration is a shrink step.}
149\label{fig-spendley-moves-reflect2}
150\end{figure}
151
152In the situation of figure \ref{fig-spendley-moves-shrink}, neither the
153reflection \#1 or reflection \#2 have improved the simplex.
154Diminishing the size of the simplex by performing a shrink step
155is the only possible move because the
156simplex has vertices which are located across the valley.
157This allows to refine the discretization grid on which the
158optimum is searched.
159
160\begin{figure}
161\begin{center}
162\includegraphics[width=10cm]{spendley-steps-shrink.png}
163\end{center}
164\caption{Spendley et al. simplex moves - shrink.}
165\label{fig-spendley-moves-shrink}
166\end{figure}
167
168\subsection{Termination criteria}
169
170TODO...
171
172\section{Numerical experiments}
173
174In this section, we present some numerical experiments
175with the Spendley et al. algorithm.
176
177\subsection{Quadratic function}
178
179The function we try to minimize is the following quadratic
180in 2 dimensions
181
182\begin{eqnarray}
183f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2
184\end{eqnarray}
185
186The stopping criteria is based on the relative size of the simplex
187with respect to the size of the initial simplex
188
189\begin{eqnarray}
190\sigma(S) < tol \times \sigma(S_0)
191\end{eqnarray}
192
193The initial simplex is a regular simplex with length unity.
194The numerical results are presented in table \ref{fig-spendley-numexp1-table}.
195
196\begin{figure}[htbp]
197\begin{center}
198\begin{tiny}
199\begin{tabular}{|l|l|}
200\hline
201Iterations & 49 \\
202Function Evaluations & 132 \\
203$x_0$ & $(2.0,2.0)$ \\
204Relative tolerance on simplex size & $10^{-8}$ \\
205Exact $x^\star$ & $(0.,0.)$\\
206Computed $x^\star$ & $(2.169e-10, 2.169e-10)$\\
207Computed $f(x^\star)$ & $4.706e-20$\\
208\hline
209\end{tabular}
210\end{tiny}
211\end{center}
212\caption{Numerical experiment with Spendley's et al. method on the quadratic function
213$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$}
214\label{fig-spendley-numexp1-table}
215\end{figure}
216
217
218The various simplices generated during the iterations are
219presented in figure \ref{fig-spendley-numexp1-historysimplex}.
220The method use reflections in the early iterations. Then there
221is no possible improvement using reflections and shrinking is necessary.
222That behaviour is an illustration of the discretization which has already
223been discussed.
224
225\begin{figure}
226\begin{center}
227\includegraphics[width=10cm]{quad2bis-spendley-simplexcontours.png}
228\end{center}
229\caption{Spendley et al. numerical experiment -- history of simplex}
230\label{fig-spendley-numexp1-historysimplex}
231\end{figure}
232
233The figure \ref{fig-spendley-numexp1-sigma} presents the history of the oriented
234length of the simplex. The length is updated step by step, where each step
235corresponds to a shrink in the algorithm.
236
237\begin{figure}
238\begin{center}
239\includegraphics[width=10cm]{quad2bis-spendley-history-sigma.png}
240\end{center}
241\caption{Spendley et al. numerical experiment -- history of length of simplex}
242\label{fig-spendley-numexp1-sigma}
243\end{figure}
244
245The convergence is quite fast in this case, since less than 60 iterations
246allow to get a function value lower than $10^{-15}$, as shown in
247figure \ref{fig-spendley-numexp1-logfopt}.
248
249\begin{figure}
250\begin{center}
251\includegraphics[width=10cm]{quad2bis-spendley-history-logfopt.png}
252\end{center}
253\caption{Spendley et al. numerical experiment -- history of logarithm of function}
254\label{fig-spendley-numexp1-logfopt}
255\end{figure}
256
257\subsection{Badly scaled quadratic function}
258
259The function we try to minimize is the following quadratic
260in 2 dimensions
261\begin{eqnarray}
262\label{quadratic-sp-function2}
263f(x_1,x_2) = a x_1^2 + x_2^2,
264\end{eqnarray}
265where $a>0$ is a chosen scaling parameter.
266The more $a$ is large, the more difficult the problem is
267to solve with the simplex algorithm.
268
269We set the maximum number of function evaluations to 400.
270The initial simplex is a regular simplex with length unity.
271
272The numerical results are presented in table \ref{fig-spendley-numexp1-table},
273where the experiment is presented for $a=100$. One can check that the
274number of function evaluation is equal to its maximum limit, even if the value of the
275function at optimum is very inacurate ($f(x^\star) \approx 0.08$).
276
277\begin{figure}[h]
278\begin{center}
279\begin{tiny}
280\begin{tabular}{|l|l|}
281\hline
282Iterations & 340 \\
283Function Evaluations & 400 \\
284$a$ & $100.0$ \\
285$x_0$ & $(10.0,10.0)$ \\
286Relative tolerance on simplex size & $10^{-8}$ \\
287Exact $x^\star$ & $(0.,0.)$\\
288Computed $x^\star$ & $(0.001,0.2)$\\
289Computed $f(x^\star)$ & $0.08$\\
290\hline
291\end{tabular}
292\end{tiny}
293\end{center}
294\caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function}
295\label{fig-spendley-numexp2-table}
296\end{figure}
297
298
299The various simplices generated during the iterations are
300presented in figure \ref{fig-spendley-numexp2-historysimplex}.
301The method use reflections in the early iterations. Then there
302is no possible improvment using reflections and shrinking is necessary.
303But the shrinking makes the simplex very small so that a large number of
304iterations are necessary to improve the function value.
305This is a limitation of the method, which is based on a simplex
306which can vary its size, but not its shape.
307
308\begin{figure}
309\begin{center}
310\includegraphics[width=10cm]{quad2-spendley-simplexcontours.png}
311\end{center}
312\caption{Spendley et al. numerical experiment with $f(x_1,x_2) = (a * x_1)^2 + x_2^2$ and $a=100$ -- history of simplex}
313\label{fig-spendley-numexp2-historysimplex}
314\end{figure}
315
316In figure \ref{fig-spendley-numexp2-scaling}, we analyse the
317behaviour of the method with respect to scaling.
318We check that the method behave poorly when the scaling is
319bad. The convergence speed is slower and slower and impractical
320when $a>10$
321
322\begin{figure}[htbp]
323\begin{center}
324\begin{tiny}
325\begin{tabular}{|l|l|l|}
326\hline
327$a$ & Function evaluations & Computed $f(x^\star)$ \\
328$1.0$ & 160 & $2.35e-18$ \\
329$10.0$ & 222 & $1.2e-17$ \\
330$100.0$ & 400 & $0.083$ \\
331$1000.0$ & 400 & $30.3$ \\
332$10000.0$ & 400 & $56.08$ \\
333\hline
334\end{tabular}
335\end{tiny}
336\end{center}
337\caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function}
338\label{fig-spendley-numexp2-scaling}
339\end{figure}
340
341\subsection{Sensitivity to dimension}
342
343In this section, we try to study the convergence of the
344Spendley et al. algorithm with respect to the number of variables.
345The function we try to minimize is the following quadratic
346in n-dimensions
347\begin{eqnarray}
348\label{quadratic-sp-function3}
349f(x_1,x_2) = \sum_{i=1,n} x_i^2.
350\end{eqnarray}
351
352The initial simplex is a regular simplex with length unity.
353The initial guess is at 0 so that this vertex is never updated
354during the iterations.
355
356For this test, we compute the rate of convergence as presented
357in Han \& Neuman. This rate is defined as
358
359\begin{eqnarray}
360\label{rho-sp-rate-convergence}
361\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
362\left(\sum_{i=0,k-1} \frac{\sigma(S_{i+1}}{\sigma(S_i}\right)^{1/k}
363\end{eqnarray}
364
365That definition can be viewed as the geometric mean of the ratio of the
366oriented lengths between successive simplices and the minimizer 0.
367This definition implies
368
369\begin{eqnarray}
370\label{rho-sp-rate-convergence2}
371\rho(S_0,n) = \textrm{lim sup}_{k\rightarrow \infty}
372\left( \frac{\sigma(S_{k+1}}{\sigma(S_0}\right)^{1/k}
373\end{eqnarray}
374
375The figure \ref{fig-sp-numexp3-dimension} presents the results of this
376experiment for $n=1,20$.
377
378The number and kids of performed steps are presented in figure \ref{fig-sp-numexp3-nbsteps}.
379It must be noticed that reflection step occurs rarely during the iterations : the algorithm mostly performs
380shrink steps.
381
382\begin{figure}[htbp]
383\begin{center}
384\begin{tiny}
385\begin{tabular}{|l|l|l|l|}
386\hline
387$n$ & \# Reflections & \# Reflection & \#Shrink\\
388 & / High & / Next to High & \\
389\hline
3901 & 0 & 0 & 27\\
3912 & 0 & 0 & 27\\
3923 & 1 & 0 & 27\\
3934 & 5 & 1 & 27\\
3945 & 0 & 0 & 27\\
3956 & 6 & 0 & 27\\
3967 & 4 & 0 & 27\\
3978 & 0 & 0 & 27\\
3989 & 12 & 1 & 27\\
39910 & 0 & 0 & 27\\
40011 & 0 & 0 & 27\\
40112 & 14 & 0 & 27\\
40213 & 0 & 0 & 27\\
40314 & 24 & 3 & 27\\
40415 & 0 & 0 & 27\\
40516 & 0 & 0 & 27\\
40617 & 21 & 0 & 27\\
40718 & 0 & 0 & 27\\
40819 & 28 & 0 & 27\\
409\hline
410\end{tabular}
411\end{tiny}
412\end{center}
413\caption{Numerical experiment with Spendley et al method on a generalized quadratic function -- number
414and kinds of steps performed}
415\label{fig-sp-numexp3-nbsteps}
416\end{figure}
417
418One can check that the number of function evaluations
419increases approximately linearily with the dimension of the problem in
420figure \ref{fig-sp-numexp3-fvn}. A rough rule of thumb is that, for $n=1,19$,
421the number of function evaluations is equal to $30n$.
422This test is in fact the best that we can expect from this algorithm : since
423most iterations are shrink steps, most iterations improves the function value.
424
425\begin{figure}[htbp]
426\begin{center}
427\begin{tiny}
428\begin{tabular}{|l|l|l|l|}
429\hline
430$n$ & Function evaluations & Iterations & $\rho(S_0,n)$\\
431\hline
4321 & 83 & 28 & 0.5125321059829373\\
4332 & 111 & 28 & 0.5125321059829373\\
4343 & 140 & 29 & 0.52448212766151725\\
4354 & 174 & 34 & 0.57669577295965202\\
4365 & 195 & 28 & 0.5125321059829373\\
4376 & 229 & 34 & 0.57669577295965202\\
4387 & 255 & 32 & 0.55719337129794622\\
4398 & 279 & 28 & 0.5125321059829373\\
4409 & 321 & 41 & 0.63352059021162177\\
44110 & 335 & 28 & 0.5125321059829373\\
44211 & 363 & 28 & 0.5125321059829373\\
44312 & 405 & 42 & 0.64044334488213628\\
44413 & 419 & 28 & 0.5125321059829373\\
44514 & 477 & 55 & 0.71157656804932146\\
44615 & 475 & 28 & 0.5125321059829373\\
44716 & 503 & 28 & 0.5125321059829373\\
44817 & 552 & 49 & 0.68253720379799854\\
44918 & 559 & 28 & 0.5125321059829373\\
45019 & 615 & 56 & 0.71591347660379834\\
451\hline
452\end{tabular}
453\end{tiny}
454\end{center}
455\caption{Numerical experiment with Spendley et al. method on a generalized quadratic function}
456\label{fig-sp-numexp3-dimension}
457\end{figure}
458
459\begin{figure}
460\begin{center}
461\includegraphics[width=10cm]{spendley-dimension-nfevals.png}
462\end{center}
463\caption{Spendley et al. numerical experiment -- number of function evaluations
464depending on the number of variables}
465\label{fig-sp-numexp3-fvn}
466\end{figure}
467
468The figure \ref{fig-nm-numexp3-rho} presents the rate of convergence
469depending on the number of variables. The figure shows that
470the rate of convergence rapidly gets close to 1 when the number
471of variables increases. That shows that the rate of convergence
472is slower and slower as the number of variables increases, as
473explained by Han \& Neuman.
474
475\begin{figure}
476\begin{center}
477\includegraphics[width=10cm]{spendley-dimension-rho.png}
478\end{center}
479\caption{Spendley et al. numerical experiment -- rate of convergence
480depending on the number of variables}
481\label{fig-sp-numexp3-rho}
482\end{figure}
483
484\section{Conclusion}
485
486We saw in the first numerical experiment that the method
487behave reasonably when the function is correctly scaled.
488When the function is badly scaled, as in the second numerical
489experiment, the Spendley et al. algorithm produces a large
490number of function evaluations and converges very slowly.
491This limitation occurs with even moderate badly scaled
492functions and generates a very slow method in these
493cases.
494
495
diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.png b/scilab_doc/neldermead/nelder-mead-contract-inside.png
new file mode 100644
index 0000000..2411847
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.png
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.svg b/scilab_doc/neldermead/nelder-mead-contract-inside.svg
new file mode 100644
index 0000000..cd756ed
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.svg
@@ -0,0 +1,311 @@
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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm"
12 height="297mm"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.46"
16 sodipodi:docname="nelder-mead-contract-inside.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-inside.png"
19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90">
21 <defs
22 id="defs4">
23 <marker
24 inkscape:stockid="Arrow1Lend"
25 orient="auto"
26 refY="0.0"
27 refX="0.0"
28 id="Arrow1Lend"
29 style="overflow:visible;">
30 <path
31 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 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" />
35 </marker>
36 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d"
38 inkscape:vp_x="0 : 526.18109 : 1"
39 inkscape:vp_y="0 : 1000 : 0"
40 inkscape:vp_z="744.09448 : 526.18109 : 1"
41 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
42 id="perspective10" />
43 </defs>
44 <sodipodi:namedview
45 id="base"
46 pagecolor="#ffffff"
47 bordercolor="#666666"
48 borderopacity="1.0"
49 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949"
52 inkscape:cx="303.93521"
53 inkscape:cy="730.24376"
54 inkscape:document-units="px"
55 inkscape:current-layer="layer1"
56 showgrid="false"
57 inkscape:window-width="1280"
58 inkscape:window-height="975"
59 inkscape:window-x="0"
60 inkscape:window-y="22" />
61 <metadata
62 id="metadata7">
63 <rdf:RDF>
64 <cc:Work
65 rdf:about="">
66 <dc:format>image/svg+xml</dc:format>
67 <dc:type
68 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
69 </cc:Work>
70 </rdf:RDF>
71 </metadata>
72 <g
73 inkscape:label="Calque 1"
74 inkscape:groupmode="layer"
75 id="layer1">
76 <text
77 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"
79 x="197.9899"
80 y="425.05746"
81 id="text3303"><tspan
82 sodipodi:role="line"
83 id="tspan3305"
84 x="197.9899"
85 y="425.05746"
86 style="font-style:italic;font-weight:normal" /></text>
87 <text
88 xml:space="preserve"
89 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"
90 x="189.90868"
91 y="417.98639"
92 id="text3315"><tspan
93 sodipodi:role="line"
94 id="tspan3317"
95 x="189.90868"
96 y="417.98639" /></text>
97 <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"
99 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"
101 sodipodi:nodetypes="cccc" />
102 <text
103 xml:space="preserve"
104 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"
105 x="445.57532"
106 y="454.06277"
107 id="text3339"><tspan
108 sodipodi:role="line"
109 id="tspan3341"
110 x="445.57532"
111 y="454.06277">R</tspan></text>
112 <text
113 xml:space="preserve"
114 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"
115 x="297.18445"
116 y="210.23674"
117 id="text2438"><tspan
118 sodipodi:role="line"
119 id="tspan2440"
120 x="297.18445"
121 y="210.23674">H</tspan></text>
122 <text
123 xml:space="preserve"
124 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"
125 x="310.83221"
126 y="384.93076"
127 id="text2442"><tspan
128 sodipodi:role="line"
129 id="tspan2444"
130 x="310.83221"
131 y="384.93076">L</tspan></text>
132 <text
133 xml:space="preserve"
134 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"
135 x="432.05054"
136 y="308.15915"
137 id="text2446"><tspan
138 sodipodi:role="line"
139 id="tspan2448"
140 x="432.05054"
141 y="308.15915">N</tspan></text>
142 <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"
144 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"
146 sodipodi:nodetypes="cccc" />
147 <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"
149 d="M 435.60634,439.45686 L 321.21202,216.07873"
150 id="path3226"
151 sodipodi:nodetypes="cc" />
152 <text
153 xml:space="preserve"
154 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"
155 x="142.93266"
156 y="199.83151"
157 id="text3306"><tspan
158 sodipodi:role="line"
159 id="tspan3308"
160 x="142.93266"
161 y="199.83151">Accepted</tspan></text>
162 <path
163 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-opacity:1"
164 d="M 208.0719,212.62955 L 326.23977,268.14483"
165 id="path3310"
166 sodipodi:nodetypes="cc" />
167 <path
168 sodipodi:type="arc"
169 style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:1, 4.00000001;stroke-dashoffset:0;stroke-opacity:1"
170 id="path3228"
171 sodipodi:cx="375.77673"
172 sodipodi:cy="472.02954"
173 sodipodi:rx="50.507626"
174 sodipodi:ry="18.687822"
175 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"
176 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-163.52526,97.403636)" />
177 <path
178 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"
180 id="path3230"
181 sodipodi:cx="375.77673"
182 sodipodi:cy="472.02954"
183 sodipodi:rx="50.507626"
184 sodipodi:ry="18.687822"
185 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"
186 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-802.48459,-155.5446)" />
187 <path
188 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"
190 id="path3232"
191 sodipodi:cx="375.77673"
192 sodipodi:cy="472.02954"
193 sodipodi:rx="50.507626"
194 sodipodi:ry="18.687822"
195 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"
196 transform="matrix(3.3350534,-1.9254939,1.9254939,3.3350534,-1805.5465,-551.5414)" />
197 <path
198 sodipodi:type="arc"
199 style="fill:none;stroke:#000000;stroke-width:0.1514795;stroke-miterlimit:4;stroke-dasharray:0.1514795, 0.60591802;stroke-dashoffset:0;stroke-opacity:1"
200 id="path3235"
201 sodipodi:cx="375.77673"
202 sodipodi:cy="472.02954"
203 sodipodi:rx="50.507626"
204 sodipodi:ry="18.687822"
205 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"
206 transform="matrix(5.7171128,-3.3007765,3.3007765,5.7171128,-3358.7739,-1156.4636)" />
207 <path
208 sodipodi:type="arc"
209 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
210 id="path3245"
211 sodipodi:cx="304.561"
212 sodipodi:cy="367.98383"
213 sodipodi:rx="2.2728431"
214 sodipodi:ry="2.2728431"
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"
216 transform="translate(130.81219,71.517787)" />
217 <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"
219 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"
221 sodipodi:nodetypes="cccc" />
222 <text
223 xml:space="preserve"
224 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"
225 x="325.27536"
226 y="285.43073"
227 id="text3398"><tspan
228 sodipodi:role="line"
229 id="tspan3400"
230 x="325.27536"
231 y="285.43073">Ci</tspan></text>
232 <path
233 sodipodi:type="arc"
234 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
235 id="path3402"
236 sodipodi:cx="304.561"
237 sodipodi:cy="367.98383"
238 sodipodi:rx="2.2728431"
239 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"
241 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
253 id="g2431"
254 transform="translate(-3.1011179e-5,-1.0874309e-4)">
255 <text
256 id="text3242"
257 y="356.25449"
258 x="542.22089"
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"
260 xml:space="preserve"><tspan
261 y="356.25449"
262 x="542.22089"
263 id="tspan3244"
264 sodipodi:role="line">H = Highest</tspan></text>
265 </g>
266 <text
267 xml:space="preserve"
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 x="542.36511"
270 y="418.40466"
271 id="text3246"><tspan
272 sodipodi:role="line"
273 id="tspan3248"
274 x="542.36511"
275 y="418.40466">L = Lowest</tspan></text>
276 <text
277 xml:space="preserve"
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"
279 x="542.30328"
280 y="387.3295"
281 id="text3250"><tspan
282 sodipodi:role="line"
283 id="tspan3252"
284 x="542.30328"
285 y="387.3295">N = Next to highest</tspan></text>
286 <text
287 xml:space="preserve"
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"
289 x="543.91089"
290 y="472.68198"
291 id="text3439"><tspan
292 sodipodi:role="line"
293 id="tspan3441"
294 x="543.91089"
295 y="472.68198">Ci = Contraction </tspan><tspan
296 sodipodi:role="line"
297 x="543.91089"
298 y="499.06259"
299 id="tspan3443"> (inside)</tspan></text>
300 <text
301 xml:space="preserve"
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"
303 x="543.71509"
304 y="530.39539"
305 id="text2435"><tspan
306 sodipodi:role="line"
307 id="tspan2437"
308 x="543.71509"
309 y="530.39539">f(R) &gt;= f(H)</tspan></text>
310 </g>
311</svg>
diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.png b/scilab_doc/neldermead/nelder-mead-contract-outside.png
new file mode 100644
index 0000000..fe38040
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.png
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.svg b/scilab_doc/neldermead/nelder-mead-contract-outside.svg
new file mode 100644
index 0000000..fb5200d
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.svg
@@ -0,0 +1,312 @@
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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm"
12 height="297mm"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.46"
16 sodipodi:docname="nelder-mead-contract-outside.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-outside.png"
19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90">
21 <defs
22 id="defs4">
23 <marker
24 inkscape:stockid="Arrow1Lend"
25 orient="auto"
26 refY="0.0"
27 refX="0.0"
28 id="Arrow1Lend"
29 style="overflow:visible;">
30 <path
31 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 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" />
35 </marker>
36 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d"
38 inkscape:vp_x="0 : 526.18109 : 1"
39 inkscape:vp_y="0 : 1000 : 0"
40 inkscape:vp_z="744.09448 : 526.18109 : 1"
41 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
42 id="perspective10" />
43 </defs>
44 <sodipodi:namedview
45 id="base"
46 pagecolor="#ffffff"
47 bordercolor="#666666"
48 borderopacity="1.0"
49 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949"
52 inkscape:cx="207.44335"
53 inkscape:cy="636.62322"
54 inkscape:document-units="px"
55 inkscape:current-layer="layer1"
56 showgrid="false"
57 inkscape:window-width="1280"
58 inkscape:window-height="975"
59 inkscape:window-x="0"
60 inkscape:window-y="22" />
61 <metadata
62 id="metadata7">
63 <rdf:RDF>
64 <cc:Work
65 rdf:about="">
66 <dc:format>image/svg+xml</dc:format>
67 <dc:type
68 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
69 </cc:Work>
70 </rdf:RDF>
71 </metadata>
72 <g
73 inkscape:label="Calque 1"
74 inkscape:groupmode="layer"
75 id="layer1">
76 <text
77 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"
79 x="197.9899"
80 y="425.05746"
81 id="text3303"><tspan
82 sodipodi:role="line"
83 id="tspan3305"
84 x="197.9899"
85 y="425.05746"
86 style="font-style:italic;font-weight:normal" /></text>
87 <text
88 xml:space="preserve"
89 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"
90 x="189.90868"
91 y="417.98639"
92 id="text3315"><tspan
93 sodipodi:role="line"
94 id="tspan3317"
95 x="189.90868"
96 y="417.98639" /></text>
97 <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"
99 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"
101 sodipodi:nodetypes="cccc" />
102 <text
103 xml:space="preserve"
104 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"
105 x="395.57532"
106 y="434.06277"
107 id="text3339"><tspan
108 sodipodi:role="line"
109 id="tspan3341"
110 x="395.57532"
111 y="434.06277">R</tspan></text>
112 <text
113 xml:space="preserve"
114 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"
115 x="247.18446"
116 y="190.23674"
117 id="text2438"><tspan
118 sodipodi:role="line"
119 id="tspan2440"
120 x="247.18446"
121 y="190.23674">H</tspan></text>
122 <text
123 xml:space="preserve"
124 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"
125 x="253.25607"
126 y="352.30386"
127 id="text2442"><tspan
128 sodipodi:role="line"
129 id="tspan2444"
130 x="253.25607"
131 y="352.30386">L</tspan></text>
132 <text
133 xml:space="preserve"
134 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"
135 x="386.09116"
136 y="295.73529"
137 id="text2446"><tspan
138 sodipodi:role="line"
139 id="tspan2448"
140 x="386.09116"
141 y="295.73529">N</tspan></text>
142 <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"
144 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"
146 sodipodi:nodetypes="cccc" />
147 <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"
149 d="M 385.89222,419.74019 L 270.60234,196.65251"
150 id="path3226"
151 sodipodi:nodetypes="cc" />
152 <path
153 sodipodi:type="arc"
154 style="fill:none;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:1, 4.00000001;stroke-dashoffset:0;stroke-opacity:1"
155 id="path3228"
156 sodipodi:cx="375.77673"
157 sodipodi:cy="472.02954"
158 sodipodi:rx="50.507626"
159 sodipodi:ry="18.687822"
160 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"
161 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-162.81098,126.68935)" />
162 <path
163 sodipodi:type="arc"
164 style="fill:none;stroke:#000000;stroke-width:0.44742242;stroke-miterlimit:4;stroke-dasharray:0.44742241, 1.78968964;stroke-dashoffset:0;stroke-opacity:1"
165 id="path3230"
166 sodipodi:cx="375.77673"
167 sodipodi:cy="472.02954"
168 sodipodi:rx="50.507626"
169 sodipodi:ry="18.687822"
170 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"
171 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-801.7703,-126.25889)" />
172 <path
173 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"
175 id="path3232"
176 sodipodi:cx="375.77673"
177 sodipodi:cy="472.02954"
178 sodipodi:rx="50.507626"
179 sodipodi:ry="18.687822"
180 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"
181 transform="matrix(3.3350534,-1.9254939,1.9254939,3.3350534,-1804.8322,-522.25569)" />
182 <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"
184 d="M 46.429775,338.61979 C 129.63836,188.0964 361.50049,88.059116 501.73967,87.124191"
185 id="path3292"
186 sodipodi:nodetypes="cc" />
187 <text
188 xml:space="preserve"
189 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"
190 x="258.45621"
191 y="565.40521"
192 id="text3306"><tspan
193 sodipodi:role="line"
194 id="tspan3308"
195 x="258.45621"
196 y="565.40521">Accepted</tspan></text>
197 <path
198 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-opacity:1"
199 d="M 300.55628,539.03138 L 354.57225,382.77102"
200 id="path3310"
201 sodipodi:nodetypes="cc" />
202 <path
203 sodipodi:type="arc"
204 style="fill:none;stroke:#000000;stroke-width:0.1514795;stroke-miterlimit:4;stroke-dasharray:0.1514795, 0.60591802;stroke-dashoffset:0;stroke-opacity:1"
205 id="path3235"
206 sodipodi:cx="375.77673"
207 sodipodi:cy="472.02954"
208 sodipodi:rx="50.507626"
209 sodipodi:ry="18.687822"
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"
211 transform="matrix(5.7171128,-3.3007765,3.3007765,5.7171128,-3358.0596,-1127.1779)" />
212 <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"
214 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"
216 sodipodi:nodetypes="cccc" />
217 <text
218 xml:space="preserve"
219 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"
220 x="363.67239"
221 y="373.01199"
222 id="text3239"><tspan
223 sodipodi:role="line"
224 id="tspan3241"
225 x="363.67239"
226 y="373.01199">Co</tspan></text>
227 <path
228 sodipodi:type="arc"
229 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
230 id="path3243"
231 sodipodi:cx="304.561"
232 sodipodi:cy="367.98383"
233 sodipodi:rx="2.2728431"
234 sodipodi:ry="2.2728431"
235 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"
236 transform="translate(53.538085,0)" />
237 <path
238 sodipodi:type="arc"
239 style="fill:#000000;fill-opacity:1;stroke:#000000;stroke-width:1;stroke-miterlimit:4;stroke-dasharray:none;stroke-dashoffset:0;stroke-opacity:1"
240 id="path3245"
241 sodipodi:cx="304.561"
242 sodipodi:cy="367.98383"
243 sodipodi:rx="2.2728431"
244 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"
246 transform="translate(80.812192,51.517787)" />
247 <text
248 xml:space="preserve"
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"
250 x="492.50925"
251 y="524.6214"
252 id="text3238"><tspan
253 sodipodi:role="line"
254 id="tspan3240"
255 x="492.50925"
256 y="524.6214">R = Reflexion</tspan></text>
257 <text
258 xml:space="preserve"
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"
260 x="492.47833"
261 y="434.24643"
262 id="text3242"><tspan
263 sodipodi:role="line"
264 id="tspan3244"
265 x="492.47833"
266 y="434.24643">H = Highest</tspan></text>
267 <text
268 xml:space="preserve"
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"
270 x="492.62259"
271 y="497.1207"
272 id="text3246"><tspan
273 sodipodi:role="line"
274 id="tspan3248"
275 x="492.62259"
276 y="497.1207">L = Lowest</tspan></text>
277 <text
278 xml:space="preserve"
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"
280 x="492.56076"
281 y="465.68356"
282 id="text3250"><tspan
283 sodipodi:role="line"
284 id="tspan3252"
285 x="492.56076"
286 y="465.68356">N = Next to highest</tspan></text>
287 <text
288 xml:space="preserve"
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"
290 x="494.16833"
291 y="552.12207"
292 id="text3259"><tspan
293 sodipodi:role="line"
294 id="tspan3261"
295 x="494.16833"
296 y="552.12207">Co = Contraction </tspan><tspan
297 sodipodi:role="line"
298 x="494.16833"
299 y="578.50269"
300 id="tspan3263"> (outside)</tspan></text>
301 <text
302 xml:space="preserve"
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"
304 x="493.97253"
305 y="610.19745"
306 id="text2586"><tspan
307 sodipodi:role="line"
308 id="tspan2588"
309 x="493.97253"
310 y="610.19745">f(N)&lt;=f(R)&lt;f(H)</tspan></text>
311 </g>
312</svg>
diff --git a/scilab_doc/neldermead/nelder-mead-extension.png b/scilab_doc/neldermead/nelder-mead-extension.png
new file mode 100644
index 0000000..8758156
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-extension.png
Binary files differ
diff --git a/scilab_doc/neldermead/nelder-mead-extension.svg b/scilab_doc/neldermead/nelder-mead-extension.svg
new file mode 100644
index 0000000..893a1ba
--- /dev/null
+++ b/scilab_doc/neldermead/nelder-mead-extension.svg
@@ -0,0 +1,293 @@
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:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="210mm"
12 height="297mm"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.46"
16 sodipodi:docname="nelder.mead.extension.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.extension.png"
19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90">
21 <defs
22 id="defs4">
23 <marker
24 inkscape:stockid="Arrow1Lend"
25 orient="auto"
26 refY="0.0"
27 refX="0.0"
28 id="Arrow1Lend"
29 style="overflow:visible;">
30 <path
31 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 style="fill-rule:evenodd;stroke:#000000;stroke-width:1.0pt;marker-start:none;"
34 transform="scale(0.8) rotate(180) translate(12.5,0)" />
35 </marker>
36 <inkscape:perspective
37 sodipodi:type="inkscape:persp3d"
38 inkscape:vp_x="0 : 526.18109 : 1"
39 inkscape:vp_y="0 : 1000 : 0"
40 inkscape:vp_z="744.09448 : 526.18109 : 1"
41 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
42 id="perspective10" />
43 </defs>
44 <sodipodi:namedview
45 id="base"
46 pagecolor="#ffffff"
47 bordercolor="#666666"
48 borderopacity="1.0"
49 inkscape:pageopacity="0.0"
50 inkscape:pageshadow="2"
51 inkscape:zoom="0.98994949"
52 inkscape:cx="241.7257"
53 inkscape:cy="610.56309"
54 inkscape:document-units="px"
55 inkscape:current-layer="layer1"
56 showgrid="false"
57 inkscape:window-width="1280"
58 inkscape:window-height="975"
59 inkscape:window-x="0"
60 inkscape:window-y="22" />
61 <metadata
62 id="metadata7">
63 <rdf:RDF>
64 <cc:Work
65 rdf:about="">
66 <dc:format>image/svg+xml</dc:format>
67 <dc:type
68 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
69 </cc:Work>
70 </rdf:RDF>
71 </metadata>
72 <g
73 inkscape:label="Calque 1"
74 inkscape:groupmode="layer"
75 id="layer1">
76 <text
77 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"
79 x="197.9899"
80 y="425.05746"
81 id="text3303"><tspan
82 sodipodi:role="line"
83 id="tspan3305"
84 x="197.9899"
85 y="425.05746"
86 style="font-style:italic;font-weight:normal" /></text>
87 <text
88 xml:space="preserve"
89 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"
90 x="189.90868"
91 y="417.98639"
92 id="text3315"><tspan
93 sodipodi:role="line"
94 id="tspan3317"
95 x="189.90868"
96 y="417.98639" /></text>
97 <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"
99 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"
101 sodipodi:nodetypes="cccc" />
102 <text
103 xml:space="preserve"
104 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"
105 x="339.00677"
106 y="428.50693"
107 id="text3339"><tspan
108 sodipodi:role="line"
109 id="tspan3341"
110 x="339.00677"
111 y="428.50693">R</tspan></text>
112 <text
113 xml:space="preserve"
114 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"
115 x="193.64638"
116 y="190.23674"
117 id="text2438"><tspan
118 sodipodi:role="line"
119 id="tspan2440"
120 x="193.64638"
121 y="190.23674">H</tspan></text>
122 <text
123 xml:space="preserve"
124 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"
125 x="207.29414"
126 y="364.93076"
127 id="text2442"><tspan
128 sodipodi:role="line"
129 id="tspan2444"
130 x="207.29414"
131 y="364.93076">L</tspan></text>
132 <text
133 xml:space="preserve"
134 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"
135 x="336.59366"
136 y="302.30127"
137 id="text2446"><tspan
138 sodipodi:role="line"
139 id="tspan2448"
140 x="336.59366"
141 y="302.30127">N</tspan></text>
142 <text
143 xml:space="preserve"
144 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"
145 x="395.74493"
146 y="513.42316"
147 id="text2450"><tspan
148 sodipodi:role="line"
149 id="tspan2452"
150 x="395.74493"
151 y="513.42316">E</tspan></text>
152 <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"
154 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"
156 sodipodi:nodetypes="cccc" />
157 <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"
159 d="M 386.39729,523.7859 L 217.92647,196.33127"
160 id="path3226"
161 sodipodi:nodetypes="cc" />
162 <path
163 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"
165 id="path3228"
166 sodipodi:cx="375.77673"
167 sodipodi:cy="472.02954"
168 sodipodi:rx="50.507626"
169 sodipodi:ry="18.687822"
170 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"
171 transform="matrix(0.8660254,-0.5,0.5,0.8660254,-152.3352,348.10297)" />
172 <path
173 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"
175 id="path3230"
176 sodipodi:cx="375.77673"
177 sodipodi:cy="472.02954"
178 sodipodi:rx="50.507626"
179 sodipodi:ry="18.687822"
180 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"
181 transform="matrix(1.9355879,-1.1175122,1.1175122,1.9355879,-842.70542,74.802419)" />
182 <path
183 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"
185 id="path3232"
186 sodipodi:cx="375.77673"
187 sodipodi:cy="472.02954"
188 sodipodi:rx="50.507626"
189 sodipodi:ry="18.687822"
190 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"
191 transform="matrix(3.603393,-2.0804199,2.0804199,3.603393,-1926.4741,-353.05643)" />
192 <path
193 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"
194 d="M 385.89222,522.90203 L 219.12788,336.09319 L 321.77876,296.13275 L 385.89222,522.90203 z"
195 id="path3234"
196 sodipodi:nodetypes="cccc" />
197 <path
198 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;stroke-miterlimit:4;stroke-dasharray:1,4;stroke-dashoffset:0"
199 d="M 140.4112,643.2504 C 230.31478,480.61584 457.5991,376.57013 609.12198,375.55998"
200 id="path3236"
201 sodipodi:nodetypes="cc" />
202 <text
203 xml:space="preserve"
204 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"
205 x="397.06253"
206 y="223.83533"
207 id="text3238"><tspan
208 sodipodi:role="line"
209 id="tspan3240"
210 x="397.06253"
211 y="223.83533">R = Reflexion</tspan></text>
212 <text
213 xml:space="preserve"
214 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"
215 x="397.03162"
216 y="132.21082"
217 id="text3242"><tspan
218 sodipodi:role="line"
219 id="tspan3244"
220 x="397.03162"
221 y="132.21082">H = Highest</tspan></text>
222 <text
223 xml:space="preserve"
224 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"
225 x="397.17587"
226 y="193.29381"
227 id="text3246"><tspan
228 sodipodi:role="line"
229 id="tspan3248"
230 x="397.17587"
231 y="193.29381">L = Lowest</tspan></text>
232 <text
233 xml:space="preserve"
234 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"
235 x="397.11404"
236 y="162.7523"
237 id="text3250"><tspan
238 sodipodi:role="line"
239 id="tspan3252"
240 x="397.11404"
241 y="162.7523">N = Next to highest</tspan></text>
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="397.05222"
246 y="254.37686"
247 id="text3254"><tspan
248 sodipodi:role="line"
249 id="tspan3256"
250 x="397.05222"
251 y="254.37686">E = Expansion</tspan></text>
252 <path
253 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:1,4;stroke-opacity:1;stroke-dashoffset:0"
254 d="M 73.741138,577.08541 C 163.64472,414.45085 414.16255,306.36453 565.68543,305.35438"
255 id="path3292"
256 sodipodi:nodetypes="cc" />
257 <text
258 xml:space="preserve"
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"
260 x="516.39172"
261 y="663.85913"
262 id="text3306"><tspan
263 sodipodi:role="line"
264 id="tspan3308"
265 x="516.39172"
266 y="663.85913">Accepted</tspan></text>
267 <path
268 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;marker-end:url(#Arrow1Lend)"
269 d="M 508.10673,648.30117 L 416.18285,528.09301"
270 id="path3310"
271 sodipodi:nodetypes="cc" />
272 <path