summaryrefslogtreecommitdiffstats log msg author committer range
path: root/scilab_doc
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer Michael Baudin 2009-10-05 21:57:48 +0200 Michael Baudin 2009-10-05 21:57:48 +0200 5e2e6729fab0b8e212b26daa2ab8252869add7c8 (patch) bfbb53e075544525a8d67bcd0a8c79302bbce1a7 /scilab_doc dc8c3a2df5cd66c22ed76ab0f3c348d6a825a164 (diff) scilab-5e2e6729fab0b8e212b26daa2ab8252869add7c8.zipscilab-5e2e6729fab0b8e212b26daa2ab8252869add7c8.tar.gz
Transformed figures into pdf. Fixed inconsistency in the notations.
Diffstat (limited to 'scilab_doc')
 diff --git a/scilab_doc/neldermead/chapter-notations.tex b/scilab_doc/neldermead/chapter-notations.texnew file mode 100644index 0000000..226bcfe--- /dev/null+++ b/scilab_doc/neldermead/chapter-notations.tex @@ -0,0 +1,23 @@ 1 \chapter*{Notations} 2 3 4 \begin{figure}[h] 5 \begin{center} 6 \begin{tabular}{|l|l|} 7 \hline 8 $n$ & number of variables\\ 9 $\bx=(x_1,x_2,\ldots,x_n)^T \in\RR^n$ & the unknown\\ 10 $\bx_0\in\RR^n$ & the initial guess\\ 11 $\bv\in\RR^n$ & a vertex\\ 12 $S=\{\bv_i\}_{i=1,m}$ & a complex, where $m\geq n+1$ is the number of vertices\\ 13 $S=\{\bv_i\}_{i=1,n+1}$ & a simplex (with $n+1$ vertices)\\ 14 $(\bv_i)_j$ & the $j$-th component of the $i$-th vertex\\ 15 $S_0$& the initial simplex\\ 16 $S_k$& the simplex at iteration $k$\\ 17 $f:\RR^n\rightarrow\RR$& the cost function\\ 18 \hline 19 \end{tabular} 20 \end{center} 21 \caption{Notations used in this document} 22 \label{fig-notations} 23 \end{figure} diff --git a/scilab_doc/neldermead/fminsearch-so.idx b/scilab_doc/neldermead/fminsearch-so.idxnew file mode 100644index 0000000..e69de29--- /dev/null+++ b/scilab_doc/neldermead/fminsearch-so.idx diff --git a/scilab_doc/neldermead/fminsearch-so.ilg b/scilab_doc/neldermead/fminsearch-so.ilgnew file mode 100644index 0000000..cea57f1--- /dev/null+++ b/scilab_doc/neldermead/fminsearch-so.ilg @@ -0,0 +1,4 @@ 1 This is makeindex, version 2.14 [02-Oct-2002] (kpathsea + Thai support). 2 Scanning input file fminsearch-so.idx...done (0 entries accepted, 0 rejected). 3 Nothing written in fminsearch-so.ind. 4 Transcript written in fminsearch-so.ilg. diff --git a/scilab_doc/neldermead/fminsearch-so.ind b/scilab_doc/neldermead/fminsearch-so.indnew file mode 100644index 0000000..e69de29--- /dev/null+++ b/scilab_doc/neldermead/fminsearch-so.ind diff --git a/scilab_doc/neldermead/fminsearch-so.pdf b/scilab_doc/neldermead/fminsearch-so.pdfnew file mode 100644index 0000000..6604bc16--- /dev/null+++ b/scilab_doc/neldermead/fminsearch-so.pdf Binary files differ diff --git a/scilab_doc/neldermead/fminsearch-so.tex b/scilab_doc/neldermead/fminsearch-so.texnew file mode 100644index 0000000..e364aa9--- /dev/null+++ b/scilab_doc/neldermead/fminsearch-so.tex @@ -0,0 +1,86 @@ 1 \documentclass[12pt]{report} 2 3 \include{macros} 4 5 \begin{document} 6 %% User defined page headers 7 \pagestyle{fancyplain} 8 \renewcommand{\chaptermark}[1]{\markboth{\chaptername\ \thechapter. #1}{}} 9 \renewcommand{\sectionmark}[1]{\markright{\thesection. #1}} 10 \lhead[]{\fancyplain{}{\bfseries\leftmark}} 11 \rhead[]{\fancyplain{}{\bfseries\thepage}} 12 \cfoot{} 13 14 %% User defined figure legends 15 \makeatletter 16 \def\figurename{{\protect\sc \protect\small\bfseries Fig.}} 17 \def\f@ffrench{\protect\figurename\space{\protect\small\bf \thefigure}\space} 18 \let\fnum@figure\f@ffrench% 19 \let\captionORI\caption 20 \def\caption#1{\captionORI{\rm\small #1}} 21 \makeatother 22 23 %% First page 24 \thispagestyle{empty} 25 { 26 \begin{center} 27 %% Comment for DVI 28 \includegraphics[height=40mm]{scilab_logo} 29 \vskip2cm 30 31 %% Empty space between the box and the text 32 \fboxsep6mm 33 %% Box thickness 34 \fboxrule1.3pt 35 \Huge 36 $$\fbox{ 37 \begin{array}{c} 38 \textbf{Nelder-Mead}\\ 39 \textbf{User's Manual}\\ 40 \textbf{-- The Fminsearch Function --}\\ 41 \end{array} 42 } 43$$ 44 \end{center} 45 46 \vskip1cm 47 48 \begin{center} 49 \begin{large} 50 Micha\"el BAUDIN 51 \end{large} 52 \end{center} 53 54 \vskip2cm 55 56 57 \vskip1cm 58 59 60 \begin{flushright} 61 Version 0.3 \\ 62 September 2009 63 \end{flushright} 64 65 66 67 \clearpage 68 69 70 \tableofcontents 71 72 \include{fminsearch} 73 74 \clearpage 75 76 %% Bibliography 77 78 \addcontentsline{toc}{chapter}{Bibliography} 79 \bibliographystyle{plain} 80 \bibliography{neldermead} 81 82 % Index 83 \printindex 84 85 \end{document} 86 diff --git a/scilab_doc/neldermead/fminsearch.tex b/scilab_doc/neldermead/fminsearch.texnew file mode 100644index 0000000..85dac9f--- /dev/null+++ b/scilab_doc/neldermead/fminsearch.tex @@ -0,0 +1,180 @@ 1 \chapter{The \scifunction{fminsearch} function} 2 3 In this chapter, we analyze the implementation of the \scifunction{fminsearch} 4 which is provided in Scilab. In the first part, we describe the specific 5 choices of this implementation with respect to the Nelder-Mead algorithm. 6 In the second part, we present some numerical experiments which 7 allows to check that the feature is behaving as expected, by comparison 8 to Matlab's \scifunction{fminsearch}. 9 10 \section{\scifunction{fminsearch}'s algorithm} 11 12 \subsection{The algorithm} 13 14 The algorithm used is the Nelder-Mead algorithm. This corresponds to the 15 "variable" value of the "-method" option of the \scifunction{neldermead}. 16 The "non greedy" version is used, that is, the expansion point is 17 accepted only if it improves over the reflection point. 18 19 \subsection{The initial simplex} 20 21 The fminsearch algorithm uses a special initial simplex, which is an 22 heuristic depending on the initial guess. The strategy chosen by 23 fminsearch corresponds to the -simplex0method flag of the neldermead 24 component, with the "pfeffer" method. It is associated with the - 25 simplex0deltausual = 0.05 and -simplex0deltazero = 0.0075 parameters. 26 Pfeffer's method is an heuristic which is presented in "Global 27 Optimization Of Lennard-Jones Atomic Clusters" by Ellen Fan \cite{Fan2002}. 28 It is due to L. Pfeffer at Stanford. See in the help of optimsimplex for more 29 details. 30 31 \subsection{The number of iterations} 32 33 In this section, we present the default values for the number of 34 iterations in fminsearch. 35 36 The options input argument is an optionnal data structure which can 37 contain the options.MaxIter field. It stores the maximum number of 38 iterations. The default value is 200n, where n is the number of 39 variables. The factor 200 has not been chosen by chance, but is the 40 result of experiments performed against quadratic functions with 41 increasing space dimension. 42 43 This result is presented in "Effect of dimensionality on the nelder-mead 44 simplex method" by Lixing Han and Michael Neumann \cite{HanNeumann2006}. This paper is based 45 on Lixing Han's PhD, "Algorithms in Unconstrained Optimization" \cite{Han2000}. The 46 study is based on numerical experiment with a quadratic function where 47 the number of terms depends on the dimension of the space (i.e. the 48 number of variables). Their study shows that the number of iterations 49 required to reach the tolerance criteria is roughly 100n. Most 50 iterations are based on inside contractions. Since each step of the 51 Nelder-Mead algorithm only require one or two function evaluations, the 52 number of required function evaluations in this experiment is also 53 roughly 100n. 54 55 \subsection{The termination criteria} 56 57 The algorithm used by \scifunction{fminsearch} uses a particular 58 termination criteria, based both on the absolute size of the 59 simplex and the difference of the function values in the simplex. 60 This termination criteria corresponds to the "-tolssizedeltafvmethod" 61 termination criteria of the \scifunction{neldermead} component. 62 63 The size of the simplex is computed with the $\sigma-+$ method, 64 which corresponds to the "sigmaplus" method of the \scifunction{optimsimplex} 65 component. The tolerance associated with this criteria is 66 given by the "TolX" parameter of the \scifunction{options} data structure. 67 Its default value is 1.e-4. 68 69 The function value difference is the difference 70 between the highest and the lowest function value in the simplex. 71 The tolerance associated with this criteria is given by the 72 "TolFun" parameter of the \scifunction{options} data structure. 73 Its default value is 1.e-4. 74 75 \section{Numerical experiments} 76 77 In this section, we analyse the behaviour of Scilab's \scifunction{fminsearch} 78 function, by comparison of Matlab's \scifunction{fminsearch}. We especially analyse 79 the results of the optimization, so that we can check that the algorithm 80 is indeed behaving the same way, even if the implementation is completely 81 different. Our test case is based on Rosenbrock's function. 82 83 The following Matlab script allows to see the behaviour of Matlab's \scifunction{fminsearch} 84 function on Rosenbrock's test case. 85 86 \lstset{language=scilabscript} 87 \begin{lstlisting} 88 format long 89 banana = @(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2; 90 [x,fval,exitflag,output] = fminsearch(banana,[-1.2, 1]) 91 output.message 92 \end{lstlisting} 93 94 When this script is launched in Matlab, the following output is 95 produced. 96 97 \lstset{language=scilabscript} 98 \begin{lstlisting} 99 >> format long 100 >> banana = @(x)100*(x(2)-x(1)^2)^2+(1-x(1))^2; 101 >> [x,fval] = fminsearch(banana,[-1.2, 1]) 102 >> [x,fval,exitflag,output] = fminsearch(banana,[-1.2, 1]) 103 x = 104 1.000022021783570 1.000042219751772 105 fval = 106 8.177661197416674e-10 107 exitflag = 108 1 109 output = 110 iterations: 85 111 funcCount: 159 112 algorithm: 'Nelder-Mead simplex direct search' 113 message: [1x194 char] 114 >> output.message 115 ans = 116 Optimization terminated: 117 the current x satisfies the termination criteria using 118 OPTIONS.TolX of 1.000000e-04 119 and F(X) satisfies the convergence criteria using 120 OPTIONS.TolFun of 1.000000e-04 121 \end{lstlisting} 122 123 The following Scilab script allows to solve the problem with Scilab's 124 \scifunction{fminsearch}. 125 126 \lstset{language=scilabscript} 127 \begin{lstlisting} 128 format(25) 129 function y = banana (x) 130 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; 131 endfunction 132 [x , fval , exitflag , output] = fminsearch ( banana , [-1.2 1] ) 133 output.message 134 \end{lstlisting} 135 136 The output associated with this Scilab script is the following. 137 138 \lstset{language=scilabscript} 139 \begin{lstlisting} 140 -->format(25) 141 -->function y = banana (x) 142 --> y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; 143 -->endfunction 144 -->[x , fval , exitflag , output] = fminsearch ( banana , [-1.2 1] ) 145 output = 146 algorithm: "Nelder-Mead simplex direct search" 147 funcCount: 159 148 iterations: 85 149 message: [3x1 string] 150 exitflag = 151 1. 152 fval = 153 0.0000000008177661099387 154 x = 155 1.0000220217835567027009 1.0000422197517710998227 156 -->output.message 157 ans = 158 159 !Optimization terminated: ! 160 ! ! 161 !the current x satisfies the termination criteria using OPTIONS.TolX of 1.000000e-004 ! 162 ! ! 163 !and F(X) satisfies the convergence criteria using OPTIONS.TolFun of 1.000000e-004 ! 164 \end{lstlisting} 165 166 The result is as close as possible to the result produced 167 by Matlab. More specifically : 168 \begin{itemize} 169 \item the optimum $x$ is the same up to 14 significant digits, 170 \item the function value at optimum is the same up to 9 significant digits, 171 \item the number of iterations is the same, 172 \item the number of function evaluations is the same, 173 \item the exit flag is the same, 174 \item the content of the output is the same (but the string is not 175 display the same way). 176 \end{itemize} 177 178 179 %TODO : check that the iterations are the same 180 diff --git a/scilab_doc/neldermead/implementations.tex b/scilab_doc/neldermead/implementations.texindex 150f0ef..2c15246 100644--- a/scilab_doc/neldermead/implementations.tex+++ b/scilab_doc/neldermead/implementations.tex @@ -1,13 +1,13 @@ 1 \chapter{Implementations of the Nelder-Mead algorithm} 1 \chapter{Implementations of the Nelder-Mead algorithm} 2 2 3 In the following sections, we analyse the various implementations of the 3 In the following sections, we analyze the various implementations of the 4 Nelder-Mead algorithm. We analyse the Matlab implementation provided 4 Nelder-Mead algorithm. We analyze the Matlab implementation provided 5 by the \emph{fminsearch} command. We analyse the matlab algorithm provided by 5 by the \emph{fminsearch} command. We analyze the matlab algorithm provided by 6 C.T. Kelley and the Scilab port by Y. Collette. We 6 C.T. Kelley and the Scilab port by Y. Collette. We 7 present the Numerical Recipes implementations. We analyse the O'Neill 7 present the Numerical Recipes implementations. We analyze the O'Neill 8 fortran 77 implementation "AS47". The Burkardt implementation is also covered. 8 fortran 77 implementation "AS47". The Burkardt implementation is also covered. 9 The implementation provided in the NAG collection is detailed. 9 The implementation provided in the NAG collection is detailed. 10 The Nelder-Mead algorithm from the Gnu Scientific Library is analysed. 10 The Nelder-Mead algorithm from the Gnu Scientific Library is analyzed. 11 11 12 \section{Matlab : fminsearch} 12 \section{Matlab : fminsearch} 13 13 diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.texindex cc4b0a3..e041af1 100644--- a/scilab_doc/neldermead/introduction.tex+++ b/scilab_doc/neldermead/introduction.tex @@ -66,7 +66,7 @@ criteria. 66 \item The "fminsearch" component provides a Scilab commands which aims 66 \item The "fminsearch" component provides a Scilab commands which aims 67 at behaving as Matlab's fminsearch. Specific terminations criteria, 67 at behaving as Matlab's fminsearch. Specific terminations criteria, 68 initial simplex and auxiliary settings are automatically configured so 68 initial simplex and auxiliary settings are automatically configured so 69 that the behaviour of Matlab's fminsearch is exactly reproduced. 69 that the behavior of Matlab's fminsearch is exactly reproduced. 70 \item The "optimset" and "optimget" components provide Scilab commands 70 \item The "optimset" and "optimget" components provide Scilab commands 71 to emulate their Matlab counterparts. 71 to emulate their Matlab counterparts. 72 \item The "nmplot" component provides features to 72 \item The "nmplot" component provides features to @@ -168,10 +168,7 @@ is used, which corresponds to the "variable" value of the "-method" option. 168 The verbose mode is enabled so that messages are generated during the algorithm. 168 The verbose mode is enabled so that messages are generated during the algorithm. 169 After the optimization is performed, the optimum is retrieved with quiery features. 169 After the optimization is performed, the optimum is retrieved with quiery features. 170 170 171 \lstset{language=Scilab} 171 \lstset{language=scilabscript} 172 \lstset{numbers=left} 173 \lstset{basicstyle=\footnotesize} 174 \lstset{keywordstyle=\bfseries} 175 \begin{lstlisting} 172 \begin{lstlisting} 176 function y = rosenbrock (x) 173 function y = rosenbrock (x) 177 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; 174 y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2; @@ -193,10 +190,7 @@ nm = neldermead_destroy(nm); 193 190 194 This produces the following output. 191 This produces the following output. 195 192 196 \lstset{language=Scilab} 193 \lstset{language=scilabscript} 197 \lstset{numbers=left} 198 \lstset{basicstyle=\footnotesize} 199 \lstset{keywordstyle=\bfseries} 200 \begin{lstlisting} 194 \begin{lstlisting} 201 -->nm = neldermead_search(nm); 195 -->nm = neldermead_search(nm); 202 Function Evaluation #1 is [24.2] at [-1.2 1] 196 Function Evaluation #1 is [24.2] at [-1.2 1] @@ -314,10 +308,7 @@ and are presented in figure \ref{fig-intro-demos}. 314 The following script shows where the demonstration scripts are 308 The following script shows where the demonstration scripts are 315 available from the Scilab installation directory. 309 available from the Scilab installation directory. 316 310 317 \lstset{language=Scilab} 311 \lstset{language=scilabscript} 318 \lstset{numbers=left} 319 \lstset{basicstyle=\footnotesize} 320 \lstset{keywordstyle=\bfseries} 321 \begin{lstlisting} 312 \begin{lstlisting} 322 -->cd SCI/modules/optimization/demos/neldermead 313 -->cd SCI/modules/optimization/demos/neldermead 323 ans = 314 ans = @@ -361,4 +352,3 @@ a good source of information on how to use the functions. 361 352 362 353 363 354 364 diff --git a/scilab_doc/neldermead/macros.tex b/scilab_doc/neldermead/macros.texindex 8c9af33..9464b36 100644--- a/scilab_doc/neldermead/macros.tex+++ b/scilab_doc/neldermead/macros.tex @@ -8,6 +8,10 @@ 8 %% Comment for DVI 8 %% Comment for DVI 9 \usepackage[pdftex]{graphicx} 9 \usepackage[pdftex]{graphicx} 10 10 11 %% Index 12 \usepackage{makeidx} 13 \makeindex 14 11 %% Figures formats: jpeg or pdf 15 %% Figures formats: jpeg or pdf 12 %% Comment for DVI 16 %% Comment for DVI 13 \DeclareGraphicsExtensions{.jpg,.pdf} 17 \DeclareGraphicsExtensions{.jpg,.pdf} @@ -47,6 +51,8 @@ 47 \newcommand{\bv}{\mathbf{v}} 51 \newcommand{\bv}{\mathbf{v}} 48 \newcommand{\bx}{\mathbf{x}} 52 \newcommand{\bx}{\mathbf{x}} 49 \newcommand{\bl}{\mathbf{l}} 53 \newcommand{\bl}{\mathbf{l}} 54 \newcommand{\br}{\mathbf{r}} 55 \newcommand{\bg}{\mathbf{g}} 50 56 51 \usepackage{url} 57 \usepackage{url} 52 58 @@ -231,4 +237,8 @@ 231 \newcommand{\RR}{\mathbb{R}} 237 \newcommand{\RR}{\mathbb{R}} 232 \newcommand{\CC}{\mathbb{C}} 238 \newcommand{\CC}{\mathbb{C}} 233 239 240 % For symbol degree 241 \DeclareTextSymbol{\degre}{T1}{6} 242 243 234 244 diff --git a/scilab_doc/neldermead/mcKinnon-insidecontraction.pdf b/scilab_doc/neldermead/mcKinnon-insidecontraction.pdfnew file mode 100644index 0000000..883176b--- /dev/null+++ b/scilab_doc/neldermead/mcKinnon-insidecontraction.pdf Binary files differ diff --git a/scilab_doc/neldermead/mcKinnon-insidecontraction.svg b/scilab_doc/neldermead/mcKinnon-insidecontraction.svgnew file mode 100644index 0000000..6ee8589--- /dev/null+++ b/scilab_doc/neldermead/mcKinnon-insidecontraction.svg @@ -0,0 +1,363 @@ 1 2 3 diff --git a/scilab_doc/neldermead/method-neldermead.tex b/scilab_doc/neldermead/method-neldermead.texindex 8e9fd1f..35398c3 100644--- a/scilab_doc/neldermead/method-neldermead.tex+++ b/scilab_doc/neldermead/method-neldermead.tex @@ -3,56 +3,76 @@ 3 In this chapter, we present Nelder and Mead's \cite{citeulike:3009487} algorithm. 3 In this chapter, we present Nelder and Mead's \cite{citeulike:3009487} algorithm. 4 We begin by the analysis of the algorithm, which is based on a variable shape simplex. 4 We begin by the analysis of the algorithm, which is based on a variable shape simplex. 5 Then, we present geometric situations where the various steps of the algorithm 5 Then, we present geometric situations where the various steps of the algorithm 6 might be used. In the third part, we present the rate of convergence toward the optimum of 6 are used. In the third part, we present the rate of convergence toward the optimum of 7 the Nelder-Mead algorithm. This part is mainly based on Han and Neumann's paper \cite{HanNeumann2006}, 7 the Nelder-Mead algorithm. This part is mainly based on Han and Neumann's paper \cite{HanNeumann2006}, 8 which is based on a class of quadratic functions with a special initial 8 which makes use of a class of quadratic functions with a special initial 9 simplex. The core of this chapter is the analysis of several numerical 9 simplex. The core of this chapter is the analysis of several numerical 10 experiments which have been performed with the neldermead component. 10 experiments which have been performed with the neldermead component. 11 We analyse the behaviour of the algorithm on quadratic functions and 11 We analyze the behavior of the algorithm on quadratic functions and 12 present several counter examples where the Nelder-Mead algorithm is 12 present several counter examples where the Nelder-Mead algorithm is 13 known to fail. 13 known to fail. 14 14 15 \section{Introduction} 15 \section{Introduction} 16 16 17 The goal of Nelder and Mead algorithm is to solve the 17 In this section, we present the Nelder-Mead algorithm for unconstrained optimization. 18 This algorithm is based on the iterative update of a simplex. 19 Then we present various geometric situations which might occur 20 during the algorithm. 21 22 \subsection{Overview} 23 24 The goal of the Nelder and Mead algorithm is to solve the 18 following unconstrained optimization problem 25 following unconstrained optimization problem 19 \begin{eqnarray} 26 \begin{eqnarray} 20 \min f(x) 27 \min f(\bx) 21 \end{eqnarray} 28 \end{eqnarray} 22 where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 29 where $\bx\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 23 function $f:\RR^n\rightarrow \RR$. 30 function $f:\RR^n\rightarrow \RR$. 24 31 25 The Nelder-Mead method is an improvment over the Spendley's et al. 32 The Nelder-Mead method is an improvement over the Spendley's et al. 26 method with the goal of allowing the simplex to vary in shape. 33 method with the goal of allowing the simplex to vary in \emph{shape}, 27 The Nelder-Mead algorithm makes use of four parameters: the 34 and not only in \emph{size}, as in Spendley's et al. algorithm. 28 coefficient of reflection $\rho$, expansion $\chi$, 29 contraction $\gamma$ and shrinkage $\sigma$. 30 When the expansion or contraction steps are performed, the shape 31 of the simplex is changed, thus "adapting itself to the 32 local landscape" \cite{citeulike:3009487}. 33 35 34 These parameters should satisfy the following inequalities \cite{citeulike:3009487,lagarias:112} 36 This algorithms is based on the iterative update of 35 \begin{eqnarray} 37 a \emph{simplex} made of $n+1$ points $S=\{\bv_i\}_{i=1,n+1}$. Each point 36 \label{condition-coeffs} 38 in the simplex is called a \emph{vertex} and is associated with 37 \rho>0, \qquad \chi > 1, \qquad \chi > \rho, \qquad 0<\gamma<1, \qquad \textrm{and} \qquad 0<\sigma<1. 39 a function value $f_i=f(\bv_i)$ for $i=1,n+1$. 38 \end{eqnarray} 39 40 40 The standard values for these coefficients are 41 The vertices are sorted by increasing function values so that the 42 \emph{best} vertex has index 1 and the \emph{worst} vertex 43 has index $n+1$ 41 \begin{eqnarray} 44 \begin{eqnarray} 42 \label{standard-coeffs} 45 \label{sorted-vertices-fv} 43 \rho=1, \qquad \chi =2, \qquad \gamma=\frac{1}{2}, \qquad \textrm{and} \qquad \sigma=\frac{1}{2}. 46 f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 44 \end{eqnarray} 47 \end{eqnarray} 45 48 46 In \cite{Kelley1999}, the Nelder-Mead algorithm is presented with 49 The $\bv_1$ vertex (resp. the $\bv_{n+1}$ vertex) is called the \emph{best} 47 other parameter names, that is $\mu_r = \rho$, $\mu_e = \rho\chi$, $\mu_{ic} = -\gamma$ 50 vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest) 48 and $\mu_{oc} = \rho\gamma$. These coefficients must satisfy the following 51 function value. 49 inequality 50 52 53 The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices 54 where the vertex $\bv_j$ has been 55 excluded. This centroid is 51 \begin{eqnarray} 56 \begin{eqnarray} 52 -1 < \mu_{ic} < 0 < \mu_{oc} < \mu_r < \mu_e 57 \label{centroid-generalized} 58 \overline{\bx} (j) = 59 \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i. 53 \end{eqnarray} 60 \end{eqnarray} 61 The algorithm makes use 62 of one coefficient $\rho>0$, called the reflection factor. The standard 63 value of this coefficient is $\rho=1$. 64 The algorithm attempts to replace some vertex 65 $\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$ 66 to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by 67 \begin{eqnarray} 68 \label{interpolate-generalized} 69 \bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j. 70 \end{eqnarray} 71 72 \subsection{Algorithm} 54 73 55 The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}. 74 In this section, we analyze the Nelder-Mead algorithm, which 75 is presented in figure \ref{algo-neldermead}. 56 76 57 \begin{figure}[htbp] 77 \begin{figure}[htbp] 58 \begin{algorithmic} 78 \begin{algorithmic} @@ -61,9 +81,11 @@ The Nelder-Mead algorithm is presented in figure \ref{algo-neldermead}. 61 \STATE $S\gets S_0$ 81 \STATE $S\gets S_0$ 62 \WHILE{$\sigma(S)>tol$} 82 \WHILE{$\sigma(S)>tol$} 63 \STATE $\overline{x}\gets \overline{x}(n+1)$ 83 \STATE $\overline{x}\gets \overline{x}(n+1)$ 64 \STATE $x_r \gets x(\rho,n+1)$, $f_r \gets f(x_r)$ \COMMENT{Reflect} 84 \STATE $x_r \gets x(\rho,n+1)$ \COMMENT{Reflect} 85 \STATE $f_r \gets f(x_r)$ 65 \IF {$f_r0, \qquad \chi > 1, \qquad \chi > \rho, \qquad 0<\gamma<1 \qquad \textrm{and} \qquad 0<\sigma<1. 133 \end{eqnarray} 134 The standard values for these coefficients are 135 \begin{eqnarray} 136 \label{standard-coeffs} 137 \rho=1, \qquad \chi =2, \qquad \gamma=\frac{1}{2} \qquad \textrm{and} \qquad \sigma=\frac{1}{2}. 138 \end{eqnarray} 139 140 In \cite{Kelley1999}, the Nelder-Mead algorithm is presented with 141 other parameter names, that is$\mu_r = \rho$,$\mu_e = \rho\chi$,$\mu_{ic} = -\gamma$142 and$\mu_{oc} = \rho\gamma$. These coefficients must satisfy the following 143 inequality 144 \begin{eqnarray} 145 -1 < \mu_{ic} < 0 < \mu_{oc} < \mu_r < \mu_e. 146 \end{eqnarray} 147 148 At each iteration, we compute the centroid 149$\overline{\bx} (n+1)$where the worst vertex$\bv_{n+1}$150 has been excluded. This centroid is 151 \begin{eqnarray} 152 \label{centroid-worst} 153 \overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i. 154 \end{eqnarray} 155 We perform a reflection with respect to the worst vertex$\bv_{n+1}$, 156 which creates the reflected point$\bx_r$defined by 157 \begin{eqnarray} 158 \label{interpolate-worst} 159 \bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1} 160 \end{eqnarray} 161 We then compute the function value of the reflected 162 point as$f_r=f(\bx_r)$. 163 164 From that point, there are several possibilities, which 165 are listed below. Most steps try to replace the 166 worst vertex$\bv_{n+1}$by a better point, which is computed 167 depending on the context. 168 \begin{itemize} 169 \item In the case where$f_rcomputeroots1 ( 10 ) 550 -->computeroots1 ( 10 ) 444 Polynomial for outside contraction : 551 Polynomial for outside contraction : 445 552 446 2 3 4 5 6 7 8 9 10 553 2 3 4 5 6 7 8 9 10 447 10 - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x + 20x 554 10 - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x - 3x + 20x 448 #1/10 |0.5822700+%i*0.7362568|=0.938676 555 Roots : 449 #2/10 |0.5822700-%i*0.7362568|=0.938676 556 Root #1/10 |0.5822700+%i*0.7362568|=0.938676 450 #3/10 |-0.5439060+%i*0.7651230|=0.938747 557 Root #2/10 |0.5822700-%i*0.7362568|=0.938676 451 #4/10 |-0.5439060-%i*0.7651230|=0.938747 558 Root #3/10 |-0.5439060+%i*0.7651230|=0.938747 452 #5/10 |0.9093766+%i*0.0471756|=0.910599 559 Root #4/10 |-0.5439060-%i*0.7651230|=0.938747 453 #6/10 |0.9093766-%i*0.0471756|=0.910599 560 Root #5/10 |0.9093766+%i*0.0471756|=0.910599 454 #7/10 |0.0191306+%i*0.9385387|=0.938734 561 Root #6/10 |0.9093766-%i*0.0471756|=0.910599 455 #8/10 |0.0191306-%i*0.9385387|=0.938734 562 Root #7/10 |0.0191306+%i*0.9385387|=0.938734 456 #9/10 |-0.8918713+%i*0.2929516|=0.938752 563 Root #8/10 |0.0191306-%i*0.9385387|=0.938734 457 #10/10 |-0.8918713-%i*0.2929516|=0.938752 564 Root #9/10 |-0.8918713+%i*0.2929516|=0.938752 565 Root #10/10 |-0.8918713-%i*0.2929516|=0.938752 458 Polynomial for inside contraction : 566 Polynomial for inside contraction : 459 567 460 2 3 4 5 6 7 8 9 10 568 2 3 4 5 6 7 8 9 10 461 - 10 - x - x - x - x - x - x - x - x - x + 20x 569 - 10 - x - x - x - x - x - x - x - x - x + 20x 462 #1/10 |0.7461586+%i*0.5514088|=0.927795 570 Roots : 463 #2/10 |0.7461586-%i*0.5514088|=0.927795 571 Root #1/10 |0.7461586+%i*0.5514088|=0.927795 464 #3/10 |-0.2879931+%i*0.8802612|=0.926175 572 Root #2/10 |0.7461586-%i*0.5514088|=0.927795 465 #4/10 |-0.2879931-%i*0.8802612|=0.926175 573 Root #3/10 |-0.2879931+%i*0.8802612|=0.926175 466 #5/10 |-0.9260704|=0.926070 574 Root #4/10 |-0.2879931-%i*0.8802612|=0.926175 467 #6/10 |0.9933286|=0.993329 575 Root #5/10 |-0.9260704|=0.926070 468 #7/10 |0.2829249+%i*0.8821821|=0.926440 576 Root #6/10 |0.9933286|=0.993329 469 #8/10 |0.2829249-%i*0.8821821|=0.926440 577 Root #7/10 |0.2829249+%i*0.8821821|=0.926440 470 #9/10 |-0.7497195+%i*0.5436596|=0.926091 578 Root #8/10 |0.2829249-%i*0.8821821|=0.926440 471 #10/10 |-0.7497195-%i*0.5436596|=0.926091 579 Root #9/10 |-0.7497195+%i*0.5436596|=0.926091 580 Root #10/10 |-0.7497195-%i*0.5436596|=0.926091 472 Polynomial for reflection : 581 Polynomial for reflection : 473 582 474 2 3 4 5 6 7 8 9 10 583 2 3 4 5 6 7 8 9 10 475 10 - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x + 10x 584 10 - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x - 2x + 10x 476 #1/10 |0.6172695+%i*0.7867517|=1.000000 585 Roots : 477 #2/10 |0.6172695-%i*0.7867517|=1.000000 586 Root #1/10 |0.6172695+%i*0.7867517|=1.000000 478 #3/10 |-0.5801834+%i*0.8144859|=1.000000 587 Root #2/10 |0.6172695-%i*0.7867517|=1.000000 479 #4/10 |-0.5801834-%i*0.8144859|=1.000000 588 Root #3/10 |-0.5801834+%i*0.8144859|=1.000000 480 #5/10 |0.9946011+%i*0.1037722|=1.000000 589 Root #4/10 |-0.5801834-%i*0.8144859|=1.000000 481 #6/10 |0.9946011-%i*0.1037722|=1.000000 590 Root #5/10 |0.9946011+%i*0.1037722|=1.000000 482 #7/10 |0.0184670+%i*0.9998295|=1.000000 591 Root #6/10 |0.9946011-%i*0.1037722|=1.000000 483 #8/10 |0.0184670-%i*0.9998295|=1.000000 592 Root #7/10 |0.0184670+%i*0.9998295|=1.000000 484 #9/10 |-0.9501543+%i*0.3117800|=1.000000 593 Root #8/10 |0.0184670-%i*0.9998295|=1.000000 485 #10/10 |-0.9501543-%i*0.3117800|=1.000000 594 Root #9/10 |-0.9501543+%i*0.3117800|=1.000000 595 Root #10/10 |-0.9501543-%i*0.3117800|=1.000000 486 \end{verbatim} 596 \end{verbatim} 487 \end{tiny} 597 \end{small} 488 598 489 The following Scilab script allows to compute the minimum and 599 The following Scilab script allows to compute the minimum and 490 the maximum of the modulus of the roots. 600 the maximum of the modulus of the roots. 491 The "e" option of the "roots" command has been used to force the 601 The "e" option of the "roots" command has been used to force the 492 use of the eigenvalues of the companion matrix as the computationnal 602 use of the eigenvalues of the companion matrix as the computational 493 method. The default algorithm, based on the Jenkins-Traub Rpoly 603 method. The default algorithm, based on the Jenkins-Traub Rpoly 494 method is generating a convergence error and cannot be used 604 method is generating a convergence error and cannot be used 495 in this case. 605 in this case. 496 606 497 \lstset{language=Scilab} 607 \lstset{language=scilabscript} 498 \lstset{numbers=left} 499 \lstset{basicstyle=\footnotesize} 500 \lstset{keywordstyle=\bfseries} 501 \begin{lstlisting} 608 \begin{lstlisting} 502 function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n ) 609 function [rminoc , rmaxoc , rminic , rmaxic] = computeroots1_abstract ( n ) 503 // Polynomial for outside contraction : 610 // Polynomial for outside contraction : @@ -537,9 +644,9 @@ function drawfigure1 ( nbmax ) 537 end 644 end 538 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] ) 645 plot2d ( 1:nbmax , [ rminoctable' , rmaxoctable' , rminictable' , rmaxictable' ] ) 539 f = gcf(); 646 f = gcf(); 540 f.children.title.text = "Nelder-Mead caracteristic equation roots"; 647 f.children.title.text = "Nelder-Mead characteristic equation roots"; 541 f.children.x_label.text = "Number of variables (n)"; 648 f.children.x_label.text = "Number of variables (n)"; 542 f.children.y_label.text = "Roots of the caracteristic equation"; 649 f.children.y_label.text = "Roots of the characteristic equation"; 543 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]); 650 captions(f.children.children.children,["R-max-IC","R-min-IC","R-max-OC","R-min-OC"]); 544 f.children.children(1).legend_location="in_lower_right"; 651 f.children.children(1).legend_location="in_lower_right"; 545 for i = 1:4 652 for i = 1:4 @@ -557,13 +664,13 @@ The minimum and maximum roots of the inside contraction ("ic" in the table) and 557 outside contraction ("oc" in the table) steps are 664 outside contraction ("oc" in the table) steps are 558 presented in table \ref{table-nm-roots-table}. These 665 presented in table \ref{table-nm-roots-table}. These 559 roots are presented graphically in figure \ref{fig-nm-roots}. 666 roots are presented graphically in figure \ref{fig-nm-roots}. 560 One can see that the roots converge toward 1 when $n\rightarrow \infty$. 667 We see that the roots start from 0.5 when $n=1$ and 561 668 converge rapidly toward 1 when $n\rightarrow \infty$. 562 669 563 \begin{figure}[htbp] 670 \begin{figure}[htbp] 564 \begin{center} 671 \begin{center} 565 \begin{tiny} 672 \begin{tiny} 566 \begin{tabular}{|l|l||l|l|l|} 673 \begin{tabular}{|l|l|l|l|l|} 567 \hline 674 \hline 568 $n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{ic}$ & $\max_{i=1,n}\mu_i^{ic}$ \\ 675 $n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{ic}$ & $\max_{i=1,n}\mu_i^{ic}$ \\ 569 \hline 676 \hline @@ -623,7 +730,7 @@ $n$ & $\min_{i=1,n}\mu_i^{oc}$ & $\max_{i=1,n}\mu_i^{oc}$ & $\min_{i=1,n}\mu_i^{ 623 \end{tabular} 730 \end{tabular} 624 \end{tiny} 731 \end{tiny} 625 \end{center} 732 \end{center} 626 \caption{Roots of the caracteristic equations of the Nelder-Mead method with standard 733 \caption{Roots of the characteristic equations of the Nelder-Mead method with standard 627 coefficients. (Some results are not displayed to make the table fit the page).} 734 coefficients. (Some results are not displayed to make the table fit the page).} 628 \label{table-nm-roots-table} 735 \label{table-nm-roots-table} 629 \end{figure} 736 \end{figure} @@ -632,60 +739,56 @@ coefficients. (Some results are not displayed to make the table fit the page).} 632 \begin{center} 739 \begin{center} 633 \includegraphics[width=10cm]{neldermead-roots.png} 740 \includegraphics[width=10cm]{neldermead-roots.png} 634 \end{center} 741 \end{center} 635 \caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with standard 742 \caption{Modulus of the roots of the characteristic equations of the Nelder-Mead method with standard 636 coefficients -- R-max-IC is the maximum of the modulus of the root of the Inside Contraction steps} 743 coefficients -- R-max-IC is the maximum of the modulus of the root of the Inside Contraction steps} 637 \label{fig-nm-roots} 744 \label{fig-nm-roots} 638 \end{figure} 745 \end{figure} 639 746 640 \subsection{With variable parameters} 747 \subsection{With variable parameters} 641 748 642 In this section, we analyse the roots of the caracteristic 749 In this section, we analyze the roots of the characteristic 643 equation with \emph{variable} inside and outside contraction 750 equation with \emph{variable} inside and outside contraction 644 coefficients. 751 coefficients. 645 752 646 \emph{Outside contraction} If the outside contraction step is repeatedly performed 753 \emph{Outside contraction} \\ 647 with variable$\mu_{oc} > 0$, then 754 If the outside contraction step is repeatedly performed 648 755 with variable$\mu_{oc} \in }0,\mu_r[$, then 649 \begin{eqnarray} 756 \begin{eqnarray} 650 \bv^{(k+n)} &=& \overline{\bold{v}}^{(k)} 757 \bv^{(k+n)} &=& \overline{\bold{v}}^{(k)} 651 + \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\ 758 + \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\ 652 &=& (1 + \mu_{oc} ) \overline{\bold{v}}^{(k)} - \mu_{oc} \bv^{(k)} 759 &=& (1 + \mu_{oc} ) \overline{\bold{v}}^{(k)} - \mu_{oc} \bv^{(k)} 653 \end{eqnarray} 760 \end{eqnarray} 654 By plugging the definition of the centroid into the previous equality, one 761 By plugging the definition of the centroid into the previous equality, we 655 find the recurrence formula 762 find the recurrence formula 656 657 \begin{eqnarray} 763 \begin{eqnarray} 658 n \bv^{(k+n)} - (1 + \mu_{oc} ) \bv^{(k+1)} - \ldots - (1 + \mu_{oc} ) \bv^{(k+n-1)} + n\mu_{oc}\bv^{(k)} = 0 764 n \bv^{(k+n)} - (1 + \mu_{oc} ) \bv^{(k+1)} - \ldots - (1 + \mu_{oc} ) \bv^{(k+n-1)} + n\mu_{oc}\bv^{(k)} = 0 659 \end{eqnarray} 765 \end{eqnarray} 660 766 661 The associated caracteristic equation is 767 The associated characteristic equation is 662 663 \begin{eqnarray} 768 \begin{eqnarray} 664 \label{recurrence-variable} 769 \label{recurrence-variable} 665 n \mu^n - (1 + \mu_{oc} ) \mu^{n-1} - \ldots - (1 + \mu_{oc} ) \mu + n \mu_{oc} = 0. 770 n \mu^n - (1 + \mu_{oc} ) \mu^{n-1} - \ldots - (1 + \mu_{oc} ) \mu + n \mu_{oc} = 0. 666 \end{eqnarray} 771 \end{eqnarray} 667 772 668 \emph{Inside contraction} We suppose that the inside contraction step is repeatedly performed 773 \emph{Inside contraction} \\ 669 with$-1 < \mu_{ic} < 0$. The caracteristic equation is the same as \ref{recurrence-variable}, 774 We suppose that the inside contraction step is repeatedly performed 775 with$-1 < \mu_{ic} < 0$. The characteristic equation is the same as \ref{recurrence-variable}, 670 but it is here studied in the range$\mu_{ic}\in]-1, 0[$. 776 but it is here studied in the range$\mu_{ic}\in]-1, 0[$. 671 777 672 To study the convergence of the method, one simply have 778 To study the convergence of the method, we simply have 673 to study the roots of equation \ref{recurrence-variable}, where 779 to study the roots of equation \ref{recurrence-variable}, where 674 the range$]-1,0[$corresponds to the inside contraction (with$-1/2$780 the range$]-1,0[$corresponds to the inside contraction (with$-1/2$675 as the standard value) and where the range$]0,\mu_r[$corresponds to the outside contraction (with$1/2$781 as the standard value) and where the range$]0,\mu_r[$corresponds to the outside contraction (with$1/2$676 as the standard value). 782 as the standard value). 677 783 678 In the following Scilab script, one computes the minimum and 784 In the following Scilab script, we compute the minimum and 679 maximum root of the caracteristic equation, with$n$fixed. 785 maximum root of the characteristic equation, with$n$fixed. 680 786 681 \lstset{language=Scilab} 787 \lstset{language=scilabscript} 682 \lstset{numbers=left} 683 \lstset{basicstyle=\footnotesize} 684 \lstset{keywordstyle=\bfseries} 685 \begin{lstlisting} 788 \begin{lstlisting} 686 // 789 // 687 // rootsvariable -- 790 // rootsvariable -- 688 // Compute roots of the caracteristic equation 791 // Compute roots of the characteristic equation 689 // of Nelder-Mead with variable coefficient mu. 792 // of Nelder-Mead with variable coefficient mu. 690 // Polynomial for outside/inside contraction : 793 // Polynomial for outside/inside contraction : 691 // n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0 794 // n mu - (1+mu)x - ... - (1+mu)x^(n-1) + n x^(n) = 0 @@ -715,9 +818,9 @@ function drawfigure_variable ( n , nmumax ) 715 plot2d ( mutable , [ rmintable' , rmaxtable' ] ) 818 plot2d ( mutable , [ rmintable' , rmaxtable' ] ) 716 f = gcf(); 819 f = gcf(); 717 pause 820 pause 718 f.children.title.text = "Nelder-Mead caracteristic equation roots"; 821 f.children.title.text = "Nelder-Mead characteristic equation roots"; 719 f.children.x_label.text = "Contraction coefficient"; 822 f.children.x_label.text = "Contraction coefficient"; 720 f.children.y_label.text = "Roots of the caracteristic equation"; 823 f.children.y_label.text = "Roots of the characteristic equation"; 721 captions(f.children.children.children,["R-max","R-min"]); 824 captions(f.children.children.children,["R-max","R-min"]); 722 f.children.children(1).legend_location="in_lower_right"; 825 f.children.children(1).legend_location="in_lower_right"; 723 for i = 1:2 826 for i = 1:2 @@ -731,7 +834,7 @@ endfunction 731 \end{lstlisting} 834 \end{lstlisting} 732 835 733 The figure \ref{fig-nm-roots-variable} presents the minimum 836 The figure \ref{fig-nm-roots-variable} presents the minimum 734 and maximum modulus of the roots of the caracteristic equation 837 and maximum modulus of the roots of the characteristic equation 735 with$n=10$. The result is that when$\mu_{oc}$is close to 0, the 838 with$n=10$. The result is that when$\mu_{oc}$is close to 0, the 736 minimum root has a modulus close to 0. The maximum root remains close to 839 minimum root has a modulus close to 0. The maximum root remains close to 737 1, whatever the value of the contraction coefficient. 840 1, whatever the value of the contraction coefficient. @@ -749,18 +852,34 @@ experiment. 749 \begin{center} 852 \begin{center} 750 \includegraphics[width=10cm]{neldermead-roots-variable.png} 853 \includegraphics[width=10cm]{neldermead-roots-variable.png} 751 \end{center} 854 \end{center} 752 \caption{Modulus of the roots of the caracteristic equations of the Nelder-Mead method with variable 855 \caption{Modulus of the roots of the characteristic equations of the Nelder-Mead method with variable 753 contraction coefficient and$n=10$-- R-max is the maximum of the modulus of the root of the 856 contraction coefficient and$n=10$-- R-max is the maximum of the modulus of the root of the 754 caracteristic equation} 857 characteristic equation} 755 \label{fig-nm-roots-variable} 858 \label{fig-nm-roots-variable} 756 \end{figure} 859 \end{figure} 757 860 758 759 760 \section{Numerical experiments} 861 \section{Numerical experiments} 761 862 762 In this section, we present some numerical experiments 863 In this section, we present some numerical experiments 763 with the Nelder-Mead algorithm. 864 with the Nelder-Mead algorithm. 865 The two first numerical experiments involve simple quadratic functions. 866 These experiments allows to see the difference between 867 Spendley's et al. algorithm and the Nelder-Mead algorithm. 868 We then present several experiments taken from the bibliography. 869 The O'Neill experiments \cite{O'Neill1971AAF} are performed in order 870 to check that our algorithm is a correct implementation. 871 We then present several numerical experiments where the Nelder-Mead 872 does not converge properly. 873 We analyze the Mc Kinnon counter example 874 from \cite{589109}. We show the behavior of the 875 Nelder-Mead simplex method for a family of examples which cause the 876 method to converge to a non stationnary point. 877 We analyze the counter examples presented by Han in his Phd thesis \cite{Han2000}. 878 In these experiments, the Nelder-Mead algorithm degenerates by applying repeatedly 879 the inside contraction step. 880 We also reproduce numerical experiments extracted from Torczon's Phd Thesis 881 \cite{Torczon89multi-directionalsearch}, where Virginia Torczon 882 presents the multi-directional direct search algorithm. 764 883 765 \subsection{Quadratic function} 884 \subsection{Quadratic function} 766 885 @@ -783,7 +902,7 @@ The numerical results are presented in table \ref{fig-nm-numexp1-table}. 783 902 784 \begin{figure}[htbp] 903 \begin{figure}[htbp] 785 \begin{center} 904 \begin{center} 786 \begin{tiny} 905 %\begin{tiny} 787 \begin{tabular}{|l|l|} 906 \begin{tabular}{|l|l|} 788 \hline 907 \hline 789 Iterations & 65 \\ 908 Iterations & 65 \\ @@ -795,7 +914,7 @@ Computed$x^\star$&$(7.3e-10 , -2.5e-9)$\\ 795 Computed$f(x^\star)$&$8.7e-18$\\ 914 Computed$f(x^\star)$&$8.7e-18$\\ 796 \hline 915 \hline 797 \end{tabular} 916 \end{tabular} 798 \end{tiny} 917 %\end{tiny} 799 \end{center} 918 \end{center} 800 \caption{Numerical experiment with Nelder-Mead method on the quadratic function 919 \caption{Numerical experiment with Nelder-Mead method on the quadratic function 801$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$} 920$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$} @@ -806,7 +925,7 @@$f(x_1,x_2) = x_1^2 + x_2^2 - x_1 x_2$} 806 The various simplices generated during the iterations are 925 The various simplices generated during the iterations are 807 presented in figure \ref{fig-nm-numexp1-historysimplex}. 926 presented in figure \ref{fig-nm-numexp1-historysimplex}. 808 The method use reflections in the early iterations. Then there 927 The method use reflections in the early iterations. Then there 809 is no possible improvment using reflections and shrinking is necessary. 928 is no possible improvement using reflections and shrinking is necessary. 810 929 811 \begin{figure} 930 \begin{figure} 812 \begin{center} 931 \begin{center} @@ -857,7 +976,7 @@ We set the maximum number of function evaluations to 400. 857 The initial simplex is computed from the coordinate axis and the unit length. 976 The initial simplex is computed from the coordinate axis and the unit length. 858 977 859 The numerical results are presented in table \ref{fig-nm-numexp2-table}, 978 The numerical results are presented in table \ref{fig-nm-numexp2-table}, 860 where the experiment is presented for$a=100$. One can check that the 979 where the experiment is presented for$a=100$. We can check that the 861 number of function evaluation (161 function evaluations) is much lower than the number 980 number of function evaluation (161 function evaluations) is much lower than the number 862 for the fixed shape Spendley et al. method (400 function evaluations) 981 for the fixed shape Spendley et al. method (400 function evaluations) 863 and that the function value at optimum is very accurate ($f(x^\star)\approx 1.e-17$982 and that the function value at optimum is very accurate ($f(x^\star)\approx 1.e-17$@@ -865,7 +984,7 @@ compared to Spendley's et al.$f(x^\star) \approx 0.08$). 865 984 866 \begin{figure}[h] 985 \begin{figure}[h] 867 \begin{center} 986 \begin{center} 868 \begin{tiny} 987 %\begin{tiny} 869 \begin{tabular}{|l|l|l|} 988 \begin{tabular}{|l|l|l|} 870 \hline 989 \hline 871 & Nelder-Mead & Spendley et al.\\ 990 & Nelder-Mead & Spendley et al.\\ @@ -880,7 +999,7 @@ Computed$x^\star$&$(2.e-10, -3.e-9)$&$(0.001,0.2)$\\ 880 Computed$f(x^\star)$&$1.e-17$&$0.08$\\ 999 Computed$f(x^\star)$&$1.e-17$&$0.08$\\ 881 \hline 1000 \hline 882 \end{tabular} 1001 \end{tabular} 883 \end{tiny} 1002 %\end{tiny} 884 \end{center} 1003 \end{center} 885 \caption{Numerical experiment with Nelder-Mead method on a badly scaled quadratic function. 1004 \caption{Numerical experiment with Nelder-Mead method on a badly scaled quadratic function. 886 The variable shape Nelder-Mead algorithm improves the accuracy of the result compared 1005 The variable shape Nelder-Mead algorithm improves the accuracy of the result compared @@ -888,16 +1007,16 @@ to the fixed shaped Spendley et al. method.} 888 \label{fig-nm-numexp2-table} 1007 \label{fig-nm-numexp2-table} 889 \end{figure} 1008 \end{figure} 890 1009 891 In figure \ref{fig-nm-numexp2-scaling}, we analyse the 1010 In figure \ref{fig-nm-numexp2-scaling}, we analyze the 892 behaviour of the method with respect to scaling. 1011 behavior of the method with respect to scaling. 893 We check that the method behave very smoothly, with a very 1012 We check that the method behave very smoothly, with a very 894 small number of additionnal function evaluations when the 1013 small number of additional function evaluations when the 895 scaling deteriorates. This shows how much the Nelder-Mead algorithms 1014 scaling deteriorates. This shows how much the Nelder-Mead algorithms 896 improves over the Spendley et al. method. 1015 improves over Spendley's et al. method. 897 1016 898 \begin{figure}[htbp] 1017 \begin{figure}[htbp] 899 \begin{center} 1018 \begin{center} 900 \begin{tiny} 1019 %\begin{tiny} 901 \begin{tabular}{|l|l|l|l|} 1020 \begin{tabular}{|l|l|l|l|} 902 \hline 1021 \hline 903$a$& Function evaluations & Computed$f(x^\star)$& Computed$x^\star$\\ 1022$a$& Function evaluations & Computed$f(x^\star)$& Computed$x^\star$\\ @@ -908,7 +1027,7 @@$1000.0$& 165 &$1.0e-17$&$(-1.e-010 9.e-10)$\\ 908$10000.0$& 167 &$3.0e-17$&$(5.0e-11,-1.0e-10)$\\ 1027$10000.0$& 167 &$3.0e-17$&$(5.0e-11,-1.0e-10)$\\ 909 \hline 1028 \hline 910 \end{tabular} 1029 \end{tabular} 911 \end{tiny} 1030 %\end{tiny} 912 \end{center} 1031 \end{center} 913 \caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function} 1032 \caption{Numerical experiment with Spendley's et al. method on a badly scaled quadratic function} 914 \label{fig-nm-numexp2-scaling} 1033 \label{fig-nm-numexp2-scaling} @@ -937,7 +1056,7 @@ experiment for$n=1,19$. 937 During the iterations, no shrink steps are performed. The 1056 During the iterations, no shrink steps are performed. The 938 algorithm performs reflections, inside and outside contractions. 1057 algorithm performs reflections, inside and outside contractions. 939 The figure \ref{fig-nm-numexp3-steps} shows the detailed sequence of 1058 The figure \ref{fig-nm-numexp3-steps} shows the detailed sequence of 940 iterations for$n=10$. One can see that there is no general 1059 iterations for$n=10$. We see that there is no general 941 pattern for the iterations. One can check, however, that there 1060 pattern for the iterations. One can check, however, that there 942 are never no more than$n$consecutive reflection steps, which is 1061 are never no more than$n$consecutive reflection steps, which is 943 as expected. After one or more contractions, the reflection 1062 as expected. After one or more contractions, the reflection @@ -947,7 +1066,7 @@ vertices are moved in at most$n$reflection steps. 947 1066 948 \begin{figure}[htbp] 1067 \begin{figure}[htbp] 949 \begin{center} 1068 \begin{center} 950 \begin{tiny} 1069 %\begin{tiny} 951 \begin{verbatim} 1070 \begin{verbatim} 952 I 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 1071 I 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 953 R 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 1072 R R R R R R R R R R R R R I R I I R I R O I I I I R I R I I R O I R R @@ -968,7 +1087,7 @@ R I I R I I R R R R R O R R R I R R R R I R I R R I R I I R R I I R R 968 I 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 1087 I 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 969 R R R R I I I R R 1088 R R R R I I I R R 970 \end{verbatim} 1089 \end{verbatim} 971 \end{tiny} 1090 %\end{tiny} 972 \end{center} 1091 \end{center} 973 \caption{Numerical experiment with Nelder-Mead method on a generalized 1092 \caption{Numerical experiment with Nelder-Mead method on a generalized 974 quadratic function - steps of the algorithm : I = inside contraction, O = outside contraction, 1093 quadratic function - steps of the algorithm : I = inside contraction, O = outside contraction, @@ -981,12 +1100,12 @@ the kind of steps performed during the iterations for$n=1,19$. 981 It appears that the number of shrink steps and expansion steps is zero, as expected. 1100 It appears that the number of shrink steps and expansion steps is zero, as expected. 982 More interesting is that the number of reflection is 1101 More interesting is that the number of reflection is 983 larger than the number of inside contraction when$n$1102 larger than the number of inside contraction when$n$984 is large. The number of outside contraction is allways 1103 is large. The number of outside contraction is always 985 the smallest in this case. 1104 the smallest in this case. 986 1105 987 \begin{figure}[htbp] 1106 \begin{figure}[htbp] 988 \begin{center} 1107 \begin{center} 989 \begin{tiny} 1108 %\begin{tiny} 990 \begin{tabular}{|l|l|l|l|l|l|} 1109 \begin{tabular}{|l|l|l|l|l|l|} 991 \hline 1110 \hline 992$n$& \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\ 1111$n$& \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\ @@ -1013,21 +1132,21 @@$n$& \# Reflections & \# Expansion & \# Inside & \# Outside & \#Shrink\\ 1013 19 & 767 & 0 & 480 & 48 & 0\\ 1132 19 & 767 & 0 & 480 & 48 & 0\\ 1014 \hline 1133 \hline 1015 \end{tabular} 1134 \end{tabular} 1016 \end{tiny} 1135 %\end{tiny} 1017 \end{center} 1136 \end{center} 1018 \caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function -- number 1137 \caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function -- number 1019 and kinds of steps performed} 1138 and kinds of steps performed} 1020 \label{fig-nm-numexp3-nbsteps} 1139 \label{fig-nm-numexp3-nbsteps} 1021 \end{figure} 1140 \end{figure} 1022 1141 1023 One can check that the number of function evaluations 1142 We check that the number of function evaluations 1024 increases approximately linearily with the dimension of the problem in 1143 increases approximately linearly with the dimension of the problem in 1025 figure \ref{fig-nm-numexp3-fvn}. A rough rule of thumb is that, for$n=1,19$, 1144 figure \ref{fig-nm-numexp3-fvn}. A rough rule of thumb is that, for$n=1,19$, 1026 the number of function evaluations is equal to$100n$. 1145 the number of function evaluations is equal to$100n$. 1027 1146 1028 \begin{figure}[htbp] 1147 \begin{figure}[htbp] 1029 \begin{center} 1148 \begin{center} 1030 \begin{tiny} 1149 %\begin{tiny} 1031 \begin{tabular}{|l|l|l|l|} 1150 \begin{tabular}{|l|l|l|l|} 1032 \hline 1151 \hline 1033$n$& Function evaluations & Iterations &$\rho(S_0,n)$\\ 1152$n$& Function evaluations & Iterations &$\rho(S_0,n)$\\ @@ -1053,7 +1172,7 @@$n$& Function evaluations & Iterations &$\rho(S_0,n)$\\ 1053 19 & 1843 & 1296 & 0.98584701106083183\\ 1172 19 & 1843 & 1296 & 0.98584701106083183\\ 1054 \hline 1173 \hline 1055 \end{tabular} 1174 \end{tabular} 1056 \end{tiny} 1175 %\end{tiny} 1057 \end{center} 1176 \end{center} 1058 \caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function} 1177 \caption{Numerical experiment with Nelder-Mead method on a generalized quadratic function} 1059 \label{fig-nm-numexp3-dimension} 1178 \label{fig-nm-numexp3-dimension} @@ -1153,11 +1272,11 @@ The table \ref{fig-nm-oneill-table} presents the results which were 1153 computed by O'Neill compared with our software. 1272 computed by O'Neill compared with our software. 1154 For most experiments, the results are very close in terms of 1273 For most experiments, the results are very close in terms of 1155 number of function evaluations. 1274 number of function evaluations. 1156 The problem \#4 exhibits a completely different behaviour than the 1275 The problem \#4 exhibits a completely different behavior than the 1157 results presented by O'Neill. For us, the maximum number of function evaluations 1276 results presented by O'Neill. For us, the maximum number of function evaluations 1158 is reached (i.e. 1000 function evaluations), whereas for O'Neill, the algorithm 1277 is reached (i.e. 1000 function evaluations), whereas for O'Neill, the algorithm 1159 is restarted and gives the result with 474 function evaluations. 1278 is restarted and gives the result with 474 function evaluations. 1160 We did not find any explanation for this behaviour. A possible cause of 1279 We did not find any explanation for this behavior. A possible cause of 1161 difference may be the floating point system which are different and may 1280 difference may be the floating point system which are different and may 1162 generate different simplices in the algorithms. 1281 generate different simplices in the algorithms. 1163 Although the CPU times cannot be 1282 Although the CPU times cannot be @@ -1169,7 +1288,7 @@ and the problems 3 and 4 were solved in 22.25 seconds. 1169 1288 1170 \begin{figure}[htbp] 1289 \begin{figure}[htbp] 1171 \begin{center} 1290 \begin{center} 1172 \begin{tiny} 1291 %\begin{tiny} 1173 \begin{tabular}{|l|l|l|l|l|l|l|} 1292 \begin{tabular}{|l|l|l|l|l|l|l|} 1174 \hline 1293 \hline 1175 Author & Problem & Function & No. of Restarts & Function Value & Iterations & CPU\\ 1294 Author & Problem & Function & No. of Restarts & Function Value & Iterations & CPU\\ @@ -1188,71 +1307,72 @@ O'Neill & 4 & 474 & 1 & 3.80 e-7 & ? & ? \\ 1188 Baudin & 4 & 999 & 0 & 5.91 e-9 & 676 & - \\ 1307 Baudin & 4 & 999 & 0 & 5.91 e-9 & 676 & - \\ 1189 \hline 1308 \hline 1190 \end{tabular} 1309 \end{tabular} 1191 \end{tiny} 1310 %\end{tiny} 1192 \end{center} 1311 \end{center} 1193 \caption{Numerical experiment with Nelder-Mead method on O'Neill test cases - O'Neill results and our results} 1312 \caption{Numerical experiment with Nelder-Mead method on O'Neill test cases - O'Neill results and our results} 1194 \label{fig-nm-oneill-table} 1313 \label{fig-nm-oneill-table} 1195 \end{figure} 1314 \end{figure} 1196 1315 1197 \subsection{Convergence to a non stationnary point} 1316 \subsection{Convergence to a non stationnary point} 1317 \label{section-mcKinnon} 1198 1318 1199 In this section, we analyse the Mc Kinnon counter example 1319 In this section, we analyze the Mc Kinnon counter example 1200 from \cite{589109}. We show the behavior of the 1320 from \cite{589109}. We show the behavior of the 1201 Nelder-Mead simplex method for a family of examples which cause the 1321 Nelder-Mead simplex method for a family of examples which cause the 1202 method to converge to a nonstationnary point. 1322 method to converge to a non stationnary point. 1203 1323 1204 Consider a simplex in two dimensions with vertices at 0 (i.e. the origin), 1324 Consider a simplex in two dimensions with vertices at 0 (i.e. the origin), 1205$v^{(n+1)}$and$v^{(n)}$. Assume that 1325$\bv^{(n+1)}$and$\bv^{(n)}$. Assume that 1206 1326 1207 \begin{eqnarray} 1327 \begin{eqnarray} 1208 \label{mckinnon-sortedfv} 1328 \label{mckinnon-sortedfv} 1209 f(0) < f(v^{(n+1)}) < f(v^{(n)}). 1329 f(0) < f(\bv^{(n+1)}) < f(\bv^{(n)}). 1210 \end{eqnarray} 1330 \end{eqnarray} 1211 1331 1212 The centroid of the simplex is$\overline{v} = v^{(n+1)}/2$, the midpoint 1332 The centroid of the simplex is$\overline{\bv} = \bv^{(n+1)}/2$, the midpoint 1213 of the line joining the best and second vertex. The refected 1333 of the line joining the best and second vertex. The reflected 1214 point is then computed as 1334 point is then computed as 1215 1335 1216 \begin{eqnarray} 1336 \begin{eqnarray} 1217 \label{mckinnon-reflection} 1337 \label{mckinnon-reflection} 1218 r^{(n)} = \overline{v} + \rho ( \overline{v} - v^{(n)} ) = v^{(n+1)} - v^{(n)} 1338 \br^{(n)} = \overline{\bv} + \rho ( \overline{\bv} - \bv^{(n)} ) 1339 = \bv^{(n+1)} - \bv^{(n)} 1219 \end{eqnarray} 1340 \end{eqnarray} 1220 1341 1221 Assume that the reflection point$r^{(n)}$is rejected, i.e. that 1342 Assume that the reflection point$\br^{(n)}$is rejected, i.e. that 1222$f(v^{(n)}) < f(r^{(n)})$. In this case, the inside contraction 1343$f(\bv^{(n)}) < f(\br^{(n)})$. In this case, the inside contraction 1223 step is taken and the point$v^{(n+2)}$is computed using the 1344 step is taken and the point$\bv^{(n+2)}$is computed using the 1224 reflection factor$-\gamma = -1/2$so that 1345 reflection factor$-\gamma = -1/2$so that 1225 1346 1226 \begin{eqnarray} 1347 \begin{eqnarray} 1227 \label{mckinnon-insidecontraction} 1348 \label{mckinnon-insidecontraction} 1228 v^{(n+2)} = \overline{v} - \gamma ( \overline{v} - v^{(n)} ) = \frac{1}{4} v^{(n+1)} - \frac{1}{2} v^{(n)} 1349 \bv^{(n+2)} = \overline{\bv} - 1350 \gamma ( \overline{\bv} - \bv^{(n)} ) 1351 = \frac{1}{4} \bv^{(n+1)} - \frac{1}{2} \bv^{(n)} 1229 \end{eqnarray} 1352 \end{eqnarray} 1230 1353 1231 Assume then that the inside contraction point is accepted, i.e.$f(v^{(n+2)}) < f(v^{(n+1)})$. 1354 Assume then that the inside contraction point is accepted, i.e.$f(\bv^{(n+2)}) < f(\bv^{(n+1)})$. 1232 If this sequence of steps repeats, the simplices are subject to the 1355 If this sequence of steps repeats, the simplices are subject to the 1233 following linear reccurence formula 1356 following linear recurrence formula 1234 1357 1235 \begin{eqnarray} 1358 \begin{eqnarray} 1236 \label{mckinnon-reccurence} 1359 \label{mckinnon-reccurence} 1237 4 v^{(n+2)} - v^{(n+1)} + 2 v^{(n)} = 0 1360 4 \bv^{(n+2)} - \bv^{(n+1)} + 2 \bv^{(n)} = 0 1238 \end{eqnarray} 1361 \end{eqnarray} 1239 1362 1240 Their general solutions are of the form 1363 Their general solutions are of the form 1241 1364 1242 \begin{eqnarray} 1365 \begin{eqnarray} 1243 v^{(n)} = \lambda_1^k a_1 + \lambda_2^k a_2 1366 \bv^{(n)} = \lambda_1^k a_1 + \lambda_2^k a_2 1244 \end{eqnarray} 1367 \end{eqnarray} 1245 where${\lambda_i}_{i=1,2}$are the roots of the characteristic equation and 1368 where${\lambda_i}_{i=1,2}$are the roots of the characteristic equation and 1246${a_i}_{i=1,2} \in \RR^n$. 1369${a_i}_{i=1,2} \in \RR^n$. 1247 The caracteristic equation is 1370 The characteristic equation is 1248 1249 \begin{eqnarray} 1371 \begin{eqnarray} 1250 \label{mckinnon-caracequation} 1372 \label{mckinnon-caracequation} 1251 4 \lambda^2 - \lambda + 2 \lambda = 0 1373 4 \lambda^2 - \lambda + 2 \lambda = 0 1252 \end{eqnarray} 1374 \end{eqnarray} 1253 1254 and has the roots 1375 and has the roots 1255 1256 \begin{eqnarray} 1376 \begin{eqnarray} 1257 \label{mckinnon-roots} 1377 \label{mckinnon-roots} 1258 \lambda_1 = \frac{1 + \sqrt{33}}{8}\approx 0.84307, 1378 \lambda_1 = \frac{1 + \sqrt{33}}{8}\approx 0.84307, @@ -1260,25 +1380,23 @@ and has the roots 1260 \end{eqnarray} 1380 \end{eqnarray} 1261 1381 1262 After Mc Kinnon has presented the computation of the roots of the 1382 After Mc Kinnon has presented the computation of the roots of the 1263 caracteristic equation, he presents a special initial simplex 1383 characteristic equation, he presents a special initial simplex 1264 for which the simplices degenerates because of repeated failure by inside 1384 for which the simplices degenerates because of repeated failure by inside 1265 contraction (RFIC in his article). Consider the initial simplex with 1385 contraction (RFIC in his article). Consider the initial simplex with 1266 vertices$v^{(0)} = (1,1)$and$v^{(1)} = (\lambda_1,\lambda_2)$and 1386 vertices$\bv^{(0)} = (1,1)$and$\bv^{(1)} = (\lambda_1,\lambda_2)$and 1267$0$. If follows that the particular solution for these initial 1387$0$. If follows that the particular solution for these initial 1268 conditions is$v^{(n)} = (\lambda_1^n,\lambda_2^n)$. 1388 conditions is$\bv^{(n)} = (\lambda_1^n,\lambda_2^n)$. 1269 1270 Consider the function$f(x,y)$given by 1271 1389 1390 Consider the function$f(x_1,x_2)$given by 1272 \begin{eqnarray} 1391 \begin{eqnarray} 1273 \label{mckinnon-function} 1392 \label{mckinnon-function} 1274 f(x,y) &=& \theta \phi |x|^\tau + y + y^2, \qquad x\leq 0,\\ 1393 f(x_1,x_2) &=& \theta \phi |x_1|^\tau + x_2 + x_2^2, \qquad x_1\leq 0,\\ 1275 &=&\theta x^\tau + y + y^2, \qquad x\geq 0. 1394 &=&\theta x_1^\tau + x_2 + x_2^2, \qquad x_1\geq 0. 1276 \end{eqnarray} 1395 \end{eqnarray} 1277 1278 where$\theta$and$\phi$are positive constants. Note that$(0,-1)$1396 where$\theta$and$\phi$are positive constants. Note that$(0,-1)$1279 is a descent direction from the origin$(0,0)$and that f is stricly convex 1397 is a descent direction from the origin$(0,0)$and that f is stricly convex 1280 provided$\tau>1$.$f$has continuous first derivatives if$\tau>1$, continuous second 1398 provided$\tau>1$.$f$has continuous first derivatives if$\tau>1$, continuous second 1281 derivatives if$\tau>2$and continous third derivatives if$\tau>3$. 1399 derivatives if$\tau>2$and continuous third derivatives if$\tau>3$. 1282 1400 1283 Mc Kinnon computed the conditions on$\theta,\phi$and$\tau$1401 Mc Kinnon computed the conditions on$\theta,\phi$and$\tau$1284 so that the function values are ordered as expected, i.e. so that the 1402 so that the function values are ordered as expected, i.e. so that the @@ -1290,16 +1408,17 @@ for$\tau=3$,$\theta=6$and$\phi = 400$. 1290 1408 1291 We consider here the more regular case$\tau=3$,$\theta=6$1409 We consider here the more regular case$\tau=3$,$\theta=6$1292 and$\phi = 400$, i.e. the function is defined by 1410 and$\phi = 400$, i.e. the function is defined by 1293 1294 \begin{eqnarray} 1411 \begin{eqnarray} 1295 \label{mckinnon-function3} 1412 \label{mckinnon-function3} 1296 f(x,y) &=& - 2400 x^3 + y + y^2, \qquad x\leq 0, \\ 1413 f(x_1,x_2) &=& - 2400 x_1^3 + x_2 + x_2^2, \qquad x_1\leq 0, \\ 1297 &=& 6 x^3 + y + y^2, \qquad x\geq 0. 1414 &=& 6 x_1^3 + x_2 + x_2^2, \qquad x_1\geq 0. 1298 \end{eqnarray} 1415 \end{eqnarray} 1299 1416 1300 The figure \ref{fig-nm-numexp-mckinnon} shows the contour plot of this function and the first 1417 The figure \ref{fig-nm-numexp-mckinnon} shows the contour plot of this function and the first 1301 steps of the Nelder-Mead method. 1418 steps of the Nelder-Mead method. 1302 1419 The global minimum is located at$(0,-1/2)$. 1420 Notice that the simplex degenerates to the 1421 point$(0,0)$, which is a non stationnary point. 1303 1422 1304 \begin{figure} 1423 \begin{figure} 1305 \begin{center} 1424 \begin{center} @@ -1310,6 +1429,23 @@ a non stationnary point} 1310 \label{fig-nm-numexp-mckinnon} 1429 \label{fig-nm-numexp-mckinnon} 1311 \end{figure} 1430 \end{figure} 1312 1431 1432 The figure \ref{fig-nm-numexp-mckinnon-detail} presents the first steps 1433 of the algorithm in this numerical experiment. Because of the 1434 particular shape of the contours of the function, the reflected 1435 point is always worse that the worst vertex$\bx_{n+1}$. This 1436 leads to the inside contraction step. The vertices constructed 1437 by Mc Kinnon are so that the situation loops without end. 1438 1439 \begin{figure} 1440 \begin{center} 1441 \includegraphics[width=10cm]{mcKinnon-insidecontraction.pdf} 1442 \end{center} 1443 \caption{Nelder-Mead numerical experiment -- Detail of the first steps. 1444 The simplex converges to a non stationnary point, after repeated 1445 inside contractions.} 1446 \label{fig-nm-numexp-mckinnon-detail} 1447 \end{figure} 1448 1313 \subsection{Han counter examples} 1449 \subsection{Han counter examples} 1314 1450 1315 In his Phd thesis \cite{Han2000}, Han presents two counter examples 1451 In his Phd thesis \cite{Han2000}, Han presents two counter examples @@ -1319,15 +1455,14 @@ the inside contraction step. 1319 \subsubsection{First counter example} 1455 \subsubsection{First counter example} 1320 1456 1321 The first counter example is based on the function 1457 The first counter example is based on the function 1322 1323 \begin{eqnarray} 1458 \begin{eqnarray} 1324 \label{han-function1} 1459 \label{han-function1} 1325 f(x,y) &=& x^2 + y ( y + 2 ) ( y - 0.5 ) ( y - 2 ) 1460 f(x_1,x_2) &=& x_1^2 + x_2 ( x_2 + 2 ) ( x_2 - 0.5 ) ( x_2 - 2 ) 1326 \end{eqnarray} 1461 \end{eqnarray} 1327 1462 1328 This function is nonconvex, bounded below and has bounded level 1463 This function is nonconvex, bounded below and has bounded level 1329 sets. The initial simplex is chosen as$S_0 = [(0.,-1),(0,1),(1,0)]$. 1464 sets. The initial simplex is chosen as$S_0 = [(0.,-1),(0,1),(1,0)]$. 1330 Han prooves that the Nelder-Mead algorithm generates a sequence of simplices 1465 Han proves that the Nelder-Mead algorithm generates a sequence of simplices 1331$S_k = [(0.,-1),(0,1),(\frac{1}{2^k},0)]$. 1466$S_k = [(0.,-1),(0,1),(\frac{1}{2^k},0)]$. 1332 1467 1333 The figure \ref{fig-nm-numexp-han1} presents the isovalues and the 1468 The figure \ref{fig-nm-numexp-han1} presents the isovalues and the @@ -1347,24 +1482,32 @@ a non stationnary point} 1347 \subsubsection{Second counter example} 1482 \subsubsection{Second counter example} 1348 1483 1349 The second counter example is based on the function 1484 The second counter example is based on the function 1350 1351 \begin{eqnarray} 1485 \begin{eqnarray} 1352 \label{han-function2} 1486 \label{han-function2} 1353 f(x,y) &=& x^2 + \rho(y) 1487 f(x_1,x_2) &=& x_1^2 + \rho(x_2) 1354 \end{eqnarray} 1488 \end{eqnarray} 1355 where$\rho$is a continuous convex function with bounded level 1489 where$\rho$is a continuous convex function with bounded level 1356 sets which satisfies 1490 sets defined by 1357 \begin{eqnarray} 1491 \begin{eqnarray} 1358 \label{han-function2-rho} 1492 \label{han-function2-rho} 1359 \rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\ 1493 \left\{ 1360 & \geq & 0, \qquad \textrm{if} \qquad |y|> 1. 1494 \begin{array}{ll} 1495 \rho(x_2) =0, &\qquad \textrm{if} \qquad |x_2|\leq 1, \\ 1496 \rho(x_2)\geq 0, &\qquad \textrm{if} \qquad |x_2|> 1. 1497 \end{array} 1498 \right. 1361 \end{eqnarray} 1499 \end{eqnarray} 1362 The example given by Han for such a$\rho$function is 1500 The example given by Han for such a$\rho$function is 1363 \begin{eqnarray} 1501 \begin{eqnarray} 1364 \label{han-function2-rho2} 1502 \label{han-function2-rho2} 1365 \rho(y) &=& 0, \qquad \textrm{if} \qquad |y|\leq 1, \\ 1503 \rho(x_2) = 1366 & = & y - 1, \qquad \textrm{if} \qquad y> 1, \\ 1504 \left\{ 1367 & = & -y - 1, \qquad \textrm{if} \qquad y < -1. 1505 \begin{array}{ll} 1506 0, &\qquad \textrm{if} \qquad |x_2|\leq 1, \\ 1507 x_2 - 1, &\qquad \textrm{if} \qquad x_2> 1, \\ 1508 -x_2 - 1, &\qquad \textrm{if} \qquad x_2 < -1. 1509 \end{array} 1510 \right. 1368 \end{eqnarray} 1511 \end{eqnarray} 1369 1512 1370 The initial simplex is chosen as$S_0 = [(0.,1/2),(0,-1/2),(1,0)]$. 1513 The initial simplex is chosen as$S_0 = [(0.,1/2),(0,-1/2),(1,0)]$. @@ -1391,11 +1534,11 @@ into a degenerate simplex, by applying repeated inside contractions. 1391 \subsection{Torczon's numerical experiments} 1534 \subsection{Torczon's numerical experiments} 1392 1535 1393 In her Phd Thesis \cite{Torczon89multi-directionalsearch}, Virginia Torczon 1536 In her Phd Thesis \cite{Torczon89multi-directionalsearch}, Virginia Torczon 1394 presents the multi-directionnal direct search algorithm. In order to analyse the 1537 presents the multi-directional direct search algorithm. In order to analyze the 1395 performances of her new algorithm, she presents some interesting numerical 1538 performances of her new algorithm, she presents some interesting numerical 1396 experiments with the Nelder-Mead algorithm. 1539 experiments with the Nelder-Mead algorithm. 1397 These numerical experiments are based on the collection of test problems \cite{355943}, 1540 These numerical experiments are based on the collection of test problems \cite{355943}, 1398 published in the ACM by Moré, Garbow and Hillstrom in 1981. 1541 published in the ACM by Mor\'e, Garbow and Hillstrom in 1981. 1399 These test problems are associated with varying number of variables. 1542 These test problems are associated with varying number of variables. 1400 In her Phd, Torczon presents numerical experiments with$n$from 8 1543 In her Phd, Torczon presents numerical experiments with$n$from 8 1401 to 40. 1544 to 40. @@ -1403,16 +1546,15 @@ The stopping rule is based on the relative size of the simplex. 1403 The angle between the descent direction (given by the worst point and the centroid), and the 1546 The angle between the descent direction (given by the worst point and the centroid), and the 1404 gradient of the function is computed when the algorithm is stopped. 1547 gradient of the function is computed when the algorithm is stopped. 1405 Torczon shows that, when the tolerance on the relative simplex size is decreased, the 1548 Torczon shows that, when the tolerance on the relative simplex size is decreased, the 1406 angle converges toward 90°. This fact is observed even for moderate 1549 angle converges toward 90 \degre. This fact is observed even for moderate 1407 number of dimensions. 1550 number of dimensions. 1408 1551 1409 In this section, we try to reproduce Torczon numerical experiments. 1552 In this section, we try to reproduce Torczon numerical experiments. 1410 1553 1411 All experiments are associated with the following sum of squares cost function 1554 All experiments are associated with the following sum of squares cost function 1412 1413 \begin{eqnarray} 1555 \begin{eqnarray} 1414 \label{torzcon-sumofsquares} 1556 \label{torzcon-sumofsquares} 1415 f(x) &=& \sum_{i=1,m} f_i(x)^2, 1557 f(\bx) &=& \sum_{i=1,m} f_i(\bx)^2, 1416 \end{eqnarray} 1558 \end{eqnarray} 1417 where$m\geq 1$is the number of functions$f_i$in the problem. 1559 where$m\geq 1$is the number of functions$f_i$in the problem. 1418 1560 @@ -1421,9 +1563,9 @@ simplex and is the following 1421 1563 1422 \begin{eqnarray} 1564 \begin{eqnarray} 1423 \label{torzcon-stopping} 1565 \label{torzcon-stopping} 1424 \frac{1}{\Delta} \max_{i=1,n} \|v_i^k - v_0^k\| \leq \epsilon, 1566 \frac{1}{\Delta} \max_{i=2,n+1} \|\bv_i - \bv_1\| \leq \epsilon, 1425 \end{eqnarray} 1567 \end{eqnarray} 1426 where$\Delta = \max( 1 , \|v_0^k\| )$. Decreasing the value of 1568 where$\Delta = \max( 1 , \|\bv_1\| )$. Decreasing the value of 1427$\epsilon$allows to get smaller simplex sizes. 1569$\epsilon$allows to get smaller simplex sizes. 1428 1570 1429 \subsubsection{Penalty \#1} 1571 \subsubsection{Penalty \#1} @@ -1431,21 +1573,22 @@ The first test function is the \emph{Penalty \#1} function : 1431 1573 1432 \begin{eqnarray} 1574 \begin{eqnarray} 1433 \label{torzcon-sumofsquares-case1} 1575 \label{torzcon-sumofsquares-case1} 1434 f_i(x) &=& \sqrt{1.e-5}(x_i - 1), \qquad i=1,n\\ 1576 f_i(\bx) &=& \sqrt{1.e-5}(x_i - 1), \qquad i=1,n\\ 1435 f_{n+1} & = & -\frac{1}{4} + \sum_{j=1,n} x_j^2. 1577 f_{n+1} & = & -\frac{1}{4} + \sum_{j=1,n} x_j^2. 1436 \end{eqnarray} 1578 \end{eqnarray} 1437 1579 1438 The initial guess is given by$x_0 = (x_{0,j})_{j=1,n}$and 1580 The initial guess is given by$\bx_0 = ((\bx_0)_1 , (\bx_0)_2, \ldots , (\bx_0)_n)^T$and 1439$x_{0,j} = j$for$j=1,n$. 1581$(\bx_0)_j = j$for$j=1,n$. 1440 1582 1441 The problem given by 1583 The problem given by 1442 Moré, Garbow and Hillstrom in \cite{355943} is associated with 1584 Mor\'e, Garbow and Hillstrom in \cite{355943} is associated with 1443 the size$n=4$. The value of the cost function at the initial guess 1585 the size$n=4$. The value of the cost function at the initial guess 1444$x_0 = (1,2,3,4)$is$f(x_0) = 885.063$. The value of the function 1586$\bx_0 = (1,2,3,4)^T$is$f(\bx_0) = 885.063$. The value of the function 1445 at the optimum is given in \cite{355943} as$f(x^\star) = 2.24997d-5$. 1587 at the optimum is given in \cite{355943} as$f(\bx^\star) = 2.24997d-5$. 1588 % TODO : what is the optimum ? 1446 1589 1447 Torzcon shows an experiment with the Penalty \#1 test case and$n=8$. 1590 Torzcon shows an experiment with the Penalty \#1 test case and$n=8$. 1448 For this particular case, the initial function value is$f(x_0) = 4.151406e4$. 1591 For this particular case, the initial function value is$f(\bx_0) = 4.151406.10^4$. 1449 The figure \ref{fig-nm-torczon-table} presents the results of these 1592 The figure \ref{fig-nm-torczon-table} presents the results of these 1450 experiments. The number of function evaluations is not the same 1593 experiments. The number of function evaluations is not the same 1451 so that we can conclude that the algorithm may be different 1594 so that we can conclude that the algorithm may be different @@ -1454,10 +1597,10 @@ explain why the number of function evaluations is so different. 1454 1597 1455 \begin{figure}[htbp] 1598 \begin{figure}[htbp] 1456 \begin{center} 1599 \begin{center} 1457 \begin{tiny} 1600 %\begin{tiny} 1458 \begin{tabular}{|l|l|l|l|l|} 1601 \begin{tabular}{|l|l|l|l|l|} 1459 \hline 1602 \hline 1460 Author & Step &$f(v_0^star)$& Function & Angle ($,^{\circ}$)\\ 1603 Author & Step &$f(\bv_1^\star)$& Function & Angle (\degre)\\ 1461 & Tolerance & & Evaluations & \\ 1604 & Tolerance & & Evaluations & \\ 1462 \hline 1605 \hline 1463 Torzcon & 1.e-1 & 7.0355e-5 & 1605 & 89.396677792198 \\ 1606 Torzcon & 1.e-1 & 7.0355e-5 & 1605 & 89.396677792198 \\ @@ -1476,7 +1619,7 @@ Torzcon & 1.e-5 & 6.2912e-5 & 3750 & 89.999931862232 \\ 1476 Baudin & 1.e-5 & 7.427212e-5 & 4626 & 89.999990 \\ 1619 Baudin & 1.e-5 & 7.427212e-5 & 4626 & 89.999990 \\ 1477 \hline 1620 \hline 1478 \end{tabular} 1621 \end{tabular} 1479 \end{tiny} 1622 %\end{tiny} 1480 \end{center} 1623 \end{center} 1481 \caption{Numerical experiment with Nelder-Mead method on Torczon test cases - 1624 \caption{Numerical experiment with Nelder-Mead method on Torczon test cases - 1482 Torczon results and our results} 1625 Torczon results and our results} @@ -1484,16 +1627,16 @@ Torczon results and our results} 1484 \end{figure} 1627 \end{figure} 1485 1628 1486 The figure \ref{fig-nm-numexp-torczon1} presents the 1629 The figure \ref{fig-nm-numexp-torczon1} presents the 1487 angle between the gradient of the function$-g_k$and the search 1630 angle between the gradient of the function$-\bg_k$and the search 1488 direction$x_c - x_h$, where$x_c$is the centroid of the best 1631 direction$\bx_c - \bx_h$, where$\bx_c$is the centroid of the best 1489 points and$x_h$is the worst (or high) vertex. 1632 vertices and$\bx_h$is the worst (or high) vertex. 1490 1633 1491 \begin{figure} 1634 \begin{figure} 1492 \begin{center} 1635 \begin{center} 1493 \includegraphics[width=10cm]{torczon_test1_angle.png} 1636 \includegraphics[width=10cm]{torczon_test1_angle.png} 1494 \end{center} 1637 \end{center} 1495 \caption{Nelder-Mead numerical experiment -- Penalty \#1 function -- 1638 \caption{Nelder-Mead numerical experiment -- Penalty \#1 function -- 1496 One can see that the angle between the gradient and the search direction 1639 We see that the angle between the gradient and the search direction 1497 is very close to$90^{\circ}$, especially for large number of iterations.} 1640 is very close to$90^{\circ}$, especially for large number of iterations.} 1498 \label{fig-nm-numexp-torczon1} 1641 \label{fig-nm-numexp-torczon1} 1499 \end{figure} 1642 \end{figure} @@ -1508,9 +1651,8 @@ The main advantage of the Nelder-Mead algorithm over Spendley et al. 1508 algorithm is that the shape of the simplex is dynamically updated. 1651 algorithm is that the shape of the simplex is dynamically updated. 1509 That allows to get a reasonably fast convergence rate on badly scaled 1652 That allows to get a reasonably fast convergence rate on badly scaled 1510 quadratics, or more generally when the cost function is made 1653 quadratics, or more generally when the cost function is made 1511 of a sharp valley. Nevertheless, the behaviour of the algorithm when the 1654 of a sharp valley. Nevertheless, the behavior of the algorithm when the 1512 dimension of the problem increases is disappointing : the more there are 1655 dimension of the problem increases is disappointing : the more there are 1513 variables, the more the algorithm is slow. In general, it is expected 1656 variables, the more the algorithm is slow. In general, it is expected 1514 that the number of function evaluations is roughly equal to$100n$. 1657 that the number of function evaluations is roughly equal to$100n$. 1515 1658 1516 diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.texindex 06224dd..62a9df1 100644--- a/scilab_doc/neldermead/method-spendley.tex+++ b/scilab_doc/neldermead/method-spendley.tex @@ -6,10 +6,10 @@ unconstrained optimization. 6 We begin by presenting a global overview of the algorithm. 6 We begin by presenting a global overview of the algorithm. 7 Then we present various geometric situations which might occur 7 Then we present various geometric situations which might occur 8 during the algorithm. In the second section, we present several 8 during the algorithm. In the second section, we present several 9 numerical experiments which allow to get some insight in the behaviour 9 numerical experiments which allow to get some insight in the behavior 10 of the algorithm on some simple situations. The two first cases 10 of the algorithm on some simple situations. The two first cases 11 are involving only 2 variables and are based on a quadratic function. 11 are involving only 2 variables and are based on a quadratic function. 12 The last numerical experiment explores the behaviour of the algorith 12 The last numerical experiment explores the behavior of the algorithm 13 when the number of variables increases. 13 when the number of variables increases. 14 14 15 \section{Introduction} 15 \section{Introduction} @@ -32,10 +32,10 @@ following unconstrained optimization problem 32 where$\bx\in \RR^n$,$n$is the number of optimization parameters and$f$is the objective 32 where$\bx\in \RR^n$,$n$is the number of optimization parameters and$f$is the objective 33 function$f:\RR^n\rightarrow \RR$. 33 function$f:\RR^n\rightarrow \RR$. 34 34 35 The simplex algorithms are based on the iterative update of 35 This algorithms is based on the iterative update of 36 a \emph{simplex} made of$n+1$points$S=\{\bx_i\}_{i=1,n+1}$. Each point 36 a \emph{simplex} made of$n+1$points$S=\{\bv_i\}_{i=1,n+1}$. Each point 37 in the simplex is called a \emph{vertex} and is associated with 37 in the simplex is called a \emph{vertex} and is associated with 38 a function value$f_i=f(x_i)$for$i=1,n+1$. 38 a function value$f_i=f(\bv_i)$for$i=1,n+1$. 39 39 40 The vertices are sorted by increasing function values so that the 40 The vertices are sorted by increasing function values so that the 41 \emph{best} vertex has index 1 and the \emph{worst} vertex 41 \emph{best} vertex has index 1 and the \emph{worst} vertex @@ -45,32 +45,32 @@ has index$n+1$45 f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 45 f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 46 \end{eqnarray} 46 \end{eqnarray} 47 47 48 The$\bx_1$vertex (resp. the$\bx_{n+1}$vertex) is called the \emph{best} 48 The$\bv_1$vertex (resp. the$\bv_{n+1}$vertex) is called the \emph{best} 49 vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest) 49 vertex (resp. \emph{worst}), because it is associated with the lowest (resp. highest) 50 function value. As we are going to see, the \emph{next-to-worst} vertex$\bx_n$has a 50 function value. As we are going to see, the \emph{next-to-worst} vertex$\bv_n$has a 51 special role in this algorithm. 51 special role in this algorithm. 52 52 53 The centroid of the simplex$\overline{\bx} (j)$is the center of the vertices 53 The centroid of the simplex$\overline{\bx} (j)$is the center of the vertices 54 where the vertex$\bx_j$has been 54 where the vertex$\bv_j$has been 55 excluded. This centroid is 55 excluded. This centroid is 56 \begin{eqnarray} 56 \begin{eqnarray} 57 \label{centroid-generalized} 57 \label{centroid-generalized} 58 \overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bx_i. 58 \overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i. 59 \end{eqnarray} 59 \end{eqnarray} 60 The algorithm makes use 60 The algorithm makes use 61 of one coefficient$\rho>0$, called the reflection factor. The standard 61 of one coefficient$\rho>0$, called the reflection factor. The standard 62 value of this coefficient is$\rho=1$. 62 value of this coefficient is$\rho=1$. 63 The algorithm attemps to replace some vertex 63 The algorithm attempts to replace some vertex 64$\bx_j$by a new vertex$\bx(\rho,j)$on the line from the vertex$\bx_j$64$\bv_j$by a new vertex$\bx(\rho,j)$on the line from the vertex$\bv_j$65 to the centroid$\overline{\bx}(j)$. The new vertex$\bx(\rho,j)$is defined by 65 to the centroid$\overline{\bx}(j)$. The new vertex$\bx(\rho,j)$is defined by 66 \begin{eqnarray} 66 \begin{eqnarray} 67 \label{interpolate-generalized} 67 \label{interpolate-generalized} 68 \bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bx_j. 68 \bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j. 69 \end{eqnarray} 69 \end{eqnarray} 70 70 71 \subsection{Algorithm} 71 \subsection{Algorithm} 72 72 73 In this section, we analyse Spendley's et al algorithm, which 73 In this section, we analyze Spendley's et al algorithm, which 74 is presented in figure \ref{algo-spendley}. 74 is presented in figure \ref{algo-spendley}. 75 75 76 \begin{figure}[htbp] 76 \begin{figure}[htbp] @@ -91,51 +91,51 @@ is presented in figure \ref{algo-spendley}. 91 \IF {$f_r^\prime10$455 when$a>10$@@ -644,7 +644,7 @@ The figure \ref{fig-sp-numexp3-dimension} presents the number of function 644 evaluations depending on the number of variables. 644 evaluations depending on the number of variables. 645 645 646 One can see that the number of function evaluations 646 One can see that the number of function evaluations 647 increases approximately linearily with the dimension of the problem in 647 increases approximately linearly with the dimension of the problem in 648 figure \ref{fig-sp-numexp3-fvn}. A rough rule of thumb is that, for$n=1,20$, 648 figure \ref{fig-sp-numexp3-fvn}. A rough rule of thumb is that, for$n=1,20$, 649 the number of function evaluations is equal to$30n$. 649 the number of function evaluations is equal to$30n\$. 650 This test is in fact the best that we can expect from this algorithm : since 650 This test is in fact the best that we can expect from this algorithm : since diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.pdf b/scilab_doc/neldermead/nelder-mead-contract-inside.pdfnew file mode 100644index 0000000..2291d00--- /dev/null+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.pdf Binary files differ diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.png b/scilab_doc/neldermead/nelder-mead-contract-inside.pngdeleted file mode 100644index 2411847..0000000--- a/scilab_doc/neldermead/nelder-mead-contract-inside.png+++ /dev/null Binary files differ diff --git a/scilab_doc/neldermead/nelder-mead-contract-inside.svg b/scilab_doc/neldermead/nelder-mead-contract-inside.svgindex cd756ed..1aee216 100644--- a/scilab_doc/neldermead/nelder-mead-contract-inside.svg+++ b/scilab_doc/neldermead/nelder-mead-contract-inside.svg @@ -8,8 +8,8 @@ 8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 11 width="210mm" 11 width="809.82587" 12 height="297mm" 12 height="397.0213" 13 id="svg2" 13 id="svg2" 14 sodipodi:version="0.32" 14 sodipodi:version="0.32" 15 inkscape:version="0.46" 15 inkscape:version="0.46" @@ -17,21 +17,22 @@ 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-inside.png" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-inside.png" 19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90" 20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90" 21 version="1.0"> 21 23 id="defs4"> 23 30 style="overflow:visible"> 30 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" /> 35 36 36 61 inkscape:window-y="14" /> 61 63 id="metadata7"> 63 64 @@ -72,7 +73,8 @@ 72 76 id="layer1" 77 transform="translate(-51.823231,-103.31687)"> 76 98 y="417.98639" /> 97 103 sodipodi:nodetypes="cccc" /> @@ -140,12 +142,12 @@ 140 x="432.05054" 142 x="432.05054" 141 y="308.15915">N 143 y="308.15915">N 142 148 sodipodi:nodetypes="cccc" /> 147 153 sodipodi:nodetypes="cc" /> @@ -176,7 +178,7 @@ 176 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-163.52526,97.403636)" /> 178 transform="matrix(0.8015337,-0.4627657,0.4627657,0.8015337,-163.52526,97.403636)" /> 177 188 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-802.48459,-155.5446)" /> 187 218 transform="translate(130.81219,71.517787)" /> 217 223 sodipodi:nodetypes="cccc" /> @@ -239,73 +241,77 @@ 239 sodipodi:ry="2.2728431" 241 sodipodi:ry="2.2728431" 240 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 242 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 241 transform="translate(47.474606,-93.13708)" /> 243 transform="translate(47.474606,-93.13708)" /> 242 R = Reflexion 252 246 transform="translate(139.40105,-235.36554)"> 255 R = Reflexion 257 260 H = Highest 265 id="text3242"> 266 sodipodi:role="line" 266 H = Highest 269 x="542.36511" 270 270 y="418.40466" 271 L = Lowest 275 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 276 L = Lowest 281 id="text3250">N = Next to highest 285 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 286 N = Next to highest 291 id="text3439">Ci = Contraction (inside) 296 xml:space="preserve">Ci = Contraction (inside) 305 f(R) >= f(H) 309 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 310 xml:space="preserve">f(R) ≥ f(H) 315 310 316 311 317 diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.pdf b/scilab_doc/neldermead/nelder-mead-contract-outside.pdfnew file mode 100644index 0000000..d294af6--- /dev/null+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.pdf Binary files differ diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.png b/scilab_doc/neldermead/nelder-mead-contract-outside.pngdeleted file mode 100644index fe38040..0000000--- a/scilab_doc/neldermead/nelder-mead-contract-outside.png+++ /dev/null Binary files differ diff --git a/scilab_doc/neldermead/nelder-mead-contract-outside.svg b/scilab_doc/neldermead/nelder-mead-contract-outside.svgindex fb5200d..e9fc83c 100644--- a/scilab_doc/neldermead/nelder-mead-contract-outside.svg+++ b/scilab_doc/neldermead/nelder-mead-contract-outside.svg @@ -8,8 +8,8 @@ 8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 11 width="210mm" 11 width="837.6604" 12 height="297mm" 12 height="503.00317" 13 id="svg2" 13 id="svg2" 14 sodipodi:version="0.32" 14 sodipodi:version="0.32" 15 inkscape:version="0.46" 15 inkscape:version="0.46" @@ -17,21 +17,22 @@ 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-outside.png" 18 inkscape:export-filename="K:\ProjetTclrep\doc\neldermead\nelder-mead-contract-outside.png" 19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90" 20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90" 21 version="1.0"> 21 23 id="defs4"> 23 30 style="overflow:visible"> 30 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" /> 35 36 36 61 inkscape:window-y="10" /> 61 63 id="metadata7"> 63 64 @@ -72,7 +73,8 @@ 72 76 id="layer1" 77 transform="translate(-33.845178,-66.596157)"> 76 98 y="417.98639" /> 97 103 sodipodi:nodetypes="cccc" /> @@ -140,12 +142,12 @@ 140 x="386.09116" 142 x="386.09116" 141 y="295.73529">N 143 y="295.73529">N 142 148 sodipodi:nodetypes="cccc" /> 147 153 sodipodi:nodetypes="cc" /> @@ -171,7 +173,7 @@ 171 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-801.7703,-126.25889)" /> 173 transform="matrix(1.7914474,-1.0342926,1.0342926,1.7914474,-801.7703,-126.25889)" /> 172 183 transform="matrix(3.3350534,-1.9254939,1.9254939,3.3350534,-1804.8322,-522.25569)" /> 182 188 sodipodi:nodetypes="cc" /> 187 213 transform="matrix(5.7171128,-3.3007765,3.3007765,5.7171128,-3358.0596,-1127.1779)" /> 212 218 sodipodi:nodetypes="cccc" /> @@ -244,69 +246,73 @@ 244 sodipodi:ry="2.2728431" 246 sodipodi:ry="2.2728431" 245 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 247 d="M 306.83385,367.98383 A 2.2728431,2.2728431 0 1 1 302.28816,367.98383 A 2.2728431,2.2728431 0 1 1 306.83385,367.98383 z" 246 transform="translate(80.812192,51.517787)" /> 248 transform="translate(80.812192,51.517787)" /> 247 250 x="492.50925" 252 R = Reflexion 256 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 257 R = Reflexion 262 id="text3242">H = Highest 266 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 267 H = Highest 272 id="text3246">L = Lowest 276 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 277 L = Lowest 282 id="text3250">N = Next to highest 286 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 287 N = Next to highest 292 id="text3259">Co = Contraction (outside) 300 id="tspan3261" 301 Co = Contraction (outside) 306 id="text2586">f(N)<=f(R)<f(H) 310 style="font-size:21.10450363px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans" 311 xml:space="preserve">f(N)≤f(R)<f(H) 316 311 317 312 318 diff --git a/scilab_doc/neldermead/nelder-mead-extension.pdf b/scilab_doc/neldermead/nelder-mead-extension.pdfnew file mode 100644index 0000000..7d6de4f--- /dev/null+++ b/scilab_doc/neldermead/nelder-mead-extension.pdf Binary files differ diff --git a/scilab_doc/neldermead/nelder-mead-extension.svg b/scilab_doc/neldermead/nelder-mead-extension.svgindex 893a1ba..d69765b 100644--- a/scilab_doc/neldermead/nelder-mead-extension.svg+++ b/scilab_doc/neldermead/nelder-mead-extension.svg @@ -8,30 +8,31 @@ 8 xmlns="http://www.w3.org/2000/svg" 8 xmlns="http://www.w3.org/2000/svg" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape" 11 width="210mm" 11 width="760.96051" 12 height="297mm" 12 height="516.25098" 13 id="svg2" 13 id="svg2" 14 sodipodi:version="0.32" 14 sodipodi:version="0.32" 15 inkscape:version="0.46" 15 inkscape:version="0.46" 16 sodipodi:docname="nelder.mead.extension.svg" 16 sodipodi:docname="nelder-mead-extension.svg" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 17 inkscape:output_extension="org.inkscape.output.svg.inkscape" 18 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.extension.png" 18 inkscape:export-filename="D:\TclRep\tclrep_cvs\doc\neldermead\nelder.mead.extension.png" 19 inkscape:export-xdpi="90" 19 inkscape:export-xdpi="90" 20 inkscape:export-ydpi="90"> 20 inkscape:export-ydpi="90" 21 version="1.0"> 21 23 id="defs4"> 23 30 style="overflow:visible"> 30 35 transform="matrix(-0.8,0,0,-0.8,-10,0)" /> 35 36 36 61 inkscape:window-y="21" /> 61 63 id="metadata7"> 63 64 @@ -72,7 +73,8 @@ 72 76 id="layer1" 77 transform="translate(-73.241138,-175.12971)"> 76 98 y="417.98639" /> 97 103 sodipodi:nodetypes="cccc" /> @@ -150,18 +152,18 @@ 150 x="395.74493" 152 x="395.74493" 151 y="513.42316">E 153 y="513.42316">E 152 158 sodipodi:nodetypes="cccc" /> 157 163 sodipodi:nodetypes="cc" /> 162 173 transform="matrix(0.8660254,-0.5,0.5,0.8660254,-152.3352,348.10297)" /> 172 183 transform="matrix(1.9355879,-1.1175122,1.1175122,1.9355879,-842.70542,74.802419)" /> 182 193 transform="matrix(3.603393,-2.0804199,2.0804199,3.603393,-1926.4741,-353.05643)" /> 192