Fixed problems in intro and simplex. Added figures for help and demos.

15 files changed, 500 insertions, 167 deletions

diff --git a/scilab_doc/neldermead/introduction-demos.png b/scilab_doc/neldermead/introduction-demos.png
new file mode 100644
index 0000000..2cd8327
--- /dev/null
+++ b/scilab_doc/neldermead/introduction-demos.png
diff --git a/scilab_doc/neldermead/introduction-help-fminsearch.png b/scilab_doc/neldermead/introduction-help-fminsearch.png
new file mode 100644
index 0000000..58fe455
--- /dev/null
+++ b/scilab_doc/neldermead/introduction-help-fminsearch.png
diff --git a/scilab_doc/neldermead/introduction-help.png b/scilab_doc/neldermead/introduction-help.png
new file mode 100644
index 0000000..2740b7b
--- /dev/null
+++ b/scilab_doc/neldermead/introduction-help.png
diff --git a/scilab_doc/neldermead/introduction.tex b/scilab_doc/neldermead/introduction.tex
index 303ef25..11b20ef 100644
--- a/scilab_doc/neldermead/introduction.tex
+++ b/scilab_doc/neldermead/introduction.tex
@@ -1,6 +1,12 @@
 \chapter{Introduction}
 
-The Nelder-Mead simplex algorithm, published in 1965, is an enormously 
+In this introductory chapter, we make an overview of simplex-based algorithms.
+We present the main features of the \scifunction{neldermead} component, and 
+show how to use the component with a simple example.
+
+\section{Overview}
+
+The Nelder-Mead simplex algorithm \cite{citeulike:3009487}, published in 1965, is an enormously 
 popular search method for multidimensional unconstrained optimization. 
 The Nelder-Mead algorithm should not be confused with the (probably) 
 more famous simplex algorithm of Dantzig for linear programming. The 
@@ -8,7 +14,7 @@ Nelder-Mead algorithm is especially popular in the fields of chemistry,
 chemical engineering, and medicine. Two measures of the ubiquity of the 
 Nelder-Mead algorithm are that it appears in the best-selling handbook 
 Numerical Recipes and in Matlab. In \cite{Torczon89multi-directionalsearch},
-Virginia Torczon writes : "Margaret Wright has stated that over
+Virginia Torczon writes: "Margaret Wright has stated that over
 fifty percent of the calls received by the support group for the NAG
 software library concerned the version of the Nelder-Mead 
 simplex algorithm to be found in that library". No derivative of the cost function is 
@@ -23,13 +29,18 @@ function values. The algorithm attemps to replace the worst vertex with
 a new point, which depends on the worst point and the centre of the best 
 vertices. 
 
-The goal of this toolbox is to provide a Nelder-Mead direct search optimization method to solve the 
+The goal of this toolbox is to provide a Nelder-Mead (1965) direct search optimization method to solve the 
 following unconstrained optimization problem
 \begin{eqnarray}
 \min f(x)
 \end{eqnarray}
-where $x\in \RR^n$ where $n$ is the number of optimization parameters.
-The Box complex algorithm, which is an extension of Nelder-Mead's algorithm, solves the 
+where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 
+function $f:\RR^n\rightarrow \RR$.
+In order to solve the unconstrained optimization problem, the Nelder-Mead 
+algorithm uses a variable shape simplex. The toolbox also provide Spendley's et al. 
+algorithm \cite{Spendley1962} (1962), which uses a fixed shape simplex. Historically, the algorithm created  
+by Nelder and Mead was designed as an improvement on Spendley's et al. algorithm.
+The Box complex algorithm \cite{Box1965} (1965), which is an extension of Spendley's  et al. algorithm, solves the 
 following constrained problem
 \begin{eqnarray}
 &&\min f(x)\\
@@ -46,52 +57,308 @@ The Nelder-Mead algorithm may be used in the following optimization context :
 \item there are bounds and/or non linear constraints.
 \end{itemize}
 
-The internal design of the system is based on the following components :
+The internal design of the system is based on the following components.
 \begin{itemize}
-\item "neldermead" provides various Nelder-Mead variants and manages for Nelder-Mead specific settings, such as the method to compute the initial simplex, the specific termination criteria,
-\item "fminsearch" provides a Scilab commands which aims at behaving as Matlab's fminsearch. Specific terminations criteria, initial simplex and auxiliary settings are automatically configured so that the behaviour of Matlab's fminsearch is exactly reproduced.
-\item "optimset", "optimget" provides Scilab commands to emulate their Matlab counterparts.
-\item "nmplot" provides a high-level component which provides directly output pictures for Nelder-Mead algorithm.
+\item The "neldermead" component provides various simplex-based 
+algorithms and manages for Nelder-Mead specific settings, such as the 
+method to compute the initial simplex and the specific termination 
+criteria.
+\item The "fminsearch" component provides a Scilab commands which aims 
+at behaving as Matlab's fminsearch. Specific terminations criteria, 
+initial simplex and auxiliary settings are automatically configured so 
+that the behaviour of Matlab's fminsearch is exactly reproduced.
+\item The "optimset" and "optimget" components provide Scilab commands 
+to emulate their Matlab counterparts.
+\item The "nmplot" component provides features to 
+produce directly output pictures for Nelder-Mead algorithm.
 \end{itemize}
-The current toolbox is based on (and therefore requires) the following toolboxes 
+The current toolbox is based on (and therefore requires) the following components.
 \begin{itemize}
-\item "optimbase" provides an abstract class for a general optimization component, including the number of variables, the minimum and maximum bounds, the number of non linear inequality constraints, the loggin system, various termination criteria, the cost function, etc...
-\item "optimsimplex" provides a class to manage a simplex made of an arbitrary number of vertices, including the computation of a simplex by various methods (axes, regular, Pfeffer's, randomized bounds), the computation of the size by various methods (diameter, sigma +, sigma-, etc...),
+\item The "optimbase" component provides an abstract class for a general optimization 
+component, including the number of variables, the minimum and maximum 
+bounds, the number of non linear inequality constraints, the logging 
+system, various termination criteria, the cost function, etc...
+\item The "optimsimplex" component provides a class to manage a simplex made of an 
+arbitrary number of vertices, including the computation of a simplex by 
+various methods (axes, regular, Pfeffer's, randomized bounds), the 
+computation of the size by various methods (diameter, sigma +, sigma-, 
+etc...) and many algorithms to perform reflections and shrinkages.
 \end{itemize}
 
-The following is a list of features the Nelder-Mead prototype algorithm currently provides :
+The following is a list of features the Nelder-Mead algorithm currently provides :
 \begin{itemize}
-\item Manage various simplex initializations
+\item manage various simplex initializations
   \begin{itemize}
   \item initial simplex given by user,
   \item initial simplex computed with a length and along the coordinate axes,
   \item initial regular simplex computed with Spendley et al. formula
   \item initial simplex computed by a small perturbation around the initial guess point
   \end{itemize}
-\item Manage cost function
+\item manage cost function
   \begin{itemize}
   \item optionnal additionnal argument
   \item direct communication of the task to perform : cost function or inequality constraints
   \end{itemize}
-\item Manage various termination criteria, including maximum number of iterations, tolerance on function value (relative or absolute), 
+\item manage various termination criteria 
   \begin{itemize}
+  \item maximum number of iterations, 
+  \item tolerance on function value (relative or absolute),
   \item tolerance on x (relative or absolute),
   \item tolerance on standard deviation of function value (original termination criteria in [3]),
   \item maximum number of evaluations of cost function,
   \item absolute or relative simplex size,
   \end{itemize}
-\item Manage the history of the convergence, including
+\item manage the history of the convergence, including :
+  \begin{itemize}
+  \item the history of function values,
+  \item the history of optimum point,
+  \item the history of simplices,
+  \item the history of termination criterias,
+  \end{itemize}
+\item provide a plot command which allows to graphically see the history of the simplices toward the optimum,
+\item provide query functions for 
   \begin{itemize}
-  \item history of function values,
-  \item history of optimum point,
-  \item history of simplices,
-  \item history of termination criterias,
+  \item the status of the optimization process,
+  \item the number of iterations, 
+  \item the number of function evaluations, 
+  \item the status of execution, 
+  \item the function value at initial point, 
+  \item the function value at optimal point, 
+  \item etc...
   \end{itemize}
-\item Provide a plot command which allows to graphically see the history of the simplices toward the optimum,
-\item Provide query features for the status of the optimization process number of iterations, number of function evaluations, status of execution, function value at initial point, function value at optimal point, etc...
 \item Spendley et al. fixed shaped algorithm,
 \item Kelley restart based on simplex gradient,
 \item O'Neill restart based on factorial search around optimum,
 \item Box-like method managing bounds and nonlinear inequality constraints based on arbitrary number of vertices in the simplex.
 \end{itemize}
 
+\section{How to use the Toolbox}
+
+The design of the toolbox is based on the creation of 
+a new token by the \scifunction{neldermead\_new} function.
+The Nelder-Mead object associated with this token can then 
+be configured with \scifunction{neldermead\_configure} and queried 
+with \scifunction{neldermead\_cget}. For example, the
+\scifunction{neldermead\_configure} command allows to configure the 
+number of variables, the objective function and the initial guess.
+
+The main command of the toolbox is the \scifunction{neldermead\_search} command, which
+solves the optimization problem. After an optimization has been performed,
+the \scifunction{neldermead\_get} command allows to retrieve the optimum $x^\star$,
+as well as other parameters, such as the number of iterations performed, the number 
+of evaluations of the function, etc...
+
+Once the optimization is finished, the \scifunction{neldermead\_destroy} function 
+deletes the object.
+
+\section{An example}
+
+In the following example, we search the minimum of the 2D Rosenbrock function \cite{citeulike:1903787}, 
+defined by
+\begin{eqnarray}
+f(x_1,x_2) = 100(x_2 - x_1)^2 + (1-x_1)^2
+\end{eqnarray}
+
+The following Scilab script allows to find the solution of the problem. 
+We begin by defining the function \scifunction{rosenbrock} which computes the Rosenbrock function. 
+The traditionnal initial guess $(-1.2 , 1.0)$ is used, which corresponds 
+to the "-x0" key. The initial simplex is computed along 
+the axes with a length equal to 0.1. We want to use the Nelder-Mead algorithm with variable simplex size 
+is used, which corresponds to the "variable" value of the "-method" option. 
+The verbose mode is enabled so that messages are generated during the algorithm. 
+After the optimization is performed, the optimum is retrieved with quiery features.
+
+\lstset{language=Scilab}
+\lstset{numbers=left}
+\lstset{basicstyle=\footnotesize}
+\lstset{keywordstyle=\bfseries}
+\begin{lstlisting}
+function y = rosenbrock (x)
+  y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
+endfunction
+nm = neldermead_new ();
+nm = neldermead_configure(nm,"-numberofvariables",2);
+nm = neldermead_configure(nm,"-x0",[-1.2 1.0]');
+nm = neldermead_configure(nm,"-simplex0method","axes");
+nm = neldermead_configure(nm,"-simplex0length",0.1);
+nm = neldermead_configure(nm,"-method","variable");
+nm = neldermead_configure(nm,"-verbose",1);
+nm = neldermead_configure(nm,"-function",rosenbrock);
+nm = neldermead_search(nm);
+xopt = neldermead_get(nm,"-xopt")
+fopt = neldermead_get(nm,"-fopt")
+status = neldermead_get(nm,"-status")
+nm = neldermead_destroy(nm);
+\end{lstlisting}
+
+This produces the following output.
+
+\lstset{language=Scilab}
+\lstset{numbers=left}
+\lstset{basicstyle=\footnotesize}
+\lstset{keywordstyle=\bfseries}
+\begin{lstlisting}
+-->nm = neldermead_search(nm);
+Function Evaluation #1 is [24.2] at [-1.2 1]
+Function Evaluation #1 is [24.2] at [-1.2 1]
+Function Evaluation #2 is [8.82] at [-1.1 1]
+Function Evaluation #3 is [16.4] at [-1.2 1.1]
+Step #1 : order
+=================================================================
+Iteration #1 (total = 1)
+Function Eval #3
+Xopt : -1.1 1
+Fopt : 8.820000e+000
+DeltaFv : 1.538000e+001
+Center : -1.1666667 1.0333333
+Size : 1.414214e-001
+Vertex #1/3 : fv=8.820000e+000, x=-1.100000e+000 1.000000e+000
+Vertex #2/3 : fv=1.640000e+001, x=-1.200000e+000 1.100000e+000
+Vertex #3/3 : fv=2.420000e+001, x=-1.200000e+000 1.000000e+000
+Reflect
+xbar=-1.15 1.05
+Function Evaluation #4 is [5.62] at [-1.1 1.1]
+xr=[-1.1 1.1], f(xr)=5.620000
+Expand
+Function Evaluation #5 is [4.428125] at [-1.05 1.15]
+xe=-1.05 1.15, f(xe)=4.428125
+  > Perform Expansion
+Sort
+[...]
+=================================================================
+Iteration #56 (total = 56)
+Function Eval #98
+Xopt : 0.6537880 0.4402918
+Fopt : 1.363828e-001
+DeltaFv : 1.309875e-002
+Center : 0.6788120 0.4503999
+Size : 6.945988e-002
+Vertex #1/3 : fv=1.363828e-001, x=6.537880e-001 4.402918e-001
+Vertex #2/3 : fv=1.474625e-001, x=7.107987e-001 4.799712e-001
+Vertex #3/3 : fv=1.494816e-001, x=6.718493e-001 4.309367e-001
+Reflect
+xbar=0.6822933 0.4601315
+Function Evaluation #99 is [0.1033237] at [0.6927374 0.4893262]
+xr=[0.6927374 0.4893262], f(xr)=0.103324
+Expand
+Function Evaluation #100 is [0.1459740] at [0.7031815 0.5185210]
+xe=0.7031815 0.5185210, f(xe)=0.145974
+  > Perform reflection
+Sort
+=================================================================
+Iteration #57 (total = 57)
+Function Eval #100
+Xopt : 0.6927374 0.4893262
+Fopt : 1.033237e-001
+DeltaFv : 4.413878e-002
+Center : 0.6857747 0.4698631
+Size : 6.262139e-002
+Vertex #1/3 : fv=1.033237e-001, x=6.927374e-001 4.893262e-001
+Vertex #2/3 : fv=1.363828e-001, x=6.537880e-001 4.402918e-001
+Vertex #3/3 : fv=1.474625e-001, x=7.107987e-001 4.799712e-001
+Terminate with status : maxfuneval
+-->xopt = neldermead_get(nm,"-xopt")
+ xopt  =
+ 
+    0.6927374  
+    0.4893262  
+ 
+-->fopt = neldermead_get(nm,"-fopt")
+ fopt  =
+ 
+    0.1033237  
+ 
+-->status = neldermead_get(nm,"-status")
+ status  =
+ 
+ maxfuneval   
+\end{lstlisting}
+
+\section{Help, demonstrations and unit tests}
+
+For a complete presentation of the functions and options, the reader 
+should consult the help which is provided with the component.
+The main menu of the help associated with the optimization 
+module is presented in figures \ref{fig-intro-help} and \ref{fig-intro-helpfminsearch}.
+The corresponding pages provide a complete documentation for the 
+corresponding functions, as well as many sample uses.
+
+\begin{figure}
+\begin{center}
+\includegraphics[width=15cm]{introduction-help.png}
+\end{center}
+\caption{Built-in help for the Nelder-Mead component}
+\label{fig-intro-help}
+\end{figure}
+
+\begin{figure}
+\begin{center}
+\includegraphics[width=15cm]{introduction-help-fminsearch.png}
+\end{center}
+\caption{Built-in help for the \scifunction{fminsearch} function}
+\label{fig-intro-helpfminsearch}
+\end{figure}
+
+Several demonstrations are provided with the component. These 
+are available from the "Demonstration" menu of the Scilab console
+and are presented in figure \ref{fig-intro-demos}.
+
+\begin{figure}
+\begin{center}
+\includegraphics[width=10cm]{introduction-demos.png}
+\end{center}
+\caption{Built-in demonstration scripts for the Nelder-Mead component}
+\label{fig-intro-demos}
+\end{figure}
+
+The following script shows where the demonstration scripts are 
+available from the Scilab installation directory.
+
+\lstset{language=Scilab}
+\lstset{numbers=left}
+\lstset{basicstyle=\footnotesize}
+\lstset{keywordstyle=\bfseries}
+\begin{lstlisting}
+-->cd SCI/modules/optimization/demos/neldermead
+ ans  =
+ 
+ D:\Programs\SCFD8E~1\modules\optimization\demos\neldermead   
+ 
+-->ls *.sce
+ ans  =
+ 
+!nmplot_rosenbrock.sce        !
+!                             !
+!nmplot_rosenbrock.fixed.sce  !
+!                             !
+!nmplot_quadratic.fixed.sce   !
+!                             !
+!nmplot_mckinnon2.sce         !
+!                             !
+!nmplot_mckinnon.sce          !
+!                             !
+!nmplot_han2.sce              !
+!                             !
+!nmplot_han1.sce              !
+!                             !
+!nmplot_boxproblemA.sce       !
+!                             !
+!neldermead_rosenbrock.sce    !
+!                             !
+!neldermead.dem.sce           !
+!                             !
+!fminsearch.sce               !
+\end{lstlisting}
+
+These components were developped based on unit tests, which are 
+provided with Scilab.
+These unit tests are located in the "SCI/modules/optimization/tests/unit\_tests"
+directory, under the "neldermead", "optimsimplex" and "optimbase" directories.
+Each unit test correspond to a .tst file. These tests are covering most 
+(if not all) the features provided by the components. This is why there are 
+a good source of information on how to use the functions.
+
+
+
+
+
diff --git a/scilab_doc/neldermead/method-neldermead.tex b/scilab_doc/neldermead/method-neldermead.tex
index 22529dc..8e9fd1f 100644
--- a/scilab_doc/neldermead/method-neldermead.tex
+++ b/scilab_doc/neldermead/method-neldermead.tex
@@ -1,10 +1,30 @@
 \chapter{Nelder-Mead method}
 
-\section{Analysis}
+In this chapter, we present Nelder and Mead's \cite{citeulike:3009487} algorithm.
+We begin by the analysis of the algorithm, which is based on a variable shape simplex.
+Then, we present geometric situations where the various steps of the algorithm 
+might be used. In the third part, we present the rate of convergence toward the optimum of 
+the Nelder-Mead algorithm. This part is mainly based on Han and Neumann's paper \cite{HanNeumann2006}, 
+which is based on a class of quadratic functions with a special initial 
+simplex. The core of this chapter is the analysis of several numerical 
+experiments which have been performed with the neldermead component.
+We analyse the behaviour of the algorithm on quadratic functions and 
+present several counter examples where the Nelder-Mead algorithm is 
+known to fail.
+
+\section{Introduction}
+
+The goal of Nelder and Mead algorithm is to solve the 
+following unconstrained optimization problem
+\begin{eqnarray}
+\min f(x)
+\end{eqnarray}
+where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 
+function $f:\RR^n\rightarrow \RR$.
 
 The Nelder-Mead method is an improvment over the Spendley's et al.
 method with the goal of allowing the simplex to vary in shape.
-The Nelder-Mead algorithm makes use of four parameters : the 
+The Nelder-Mead algorithm makes use of four parameters: the 
 coefficient of reflection $\rho$, expansion $\chi$, 
 contraction $\gamma$ and shrinkage $\sigma$.
 When the expansion or contraction steps are performed, the shape 
@@ -178,17 +198,17 @@ shrink steps are rare.
 \label{fig-nm-moves-shrinkafterco}
 \end{figure}
 
-\subsection{Termination criteria}
+%\subsection{Termination criteria}
 
-TODO...
+%TODO...
 
-\section{Convergence on a quadratic}
+\section{Convergence properties on a quadratic}
 
 In this section, we reproduce one result 
 presented by Han and Neumann \cite{HanNeumann2006}, which states 
 the rate of convergence toward the optimum on a class of quadratic functions with a special initial 
 simplex.
-See also the Phd by Lixing Han in 2000 \cite{Han2000}.
+Some additionnal results are also presented in the Phd thesis by Lixing Han in 2000 \cite{Han2000}.
 We study a generalized quadratic and use a particular 
 initial simplex. We show that the vertices follow 
 a recurrence equation, which is associated with a caracteristic 
@@ -735,6 +755,8 @@ caracteristic equation}
 \label{fig-nm-roots-variable}
 \end{figure}
 
+
+
 \section{Numerical experiments}
 
 In this section, we present some numerical experiments 
@@ -819,7 +841,7 @@ figure \ref{fig-nm-numexp1-logfopt}.
 \label{fig-nm-numexp1-logfopt}
 \end{figure}
 
-\subsection{Badly scaled quadratic function}
+\subsubsection{Badly scaled quadratic function}
 
 The function we try to minimize is the following quadratic 
 in 2 dimensions 
diff --git a/scilab_doc/neldermead/method-spendley.tex b/scilab_doc/neldermead/method-spendley.tex
index a3725c0..c8d58a0 100644
--- a/scilab_doc/neldermead/method-spendley.tex
+++ b/scilab_doc/neldermead/method-spendley.tex
@@ -12,7 +12,7 @@ are involving only 2 variables and are based on a quadratic function.
 The last numerical experiment explores the behaviour of the algorith
 when the number of variables increases.
 
-\section{Analysis}
+\section{Introduction}
 
 In this section, we present Spendley's et al algorithm for unconstrained optimization.
 This algorithm is based on the iterative update of a simplex. 
@@ -24,6 +24,14 @@ or a shrink is performed in practice.
 
 \subsection{Algorithm}
 
+The goal of Spendley's et al. algorithm is to solve the 
+following unconstrained optimization problem
+\begin{eqnarray}
+\min f(x)
+\end{eqnarray}
+where $x\in \RR^n$, $n$ is the number of optimization parameters and $f$ is the objective 
+function $f:\RR^n\rightarrow \RR$.
+
 The simplex algorithms are based on the iterative update of 
 a \emph{simplex} made of $n+1$ points $S=\{x_i\}_{i=1,n+1}$. Each point 
 in the simplex is called a \emph{vertex} and is associated with 
diff --git a/scilab_doc/neldermead/neldermead-introduction-so.pdf b/scilab_doc/neldermead/neldermead-introduction-so.pdf
new file mode 100644
index 0000000..c2bf429
--- /dev/null
+++ b/scilab_doc/neldermead/neldermead-introduction-so.pdf
diff --git a/scilab_doc/neldermead/neldermead-introduction-so.tex b/scilab_doc/neldermead/neldermead-introduction-so.tex
new file mode 100644
index 0000000..6a05c35
--- /dev/null
+++ b/scilab_doc/neldermead/neldermead-introduction-so.tex
@@ -0,0 +1,85 @@
+%
+% neldermead.tex --
+%   Some notes about Nelder-Mead algorithms.
+%
+% Copyright 2008-2009 Michael Baudin
+%
+\documentclass[12pt]{report}
+
+\include{macros}
+
+\begin{document}
+%% User defined page headers
+\pagestyle{fancyplain}
+\renewcommand{\chaptermark}[1]{\markboth{\chaptername\ \thechapter. #1}{}}
+\renewcommand{\sectionmark}[1]{\markright{\thesection. #1}}
+\lhead[]{\fancyplain{}{\bfseries\leftmark}}
+\rhead[]{\fancyplain{}{\bfseries\thepage}}
+\cfoot{}
+
+%% User defined figure legends
+\makeatletter
+\def\figurename{{\protect\sc \protect\small\bfseries Fig.}}
+\def\f@ffrench{\protect\figurename\space{\protect\small\bf \thefigure}\space}
+\let\fnum@figure\f@ffrench%
+\let\captionORI\caption
+\def\caption#1{\captionORI{\rm\small #1}}
+\makeatother
+
+%% First page
+\thispagestyle{empty}
+{
+\begin{center}
+%% Comment for DVI
+\includegraphics[height=40mm]{scilab_logo}
+\vskip4cm
+
+%% Empty space between the box and the text
+\fboxsep6mm
+%% Box thickness
+\fboxrule1.3pt
+\Huge
+$$\fbox{$
+  \begin{array}{c}
+  \textbf{Nelder-Mead}\\
+  \textbf{Toolbox Manual}\\
+  \textbf{-- Introduction --}\\
+  \end{array}
+  $}
+$$
+\end{center}
+\vskip4cm
+
+\normalsize
+
+\begin{flushright}
+Version 0.2 \\
+September 2009
+\end{flushright}
+
+\begin{flushright}
+Micha\"el BAUDIN
+\end{flushright}
+
+\clearpage
+
+%% Table of contents
+\renewcommand{\baselinestretch}{1.30}\small \normalsize
+
+\tableofcontents
+
+\renewcommand{\baselinestretch}{1.18}\small \normalsize
+
+\include{introduction}
+
+\clearpage
+
+
+%% Bibliography
+
+\addcontentsline{toc}{chapter}{Bibliography}
+\bibliographystyle{plain}
+\bibliography{neldermead}
+
+\end{document}
+
diff --git a/scilab_doc/neldermead/neldermead-simplex-so.pdf b/scilab_doc/neldermead/neldermead-simplex-so.pdf
index 8c94d37..6c69bb3 100644
--- a/scilab_doc/neldermead/neldermead-simplex-so.pdf
+++ b/scilab_doc/neldermead/neldermead-simplex-so.pdf
diff --git a/scilab_doc/neldermead/neldermead-spendley-so.pdf b/scilab_doc/neldermead/neldermead-spendley-so.pdf
index 454e180..ecb3671 100644
--- a/scilab_doc/neldermead/neldermead-spendley-so.pdf
+++ b/scilab_doc/neldermead/neldermead-spendley-so.pdf
diff --git a/scilab_doc/neldermead/neldermead.bib b/scilab_doc/neldermead/neldermead.bib
index 0ee9803..a92538f 100644
--- a/scilab_doc/neldermead/neldermead.bib
+++ b/scilab_doc/neldermead/neldermead.bib
@@ -27,7 +27,6 @@ doi = {10.1137/S1052623496303470}
    posted-at = {2008-09-15 16:23:09},
    priority = {2},
    title = {A Simplex Method for Function Minimization},
-   note = {\url{http://dx.doi.org/10.1093/comjnl/7.4.308}},
    volume = {7},
    year = {1965}
 }
diff --git a/scilab_doc/neldermead/neldermead.pdf b/scilab_doc/neldermead/neldermead.pdf
index c36eb3f..86443c0 100644
--- a/scilab_doc/neldermead/neldermead.pdf
+++ b/scilab_doc/neldermead/neldermead.pdf
diff --git a/scilab_doc/neldermead/neldermead.tex b/scilab_doc/neldermead/neldermead.tex
index c44550a..a199c9b 100644
--- a/scilab_doc/neldermead/neldermead.tex
+++ b/scilab_doc/neldermead/neldermead.tex
@@ -32,7 +32,7 @@
 \begin{center}
 %% Comment for DVI
 \includegraphics[height=40mm]{scilab_logo}
-\vskip4cm
+\vskip2cm
 
 %% Empty space between the box and the text
 \fboxsep6mm
@@ -42,23 +42,49 @@
 $$\fbox{$
   \begin{array}{c}
   \textbf{Nelder-Mead}\\
-  \textbf{Toolbox Manual}
+  \textbf{User's Manual}
   \end{array}
   $}
 $$
 \end{center}
-\vskip4cm
 
-\normalsize
+\vskip1cm
+
+\begin{center}
+\begin{large}
+Micha\"el BAUDIN
+\end{large}
+\end{center}
+
+\vskip2cm
+
+\textbf{Abstract}
+
+In this document, we present the Nelder-Mead component provided in Scilab.
+The introduction gives a brief overview of the optimization features of the 
+component and present an introductory example. Then we present some theory 
+associated with the simplex, a geometric concept which is central in
+the Nelder-Mead algorithm. We present several method to compute an
+initial simplex. Then we present Spendley's et al. fixed shape unconstrained 
+optimization algorithm. Several numerical experiments are provided, which 
+shows how this algorithm performs on well-scaled and badly scaled quadratics. 
+In the final section, we present the Nelder-Mead variable shape 
+unconstrained optimization algorithm. Several numerical experiments are presented,
+where some of these are counter examples, that is cases where the algorithms 
+fails to converge on a stationnary point. In the appendix of this document,
+the interested reader will find a bibliography of simplex-based algorithms,
+along with an analysis of the various implementations which are available 
+in several programming languages.
+
+\vskip1cm
+
 
 \begin{flushright}
-Version 0.2 \\
+Version 0.3 \\
 September 2009
 \end{flushright}
 
-\begin{flushright}
-Micha\"el BAUDIN
-\end{flushright}
+
 
 \clearpage
 
@@ -70,25 +96,18 @@ Micha\"el BAUDIN
 \renewcommand{\baselinestretch}{1.18}\small \normalsize
 
 \include{introduction}
-
-\include{overview}
-
 \include{section-simplex}
-
 \include{method-spendley}
-
 \include{method-neldermead}
-
 \include{conclusion}
-
 \include{acknowledgments}
 
 \clearpage
 
 %% Appendix
 \appendix
-\include{nmbibliography}
 
+\include{nmbibliography}
 \include{implementations}
 
 %% Bibliography
diff --git a/scilab_doc/neldermead/overview.tex b/scilab_doc/neldermead/overview.tex
deleted file mode 100644
index 9e044d1..0000000
--- a/scilab_doc/neldermead/overview.tex
+++ /dev/null
@@ -1,74 +0,0 @@
-\chapter{Overview}
-
-In this section, we present the main commands of the Nelder-Mead
-toolbox as well as an example of use.
-
-
-\section{How to use the Toolbox}
-
-The design of the toolbox is based on the creation of 
-a new token by the \scifunction{neldermead\_new} command.
-The Nelder-Mead object associated with this token can then 
-be configured with \scifunction{neldermead\_configure} and queried 
-with \scifunction{neldermead\_cget}. To be more specific, the
-\scifunction{neldermead\_configure} command allows to configure the 
-number of variables, the objective function and the initial guess.
-
-The main command of the toolbox is the \scifunction{neldermead\_search} command, which
-solves the optimization problem. After an optimization has been performed,
-the \scifunction{neldermead\_get} command allows to retrieve the optimum $x^\star$,
-as well as other parameters, such as the number of iterations performed, the number 
-of evaluations of the function, etc...
-
-\section{An example}
-
-In the following example, one searches the minimum of the 2D Rosenbrock function \cite{citeulike:1903787}, 
-defined by
-\begin{eqnarray}
-f(x_1,x_2) = 100(x_2 - x_1)^2 + (1-x_1)^2
-\end{eqnarray}
-
-One begins by defining the function "rosenbrock" which computes the Rosenbrock function. 
-The traditionnal initial guess $(-1.2 , 1.0)$ is used. The initial simplex is computed along 
-the axes with a length equal to 0.1. The Nelder-Mead algorithm with variable simplex size 
-is used. The verbose mode is enabled so that messages are generated during the algorithm. 
-After the optimization is performed, the optimum is retrieved with quiery features.
-
-\lstset{language=Scilab}
-\lstset{numbers=left}
-\lstset{basicstyle=\footnotesize}
-\lstset{keywordstyle=\bfseries}
-\begin{lstlisting}
-
-function y = rosenbrock (x)
-  y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
-endfunction
-
-nm = neldermead_new ();
-nm = neldermead_configure(nm,"-x0",[-1.2 1.0]');
-nm = neldermead_configure(nm,"-simplex0method","axes");
-nm = neldermead_configure(nm,"-simplex0length",0.1);
-nm = neldermead_configure(nm,"-method","variable");
-nm = neldermead_configure(nm,"-verbose",1);
-nm = neldermead_configure(nm,"-function",rosenbrock);
-nm = neldermead_search(nm);
-xopt = neldermead_get(nm,"-xopt");
-fopt = neldermead_get(nm,"-fopt");
-historyfopt = neldermead_get(nm,"-historyfopt");
-iterations = neldermead_get(nm,"-iterations");
-historyxopt = neldermead_get(nm,"-historyxopt");
-historysimplex = neldermead_get(nm,"-historysimplex");
-fx0 = neldermead_get(nm,"-fx0");
-status = neldermead_get(nm,"-status");
-nm = neldermead_destroy(nm);
-\end{lstlisting}
-
-The script makes the hypothesis that an environment variable 
-named TOOLBOX\_HOME contains the path to directory 
-which contains the toolbox, which is stored in the "neldermead" directory.
-
-For a deeper presentation of the commands and options, the reader 
-should consult the help which is provided with the package.
-
-
-
diff --git a/scilab_doc/neldermead/section-simplex.tex b/scilab_doc/neldermead/section-simplex.tex
index b9fb8d3..c56bc53 100644
--- a/scilab_doc/neldermead/section-simplex.tex
+++ b/scilab_doc/neldermead/section-simplex.tex
@@ -4,14 +4,17 @@ In this section, we present the various definitions connected
 to simplex algorithms. We introduce several methods to measure 
 the size of a simplex, including the oriented length. 
 We present several methods to compute an
-initial simplex, for example the regular simplex used by Spendley et al..
-We also present the simplex gradient, which is a forward or a centered 
-difference formula for the gradient of the cost function.
-The core of this section is from \cite{Kelley1999}.
+initial simplex, that is, the regular simplex used by Spendley et al.,
+the axis-by-axis simplex, Pfeffer's simplex and the randomized 
+bounds simplex.
+%We also present the simplex gradient, which is a forward or a centered 
+%difference formula for the gradient of the cost function.
+%The core of this section is from \cite{Kelley1999}.
 
 \section{The simplex}
 
-A \emph{simplex} $S$ in $\RR^n$ is the convex hull of $n+1$ points $S=\{\bx_i\}_{i=1,n+1}$.
+A \emph{simplex} $S$ in $\RR^n$ is the convex hull of $n+1$ points $S=\{\bx_i\}_{i=1,n+1}$,
+where $\bx_i \in \RR^n$ for $i=1,n+1$.
 
 Box extended the Nelder-Mead algorithm to handle bound and non linear constraints \cite{Box1965}.
 To be able to manage difficult cases, he uses a \emph{complex} made of $k\geq n+1$ vertices.
@@ -19,13 +22,14 @@ In this section, we will state clearly when the definition and results can be ap
 Indeed, some definitions such as the simplex gradient cannot be extended to a \emph{complex}
 and are only applicable to a \emph{simplex}.
 
-The point $\bx_i\in\RR^n$ is the $i$-th vertex of $S$. Given a function $f(\bx)\in\RR$,
+The point $\bx_i\in\RR^n$ is the $i$-th vertex of $S$,  
+where $x_i^j\in\RR$ is the $j$-th coordinate of the $i$-th vertex of the simplex $S$.
+Given a function $f(\bx)\in\RR$,
 each vertex is associated with a function value $f_i = f(\bx_i)$ for $i=1,n+1$.
 In simplex algorithms, the vertex are sorted by increasing function values 
-
 \begin{eqnarray}
 \label{simplex-sortedfv}
-f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}
+f_1 \leq f_2 \leq \ldots \leq f_n \leq f_{n+1}.
 \end{eqnarray}
 
 The sorting order is not precisely defined neither in Spendley's et al paper \cite{Spendley1962}
@@ -37,25 +41,27 @@ ordering rules have no measurable influence.
 Let $V$ denote the $n\times n$ matrix of simplex directions 
 \begin{eqnarray}
 \label{simplex-directions}
-V(S) = (\bx_2 - \bx_1, \bx_3 - \bx_1 , \ldots , \bx_{n+1} - \bx_1) = (\bv_1, \ldots , \bv_n)
+V(S) = (\bx_2 - \bx_1, \bx_3 - \bx_1 , \ldots , \bx_{n+1} - \bx_1) = (\bv_1, \ldots , \bv_n).
 \end{eqnarray}
 
-We say that $S$ is nonsingular if the matrix of simplex directions $V(S)$ is nonsingular.
-
+We say that the simplex $S$ is nonsingular if the matrix of simplex directions $V(S)$ is nonsingular.
 
 \section{The size of the simplex}
+\label{section-simplexsize}
 
 Several methods are available to compute the size of a simplex.
-In Kelley's book \cite{Kelley1999}, the author presents the diameter and the two oriented lengths.
 
 The simplex diameter $diam(S)$ is defined by 
 \begin{eqnarray}
 \label{simplex-diameter}
 diam(S) = \max_{i,j=1,n+1} \|\bx_i - \bx_j\|_2,
 \end{eqnarray}
-where $\|.\|_2$ is the euclidian norm $\|x\|_2 = \sum_{i=1,n}\bx_i^2$.
+where $\|.\|_2$ is the euclidian norm defined by 
+\begin{eqnarray}
+\|\bx\|_2 = \sum_{i=1,n}(x^j)^2.
+\end{eqnarray}
 In practical implementations, computing the diameter requires two nested loops over the 
-vertices of the simplex, i.e. $(n+1)^2$ operations. This is why authors generally 
+vertices of the simplex, i.e. requires $(n+1)^2$ operations. This is why authors generally 
 prefer to use lengths which are less expensive to compute.
 
 The two oriented lengths $\sigma_-(S)$ and $\sigma_+(S)$ are using the 
@@ -74,33 +80,33 @@ The following inequalities are satisfied between the diameter and the maximum or
 \end{eqnarray}
 
 In Nash's book \cite{nla.cat-vn1060620}, the size of the simplex $s_N(S)$ is measured
-based on the $l1$ norm and is defined by 
+based on the 1-norm and is defined by 
 \begin{eqnarray}
 \label{simplex-sizenash}
 s_N(S) = \sum_{i=2,n+1} \|\bx_i - \bx_1\|_1
 \end{eqnarray}
-where 
+where the 1-norm is defined by 
 \begin{eqnarray}
 \label{simplex-sizenash2}
-\|\bx_i - \bx_1\|_1 = \sum_{j=1,n} |x_i^j - x_1^j|
+\|\bx \|_1 = \sum_{j=1,n} |x^j|
 \end{eqnarray}
 where $x_i^j\in\RR$ is the $j$-th coordinate of the $i$-th vertex of the simplex $S$.
 
 \section{The initial simplex}
 
 While most of the theory can be developed without being very specific 
-about the initial simplex, the initial simplex plays a very important role in practice.
+about the initial simplex, it plays a very important role in practice.
 All approaches are based on the initial guess $\overline{\bx}_0\in\RR^n$ and create a 
 geometric shape based on this point.
-(We denoted the initial guess by $\overline{\bx}_0$ instead of the usual $\bx_0$
+(We denote the initial guess by $\overline{\bx}_0$ instead of the usual $\bx_0$
 in order to distinguish the initial guess from the vertices $\{\bx_i\}_{i=1,n+1}$.)
 
 
 In this section, we present the various approach to design the initial 
 simplex. In the first part, we emphasize the importance of the initial
 simplex in optimization algorithms. Then we present the regular simplex 
-approach by Spendley et al., the randomized bounds approach by Box and 
-Pfeffer's method.
+by Spendley et al., the axis-by-axis simplex, the randomized bounds approach by Box and 
+Pfeffer's simplex.
 
 \subsection{Importance of the initial simplex}
 
@@ -112,7 +118,7 @@ is typical a fixed-shape simplex algorithm (see \cite{Torczon89multi-directional
 for other patterns of a direct search method).
 If, by chance, the pattern is so that the optimum is close to one point 
 defined by the pattern, the number of iteration may be small. On the contrary, the 
-number of iterations may be high if the pattern does not come close to the 
+number of iterations may be large if the pattern does not come close to the 
 optimum.
 
 \begin{figure}
@@ -127,11 +133,11 @@ The variable-shape simplex algorithm designed by Nelder and Mead is also very
 sensitive to the initial simplex.
 One of the problems is that the initial simplex should be consistently scaled 
 with respect to the unknown $x$.
-In \cite{parkinson1972}, "An investigation into the efficiency of variants on the simplex method", 
+In "An investigation into the efficiency of variants on the simplex method" \cite{parkinson1972}, 
 Parkinson and Hutchinson explored 
-several ways of improvement. First, they investigate the sensitivity
+several improvements of Nelder and Mead's algorithm. First, they investigate the sensitivity
 of the algorithm to the initial simplex. Two parameters were investigated,
-i.e. the initial length and the orientation of the simplex. 
+that is, the initial length and the orientation of the simplex. 
 The conclusion of their study with respect to the initial simplex is 
 the following. "The orientation of the initial simplex has a significant effect 
 on efficiency, but the relationship can be too sensitive for an automatic 
@@ -140,7 +146,7 @@ predictor to provide sufficient accuracy at this time."
 Since no initial simplex clearly improves on the others, in practice, 
 it may be convenient to try different approaches.
 
-\subsection{Spendley's et al simplex}
+\subsection{Spendley's et al regular simplex}
 
 In their paper \cite{Spendley1962}, Spendley et al. use a regular 
 simplex with given size $\ell>0$. We define the parameters $p,q>0$ as 
@@ -165,10 +171,10 @@ x_i^j &=&
 \right.
 \end{eqnarray}
 for vertices $i=2,n+1$ and components $j=1,n$, 
-where $\ell \in\RR$ is the length of the simplex ($\ell>0$). Notice that this 
-length is the same for all the vertices which keeps the simplex regular.
+where $\ell \in\RR$ is the length of the simplex and satisfies $\ell>0$. Notice that this 
+length is the same for all the edges which keeps the simplex regular.
 
-The regular initial simplex is presented in figure \ref{fig-nm-simplex-regular}.
+The regular simplex is presented in figure \ref{fig-nm-simplex-regular}.
 
 \begin{figure}
 \begin{center}
@@ -178,7 +184,7 @@ The regular initial simplex is presented in figure \ref{fig-nm-simplex-regular}.
 \label{fig-nm-simplex-regular}
 \end{figure}
 
-\subsection{Simplex along the axes}
+\subsection{Axis-by-axis simplex}
 
 A very efficient and simple approach leads to an axis-by-axis simplex.
 This simplex depends on a vector of positive lengths $\bl\in\RR^n$.
@@ -191,15 +197,16 @@ The other vertices are defined by
 x_i^j &=& 
 \left\{
 \begin{array}{l}
-\overline{x}_0^j + \bl_j, \textrm{ if } j=i-1,\\
+\overline{x}_0^j + \ell_j, \textrm{ if } j=i-1,\\
 \overline{x}_0^j, \textrm{ if } j\neq i-1,\\
 \end{array}
 \right.
 \end{eqnarray}
 for vertices $i=2,n+1$ and components $j=1,n$.
 
-This kind of simplex is presented in figure \ref{fig-nm-simplex-axes}.
-The axis-by-axis approach is used in the very popular Nelder-Mead 
+This type of simplex is presented in figure \ref{fig-nm-simplex-axes},
+where $\ell_1=1$ and $\ell_2=2$.
+The axis-by-axis simplex is used in the Nelder-Mead 
 algorithm provided in Numerical Recipes in C \cite{NumericalRecipes}.
 As stated in \cite{NumericalRecipes}, the length vector $\bl$ can 
 be used as a guess for the characteristic length scale of the problem.
@@ -208,7 +215,8 @@ be used as a guess for the characteristic length scale of the problem.
 \begin{center}
 \includegraphics[width=10cm]{simplex_axes.png}
 \end{center}
-\caption{Axis-based simplex in 2 dimensions}
+\caption{Axis-based simplex in 2 dimensions -- Notice that the length along the $x$ axis is 1 while the length
+along the $y$ axis is 2. }
 \label{fig-nm-simplex-axes}
 \end{figure}
 
@@ -235,20 +243,19 @@ for vertices $i=2,n+1$ and components $j=1,n$.
 \subsection{Pfeffer's method}
 
 This initial simplex is used in the function \scifunction{fminsearch}
-and presented in \cite{Fan2002}. It is due to L. Pfeffer at Stanford.
+and presented in \cite{Fan2002}. According to \cite{Fan2002}, this simplex is due to L. Pfeffer at Stanford.
 The goal of this method is to scale the initial simplex with respect 
 to the characteristic lengths of the problem. This allows, for example,
 to manage cases where $x_1\approx 1$ and $x_2\approx 10^5$.
 As we are going to see, the scaling is defined with respect to the 
-initial guess $\bx_0$. Indeed, the initial simplex is created by 
-small perturbations around the initial guess $\overline{\bx}_0$.
+initial guess $\overline{\bx}_0$, with an axis-by-axis method.
 
 The method proceeds by defining $\delta_u,\delta_z>0$, where 
 $\delta_u$ is used for usual components of $\overline{\bx}_0$ and $\delta_z$ is 
 used for the case where one component of $\overline{\bx}_0$ is zero.
 The default values for $\delta_u$ and $\delta_z$ are 
 \begin{eqnarray}
-\delta_u = 0.05 \qquad \delta_z = 0.0075.
+\delta_u = 0.05 \qquad \textrm{and} \qquad \delta_z = 0.0075.
 \end{eqnarray}
 The first vertex of the simplex is the initial guess 
 \begin{eqnarray}
@@ -271,11 +278,11 @@ for vertices $i=2,n+1$ and components $j=1,n$.
 
 %TODO...
 
-%\section{References and notes}
+\section{References and notes}
 
-%Most of the section \ref{section-simplexgradient} is taken from 
-%Kelley's book \cite{Kelley1999}, "Iterative Methods for Optimization".
-%While this document focus on Nelder-Mead algorithm, Kelley gives a broad
-%view on optimization and present other algorithms for noisy functions,
-%like implicit filtering, multidirectional search and the Hooke-Jeeves algorithm.
+Some elements of the section \ref{section-simplexsize} is taken from 
+Kelley's book \cite{Kelley1999}, "Iterative Methods for Optimization".
+While this document focus on Nelder-Mead algorithm, Kelley gives a broad
+view on optimization and present other algorithms for noisy functions,
+like implicit filtering, multidirectional search and the Hooke-Jeeves algorithm.