summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichaŽl Baudin <michael.baudin@scilab.org>2009-10-21 15:06:17 +0200
committerMichaŽl Baudin <michael.baudin@scilab.org>2009-10-21 15:06:17 +0200
commitabcecda892336291ee3e5c972d37fda38e197169 (patch)
tree90374b5e8c7718f787094033ff1da96fa2fba9b8 /scilab_doc
parent4347c6987fe93e4756cb819920d6086f8d518fd8 (diff)
downloadscilab-abcecda892336291ee3e5c972d37fda38e197169.zip
scilab-abcecda892336291ee3e5c972d37fda38e197169.tar.gz
Updated User Manual with simplex gradient
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/fminsearch-so.pdfbin239703 -> 238829 bytes
-rw-r--r--scilab_doc/neldermead/macros.tex29
-rw-r--r--scilab_doc/neldermead/method-neldermead.tex12
-rw-r--r--scilab_doc/neldermead/method-spendley.tex12
-rw-r--r--scilab_doc/neldermead/neldermead-simplex-so.pdfbin184133 -> 295792 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.bib21
-rw-r--r--scilab_doc/neldermead/neldermead.pdfbin983277 -> 1312678 bytes
-rw-r--r--scilab_doc/neldermead/neldermead.tex4
-rw-r--r--scilab_doc/neldermead/scripts/demo_allsizes.sce26
-rw-r--r--scilab_doc/neldermead/scripts/demo_simplex_regular.sce25
-rw-r--r--scilab_doc/neldermead/scripts/norm_matrixdirection.sce28
-rw-r--r--scilab_doc/neldermead/scripts/simplex_gradient.sce54
-rw-r--r--scilab_doc/neldermead/scripts/simplexaxis_directionscondition.sce30
-rw-r--r--scilab_doc/neldermead/section-simplex.tex652
-rw-r--r--scilab_doc/neldermead/simplex_flat.pdfbin0 -> 15245 bytes
-rw-r--r--scilab_doc/neldermead/simplex_flat.svg231
-rw-r--r--scilab_doc/neldermead/simplex_towardflat.pdfbin0 -> 16139 bytes
-rw-r--r--scilab_doc/neldermead/simplex_towardflat.svg281
18 files changed, 1369 insertions, 36 deletions
diff --git a/scilab_doc/neldermead/fminsearch-so.pdf b/scilab_doc/neldermead/fminsearch-so.pdf
index 22f5123..05a0864 100644
--- a/scilab_doc/neldermead/fminsearch-so.pdf
+++ b/scilab_doc/neldermead/fminsearch-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/macros.tex b/scilab_doc/neldermead/macros.tex
index 572dd39..b713760 100644
--- a/scilab_doc/neldermead/macros.tex
+++ b/scilab_doc/neldermead/macros.tex
@@ -48,11 +48,15 @@
48\newcommand{\Dx}{\partial_x} 48\newcommand{\Dx}{\partial_x}
49\newcommand{\Dy}{\partial_y} 49\newcommand{\Dy}{\partial_y}
50 50
51\newcommand{\bv}{\mathbf{v}} 51\newcommand{\bd}{\mathbf{d}}
52\newcommand{\bx}{\mathbf{x}}
53\newcommand{\bl}{\mathbf{l}} 52\newcommand{\bl}{\mathbf{l}}
54\newcommand{\br}{\mathbf{r}} 53\newcommand{\br}{\mathbf{r}}
55\newcommand{\bg}{\mathbf{g}} 54\newcommand{\bg}{\mathbf{g}}
55\newcommand{\bp}{\mathbf{p}}
56\newcommand{\bH}{\mathbf{H}}
57\newcommand{\bv}{\mathbf{v}}
58\newcommand{\bx}{\mathbf{x}}
59\newcommand{\by}{\mathbf{y}}
56 60
57\usepackage{url} 61\usepackage{url}
58 62
@@ -313,5 +317,26 @@
313% For symbol degree 317% For symbol degree
314\DeclareTextSymbol{\degre}{T1}{6} 318\DeclareTextSymbol{\degre}{T1}{6}
315 319
320% Some environments
321\newtheorem{theorem}{Theorem}[section]
322\newtheorem{lemma}[theorem]{Lemma}
323\newtheorem{proposition}[theorem]{Proposition}
324\newtheorem{corollary}[theorem]{Corollary}
325\newtheorem{axiom}[theorem]{Axiom}
326%\newtheorem{example}[theorem]{Example}
327\newtheorem{definition}[theorem]{Definition}
328\newtheorem{remark}[theorem]{Remark}
329
330\newenvironment{proof}[1][Proof]{\begin{trivlist}
331\item[\hskip \labelsep {\bfseries #1}]}{\qed\end{trivlist}}
332
333%\newenvironment{definition}[1][Definition]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
334\newenvironment{example}[1][Example]{\begin{trivlist}\item[\hskip \labelsep {\bfseries #1}]}{$\Box$\end{trivlist}}
335%\newenvironment{remark}[1][Remark]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}}
336
337\newcommand{\qed}{\nobreak \ifvmode \relax \else
338 \ifdim\lastskip<1.5em \hskip-\lastskip
339 \hskip1.5em plus0em minus0.5em \fi \nobreak
340 \vrule height0.75em width0.5em depth0.25em\fi}
316 341
317 342
diff --git a/scilab_doc/neldermead/method-neldermead.tex b/scilab_doc/neldermead/method-neldermead.tex
index 35398c3..ea17976 100644
--- a/scilab_doc/neldermead/method-neldermead.tex
+++ b/scilab_doc/neldermead/method-neldermead.tex
@@ -42,7 +42,7 @@ The vertices are sorted by increasing function values so that the
42\emph{best} vertex has index 1 and the \emph{worst} vertex 42\emph{best} vertex has index 1 and the \emph{worst} vertex
43has index $n+1$ 43has index $n+1$
44\begin{eqnarray} 44\begin{eqnarray}
45\label{sorted-vertices-fv} 45\label{nm-sorted-vertices-fv}
46f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 46f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
47\end{eqnarray} 47\end{eqnarray}
48 48
@@ -54,7 +54,7 @@ The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices
54where the vertex $\bv_j$ has been 54where the vertex $\bv_j$ has been
55excluded. This centroid is 55excluded. This centroid is
56\begin{eqnarray} 56\begin{eqnarray}
57\label{centroid-generalized} 57\label{nm-centroid-generalized}
58\overline{\bx} (j) = 58\overline{\bx} (j) =
59\frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i. 59\frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i.
60\end{eqnarray} 60\end{eqnarray}
@@ -65,7 +65,7 @@ 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$ 65$\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$
66to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by 66to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by
67\begin{eqnarray} 67\begin{eqnarray}
68\label{interpolate-generalized} 68\label{nm-interpolate-generalized}
69\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j. 69\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j.
70\end{eqnarray} 70\end{eqnarray}
71 71
@@ -149,13 +149,13 @@ At each iteration, we compute the centroid
149$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$ 149$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$
150has been excluded. This centroid is 150has been excluded. This centroid is
151\begin{eqnarray} 151\begin{eqnarray}
152\label{centroid-worst} 152\label{nm-centroid-worst}
153\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i. 153\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i.
154\end{eqnarray} 154\end{eqnarray}
155We perform a reflection with respect to the worst vertex $\bv_{n+1}$, 155We perform a reflection with respect to the worst vertex $\bv_{n+1}$,
156which creates the reflected point $\bx_r$ defined by 156which creates the reflected point $\bx_r$ defined by
157\begin{eqnarray} 157\begin{eqnarray}
158\label{interpolate-worst} 158\label{nm-interpolate-worst}
159\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1} 159\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1}
160\end{eqnarray} 160\end{eqnarray}
161We then compute the function value of the reflected 161We then compute the function value of the reflected
@@ -752,7 +752,7 @@ coefficients.
752 752
753\emph{Outside contraction} \\ 753\emph{Outside contraction} \\
754If the outside contraction step is repeatedly performed 754If the outside contraction step is repeatedly performed
755with variable $\mu_{oc} \in }0,\mu_r[$, then 755with variable $\mu_{oc} \in [0,\mu_r[$, then
756\begin{eqnarray} 756\begin{eqnarray}
757\bv^{(k+n)} &=& \overline{\bold{v}}^{(k)} 757\bv^{(k+n)} &=& \overline{\bold{v}}^{(k)}
758+ \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\ 758+ \mu_{oc} \left( \overline{\bold{v}}^{(k)} - \bv^{(k)}\right) \\
diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex
index adb1990..dcb183f 100644
--- a/scilab_doc/neldermead/method-spendley.tex
+++ b/scilab_doc/neldermead/method-spendley.tex
@@ -41,7 +41,7 @@ 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
42has index $n+1$ 42has index $n+1$
43\begin{eqnarray} 43\begin{eqnarray}
44\label{sorted-vertices-fv} 44\label{sp-sorted-vertices-fv}
45f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}. 45f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
46\end{eqnarray} 46\end{eqnarray}
47 47
@@ -54,7 +54,7 @@ The centroid of the simplex $\overline{\bx} (j)$ is the center of the vertices
54where the vertex $\bv_j$ has been 54where the vertex $\bv_j$ has been
55excluded. This centroid is 55excluded. This centroid is
56\begin{eqnarray} 56\begin{eqnarray}
57\label{centroid-generalized} 57\label{sp-centroid-generalized}
58\overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i. 58\overline{\bx} (j) = \frac{1}{n} \sum_{i=1,n+1, i\neq j} \bv_i.
59\end{eqnarray} 59\end{eqnarray}
60The algorithm makes use 60The algorithm makes use
@@ -64,7 +64,7 @@ The algorithm attempts to replace some vertex
64$\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$ 64$\bv_j$ by a new vertex $\bx(\rho,j)$ on the line from the vertex $\bv_j$
65to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by 65to the centroid $\overline{\bx}(j)$. The new vertex $\bx(\rho,j)$ is defined by
66\begin{eqnarray} 66\begin{eqnarray}
67\label{interpolate-generalized} 67\label{sp-interpolate-generalized}
68\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j. 68\bx(\rho,j) = (1+\rho)\overline{\bx}(j) - \rho \bv_j.
69\end{eqnarray} 69\end{eqnarray}
70 70
@@ -106,13 +106,13 @@ At each iteration, we compute the centroid
106$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$ 106$\overline{\bx} (n+1)$ where the worst vertex $\bv_{n+1}$
107has been excluded. This centroid is 107has been excluded. This centroid is
108\begin{eqnarray} 108\begin{eqnarray}
109\label{centroid-worst} 109\label{sp-centroid-worst}
110\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i. 110\overline{\bx} (n+1) = \frac{1}{n} \sum_{i=1,n} \bv_i.
111\end{eqnarray} 111\end{eqnarray}
112We perform a reflection with respect to the worst vertex $\bv_{n+1}$, 112We perform a reflection with respect to the worst vertex $\bv_{n+1}$,
113which creates the reflected point $\bx_r$ defined by 113which creates the reflected point $\bx_r$ defined by
114\begin{eqnarray} 114\begin{eqnarray}
115\label{interpolate-worst} 115\label{sp-interpolate-worst}
116\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1} 116\bx_r = \bx(\rho,n+1) = (1+\rho)\overline{\bx}(n+1) - \rho \bv_{n+1}
117\end{eqnarray} 117\end{eqnarray}
118 118
@@ -309,7 +309,7 @@ $\bx_0$ & $(2.0,2.0)$ \\
309Relative tolerance on simplex size & $10^{-8}$ \\ 309Relative tolerance on simplex size & $10^{-8}$ \\
310Exact $\bx^\star$ & $(0.,0.)$\\ 310Exact $\bx^\star$ & $(0.,0.)$\\
311Computed $\bx^\star$ & $(2.169e-10, 2.169e-10)$\\ 311Computed $\bx^\star$ & $(2.169e-10, 2.169e-10)$\\
312Exact $f(\b\bx^\star)$ & $0.$\\ 312Exact $f(\bx^\star)$ & $0.$\\
313Computed $f(\bx^\star)$ & $4.706e-20$\\ 313Computed $f(\bx^\star)$ & $4.706e-20$\\
314\hline 314\hline
315\end{tabular} 315\end{tabular}
diff --git a/scilab_doc/neldermead/neldermead-simplex-so.pdf b/scilab_doc/neldermead/neldermead-simplex-so.pdf
index 6c69bb3..607a426 100644
--- a/scilab_doc/neldermead/neldermead-simplex-so.pdf
+++ b/scilab_doc/neldermead/neldermead-simplex-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead.bib b/scilab_doc/neldermead/neldermead.bib
index ca7d39a..09751c5 100644
--- a/scilab_doc/neldermead/neldermead.bib
+++ b/scilab_doc/neldermead/neldermead.bib
@@ -509,3 +509,24 @@ PAGES = {2928}
509 year = {1981} 509 year = {1981}
510} 510}
511 511
512@book{numericaloptimization,
513author = {Jorge Nocedal, Stephen J. Wright},
514title = {Numerical Optimization},
515year = {1999},
516publisher= {Springer}
517}
518
519@book{citeulike:2122238,
520 address = {Baltimore, MD, USA},
521 author = {Golub, Gene H. and Van Loan, Charles F. },
522 citeulike-article-id = {2122238},
523 isbn = {0801854148},
524 keywords = {algebra, book, computation, numerical},
525 posted-at = {2008-03-30 22:15:25},
526 priority = {2},
527 publisher = {Johns Hopkins University Press},
528 title = {Matrix computations (3rd ed.)},
529 url = {http://portal.acm.org/citation.cfm?id=248979},
530 year = {1996}
531}
532
diff --git a/scilab_doc/neldermead/neldermead.pdf b/scilab_doc/neldermead/neldermead.pdf
index 86443c0..4a3c64b 100644
--- a/scilab_doc/neldermead/neldermead.pdf
+++ b/scilab_doc/neldermead/neldermead.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermead.tex b/scilab_doc/neldermead/neldermead.tex
index 4a8a0c8..308f9b6 100644
--- a/scilab_doc/neldermead/neldermead.tex
+++ b/scilab_doc/neldermead/neldermead.tex
@@ -80,8 +80,8 @@ in several programming languages.
80 80
81 81
82\begin{flushright} 82\begin{flushright}
83Version 0.3 \\ 83Version 0.4 \\
84September 2009 84October 2009
85\end{flushright} 85\end{flushright}
86 86
87 87
diff --git a/scilab_doc/neldermead/scripts/demo_allsizes.sce b/scilab_doc/neldermead/scripts/demo_allsizes.sce
new file mode 100644
index 0000000..5c4c2bb
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/demo_allsizes.sce
@@ -0,0 +1,26 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Create a new axis-by-axis simplex and compute the
11// size by various methods.
12x0 = [0.0 0.0];
13si = optimsimplex_new ( "axes" , x0 );
14methodlist = [
15"sigmaplus"
16"sigmaminus"
17"Nash"
18"diameter"
19];
20for i = 1:size(methodlist,"*")
21 m = methodlist ( i );
22 ss = optimsimplex_size ( si , m );
23 mprintf ( "%s: %f\n", m , ss );
24end
25optimsimplex_destroy(si)
26
diff --git a/scilab_doc/neldermead/scripts/demo_simplex_regular.sce b/scilab_doc/neldermead/scripts/demo_simplex_regular.sce
new file mode 100644
index 0000000..90a5d88
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/demo_simplex_regular.sce
@@ -0,0 +1,25 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Create an initial regular simplex
11// and compute its size by various methods.
12x0 = [0.0 0.0];
13si = optimsimplex_new ( "spendley" , x0 );
14methodlist = [
15"sigmaplus"
16"sigmaminus"
17"diameter"
18];
19for i = 1:size(methodlist,"*")
20 m = methodlist ( i );
21 ss = optimsimplex_size ( si , m );
22 mprintf ( "%s: %f\n", m , ss );
23end
24optimsimplex_destroy(si);
25
diff --git a/scilab_doc/neldermead/scripts/norm_matrixdirection.sce b/scilab_doc/neldermead/scripts/norm_matrixdirection.sce
new file mode 100644
index 0000000..ab57531
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/norm_matrixdirection.sce
@@ -0,0 +1,28 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Create a new simplex by coordinates and compute the
11// norm of the matrix of directions and its oriented length
12coords = [
130.0 0.0
141.0 0.5
151.0 2.0
16];
17si = optimsimplex_new ( coords );
18D = optimsimplex_dirmat ( si )
19for i=1:2
20 nd = norm(D(1:2,i),2);
21 mprintf( "||d_%d||=%f\n",i,nd)
22end
23ss = optimsimplex_size ( si , "sigmaplus" );
24mprintf( "sigma_+(S)=%f\n",ss);
25normmatrix = norm(D);
26mprintf( "||D||=%f\n",normmatrix);
27optimsimplex_destroy(si);
28
diff --git a/scilab_doc/neldermead/scripts/simplex_gradient.sce b/scilab_doc/neldermead/scripts/simplex_gradient.sce
new file mode 100644
index 0000000..1f72789
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/simplex_gradient.sce
@@ -0,0 +1,54 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Create a new axis-by-axis simplex and compute the
11// simplex gradient
12function y = myfunction ( x )
13 y = x(1)^2 + x(2)^2
14endfunction
15x0 = [1.0 1.0];
16len = 1.e-3;
17si = optimsimplex_new ( "axes" , x0 , myfunction , len );
18sg = optimsimplex_gradientfv ( si );
19mprintf ( "Simplex Gradient=(%f %f)^T\n",sg(1),sg(2));
20eg = [2 * x0(1) 2 * x0(2)].';
21mprintf ( "Exact Gradient=(%f %f)^T\n",eg(1),eg(2));
22err = norm(sg-eg)/norm(eg);
23mprintf ( "Relative Error = %e\n",err);
24err = norm(sg-eg);
25mprintf ( "Absolute Error = %e\n",err);
26D = optimsimplex_dirmat ( si );
27k = cond(D);
28mprintf ( "k(D)=%f\n",k);
29ss = optimsimplex_size ( si );
30mprintf ( "sigma_+(D)=%e\n",ss);
31optimsimplex_destroy(si);
32
33// Create a flat simplex and compute the simplex gradient.
34R = 0.5e-3
35coords = [
36 1.0 1.0
37 1.0+1.e-3 1.0
38];
39for theta = [90.0 10.0 1.0 0.1 0.01 0.001]
40 C(1,1) = 1.0 + R * cos(theta*%pi/180);
41 C(1,2) = 1.0 + R * sin(theta*%pi/180);
42 coords(3,1:2) = C;
43 si = optimsimplex_new ( coords , myfunction );
44 sg = optimsimplex_gradientfv ( si );
45 eg = [2 * x0(1) 2 * x0(2)].';
46 err = norm(sg-eg);
47 D = optimsimplex_dirmat ( si );
48 k = cond(D);
49 ss = optimsimplex_size ( si );
50 mprintf ( "%f & %e & %e & %e \\\\\n",theta , ss , err , k);
51 optimsimplex_destroy(si);
52end
53
54
diff --git a/scilab_doc/neldermead/scripts/simplexaxis_directionscondition.sce b/scilab_doc/neldermead/scripts/simplexaxis_directionscondition.sce
new file mode 100644
index 0000000..6f57d95
--- /dev/null
+++ b/scilab_doc/neldermead/scripts/simplexaxis_directionscondition.sce
@@ -0,0 +1,30 @@
1// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
2// Copyright (C) 2009 - Digiteo - Michael Baudin
3//
4// This file must be used under the terms of the CeCILL.
5// This source file is licensed as described in the file COPYING, which
6// you should have received as part of this distribution. The terms
7// are also available at
8// http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
9
10// Create a new axis-by-axis simplex and compute the
11// matrix of directions and its condition number
12x0 = [0.0 0.0];
13si = optimsimplex_new ( "axes" , x0 );
14D = optimsimplex_dirmat ( si )
15k = cond(D)
16optimsimplex_destroy(si);
17
18// Create a flat simplex and compute its condition number.
19coords = [
200.0 0.0
211.0 0.0
220.5 1.e-10
23];
24si = optimsimplex_new ( coords );
25D = optimsimplex_dirmat ( si )
26k = cond(D)
27optimsimplex_destroy(si);
28
29
30
diff --git a/scilab_doc/neldermead/section-simplex.tex b/scilab_doc/neldermead/section-simplex.tex
index 798023e..7b5175b 100644
--- a/scilab_doc/neldermead/section-simplex.tex
+++ b/scilab_doc/neldermead/section-simplex.tex
@@ -39,7 +39,10 @@ to a simplex or to a more general a complex.
39%and are only applicable to a \emph{simplex}. 39%and are only applicable to a \emph{simplex}.
40 40
41We assume that we are given a cost function $f:\RR^n\rightarrow\RR$. 41We assume that we are given a cost function $f:\RR^n\rightarrow\RR$.
42Each vertex $\bv_i$ is associated with a function value $f_i = f(\bv_i)$ for $i=1,m$. 42Each vertex $\bv_i$ is associated with a function value
43\begin{eqnarray}
44f_i = f(\bv_i) \textrm{ for } i=1,m.
45\end{eqnarray}
43For any complex, the vertices can be sorted by increasing function values 46For any complex, the vertices can be sorted by increasing function values
44\begin{eqnarray} 47\begin{eqnarray}
45\label{simplex-sortedfv} 48\label{simplex-sortedfv}
@@ -52,15 +55,6 @@ In \cite{lagarias:112}, the sorting rules are defined precisely to be able to
52state a theoretical convergence result. In practical implementations, though, the 55state a theoretical convergence result. In practical implementations, though, the
53ordering rules have no measurable influence. 56ordering rules have no measurable influence.
54 57
55For a given simplex $S$, let $V$ denote the
56$n\times n$ matrix of simplex directions
57\begin{eqnarray}
58\label{simplex-directions}
59V(S) = (\bv_2 - \bv_1, \bv_3 - \bv_1 , \ldots , \bv_{n+1} - \bv_1).
60\end{eqnarray}
61
62We say that the simplex $S$ is nonsingular if the matrix of simplex directions $V(S)$ is nonsingular.
63
64\section{The size of the complex} 58\section{The size of the complex}
65\label{section-simplexsize} 59\label{section-simplexsize}
66 60
@@ -120,10 +114,10 @@ This is directly implied by the inequality
120&\leq& \max_{i,j=1,m} \|\bv_i - \bv_j\|_2, 114&\leq& \max_{i,j=1,m} \|\bv_i - \bv_j\|_2,
121\end{eqnarray} 115\end{eqnarray}
122which concludes the first part of the proof. 116which concludes the first part of the proof.
123We shal now proove the inequality 117We shall now proove the inequality
124\begin{eqnarray} 118\begin{eqnarray}
125\label{eq-simplex-ineqdiam} 119\label{eq-simplex-ineqdiam}
126\diam(S) \leq 2 \sigma_+(S). 120diam(S) \leq 2 \sigma_+(S).
127\end{eqnarray} 121\end{eqnarray}
128We decompose the difference 122We decompose the difference
129$\bv_i - \bv_j$ into 123$\bv_i - \bv_j$ into
@@ -147,7 +141,7 @@ With the definitions of the diameter
147and the oriented length, this immediately 141and the oriented length, this immediately
148prooves the inequality 142prooves the inequality
149\ref{eq-simplex-ineqdiam}. 143\ref{eq-simplex-ineqdiam}.
150end{proof} 144\end{proof}
151 145
152In Nash's book \cite{nla.cat-vn1060620}, the size of the simplex $s_N(S)$ is measured 146In Nash's book \cite{nla.cat-vn1060620}, the size of the simplex $s_N(S)$ is measured
153based on the 1-norm and is defined by 147based on the 1-norm and is defined by
@@ -161,6 +155,39 @@ where the 1-norm is defined by
161\|\bv_i \|_1 = \sum_{j=1,n} |(\bv_i)_j|. 155\|\bv_i \|_1 = \sum_{j=1,n} |(\bv_i)_j|.
162\end{eqnarray} 156\end{eqnarray}
163 157
158The \scifunction{optimsimplex\_size} function provides all these size algorithms.
159In the following example, we create an axis-by-axis simplex
160with length unity and compute its length by several methods.
161
162\lstset{language=scilabscript}
163\begin{lstlisting}
164xx0 = [0.0 0.0];
165si = optimsimplex_new ( "axes" , x0 );
166methodlist = [
167"sigmaplus"
168"sigmaminus"
169"Nash"
170"diameter"
171];
172for i = 1:size(methodlist,"*")
173 m = methodlist ( i );
174 ss = optimsimplex_size ( si , m );
175 mprintf ( "%s: %f\n", m , ss );
176end
177optimsimplex_destroy(si)
178\end{lstlisting}
179The previous script produces the following output.
180\lstset{language=scilabscript}
181\begin{lstlisting}
182sigmaplus: 1.000000
183sigmaminus: 1.000000
184Nash: 2.000000
185diameter: 1.414214
186\end{lstlisting}
187We check that the diameter is equal to $diam(S) = \sqrt{2}$.
188We see that inequality \ref{simplex-sigma-diam} is satisfied since
189$\sigma_+(S)=1\leq \sqrt{2} \leq 2 = 2\sigma_+(S)$.
190
164\section{The initial simplex} 191\section{The initial simplex}
165 192
166While most of the theory can be developed without being very specific 193While most of the theory can be developed without being very specific
@@ -249,6 +276,34 @@ The regular simplex is presented in figure \ref{fig-nm-simplex-regular}.
249\label{fig-nm-simplex-regular} 276\label{fig-nm-simplex-regular}
250\end{figure} 277\end{figure}
251 278
279In the following Scilab session, we define a regular simplex
280with the \scifunction{optimsimplex\_new} function.
281\lstset{language=scilabscript}
282\begin{lstlisting}
283x0 = [0.0 0.0];
284si = optimsimplex_new ( "spendley" , x0 );
285methodlist = [
286"sigmaplus"
287"sigmaminus"
288"diameter"
289];
290for i = 1:size(methodlist,"*")
291 m = methodlist ( i );
292 ss = optimsimplex_size ( si , m );
293 mprintf ( "%s: %f\n", m , ss );
294end
295optimsimplex_destroy(si);
296\end{lstlisting}
297The previous script produces the following output.
298\lstset{language=scilabscript}
299\begin{lstlisting}
300sigmaplus: 1.000000
301sigmaminus: 1.000000
302diameter: 1.000000
303\end{lstlisting}
304We check that the three sizes $diam(S)$, $\sigma_+(S)$
305and $\sigma_-(S)$ are equal, as expected from a regular simplex.
306
252\subsection{Axis-by-axis simplex} 307\subsection{Axis-by-axis simplex}
253 308
254A very efficient and simple approach leads to an axis-by-axis simplex. 309A very efficient and simple approach leads to an axis-by-axis simplex.
@@ -342,15 +397,572 @@ The other vertices are defined by
342\end{eqnarray} 397\end{eqnarray}
343for vertices $i=2,n+1$ and components $j=1,n$. 398for vertices $i=2,n+1$ and components $j=1,n$.
344 399
345%\section{The simplex gradient} 400\section{The simplex gradient}
346%\label{section-simplexgradient} 401\label{section-simplexgradient}
402
403In this section, we present the simplex gradient and proove
404that this gradient is an approximation of the gradient of the
405objective function, provided that the condition of the matrix
406of simplex directions. We derive the forward
407simplex gradient.
408
409\subsection{Matrix of simplex directions}
410
411We consider here simplices made of $m=n+1$ vertices only.
412This allows to define the matrix of simplex directions as presented
413in the following definition.
414
415\begin{definition}
416(\emph{Matrix of simplex directions})
417Assume that $S$ is a set of $m=n+1$ vertices. The $n\times n$ matrix of
418simplex directions $D(S)$ is defined by
419\begin{eqnarray}
420D(S) = (\bv_2 - \bv_1 , \bv_2-\bv_1,\ldots,\bv_{n+1} - \bv_1).
421\end{eqnarray}
422We define by $\{\bd_i\}_{i=1,n}$ the columns of the $n \times n$ matrix $D(S)$,
423i.e.
424\begin{eqnarray}
425D(S)= (\bd_1,\bd_2,\ldots,\bd_n).
426\end{eqnarray}
427We say that the simplex $S$ is \emph{nonsingular} if the matrix $D(S)$ is \emph{nonsingular}.
428We define the \emph{simplex condition} as the $l^2$ condition number
429of the matrix of simplex directions $\kappa(D(S))$.
430\end{definition}
431
432The directions $\bd_i$ can be seen as \emph{offsets}, leading from
433the first vertex to each vertex $\bv_i$, i.e.
434\begin{eqnarray}
435\bv_i = \bv_1 + \bd_1, \textrm{ for } i = 1, n.
436\end{eqnarray}
437
438\begin{example}
439(\emph{A non degenerate simplex})
440Consider the axis-by-axis simplex, with first vertex at origin and
441lengths unity. The vertices are defined by
442\begin{eqnarray}
443\bv_1=(0,0)^T, \qquad \bv_2=(1,0)^T, \qquad \bv_3=(0,1)^T,
444\end{eqnarray}
445so that the matrix of simplex directions is
446given by
447\begin{eqnarray}
448D = \left(
449\begin{array}{cc}
4501 & 0 \\
4510 & 1
452\end{array}
453\right).
454\end{eqnarray}
455Such a matrix has a unity condition number.
456
457The following Scilab session uses the \scifunction{optimsimplex}
458component to generate a axis-by-axis simplex and computes the
459matrix of directions with the \scifunction{optimsimplex\_dirmat}
460function.
461\lstset{language=scilabscript}
462\begin{lstlisting}
463x0 = [0.0 0.0];
464si = optimsimplex_new ( "axes" , x0 );
465D = optimsimplex_dirmat ( si )
466k = cond(D)
467optimsimplex_destroy(si)
468\end{lstlisting}
469The previous script produces the following output.
470\lstset{language=scilabscript}
471\begin{lstlisting}
472-->D = optimsimplex_dirmat ( si )
473 D =
474 1. 0.
475 0. 1.
476-->k = cond(D)
477 k =
478 1.
479\end{lstlisting}
480We check that an axis-by-axis simplex has a very low
481condition number.
482\end{example}
483
484\begin{example}
485(\emph{A degenerate simplex})
486In this example, we show that a flat simplex is associated
487with a high condition number.
488Consider a flat simplex, defined by its vertices:
489\begin{eqnarray}
490\bv_1=(0,0)^T, \qquad \bv_2=(1,0)^T, \qquad \bv_3=(1/2,\epsilon)^T,
491\end{eqnarray}
492with $\epsilon = 10^{-10}$. This simplex is presented in figure \ref{fig-simplex-flat}.
493
494\begin{figure}
495\begin{center}
496\includegraphics[width=5cm]{simplex_flat.pdf}
497\end{center}
498\caption{A "flat" simplex in 2 dimensions}
499\label{fig-simplex-flat}
500\end{figure}
501
502\lstset{language=scilabscript}
503\begin{lstlisting}
504coords = [
5050.0 0.0
5061.0 0.0
5070.5 1.e-10
508];
509si = optimsimplex_new ( coords );
510D = optimsimplex_dirmat ( si )
511k = cond(D)
512optimsimplex_destroy(si);
513\end{lstlisting}
514The previous script produces the following output.
515\lstset{language=scilabscript}
516\begin{lstlisting}
517-->D = optimsimplex_dirmat ( si )
518 D =
519 1. 0.5
520 0. 1.000D-10
521-->k = cond(D)
522 k =
523 1.250D+10
524\end{lstlisting}
525We see that a flat simplex is associated with a high
526condition number. Indeed, a low condition number of the matrix of
527directions is an indication of the non-degeneracy of the simplex.
528\end{example}
529
530There is a close relationship between the oriented length
531$\sigma_+(S)$ and the $l^2$ norm of the matrix of directions
532$D(S)$ as prooved in the following proposition.
533
534\begin{proposition}
535\label{prop-simplex-inequalitysigmaplus}
536Let $S$ be a simplex and consider the euclidian norm $\|.\|$.
537Therefore,
538\begin{eqnarray}
539\label{eq-simplex-inequalitysigmaplus}
540\|\bd_i\| \leq \sigma_+(S) \leq \|D\|,
541\end{eqnarray}
542for all $i=1,\ldots,n$.
543\end{proposition}
544
545\begin{proof}
546It is easy to prove that
547\begin{eqnarray}
548\|\bd_i\| \leq \sigma_+(S).
549\end{eqnarray}
550Indeed, the definition of the oriented length $\sigma_+(S)$
551in the case where there are $n+1$ vertices is
552\begin{eqnarray}
553\label{eq-simplex-sigma-np1}
554\sigma_+(S) &=& \max_{i=2,n+1} \|\bv_i - \bv_1\|_2 \\
555& = & \max_{i=1,n} \|\bd_i\|_2,
556\end{eqnarray}
557which concludes the first part of the proof.
558
559We shall now proove that
560\begin{eqnarray}
561\sigma_+(S) \leq \|D\|.
562\end{eqnarray}
563The euclidian norm is so that (\cite{citeulike:2122238}, section 2.3.1, "Definitions"),
564\begin{eqnarray}
565\|D \bx\| \leq \|D\| \|\bx\|,
566\end{eqnarray}
567for any vector $\bx\in\RR^n$. We choose the specific
568vector $\bx$ which has zeros components, except for the $i$-th row,
569which is equal to 1, i.e. $\bx=(0,\ldots,0,1,0,\ldots,0)^T$.
570With this particular choice of $\bx$ we have the properties $D\bx = \bd_i$
571and $\|\bx\| = 1$, so that the previous inequality becomes
572\begin{eqnarray}
573\label{eq-simplex-normmatrixD1}
574\|\bd_i\| \leq \|D\|,
575\end{eqnarray}
576for all $i=1,\ldots,n$.
577We can now take the maximum of the left hand-size of \ref{eq-simplex-normmatrixD1}
578and get the oriented length $\sigma_+(S)$, which
579concludes the proof.
580\end{proof}
581
582\begin{example}
583In the following Scilab session, we define a new simplex
584by its coordinates, so that the matrix of directions
585is not symetric and that the edges do not have unit
586lengths.
587\lstset{language=scilabscript}
588\begin{lstlisting}
589coords = [
5900.0 0.0
5911.0 0.5
5921.0 2.0
593];
594si = optimsimplex_new ( coords );
595D = optimsimplex_dirmat ( si )
596for i=1:2
597 nd = norm(D(1:2,i),2);
598 mprintf( "||d_%d||=%f\n",i,nd)
599end
600ss = optimsimplex_size ( si , "sigmaplus" );
601mprintf( "sigma_+(S)=%f\n",ss);
602normmatrix = norm(D);
603mprintf( "||D||=%f\n",normmatrix);
604optimsimplex_destroy(si);
605\end{lstlisting}
606The previous script produces the following output.
607\lstset{language=scilabscript}
608\begin{lstlisting}
609||d_1||=1.118034
610||d_2||=2.236068
611sigma_+(S)=2.236068
612||D||=2.422078
613\end{lstlisting}
614This result is consistent with the inequality \ref{eq-simplex-inequalitysigmaplus}.
615\end{example}
616
617\subsection{Taylor's formula}
618\label{simplex-Taylor-integral-lipshitz}
619
620The simplex gradient proposition that we shall proove in the
621next section assumes that the gradient $\bg$ of the function $f$ satisfies
622a Lipshitz condition. The following proposition presents
623a result satisfied by such functions.
624In order to simplify the notations, we denote by $\|.\|$ the
625euclidian norm.
626
627\begin{proposition}
628\label{simplex-prop-taylor-lipshitz}
629Assume that $f:\RR^n\rightarrow \RR$ is differentiable and assume that its gradient $\bg$
630is defined and continuous.
631Let $\bx\in\RR^n$ be a given point and $\bp\in\RR^n$ a vector.
632Assume that the gradient $\bg$ is Lipshitz continuous in a
633neighbourhood of $\bx$ and $\bx+\bp$ with Lipshitz constant
634$L$. Then
635\begin{eqnarray}
636|f(\bx+\bp) - f(\bx) - \bp^T \bg(\bx) |
637&\leq& \frac{1}{2} L \|\bp\|^2.
638\end{eqnarray}
639\end{proposition}
640
641\begin{proof}
642We can write Taylor's expansion of $f$ in a neighbourhood of $\bx$
643\begin{eqnarray}
644\label{simplex-taylor-gradient}
645f(\bx+\bp) &= & f(\bx) + \int_0^1 \bp^T \bg (\bx+t\bp) dt.
646\end{eqnarray}
647By definition of the Lipshitz condition on $\bg$, we have
648\begin{eqnarray}
649\| \bg(\bx) - \bg(\by) \| \leq L \|\bx - \by\|,
650\end{eqnarray}
651for $\bx$ and $\by$ in that neighbourhood.
652Assume that $t\in[0,1]$ and use the particular point $\by = \bx+t\bp$.
653We get
654\begin{eqnarray}
655\label{simplex-lipshitz-gradient}
656\| \bg(\bx+t\bp) - \bg(\bx) \| \leq t L \|\bp\|.
657\end{eqnarray}
658We now use equality \ref{simplex-taylor-gradient}, substract the
659term $\bp^T \bg(\bx)$ and get
660\begin{eqnarray}
661f(\bx+\bp) - f(\bx) - \bp^T \bg(\bx) = \int_0^1 \bp^T \left( \bg (\bx+t\bp) - \bg(\bx) \right) dt.
662\end{eqnarray}
663Therefore,
664\begin{eqnarray}
665\left|f(\bx+\bp) - f(\bx) - \bp^T \bg(\bx) \right|
666&=& \left|\int_0^1 \bp^T \left( \bg (\bx+t\bp) - \bg(\bx) \right) dt \right|\\
667&\leq & \int_0^1 \|\bp\| \left\| \bg (\bx+t\bp) - \bg(\bx) \right\| dt
668\end{eqnarray}
669We plug \ref{simplex-lipshitz-gradient} into the previous equality and get
670\begin{eqnarray}
671\left|f(\bx+\bp) - f(\bx) - \bp^T \bg(\bx) \right|
672&\leq & \int_0^1 L t \|\bp\|^2 dt \\
673&\leq& \frac{1}{2} L \|\bp\|^2,
674\end{eqnarray}
675which concludes the proof.
676\end{proof}
677
678\subsection{Forward difference simplex gradient}
679\label{simplex-section-forwardgradient}
680
681Finite difference formulas are a common tool to compute
682the numerical derivative of a function. In this section, we
683introduce the simplex gradient, which allows to compute
684an approximation of the gradient of the cost function.
685As we are going to see, this approximation is more accurate
686when the simplex has a low condition number.
687
688We denote by $\delta(S)$ the vector of objective function
689differences
690\begin{eqnarray}
691\delta(S) = ( f(\bv_2) - f(\bv_1), f(\bv_3) - f(\bv_1), \ldots, f(\bv_{n+1}) - f(\bv_1))^T.
692\end{eqnarray}
693As with classical finite difference formulas, the vector of
694function can be used to compute the simplex gradient.
695\begin{definition}
696(\emph{Simplex gradient})
697Let $S$ be a non singular simplex. The \emph{simplex gradient} $\overline{\bg}(S)$ is
698the unique solution of the linear system of equations
699\begin{eqnarray}
700\label{simplex-gradient}
701D(S)^T \overline{\bg}(S) = \delta(S).
702\end{eqnarray}
703\end{definition}
704
705By hypothesis, the simplex $S$ is nonsingular so that the
706linear system of equations has a unique solution, which is
707equal to
708\begin{eqnarray}
709\overline{\bg}(S) = (D(S)^T)^{-1} \delta(S).
710\end{eqnarray}
711By hypothesis, the matrix $D(S)$ is non singular, therefore the transpose of the
712inverse is equal to the inverse of the
713transpose (\cite{citeulike:2122238}, section 2.1.3, "Matrix Inverse"),
714i.e. $(D(S)^T)^{-1} = (D(S)^{-1})^T$.
715We denote by $D(S)^{-T}$ the inverse of the transpose so that the previous
716equality becomes
717\begin{eqnarray}
718\overline{\bg}(S) = D(S)^{-T} \delta(S).
719\end{eqnarray}
720In practice, the matrix of simplex direction is not inverted
721and the solution of \ref{simplex-gradient} is computed directly,
722using classical linear algebra libraries, like Lapack for example.
723
724The simplex gradient is an approximation of the
725gradient $\bg$ of the function $f$, as presented in the following
726proposition.
347 727
348%TODO... 728\begin{proposition}
729Let $S$ be a simplex. Let the gradient $\bg$ be Lipshitz continuous in a neighbourhood
730of $S$ with Lipshitz constant $L$. Consider the euclidian norm $\|.\|$. Then, there is $K>0$,
731depending only on $L$ such that
732\begin{eqnarray}
733\label{eq-inequality-simplexgradient}
734\| \bg(\bv_1) - \overline{\bg}(S) \|_2 \leq K \kappa(S) \sigma_+(S).
735\end{eqnarray}
736\end{proposition}
737
738\begin{proof}
739We can write the difference between the simplex
740gradient and the gradient in the following form
741\begin{eqnarray}
742\overline{\bg}(S) - \bg(\bv_1) = D(S)^{-T} \left( D(S)^T \overline{\bg}(S) - D(S)^T \bg(\bv_1) \right).
743\end{eqnarray}
744We now plug the simplex gradient definition \ref{simplex-gradient}
745into the previous equality and get
746\begin{eqnarray}
747\label{eq-simplex-gradient1}
748\overline{\bg}(S) - \bg(\bv_1) = D(S)^{-T} \left( \delta(S) - D(S)^T \bg(\bv_1) \right).
749\end{eqnarray}
750
751The fact that the euclidian norm $\|.\|$ satisfies the
752inequality
753\begin{eqnarray}
754\| A B \| \leq \|A\|\|B\|,
755\end{eqnarray}
756for any matrices $A$ and $B$ with suitable number of rows
757and columns (\cite{citeulike:2122238}, section 2.3, "Matrix Norms")
758plays an important role in the results that we are going to derive.
759Indeed, we can compute the euclidian norm of both sides
760of equation \ref{eq-simplex-gradient1} and get
761\begin{eqnarray}
762\left\| \overline{\bg}(S) - \bg(\bv_1) \right\|
763&=& \left\| D(S)^{-T} \left( \delta(S) - D(S)^T \bg(\bv_1) \right) \right\|.
764\end{eqnarray}
765Therefore,
766\begin{eqnarray}
767\label{eq-simplex-gradient2}
768\left\| \overline{\bg}(S) - \bg(\bv_1) \right\|
769&\leq& \left\| D(S)^{-T} \right\| \left\| \delta(S) - D(S)^T \bg(\bv_1) \right\|.
770\end{eqnarray}
771The suite of the proof is based on the computation of the right-hand side
772of equation \ref{eq-simplex-gradient2}, that is, the computation of the norm
773of the vector $\delta(S) - D(S)^T \bg(\bv_1)$.
774
775By hypothesis, the gradient $\bg$ is Lipshitz continuous in
776a neighbourhood of $S$. By proposition \ref{simplex-prop-taylor-lipshitz},
777we have
778\begin{eqnarray}
779\left| f(\bv_1 + \bd_i) - f(\bv_1) - \bd_i^T \bg(\bv_1) \right| \leq \frac{1}{2} L \|\bd_i\|^2,
780\end{eqnarray}
781for $i=1,n$.
782By definition of the direction $\bd_i$, we have $\bv_1 + \bd_i = \bv_i$ for
783$i = 1,n$. By proposition \ref{prop-simplex-inequalitysigmaplus},
784we have $\|\bd_j\| \leq \sigma_+(S)$ for all $j=1,n$.
785Hence,
786\begin{eqnarray}
787\label{simplex-eq-taylor-lipshitz1}
788\left| f(\bv_i) - f(\bv_1) - \bd_i^T \bg(\bv_1) \right| \leq \frac{1}{2} L \sigma_+(S)^2,
789\end{eqnarray}
790We can use this to compute the euclidian norm of the
791vector $\delta(S) - D^T \bg(\bv_1)$. Using ineguality \ref{simplex-eq-taylor-lipshitz1},
792the square of the norm of this vector is
793\begin{eqnarray}
794\left\| \delta(S) - D^T \bg(\bv_1) \right\|^2
795& = & \sum_{i=1,n} \left( f(\bv_i) - f(\bv_1) - \bd_i^T \bg(\bv_1)\right)^2 \\
796&\leq & \sum_{i=1,n} \left( \frac{1}{2} L \sigma_+(S)^2 \right)^2\\
797&\leq & n \left( \frac{1}{2} L \sigma_+(S)^2 \right)^2
798\end{eqnarray}
799which finally implies
800\begin{eqnarray}
801\left\| \delta(S) - D^T \bg(\bv_1) \right\|^2
802\leq \frac{1}{2} \sqrt{n} L \sigma_+(S)^2.
803\end{eqnarray}
804Let us define the constant $K = \frac{1}{2} \sqrt{n} L$.
805The previous inequality becomes
806\begin{eqnarray}
807\left\| \delta(S) - D^T \bg(\bv_1) \right\|^2
808\leq K \sigma_+(S)^2.
809\end{eqnarray}
810We can now plug the previous equality into inequality \ref{eq-simplex-gradient2}
811and get
812\begin{eqnarray}
813\left\| \overline{\bg}(S) - \bg(\bv_1) \right\|
814&\leq& K \left\| D(S)^{-T} \right\| \sigma_+(S)^2.
815\end{eqnarray}
816By proposition \ref{prop-simplex-inequalitysigmaplus},
817we have $\sigma_+(S) \leq \|D\|$, so that the previous inequality
818is transformed into
819\begin{eqnarray}
820\left\| \overline{\bg}(S) - \bg(\bv_1) \right\|
821&\leq& K \left\| D(S)^{-T} \right\| \left\| D(S) \right\| \sigma_+(S).
822\end{eqnarray}
823The $l^2$ norm of the matrix $D(S)$ is the largest eigenvalue
824of the matrix $D(S)^T D(S)$,
825so that the norm is not affected by transposition, which implies that
826$\left\| D(S)^{-T} \right\| = \left\| D(S)^{-1} \right\|$.
827The condition number of the matrix of direction $\kappa(S)$
828is equal to $\left\| D(S)^{-1} \right\| \left\| D(S) \right\|$
829(\cite{citeulike:2122238}, section 2.7.2, "Condition"),
830which concludes the proof.
831\end{proof}
832
833\begin{example}
834(\emph{Simplex gradient with a non-degenerate simplex})
835In the following Scilab session, we define the
836function $f(\bx)=x_1^2 + x_2^2$, where $\bx\in\RR^2$.
837The exact gradient of this function is $\bg=(x_1,x_2)^T$.
838We create an axis-by-axis simplex based on the relatively
839small length $\ell=10^{-3}$. This simplex defines
840a rectangular triangle, similar to the one presented in
841figure \ref{fig-nm-simplex-axes}, but with smaller
842edges.
843
844\lstset{language=scilabscript}
845\begin{lstlisting}
846function y = myfunction ( x )
847 y = x(1)^2 + x(2)^2
848endfunction
849x0 = [1.0 1.0];
850len = 1.e-3;
851si = optimsimplex_new ( "axes" , x0 , myfunction , len );
852sg = optimsimplex_gradientfv ( si );
853mprintf ( "Simplex Gradient=(%f %f)^T\n",sg(1),sg(2));
854eg = [2 * x0(1) 2 * x0(2)].';
855mprintf ( "Exact Gradient=(%f %f)^T\n",eg(1),eg(2));
856err = norm(sg-eg)/norm(eg);
857mprintf ( "Relative Error = %e\n",err);
858err = norm(sg-eg);
859mprintf ( "Absolute Error = %e\n",err);
860D = optimsimplex_dirmat ( si );
861k = cond(D);
862mprintf ( "k(D)=%f\n",k);
863ss = optimsimplex_size ( si );
864mprintf ( "sigma_+(D)=%e\n",ss);
865optimsimplex_destroy(si);
866\end{lstlisting}
867
868The previous script produces the following output.
869\lstset{language=scilabscript}
870\begin{lstlisting}
871Simplex Gradient=(2.001000 2.001000)^T
872Exact Gradient=(2.000000 2.000000)^T
873Absolute Error = 1.414214e-003
874k(D)=1.000000
875sigma_+(D)=1.000000e-003
876\end{lstlisting}
877We check that the inequality \ref{eq-inequality-simplexgradient}
878gives an accurate measure of the approximation. Indeed, since the
879Lipshitz constant for the gradient $\bg$ is $L=2$,
880we have the constant $K=\sqrt{2}$.
881\end{example}
882
883\begin{example}
884(\emph{Simplex gradient with a simplex close to degenerate})
885We consider what happens when an axis-by-axis simplex is transformed into
886a degenerate simplex. This situation is presented in figure \ref{fig-simplex-towardflat},
887where the third vertex moves on a circle with radius $0.5.10^{-3}$
888toward the center of an edge. Therefore the simplex degenerates
889and its condition number increases dramatically.
890
891\begin{figure}
892\begin{center}
893\includegraphics[width=7cm]{simplex_towardflat.pdf}
894\end{center}
895\caption{An axis-by-axis simplex which degenerates into a "flat" simplex in 2 dimensions.}
896\label{fig-simplex-towardflat}
897\end{figure}
898
899In the following Scilab script, we create a simplex
900as presented in figure \ref{fig-simplex-towardflat}.
901We use decreasing values of the angle $\theta$ between the
902two directions, starting from $\theta=90$~(\degre) and going
903down to $\theta=0.001$~(\degre).
904Then we compute the gradient and the absolute error,
905as well as the condition number and the size of the simplex.
906
907\lstset{language=scilabscript}
908\begin{lstlisting}
909R = 0.5e-3
910coords = [
911 1.0 1.0
912 1.0+1.e-3 1.0
913];
914for theta = [90.0 10.0 1.0 0.1 0.01 0.001]
915 C(1,1) = 1.0 + R * cos(theta*%pi/180);
916 C(1,2) = 1.0 + R * sin(theta*%pi/180);
917 coords(3,1:2) = C;
918 si = optimsimplex_new ( coords , myfunction );
919 sg = optimsimplex_gradientfv ( si );
920 eg = [2 * x0(1) 2 * x0(2)].';
921 err = norm(sg-eg);
922 D = optimsimplex_dirmat ( si );
923 k = cond(D);
924 ss = optimsimplex_size ( si );
925 mprintf ( "%f %e %e %e\n",theta , ss , err , k);
926 optimsimplex_destroy(si);
927end
928\end{lstlisting}
929
930The results are presented in table \ref{fig-simplex-towardflat-table}.
931
932\begin{figure}
933\begin{center}
934\begin{tabular}{|l|l|l|l|}
935\hline
936$\theta$ (\degre) & $\sigma_+(S)$ & $\left\| \overline{\bg}(S) - \bg(\bv_1) \right\|$ & $\kappa(S)$ \\
937\hline
93890.000000 & 1.000000e-003 & 1.118034e-003 & 2.000000e+000 \\
93910.000000 & 1.000000e-003 & 2.965584e-003 & 1.432713e+001 \\
9401.000000 & 1.000000e-003 & 2.865807e-002 & 1.432397e+002 \\
9410.100000 & 1.000000e-003 & 2.864799e-001 & 1.432395e+003 \\
9420.010000 & 1.000000e-003 & 2.864789e+000 & 1.432394e+004 \\
9430.001000 & 1.000000e-003 & 2.864789e+001 & 1.432394e+005 \\
944\hline
945\end{tabular}
946\end{center}
947\label{fig-simplex-towardflat-table}
948\end{figure}
949We see that while the oriented length $\sigma_+(S)$ is constant,
950the simplex gradient is more and more inaccurate as the
951condition number $\kappa(S)$ is increasing.
952\end{example}
349 953
350\section{References and notes} 954\section{References and notes}
351 955
352Some elements of the section \ref{section-simplexsize} is taken from 956The section \ref{simplex-section-forwardgradient} and some
353Kelley's book \cite{Kelley1999}, "Iterative Methods for Optimization". 957elements of the section \ref{section-simplexsize}
354While this document focus on Nelder-Mead algorithm, Kelley gives a broad 958are taken from Kelley's book \cite{Kelley1999}, "Iterative Methods for Optimization".
959While this book focus on Nelder-Mead algorithm, Kelley gives a broad
355view on optimization and present other algorithms for noisy functions, 960view on optimization and present other algorithms for noisy functions,
356like implicit filtering, multidirectional search and the Hooke-Jeeves algorithm. \ No newline at end of file 961like implicit filtering, multidirectional search and the Hooke-Jeeves algorithm.
962
963The section \ref{simplex-Taylor-integral-lipshitz}, which
964present Taylor's formula with a Lisphitz continous gradient is based
965on \cite{numericaloptimization}, "Elements of Analysis, Geometry, Topology",
966section "Mean Value Theorem".
967
968
diff --git a/scilab_doc/neldermead/simplex_flat.pdf b/scilab_doc/neldermead/simplex_flat.pdf
new file mode 100644
index 0000000..a37da3b
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_flat.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/simplex_flat.svg b/scilab_doc/neldermead/simplex_flat.svg
new file mode 100644
index 0000000..923a35e
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_flat.svg
@@ -0,0 +1,231 @@
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!-- Created with Inkscape (http://www.inkscape.org/) -->
3<svg
4 xmlns:dc="http://purl.org/dc/elements/1.1/"
5 xmlns:cc="http://creativecommons.org/ns#"
6 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
7 xmlns:svg="http://www.w3.org/2000/svg"
8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="433.79269"
12 height="387.96326"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.46"
16 sodipodi:docname="simplex_flat.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="D:\Baudin\ProjetScilab\git\scilab\scilab_doc\neldermead\simplex_initialfixed.png"
19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90"
21 version="1.0">
22 <defs
23 id="defs4">
24 <marker
25 inkscape:stockid="Arrow1Lend"
26 orient="auto"
27 refY="0"
28 refX="0"
29 id="Arrow1Lend"
30 style="overflow:visible">
31 <path
32 id="path3318"
33 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
34 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
35 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
36 </marker>
37 <inkscape:perspective
38 sodipodi:type="inkscape:persp3d"
39 inkscape:vp_x="0 : 526.18109 : 1"
40 inkscape:vp_y="0 : 1000 : 0"
41 inkscape:vp_z="744.09448 : 526.18109 : 1"
42 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
43 id="perspective10" />
44 </defs>
45 <sodipodi:namedview
46 id="base"
47 pagecolor="#ffffff"
48 bordercolor="#666666"
49 borderopacity="1.0"
50 inkscape:pageopacity="0.0"
51 inkscape:pageshadow="2"
52 inkscape:zoom="1.4"
53 inkscape:cx="405.0825"
54 inkscape:cy="122.64559"
55 inkscape:document-units="px"
56 inkscape:current-layer="layer1"
57 showgrid="true"
58 inkscape:window-width="1280"
59 inkscape:window-height="975"
60 inkscape:window-x="1794"
61 inkscape:window-y="39">
62 <inkscape:grid
63 type="xygrid"
64 id="grid2474"
65 visible="true"
66 enabled="true" />
67 </sodipodi:namedview>
68 <metadata
69 id="metadata7">
70 <rdf:RDF>
71 <cc:Work
72 rdf:about="">
73 <dc:format>image/svg+xml</dc:format>
74 <dc:type
75 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
76 </cc:Work>
77 </rdf:RDF>
78 </metadata>
79 <g
80 inkscape:label="Calque 1"
81 inkscape:groupmode="layer"
82 id="layer1"
83 transform="translate(-252.76102,-130.72577)">
84 <text
85 xml:space="preserve"
86 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
87 x="197.9899"
88 y="425.05746"
89 id="text3303"><tspan
90 sodipodi:role="line"
91 id="tspan3305"
92 x="197.9899"
93 y="425.05746"
94 style="font-style:italic;font-weight:normal" /></text>
95 <text
96 xml:space="preserve"
97 style="font-size:40px;font-style:normal;font-weight:bold;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
98 x="189.90868"
99 y="417.98639"
100 id="text3315"><tspan
101 sodipodi:role="line"
102 id="tspan3317"
103 x="189.90868"
104 y="417.98639" /></text>
105 <path
106 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2.5;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
107 d="M 450.14192,398.17752 L 303.35218,471.7743 L 585.74465,471.89028 L 450.14192,398.17752 z"
108 id="path2423"
109 sodipodi:nodetypes="cccc" />
110 <path
111 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
112 d="M 279.54576,471.93831 L 647.89619,471.93831"
113 id="path2441"
114 sodipodi:nodetypes="cc" />
115 <path
116 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
117 d="M 304.15998,492.55612 L 304.15998,152.30983"
118 id="path3734"
119 sodipodi:nodetypes="cc" />
120 <text
121 xml:space="preserve"
122 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
123 x="263.65784"
124 y="518.20074"
125 id="text2456"><tspan
126 sodipodi:role="line"
127 id="tspan2458"
128 x="263.65784"
129 y="518.20074"
130 style="font-weight:bold">0</tspan></text>
131 <path
132 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
133 d="M 587.13773,462.46684 L 587.13773,482.87505"
134 id="path2468"
135 sodipodi:nodetypes="cc" />
136 <text
137 xml:space="preserve"
138 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
139 x="575.26447"
140 y="518.68903"
141 id="text2470"><tspan
142 sodipodi:role="line"
143 id="tspan2472"
144 x="575.26447"
145 y="518.68903">1</tspan></text>
146 <path
147 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
148 d="M 316.39973,398.27829 L 292.15608,398.27829"
149 id="path2480"
150 sodipodi:nodetypes="cc" />
151 <text
152 xml:space="preserve"
153 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
154 x="267.05627"
155 y="409.90775"
156 id="text2484"><tspan
157 sodipodi:role="line"
158 id="tspan2486"
159 x="267.05627"
160 y="409.90775">őĶ</tspan></text>
161 <text
162 xml:space="preserve"
163 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
164 x="655.77972"
165 y="518.68903"
166 id="text3844"><tspan
167 sodipodi:role="line"
168 x="655.77972"
169 y="518.68903"
170 id="tspan3848">x</tspan></text>
171 <text
172 xml:space="preserve"
173 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
174 x="263.70776"
175 y="165.36499"
176 id="text2523"><tspan
177 sodipodi:role="line"
178 id="tspan2525"
179 x="263.70776"
180 y="165.36499" /></text>
181 <g
182 id="g2583"
183 transform="translate(7.8789978,0)">
184 <text
185 id="text2519"
186 y="151.46796"
187 x="244.58905"
188 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
189 xml:space="preserve"><tspan
190 id="tspan2521"
191 y="151.46796"
192 x="244.58905"
193 sodipodi:role="line">x</tspan></text>
194 <text
195 id="text2560"
196 y="157.46684"
197 x="267.04935"
198 style="font-size:18px;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"
199 xml:space="preserve"><tspan
200 y="157.46684"
201 x="267.04935"
202 id="tspan2562"
203 sodipodi:role="line">2</tspan></text>
204 </g>
205 <text
206 xml:space="preserve"
207 style="font-size:18px;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"
208 x="677.49219"
209 y="518.68903"
210 id="text2564"><tspan
211 sodipodi:role="line"
212 id="tspan2566"
213 x="677.49219"
214 y="518.68903">1</tspan></text>
215 <path
216 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
217 d="M 447.84934,462.46684 L 447.84934,483.16009"
218 id="path2414"
219 sodipodi:nodetypes="cc" />
220 <text
221 xml:space="preserve"
222 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
223 x="421.43472"
224 y="518.20074"
225 id="text2416"><tspan
226 sodipodi:role="line"
227 id="tspan2418"
228 x="421.43472"
229 y="518.20074">0.5</tspan></text>
230 </g>
231</svg>
diff --git a/scilab_doc/neldermead/simplex_towardflat.pdf b/scilab_doc/neldermead/simplex_towardflat.pdf
new file mode 100644
index 0000000..bbc83b7
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_towardflat.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/simplex_towardflat.svg b/scilab_doc/neldermead/simplex_towardflat.svg
new file mode 100644
index 0000000..6537528
--- /dev/null
+++ b/scilab_doc/neldermead/simplex_towardflat.svg
@@ -0,0 +1,281 @@
1<?xml version="1.0" encoding="UTF-8" standalone="no"?>
2<!-- Created with Inkscape (http://www.inkscape.org/) -->
3<svg
4 xmlns:dc="http://purl.org/dc/elements/1.1/"
5 xmlns:cc="http://creativecommons.org/ns#"
6 xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
7 xmlns:svg="http://www.w3.org/2000/svg"
8 xmlns="http://www.w3.org/2000/svg"
9 xmlns:sodipodi="http://sodipodi.sourceforge.net/DTD/sodipodi-0.dtd"
10 xmlns:inkscape="http://www.inkscape.org/namespaces/inkscape"
11 width="670.23901"
12 height="394.02417"
13 id="svg2"
14 sodipodi:version="0.32"
15 inkscape:version="0.46"
16 sodipodi:docname="simplex_towardflat.svg"
17 inkscape:output_extension="org.inkscape.output.svg.inkscape"
18 inkscape:export-filename="D:\Baudin\ProjetScilab\git\scilab\scilab_doc\neldermead\simplex_initialfixed.png"
19 inkscape:export-xdpi="90"
20 inkscape:export-ydpi="90"
21 version="1.0">
22 <defs
23 id="defs4">
24 <marker
25 inkscape:stockid="Arrow1Lend"
26 orient="auto"
27 refY="0"
28 refX="0"
29 id="Arrow1Lend"
30 style="overflow:visible">
31 <path
32 id="path3318"
33 d="M 0,0 L 5,-5 L -12.5,0 L 5,5 L 0,0 z"
34 style="fill-rule:evenodd;stroke:#000000;stroke-width:1pt;marker-start:none"
35 transform="matrix(-0.8,0,0,-0.8,-10,0)" />
36 </marker>
37 <inkscape:perspective
38 sodipodi:type="inkscape:persp3d"
39 inkscape:vp_x="0 : 526.18109 : 1"
40 inkscape:vp_y="0 : 1000 : 0"
41 inkscape:vp_z="744.09448 : 526.18109 : 1"
42 inkscape:persp3d-origin="372.04724 : 350.78739 : 1"
43 id="perspective10" />
44 </defs>
45 <sodipodi:namedview
46 id="base"
47 pagecolor="#ffffff"
48 bordercolor="#666666"
49 borderopacity="1.0"
50 inkscape:pageopacity="0.0"
51 inkscape:pageshadow="2"
52 inkscape:zoom="0.49497475"
53 inkscape:cx="111.62031"
54 inkscape:cy="100.19422"
55 inkscape:document-units="px"
56 inkscape:current-layer="layer1"
57 showgrid="true"
58 inkscape:window-width="1280"
59 inkscape:window-height="894"
60 inkscape:window-x="1794"
61 inkscape:window-y="120">
62 <inkscape:grid
63 type="xygrid"
64 id="grid2474"
65 visible="true"
66 enabled="true" />
67 </sodipodi:namedview>
68 <metadata
69 id="metadata7">
70 <rdf:RDF>
71 <cc:Work
72 rdf:about="">
73 <dc:format>image/svg+xml</dc:format>
74 <dc:type
75 rdf:resource="http://purl.org/dc/dcmitype/StillImage" />
76 </cc:Work>
77 </rdf:RDF>
78 </metadata>
79 <g
80 inkscape:label="Calque 1"
81 inkscape:groupmode="layer"
82 id="layer1"
83 transform="translate(-128.78833,-130.72577)">
84 <text
85 xml:space="preserve"
86 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
87 x="197.9899"
88 y="425.05746"
89 id="text3303"><tspan
90 sodipodi:role="line"
91 id="tspan3305"
92 x="197.9899"
93 y="425.05746"
94 style="font-style:italic;font-weight:normal" /></text>
95 <text
96 xml:space="preserve"
97 style="font-size:40px;font-style:normal;font-weight:bold;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
98 x="189.90868"
99 y="417.98639"
100 id="text3315"><tspan
101 sodipodi:role="line"
102 id="tspan3317"
103 x="189.90868"
104 y="417.98639" /></text>
105 <path
106 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
107 d="M 279.54576,471.93831 L 790.76204,471.93831"
108 id="path2441"
109 sodipodi:nodetypes="cc" />
110 <path
111 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1.25;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
112 d="M 304.15998,492.55612 L 304.15998,152.30983"
113 id="path3734"
114 sodipodi:nodetypes="cc" />
115 <text
116 xml:space="preserve"
117 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
118 x="263.65784"
119 y="518.20074"
120 id="text2456"><tspan
121 sodipodi:role="line"
122 id="tspan2458"
123 x="263.65784"
124 y="518.20074"
125 style="font-weight:bold">0</tspan></text>
126 <path
127 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
128 d="M 644.01235,462.46684 L 644.01235,482.87505"
129 id="path2468"
130 sodipodi:nodetypes="cc" />
131 <text
132 xml:space="preserve"
133 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
134 x="578.78833"
135 y="518.68903"
136 id="text2470"><tspan
137 sodipodi:role="line"
138 id="tspan2472"
139 x="578.78833"
140 y="518.68903">1+1.e-3</tspan></text>
141 <path
142 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
143 d="M 316.39973,418.99258 L 292.15608,418.99258"
144 id="path2480"
145 sodipodi:nodetypes="cc" />
146 <text
147 xml:space="preserve"
148 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
149 x="267.05627"
150 y="433.47916"
151 id="text2484"><tspan
152 sodipodi:role="line"
153 id="tspan2486"
154 x="267.05627"
155 y="433.47916">1</tspan></text>
156 <text
157 xml:space="preserve"
158 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
159 x="263.70776"
160 y="165.36499"
161 id="text2523"><tspan
162 sodipodi:role="line"
163 id="tspan2525"
164 x="263.70776"
165 y="165.36499" /></text>
166 <g
167 id="g2583"
168 transform="translate(7.8789978,0)">
169 <text
170 id="text2519"
171 y="151.46796"
172 x="244.58905"
173 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
174 xml:space="preserve"><tspan
175 id="tspan2521"
176 y="151.46796"
177 x="244.58905"
178 sodipodi:role="line">x</tspan></text>
179 <text
180 id="text2560"
181 y="157.46684"
182 x="267.04935"
183 style="font-size:18px;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"
184 xml:space="preserve"><tspan
185 y="157.46684"
186 x="267.04935"
187 id="tspan2562"
188 sodipodi:role="line">2</tspan></text>
189 </g>
190 <g
191 id="g2436"
192 transform="translate(-0.4397342,0)">
193 <text
194 id="text3844"
195 y="518.68903"
196 x="770.77972"
197 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
198 xml:space="preserve"><tspan
199 id="tspan3848"
200 y="518.68903"
201 x="770.77972"
202 sodipodi:role="line">x</tspan></text>
203 <text
204 id="text2564"
205 y="524.74994"
206 x="792.76105"
207 style="font-size:18px;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"
208 xml:space="preserve"><tspan
209 y="524.74994"
210 x="792.76105"
211 id="tspan2566"
212 sodipodi:role="line">1</tspan></text>
213 </g>
214 <path
215 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
216 d="M 363.56363,462.46684 L 363.56363,483.16009"
217 id="path2414"
218 sodipodi:nodetypes="cc" />
219 <text
220 xml:space="preserve"
221 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
222 x="353.57758"
223 y="518.20074"
224 id="text2416"><tspan
225 sodipodi:role="line"
226 id="tspan2418"
227 x="353.57758"
228 y="518.20074">1</tspan></text>
229 <g
230 id="g2448"
231 transform="translate(-81.6609,78.571429)">
232 <g
233 transform="translate(140,-130)"
234 id="g2433">
235 <path
236 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1"
237 d="M 438.85183,432.31993 L 303.35218,471.7743 L 586.13765,471.89028 L 438.85183,432.31993 z"
238 id="path2423"
239 sodipodi:nodetypes="cccc" />
240 </g>
241 <path
242 sodipodi:nodetypes="cccc"
243 id="path2431"
244 d="M 444.42192,201.71371 L 444.42192,341.14371 L 725.68063,341.17851 L 444.42192,201.71371 z"
245 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:2;stroke-linecap:butt;stroke-linejoin:miter;stroke-miterlimit:4;stroke-dasharray:none;stroke-opacity:1" />
246 </g>
247 <text
248 xml:space="preserve"
249 style="font-size:40px;font-style:normal;font-weight:normal;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Vera Sans"
250 x="124.43286"
251 y="289.19156"
252 id="text2442"><tspan
253 sodipodi:role="line"
254 id="tspan2444"
255 x="124.43286"
256 y="289.19156">1+0.5e-3</tspan></text>
257 <path
258 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1"
259 d="M 316.66856,277.97474 L 292.42491,277.97474"
260 id="path2446"
261 sodipodi:nodetypes="cc" />
262 <path
263 sodipodi:type="arc"
264 style="opacity:1;fill:none;fill-opacity:1;stroke:#000000;stroke-width:0.54804182;marker-start:none;marker-end:none;stroke-miterlimit:4;stroke-dasharray:0.54804184, 1.64412552;stroke-dashoffset:0;stroke-opacity:1"
265 id="path2421"
266 sodipodi:cx="220"
267 sodipodi:cy="217.96326"
268 sodipodi:rx="77.14286"
269 sodipodi:ry="77.14286"
270 d="M 220,140.8204 A 77.14286,77.14286 0 0 1 297.1424,217.69691 L 220,217.96326 z"
271 transform="matrix(1.8246782,0,0,1.8246782,-38.939414,22.624742)"
272 sodipodi:start="4.712389"
273 sodipodi:end="6.2797327" />
274 <path
275 style="fill:none;fill-rule:evenodd;stroke:#000000;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;marker-end:url(#Arrow1Lend);stroke-miterlimit:4;stroke-dasharray:1, 4;stroke-dashoffset:0;stroke-opacity:1"
276 d="M 109.09648,148.5571 C 171.4734,150.2361 215.41504,185.68021 235.87062,226.84393"
277 id="path7073"
278 transform="translate(252.76102,130.72577)"
279 sodipodi:nodetypes="cc" />
280 </g>
281</svg>