summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichaŽl Baudin <michael.baudin@scilab.org>2009-09-03 10:14:14 +0200
committerMichaŽl Baudin <michael.baudin@scilab.org>2009-09-03 10:14:14 +0200
commit549e910561e13ebe97f97e2d73803ff99aefa462 (patch)
treec5a9b6c1e352465d3e55e54a857a98659076e052 /scilab_doc
parenta5a0f59140248949917e5683c01432cf15b42f85 (diff)
downloadscilab-549e910561e13ebe97f97e2d73803ff99aefa462.zip
scilab-549e910561e13ebe97f97e2d73803ff99aefa462.tar.gz
Updated doc for neldermead
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/macros.tex69
-rw-r--r--scilab_doc/neldermead/neldermead-simplex-so.pdfbin0 -> 177631 bytes
-rw-r--r--scilab_doc/neldermead/neldermead-simplex-so.tex89
-rw-r--r--scilab_doc/neldermead/neldermead.bib15
-rw-r--r--scilab_doc/neldermead/neldermead.pdfbin951124 -> 971928 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.tex85
-rw-r--r--scilab_doc/neldermead/nmbibliography.tex6
-rw-r--r--scilab_doc/neldermead/overview.tex12
-rw-r--r--scilab_doc/neldermead/scripts/initialsimplex_axes.sce29
-rw-r--r--scilab_doc/neldermead/scripts/initialsimplex_regular.sce33
-rw-r--r--scilab_doc/neldermead/section-simplex.tex163
-rw-r--r--scilab_doc/neldermead/simplex_axes.pngbin0 -> 3823 bytes
-rw-r--r--scilab_doc/neldermead/simplex_initialfixed.pngbin0 -> 48421 bytes
-rw-r--r--scilab_doc/neldermead/simplex_initialfixed.svg186
-rw-r--r--scilab_doc/neldermead/simplex_regular.pngbin0 -> 4214 bytes
15 files changed, 585 insertions, 102 deletions
diff --git a/scilab_doc/neldermead/macros.tex b/scilab_doc/neldermead/macros.tex
new file mode 100644
index 0000000..a205b7b
--- /dev/null
+++ b/scilab_doc/neldermead/macros.tex
@@ -0,0 +1,69 @@
1%% Good fonts for PDF
2\usepackage[cyr]{aeguill}
3
4%% Package for page headers
5\usepackage{fancyhdr}
6
7%% Package to include graphics
8%% Comment for DVI
9\usepackage[pdftex]{graphicx}
10
11%% Figures formats: jpeg or pdf
12%% Comment for DVI
13\DeclareGraphicsExtensions{.jpg,.pdf}
14
15%% Package to create Hyperdocuments
16%% Comment for DVI
17\usepackage[pdftex,colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
18
19%% Package to control printed area size
20\usepackage{anysize}
21%% ...by defining margins {left}{right}{top}{bottom}
22\marginsize{22mm}{14mm}{12mm}{25mm}
23
24%% Package used to include a bibliography
25\usepackage{natbib}
26
27%% R for real numbers
28\usepackage{amssymb}
29
30%% User defined commands
31
32%% Figure reference
33\newcommand{\figref}[1]{figure~\ref{#1}}
34
35%% Equation reference
36\newcommand{\Ref}[1]{(\ref{#1})}
37
38%% Emphasize a word or a group of words
39\newcommand{\empha}[1]{\textit{\textbf{#1}}}
40
41%% Derivation operators
42\newcommand{\D}{\partial}
43\newcommand{\Dt}{\partial_t}
44\newcommand{\Dx}{\partial_x}
45\newcommand{\Dy}{\partial_y}
46
47\newcommand{\bv}{\mathbf{v}}
48\newcommand{\bx}{\mathbf{x}}
49\newcommand{\bl}{\mathbf{l}}
50
51\usepackage{url}
52
53% Scilab macros
54\newcommand{\scifunction}[1]{\textit{#1}}
55
56% To highlight source code
57\usepackage{listings}
58
59\usepackage{algorithmic}
60
61% To allow one bibliograph by chapter
62%\usepackage[sectionbib]{chapterbib}
63\usepackage{url}
64
65% Maths shortcuts
66\newcommand{\RR}{\mathbb{R}}
67\newcommand{\CC}{\mathbb{C}}
68
69
diff --git a/scilab_doc/neldermead/neldermead-simplex-so.pdf b/scilab_doc/neldermead/neldermead-simplex-so.pdf
new file mode 100644
index 0000000..7d0151f
--- /dev/null
+++ b/scilab_doc/neldermead/neldermead-simplex-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead-simplex-so.tex b/scilab_doc/neldermead/neldermead-simplex-so.tex
new file mode 100644
index 0000000..84719ac
--- /dev/null
+++ b/scilab_doc/neldermead/neldermead-simplex-so.tex
@@ -0,0 +1,89 @@
1%
2% neldermead.tex --
3% Some notes about Nelder-Mead algorithms.
4%
5% Copyright 2008-2009 Michael Baudin
6%
7\documentclass[12pt]{report}
8
9\include{macros}
10
11\begin{document}
12%% User defined page headers
13\pagestyle{fancyplain}
14\renewcommand{\chaptermark}[1]{\markboth{\chaptername\ \thechapter. #1}{}}
15\renewcommand{\sectionmark}[1]{\markright{\thesection. #1}}
16\lhead[]{\fancyplain{}{\bfseries\leftmark}}
17\rhead[]{\fancyplain{}{\bfseries\thepage}}
18\cfoot{}
19
20%% User defined figure legends
21\makeatletter
22\def\figurename{{\protect\sc \protect\small\bfseries Fig.}}
23\def\f@ffrench{\protect\figurename\space{\protect\small\bf \thefigure}\space}
24\let\fnum@figure\f@ffrench%
25\let\captionORI\caption
26\def\caption#1{\captionORI{\rm\small #1}}
27\makeatother
28
29%% First page
30\thispagestyle{empty}
31{
32\begin{center}
33%% Comment for DVI
34\includegraphics[height=40mm]{scilab_logo}
35\vskip4cm
36
37%% Empty space between the box and the text
38\fboxsep6mm
39%% Box thickness
40\fboxrule1.3pt
41\Huge
42$$\fbox{$
43 \begin{array}{c}
44 \textbf{Nelder-Mead}\\
45 \textbf{Toolbox Manual}\\
46 \textbf{-- Simplex Theory --}
47 \end{array}
48 $}
49$$
50\end{center}
51\vskip8cm
52
53\normalsize
54
55\begin{flushright}
56Version 0.2 \\
57September 2009
58\end{flushright}
59
60\begin{flushright}
61Micha\"el BAUDIN
62\end{flushright}
63
64\clearpage
65
66%% Table of contents
67\renewcommand{\baselinestretch}{1.30}\small \normalsize
68
69\tableofcontents
70
71\renewcommand{\baselinestretch}{1.18}\small \normalsize
72
73
74\include{section-simplex}
75
76
77\clearpage
78
79%% Appendix
80\appendix
81
82%% Bibliography
83
84\addcontentsline{toc}{chapter}{Bibliography}
85\bibliographystyle{plain}
86\bibliography{neldermead}
87
88\end{document}
89
diff --git a/scilab_doc/neldermead/neldermead.bib b/scilab_doc/neldermead/neldermead.bib
index 0ff90c5..d2835e9 100644
--- a/scilab_doc/neldermead/neldermead.bib
+++ b/scilab_doc/neldermead/neldermead.bib
@@ -253,9 +253,9 @@ publisher= {}}
253} 253}
254 254
255@TECHREPORT{Andersson01multiobjectiveoptimization, 255@TECHREPORT{Andersson01multiobjectiveoptimization,
256 author = {Johan Andersson and Linköpings Universitet}, 256 author = {Johan Andersson and Link\"opings Universitet},
257 title = {Multiobjective Optimization in Engineering Design: Applications to . . .}, 257 title = {Multiobjective Optimization in Engineering Design: Application to Fluid Power Systems},
258 institution = {Department of Mechanical Engineering, Linköping University}, 258 institution = {Department of Mechanical Engineering, Link\"oping University},
259 year = {2001}, 259 year = {2001},
260 note={\url{https://polopoly.liu.se/content/1/c6/10/99/74/phdthesis.pdf}, 260 note={\url{https://polopoly.liu.se/content/1/c6/10/99/74/phdthesis.pdf},
261 \url{http://www.iei.liu.se/machine/johan-olvander/home"l=en}, 261 \url{http://www.iei.liu.se/machine/johan-olvander/home"l=en},
@@ -462,3 +462,12 @@ eprint = {http://comjnl.oxfordjournals.org/cgi/reprint/6/2/163.pdf}
462 address = {New York, NY, USA}, 462 address = {New York, NY, USA},
463 } 463 }
464 464
465@TECHREPORT{Fan2002,
466 author = {Ellen Fan},
467 title = {Global Optimization Of Lennard-Jones Atomic Clusters},
468 institution = {McMaster University},
469 year = {2002},
470 month = {February},
471 day={26}
472}
473
diff --git a/scilab_doc/neldermead/neldermead.pdf b/scilab_doc/neldermead/neldermead.pdf
index 856204e..c36eb3f 100644
--- a/scilab_doc/neldermead/neldermead.pdf
+++ b/scilab_doc/neldermead/neldermead.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead.tex b/scilab_doc/neldermead/neldermead.tex
index 951c8c5..1b927df 100644
--- a/scilab_doc/neldermead/neldermead.tex
+++ b/scilab_doc/neldermead/neldermead.tex
@@ -6,73 +6,7 @@
6% 6%
7\documentclass[12pt]{report} 7\documentclass[12pt]{report}
8 8
9%% Good fonts for PDF 9\include{macros}
10\usepackage[cyr]{aeguill}
11
12%% Package for page headers
13\usepackage{fancyhdr}
14
15%% Package to include graphics
16%% Comment for DVI
17\usepackage[pdftex]{graphicx}
18
19%% Figures formats: jpeg or pdf
20%% Comment for DVI
21\DeclareGraphicsExtensions{.jpg,.pdf}
22
23%% Package to create Hyperdocuments
24%% Comment for DVI
25\usepackage[pdftex,colorlinks=true,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
26
27%% Package to control printed area size
28\usepackage{anysize}
29%% ...by defining margins {left}{right}{top}{bottom}
30\marginsize{22mm}{14mm}{12mm}{25mm}
31
32%% Package used to include a bibliography
33\usepackage{natbib}
34
35%% R for real numbers
36\usepackage{amssymb}
37
38%% User defined commands
39
40%% Figure reference
41\newcommand{\figref}[1]{figure~\ref{#1}}
42
43%% Equation reference
44\newcommand{\Ref}[1]{(\ref{#1})}
45
46%% Emphasize a word or a group of words
47\newcommand{\empha}[1]{\textit{\textbf{#1}}}
48
49%% Derivation operators
50\newcommand{\D}{\partial}
51\newcommand{\Dt}{\partial_t}
52\newcommand{\Dx}{\partial_x}
53\newcommand{\Dy}{\partial_y}
54
55\newcommand{\bv}{\mathbf{v}}
56\newcommand{\bx}{\mathbf{x}}
57
58\usepackage{url}
59
60% Scilab macros
61\newcommand{\scimacro}[1]{\textit{#1}}
62\newcommand{\scicommand}[1]{\textit{#1}}
63
64% To highlight source code
65\usepackage{listings}
66
67\usepackage{algorithmic}
68
69% To allow one bibliograph by chapter
70%\usepackage[sectionbib]{chapterbib}
71\usepackage{url}
72
73% Maths shortcuts
74\newcommand{\RR}{\mathbb{R}}
75\newcommand{\CC}{\mathbb{C}}
76 10
77\begin{document} 11\begin{document}
78%% User defined page headers 12%% User defined page headers
@@ -118,8 +52,8 @@ $$
118\normalsize 52\normalsize
119 53
120\begin{flushright} 54\begin{flushright}
121Version 0.1 \\ 55Version 0.2 \\
122March 2009 56September 2009
123\end{flushright} 57\end{flushright}
124 58
125\begin{flushright} 59\begin{flushright}
@@ -139,9 +73,11 @@ Micha\"el BAUDIN
139 73
140\include{overview} 74\include{overview}
141 75
142\include{installation} 76\include{section-simplex}
77
78\include{method-spendley}
143 79
144\include{validation} 80\include{method-neldermead}
145 81
146\include{conclusion} 82\include{conclusion}
147 83
@@ -155,13 +91,6 @@ Micha\"el BAUDIN
155 91
156\include{implementations} 92\include{implementations}
157 93
158\include{section-simplex}
159
160\include{method-spendley}
161
162\include{method-neldermead}
163
164
165%% Bibliography 94%% Bibliography
166 95
167\addcontentsline{toc}{chapter}{Bibliography} 96\addcontentsline{toc}{chapter}{Bibliography}
diff --git a/scilab_doc/neldermead/nmbibliography.tex b/scilab_doc/neldermead/nmbibliography.tex
index a5191ab..3a23e03 100644
--- a/scilab_doc/neldermead/nmbibliography.tex
+++ b/scilab_doc/neldermead/nmbibliography.tex
@@ -177,7 +177,7 @@ satisfy the constraints.
177W. H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery, 177W. H. Press, Saul A. Teukolsky, William T. Vetterling and Brian P. Flannery,
1781992 1781992
179 179
180An ANSI C implementation of the Nelder-Mead algorithm is given. 180In this book \cite{NumericalRecipes}, an ANSI C implementation of the Nelder-Mead algorithm is given.
181The initial simplex is based on the axis. 181The initial simplex is based on the axis.
182The termination criterion is based on the relative difference of the 182The termination criterion is based on the relative difference of the
183function value of the best and worst vertices in the simplex. 183function value of the best and worst vertices in the simplex.
@@ -331,10 +331,10 @@ function typical in penalty methods.
331 331
332No numerical experiment is presented. 332No numerical experiment is presented.
333 333
334\section{√Ėlvander, 2001} 334\section{Andersson, 2001}
335 335
336"Multiobjective Optimization in Engineering Design - Application to fluid Power Systems" 336"Multiobjective Optimization in Engineering Design - Application to fluid Power Systems"
337Johan √Ėlvander (formerly Andersson), 2001 337Johan Andersson, 2001
338 338
339This PhD thesis \cite{Andersson01multiobjectiveoptimization} gives a brief overview of the Complex method by Box in 339This PhD thesis \cite{Andersson01multiobjectiveoptimization} gives a brief overview of the Complex method by Box in
340section 5.1. 340section 5.1.
diff --git a/scilab_doc/neldermead/overview.tex b/scilab_doc/neldermead/overview.tex
index 7aba210..9e044d1 100644
--- a/scilab_doc/neldermead/overview.tex
+++ b/scilab_doc/neldermead/overview.tex
@@ -7,16 +7,16 @@ toolbox as well as an example of use.
7\section{How to use the Toolbox} 7\section{How to use the Toolbox}
8 8
9The design of the toolbox is based on the creation of 9The design of the toolbox is based on the creation of
10a new token by the \scimacro{neldermead\_new} command. 10a new token by the \scifunction{neldermead\_new} command.
11The Nelder-Mead object associated with this token can then 11The Nelder-Mead object associated with this token can then
12be configured with \scimacro{neldermead\_configure} and queried 12be configured with \scifunction{neldermead\_configure} and queried
13with \scimacro{neldermead\_cget}. To be more specific, the 13with \scifunction{neldermead\_cget}. To be more specific, the
14\scimacro{neldermead\_configure} command allows to configure the 14\scifunction{neldermead\_configure} command allows to configure the
15number of variables, the objective function and the initial guess. 15number of variables, the objective function and the initial guess.
16 16
17The main command of the toolbox is the \scimacro{neldermead\_search} command, which 17The main command of the toolbox is the \scifunction{neldermead\_search} command, which
18solves the optimization problem. After an optimization has been performed, 18solves the optimization problem. After an optimization has been performed,
19the \scimacro{neldermead\_get} command allows to retrieve the optimum $x^\star$, 19the \scifunction{neldermead\_get} command allows to retrieve the optimum $x^\star$,
20as well as other parameters, such as the number of iterations performed, the number 20as well as other parameters, such as the number of iterations performed, the number
21of evaluations of the function, etc... 21of evaluations of the function, etc...
22 22
diff --git a/scilab_doc/neldermead/scripts/initialsimplex_axes.sce b/scilab_doc/neldermead/scripts/initialsimplex_axes.sce
new file mode 100644
index 0000000..3400bf1
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/initialsimplex_axes.sce
@@ -0,0 +1,29 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Draw a simplex along the axes in 2D
11x = zeros(4,1)
12y = zeros(4,1)
13
14// First point is (0,0)
15// Second point is (1,0)
16x(2) = 1.0
17y(2) = 0
18// Third point is (0,2)
19x(3) = 0.0
20y(3) = 2.0
21// Fourth point is (0,0), just to make the loop in the simplex
22// Now plot the simplex
23plot(x,y)
24f = gcf()
25f.children.children.children.thickness = 4
26f.children.children.children.mark_style = 9
27f.children.children.children.mark_foreground = 3
28f.children.children.children.mark_size = 10
29
diff --git a/scilab_doc/neldermead/scripts/initialsimplex_regular.sce b/scilab_doc/neldermead/scripts/initialsimplex_regular.sce
new file mode 100644
index 0000000..ff97221
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/initialsimplex_regular.sce
@@ -0,0 +1,33 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Draw a regular simplex in 2D
11n = 2
12p = (n - 1.0 + sqrt(n + 1))/(n * sqrt(2.0))
13q = (sqrt(n + 1) - 1.0)/(n * sqrt(2.0))
14
15x = zeros(4,1)
16y = zeros(4,1)
17
18// First point is (0,0)
19// Second point is (p,q)
20x(2) = p
21y(2) = q
22// Third point is (q,p)
23x(3) = q
24y(3) = p
25// Fourth point is (0,0), just to make the loop in the simplex
26// Now plot the simplex
27plot(x,y)
28f = gcf()
29f.children.children.children.thickness = 4
30f.children.children.children.mark_style = 9
31f.children.children.children.mark_foreground = 3
32f.children.children.children.mark_size = 10
33
diff --git a/scilab_doc/neldermead/section-simplex.tex b/scilab_doc/neldermead/section-simplex.tex
index b676b25..7b65b72 100644
--- a/scilab_doc/neldermead/section-simplex.tex
+++ b/scilab_doc/neldermead/section-simplex.tex
@@ -35,7 +35,6 @@ state a theoretical convergence result. In practical implementations, though, th
35ordering rules have no measurable influence. 35ordering rules have no measurable influence.
36 36
37Let $V$ denote the $n\times n$ matrix of simplex directions 37Let $V$ denote the $n\times n$ matrix of simplex directions
38
39\begin{eqnarray} 38\begin{eqnarray}
40\label{simplex-directions} 39\label{simplex-directions}
41V(S) = (\bx_2 - \bx_1, \bx_3 - \bx_1 , \ldots , \bx_{n+1} - \bx_1) = (\bv_1, \ldots , \bv_n) 40V(S) = (\bx_2 - \bx_1, \bx_3 - \bx_1 , \ldots , \bx_{n+1} - \bx_1) = (\bv_1, \ldots , \bv_n)
@@ -50,12 +49,11 @@ Several methods are available to compute the size of a simplex.
50In Kelley's book \cite{Kelley1999}, the author presents the diameter and the two oriented lengths. 49In Kelley's book \cite{Kelley1999}, the author presents the diameter and the two oriented lengths.
51 50
52The simplex diameter $diam(S)$ is defined by 51The simplex diameter $diam(S)$ is defined by
53
54\begin{eqnarray} 52\begin{eqnarray}
55\label{simplex-diameter} 53\label{simplex-diameter}
56diam(S) = \max_{i,j=1,n+1} \|\bx_i - \bx_j\| 54diam(S) = \max_{i,j=1,n+1} \|\bx_i - \bx_j\|_2,
57\end{eqnarray} 55\end{eqnarray}
58 56where $\|.\|_2$ is the euclidian norm $\|x\|_2 = \sum_{i=1,n}\bx_i^2$.
59In practical implementations, computing the diameter requires two nested loops over the 57In practical implementations, computing the diameter requires two nested loops over the
60vertices of the simplex, i.e. $(n+1)^2$ operations. This is why authors generally 58vertices of the simplex, i.e. $(n+1)^2$ operations. This is why authors generally
61prefer to use lengths which are less expensive to compute. 59prefer to use lengths which are less expensive to compute.
@@ -65,7 +63,7 @@ first vertex as the reference point and are defined by
65 63
66\begin{eqnarray} 64\begin{eqnarray}
67\label{simplex-sigma} 65\label{simplex-sigma}
68\sigma_+(S) = \max_{i=2,n+1} \|\bx_i - \bx_1\| \qquad \textrm { and } \qquad \sigma_-(S) = \min_{i=2,n+1} \|\bx_i - \bx_1\| 66\sigma_+(S) = \max_{i=2,n+1} \|\bx_i - \bx_1\|_2 \qquad \textrm { and } \qquad \sigma_-(S) = \min_{i=2,n+1} \|\bx_i - \bx_1\|_2
69\end{eqnarray} 67\end{eqnarray}
70 68
71The following inequalities are satisfied between the diameter and the maximum oriented length 69The following inequalities are satisfied between the diameter and the maximum oriented length
@@ -76,24 +74,165 @@ The following inequalities are satisfied between the diameter and the maximum or
76\end{eqnarray} 74\end{eqnarray}
77 75
78In Nash's book \cite{nla.cat-vn1060620}, the size of the simplex $s_N(S)$ is measured 76In Nash's book \cite{nla.cat-vn1060620}, the size of the simplex $s_N(S)$ is measured
79based on the $\l-1$ norm and is defined by 77based on the $l1$ norm and is defined by
80
81\begin{eqnarray} 78\begin{eqnarray}
82\label{simplex-sizenash} 79\label{simplex-sizenash}
83s_N(S) = \sum_{i=2,n+1} \|\bx_i - \bx_1\| 80s_N(S) = \sum_{i=2,n+1} \|\bx_i - \bx_1\|_1
84\end{eqnarray} 81\end{eqnarray}
85
86where 82where
87
88\begin{eqnarray} 83\begin{eqnarray}
89\label{simplex-sizenash2} 84\label{simplex-sizenash2}
90\|\bx_i - \bx_1\| = \sum_{i=1,n+1} |x_i^j - x_1^j| 85\|\bx_i - \bx_1\|_1 = \sum_{j=1,n} |x_i^j - x_1^j|
91\end{eqnarray} 86\end{eqnarray}
92
93where $x_i^j\in\RR$ is the $j$-th coordinate of the $i$-th vertex of the simplex $S$. 87where $x_i^j\in\RR$ is the $j$-th coordinate of the $i$-th vertex of the simplex $S$.
94 88
95\section{The initial simplex} 89\section{The initial simplex}
96 90
91While most of the theory can be developed without being very specific
92about the initial simplex, the initial simplex plays a very important role in practice.
93All approaches are based on the initial guess $\overline{\bx}_0\in\RR^n$ and create a
94geometric shape based on this point.
95
96In this section, we present the various approach to design the initial
97simplex. In the first part, we emphasize the importance of the initial
98simplex in optimization algorithms. Then we present the regular simplex
99approach by Spendley et al., the randomized bounds approach by Box and
100Pfeffer's method.
101
102\subsection{Importance of the initial simplex}
103
104The initial simplex is particularily important in the case of Spendley's et al
105method, where the shape of the simplex is fixed during the iterations.
106Therefore, the algorithm can only go through points which are on the pattern
107defined by the initial simplex. The pattern presented in figure \ref{fig-nm-simplex-fixedshape}
108is typical a fixed-shape simplex algorithm (see \cite{Torczon89multi-directionalsearch}, chapter 3,
109for other patterns of a direct search method).
110If, by chance, the pattern is so that the optimum is close to one point
111defined by the pattern, the number of iteration may be small. On the contrary, the
112number of iterations may be high if the pattern does not come close to the
113optimum.
114
115\begin{figure}
116\begin{center}
117\includegraphics[width=7cm]{simplex_initialfixed.png}
118\end{center}
119\caption{Typical pattern with fixed-shape Spendley's et al algorithm}
120\label{fig-nm-simplex-fixedshape}
121\end{figure}
122
123The variable-shape simplex algorithm designed by Nelder and Mead is also very
124sensitive to the initial simplex.
125One of the problems is that the initial simplex should be consistently scaled
126with respect to the unknown $x$.
127In \cite{parkinson1972}, "An investigation into the efficiency of variants on the simplex method",
128Parkinson and Hutchinson explored
129several ways of improvement. First, they investigate the sensitivity
130of the algorithm to the initial simplex. Two parameters were investigated,
131i.e. the initial length and the orientation of the simplex.
132The conclusion of their study with respect to the initial simplex is
133the following. "The orientation of the initial simplex has a significant effect
134on efficiency, but the relationship can be too sensitive for an automatic
135predictor to provide sufficient accuracy at this time."
136
137Since no initial simplex clearly improves on the others, in practice,
138it may be convenient to try different approaches.
139
140\subsection{Spendley's et al simplex}
141
142In their paper \cite{Spendley1962}, Spendley et al. use a regular
143simplex with given size $\ell>0$. We define the parameters $p,q>0$ as
144\begin{eqnarray}
145p &=& \frac{1}{n\sqrt{2}} \left(n-1 + \sqrt{n+1}\right), \\
146q &=& \frac{1}{n\sqrt{2}} \left(\sqrt{n+1} - 1\right).
147\end{eqnarray}
148We can now define the vertices of the simplex $S=\{\bx_i\}_{i=1,n+1}$.
149The first vertex of the simplex is the initial guess
150\begin{eqnarray}
151\bx_1 &=& \overline{\bx}_0.
152\end{eqnarray}
153The other vertices are defined by $\bx_i = \left( x_i^1, \ldots x_i^n\right)\in\RR^n$
154where the coordinates $x_i^j$ are
155\begin{eqnarray}
156x_i^j &=&
157\left\{
158\begin{array}{l}
159\overline{x}_0^j + \ell p, \textrm{ if } j=i-1,\\
160\overline{x}_0^j + \ell q, \textrm{ if } j\neq i-1,\\
161\end{array}
162\right.
163\end{eqnarray}
164for $i=2,n+1$ where $\ell \in\RR$ is the length of the simplex ($\ell>0$). Notice that this
165length is the same for all the vertices which keeps the simplex regular.
166
167The regular initial simplex is presented in figure \ref{fig-nm-simplex-regular}.
168
169\begin{figure}
170\begin{center}
171\includegraphics[width=10cm]{simplex_regular.png}
172\end{center}
173\caption{Regular simplex in 2 dimensions}
174\label{fig-nm-simplex-regular}
175\end{figure}
176
177\subsection{Simplex along the axes}
178
179A very efficient and simple approach leads to an axis-by-axis simplex.
180This simplex depends on a vector of positive lengths $\bl\in\RR^n$.
181The first vertex of the simplex is the initial guess
182\begin{eqnarray}
183\bx_1 &=& \overline{\bx}_0.
184\end{eqnarray}
185The other vertices are defined by
186\begin{eqnarray}
187x_i^j &=&
188\left\{
189\begin{array}{l}
190\overline{x}_0^j + \bl_j, \textrm{ if } j=i-1,\\
191\overline{x}_0^j, \textrm{ if } j\neq i-1,\\
192\end{array}
193\right.
194\end{eqnarray}
195for $i=2,n+1$
196
197This kind of simplex is presented in figure \ref{fig-nm-simplex-axes}.
198The axis-by-axis approach is used in the very popular Nelder-Mead
199algorithm provided in Numerical Recipes in C \cite{NumericalRecipes}.
200As stated in \cite{NumericalRecipes}, the length vector $\bl$ can
201be used as a guess for the characteristic length scale of the problem.
202
203\begin{figure}
204\begin{center}
205\includegraphics[width=10cm]{simplex_axes.png}
206\end{center}
207\caption{Axis-based simplex in 2 dimensions}
208\label{fig-nm-simplex-axes}
209\end{figure}
210
211\subsection{Randomized bounds}
212
213Assume that the variable $\bx\in\RR^n$ is bounded so that
214\begin{eqnarray}
215m^j \leq x^j \leq M^j,
216\end{eqnarray}
217for $j=1,n$, where $m_j,M_j\in\RR$ are minimum and maximum bounds and $m_j\leq M_j$.
218A method suggested by Box in \cite{Box1965} is based on the use of
219pseudo-random numbers. Let $\{\theta_i^j\}_{i=1,n+1,j=1,n}\in[0,1]$ be
220a sequence of random numbers uniform in the interval $[0,1]$.
221The first vertex of the simplex is the initial guess
222\begin{eqnarray}
223\bx_1 &=& \overline{\bx}_0.
224\end{eqnarray}
225The other vertices are defined by
226\begin{eqnarray}
227x_i^j &=& m^j + \theta_i^j (M^j - m^j),
228\end{eqnarray}
229for $i=2,n+1$.
230
231\subsection{Pfeffer's method}
232
233This initial simplex is used in the function \scifunction{fminsearch}
234and presented in \cite{Fan2002}. It is due to L. Pfeffer at Stanford.
235
97TODO... 236TODO...
98 237
99\section{The simplex gradient} 238\section{The simplex gradient}
diff --git a/scilab_doc/neldermead/simplex_axes.png b/scilab_doc/neldermead/simplex_axes.png
new file mode 100644
index 0000000..5f4ae08
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_axes.png
Binary files differ
diff --git a/scilab_doc/neldermead/simplex_initialfixed.png b/scilab_doc/neldermead/simplex_initialfixed.png
new file mode 100644
index 0000000..19744b1
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_initialfixed.png
Binary files differ
diff --git a/scilab_doc/neldermead/simplex_initialfixed.svg b/scilab_doc/neldermead/simplex_initialfixed.svg
new file mode 100644
index 0000000..570e699
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_initialfixed.svg
@@ -0,0 +1,186 @@
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="simplex_initialfixed.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="D:\Baudin\ProjetScilab\git\scilab\scilab_doc\neldermead\simplex_initialfixed.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.7"
52 inkscape:cx="442.35299"
53 inkscape:cy="588.84474"
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="23"
60 inkscape:window-y="23" />
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:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
99 d="M 365.56905,409.49836 L 427.80761,277.51322 L 513.06083,388.13428 L 365.56905,409.49836 z"
100 id="path2423"
101 sodipodi:nodetypes="cccc" />
102 <path
103 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
104 d="M 38.11719,409.08117 L 709.32476,409.08117"
105 id="path2441" />
106 <path
107 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
108 d="M 365.58855,686.84184 L 365.58855,89.452684"
109 id="path3734" />
110 <path
111 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
112 d="M 303.03042,540.90943 L 365.26898,408.92428 L 450.52221,519.54534 L 303.03042,540.90943 z"
113 id="path3772"
114 sodipodi:nodetypes="cccc" />
115 <path
116 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
117 d="M 450.54214,519.44989 L 512.7807,387.46474 L 598.03392,498.0858 L 450.54214,519.44989 z"
118 id="path3776"
119 sodipodi:nodetypes="cccc" />
120 <path
121 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
122 d="M 217.47355,430.6039 L 279.71211,298.61875 L 364.96534,409.23981 L 217.47355,430.6039 z"
123 id="path3778"
124 sodipodi:nodetypes="cccc" />
125 <path
126 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
127 d="M 279.54404,297.94345 L 341.7826,165.9583 L 427.03582,276.57936 L 279.54404,297.94345 z"
128 id="path3780"
129 sodipodi:nodetypes="cccc" />
130 <path
131 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
132 d="M 428.02637,276.64475 L 490.26493,144.65961 L 575.51815,255.28066 L 428.02637,276.64475 z"
133 id="path3782"
134 sodipodi:nodetypes="cccc" />
135 <path
136 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
137 d="M 513.22116,388.00651 L 575.45973,256.02136 L 660.71295,366.64242 L 513.22116,388.00651 z"
138 id="path3784"
139 sodipodi:nodetypes="cccc" />
140 <path
141 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
142 d="M 155.40306,562.65582 L 217.64162,430.67067 L 302.89484,541.29173 L 155.40306,562.65582 z"
143 id="path3786"
144 sodipodi:nodetypes="cccc" />
145 <path
146 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
147 d="M 131.67023,319.24215 L 193.90879,187.25699 L 279.16202,297.87806 L 131.67023,319.24215 z"
148 id="path3788"
149 sodipodi:nodetypes="cccc" />
150 <path
151 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
152 d="M 69.599741,452.51113 L 131.8383,320.52598 L 217.09153,431.14704 L 69.599741,452.51113 z"
153 id="path3790"
154 sodipodi:nodetypes="cccc" />
155 <path
156 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
157 d="M 240.49209,674.52036 L 302.73065,542.53521 L 387.98388,653.15627 L 240.49209,674.52036 z"
158 id="path3792"
159 sodipodi:nodetypes="cccc" />
160 <path
161 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
162 d="M 388.47165,652.82463 L 450.71021,520.83948 L 535.96344,631.46054 L 388.47165,652.82463 z"
163 id="path3794"
164 sodipodi:nodetypes="cccc" />
165 <text
166 xml:space="preserve"
167 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"
168 x="311.12698"
169 y="86.656349"
170 id="text3840"><tspan
171 sodipodi:role="line"
172 id="tspan3842"
173 x="311.12698"
174 y="86.656349">y</tspan></text>
175 <text
176 xml:space="preserve"
177 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"
178 x="717.20831"
179 y="458.39249"
180 id="text3844"><tspan
181 sodipodi:role="line"
182 x="717.20831"
183 y="458.39249"
184 id="tspan3848">x</tspan></text>
185 </g>
186</svg>
diff --git a/scilab_doc/neldermead/simplex_regular.png b/scilab_doc/neldermead/simplex_regular.png
new file mode 100644
index 0000000..8b44375
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_regular.png
Binary files differ