summaryrefslogtreecommitdiffstats
path: root/scilab_doc
diff options
context:
space:
mode:
authorMichaŽl Baudin <michael.baudin@scilab.org>2009-11-06 15:52:01 +0100
committerMichaŽl Baudin <michael.baudin@scilab.org>2009-11-06 15:52:01 +0100
commit35984fb4468c6b19f75bed71317194031b9f62a7 (patch)
treedce398ce29db2a7e9282236a7637a1dc68300049 /scilab_doc
parent40c7f6c9f767b75e1a75e839cebe1a91723f6072 (diff)
downloadscilab-35984fb4468c6b19f75bed71317194031b9f62a7.zip
scilab-35984fb4468c6b19f75bed71317194031b9f62a7.tar.gz
fminsearch: Updated manual for automatic restarts
Diffstat (limited to 'scilab_doc')
-rw-r--r--scilab_doc/neldermead/neldermead-neldermead-so.pdfbin592350 -> 622384 bytes
-rw-r--r--scilab_doc/neldermead/neldermeadmethod/mckinnonkelley-history-simplex.pngbin0 -> 6902 bytes
-rw-r--r--scilab_doc/neldermead/neldermeadmethod/method-neldermead.tex301
3 files changed, 238 insertions, 63 deletions
diff --git a/scilab_doc/neldermead/neldermead-neldermead-so.pdf b/scilab_doc/neldermead/neldermead-neldermead-so.pdf
index b22c0b6..0c2f8b0 100644
--- a/scilab_doc/neldermead/neldermead-neldermead-so.pdf
+++ b/scilab_doc/neldermead/neldermead-neldermead-so.pdf
Binary files differ
diff --git a/scilab_doc/neldermead/neldermeadmethod/mckinnonkelley-history-simplex.png b/scilab_doc/neldermead/neldermeadmethod/mckinnonkelley-history-simplex.png
new file mode 100644
index 0000000..a48528b
--- /dev/null
+++ b/scilab_doc/neldermead/neldermeadmethod/mckinnonkelley-history-simplex.png
Binary files differ
diff --git a/scilab_doc/neldermead/neldermeadmethod/method-neldermead.tex b/scilab_doc/neldermead/neldermeadmethod/method-neldermead.tex
index 7cddfbf..997fbb3 100644
--- a/scilab_doc/neldermead/neldermeadmethod/method-neldermead.tex
+++ b/scilab_doc/neldermead/neldermeadmethod/method-neldermead.tex
@@ -324,6 +324,140 @@ shrink steps are rare.
324 324
325%TODO... 325%TODO...
326 326
327\section{Automatic restarts}
328
329In this section, we describe an algorithm which enables the user
330to perform automatic restarts when a search has failed.
331A condition is used to detect that a false minimum has been reached.
332We describe the automatic restart algorithm as well as the
333conditions used to detect a false minimum.
334
335\subsection{Automatic restart algorithm}
336
337In this section, we present the automatic restart algorithm.
338
339The goal of this algorithm is to detect that a false minimum has been found,
340a situation which may occur with the Nelder-Mead algorithm, as we are
341going to see in the numerical experiments section.
342These problems are known by practitionners since decades and several authors
343have tried to detect and solve this specific problem.
344
345In 1971, O'Neill published a fortran 77 implementation of the Nelder-Mead
346algorithm \cite{O'Neill1971AAF}. In order to check that the algorithm has converged,
347a factorial test is used. This test will be detailed later in this section.
348If a false minimum is found by this test, O'Neill suggests to restart the
349algorithm.
350
351In 1998, Mc Kinnon \cite{589109} showed a simple objective function
352for which the Nelder-Mead algorithm fails to converge to a minimum and, instead,
353converge to a non-stationnary point. In this numerical experiment, the simplex
354degenerates toward a single point. In 1999, Kelley \cite{589283} shows that
355restarting the algorithm allows to converge toward the global minimum.
356In order to detect the convergence problem, Kelley adapted the sufficient decrease
357condition which is classical in the frameword of gradient-based algorithms.
358When this condition is met, the algorithm is stopped and a restart should be performed.
359
360Scilab provides an automatic restart algorithm, which allows to detect
361that a false optimum has been reached and that a new search must be performed.
362The algorithm is based on a loop where a maximum number of restarts
363is allowed. The default maximum number of restarts is 3, which means that the maximum
364number of searches is 4.
365
366After a search has been performed, a condition is computed to know whether a restart
367must be performed. There are two conditions which are implemented:
368\begin{itemize}
369\item O'Neill factorial test,
370\item Kelley's stagnation condition.
371\end{itemize}
372We will analyze these tests later in this section.
373
374Notice that the automatic restarts are available whatever the simplex algorithm,
375be it the Nelder-Mead variable shape simplex algorithm, Spendley's et al. fixed shape
376simplex algorithm or any other algorithm. This is because the
377automatic restart is a loop programmed above the optimization algorithm.
378
379The automatic restart algorithm is presented in \ref{algo-automaticrestart}.
380Notice that, if a false minimum is detected after the maximum number of restart has been reached,
381the status is set to "maxrestart".
382
383\begin{figure}[htbp]
384\begin{algorithmic}
385\STATE $restartnb \gets 0$
386\STATE $reached \gets FALSE$
387\FOR{$i= 1$ to $restartmax + 1$}
388 \STATE $search()$
389 \STATE $istorestart = istorestart ()$
390 \IF {$NOT(istorestart)$}
391 \STATE $reached \gets TRUE$ \COMMENT{Convergence}
392 \STATE $BREAK$
393 \ENDIF
394 \IF {$i<restartmax$}
395 \STATE $restartnb \gets restartnb + 1$ \COMMENT{A restart is going to be performed}
396 \ENDIF
397\ENDFOR
398\IF {$reached$}
399 \STATE printf ( "Convergence reached after %d restarts." , restartnb )
400\ELSE
401 \STATE printf ( "Convergence not reached after maximum %d restarts." , restartnb )
402 \STATE $status \gets "maxrestart"$
403\ENDIF
404\end{algorithmic}
405\caption{Nelder-Mead algorithm -- Automatic restart algorithm.}
406\label{algo-automaticrestart}
407\end{figure}
408
409\subsection{O'Neill factorial test}
410
411In this sectin, we present O'Neill's factorial test.
412This algorithm is given a vector of lengths, stored in the
413$step$ variable. It is also given a small value $\epsilon$, which
414is an step length relative to the $step$ variable.
415The algorithm is presented in figure \ref{algo-factorialtest}.
416
417\begin{figure}[htbp]
418\begin{algorithmic}
419\STATE $\bx \gets \bx^\star$
420\STATE $istorestart = FALSE$
421\FOR{$i = 1$ to $n$}
422 \STATE $\delta = step ( i ) * \epsilon$
423 \IF { $\delta == 0.0$ }
424 \STATE $\delta = \epsilon$
425 \ENDIF
426 \STATE $x ( i ) = x ( i ) + \delta$
427 \STATE $fv = f ( x ) $
428 \IF { $ fv < fopt $}
429 \STATE $istorestart = TRUE$
430 \STATE break
431 \ENDIF
432 \STATE $x ( i ) = x ( i ) - \delta - \delta $
433 \STATE $fv = f ( x ) $
434 \IF { $ fv < fopt $}
435 \STATE $istorestart = TRUE$
436 \STATE break
437 \ENDIF
438 \STATE $x ( i ) = x ( i ) + \delta$
439\ENDFOR
440\end{algorithmic}
441\caption{O'Neill's factorial test}
442\label{algo-factorialtest}
443\end{figure}
444
445O'Neill's factorial test requires a large number of function evaluations, namely
446$2^n$ function evaluations. In O'Neill's implementation, the parameter
447$\epsilon$ is set to the constant value $1.e-3$.
448In Scilab's implementation, this parameter can be customized,
449thanks to the \scivar{-restarteps} option. Its default value is \scivar{\%eps},
450the machine epsilon. In O'Neill's implementation, the parameter \scivar{step}
451is equal to the vector of length used in order to compute the initial
452simplex. In Scilab's implementation, the two parameters are different,
453and the \scivar{step} used in the factorial test can be customized
454with the \scivar{-restartstep} option. Its default value is 1.0, which is
455expanded into a vector with size $n$.
456
457%\subsection{Kelley's stagnation detection}
458
459% TODO...
460
327\section{Convergence properties on a quadratic} 461\section{Convergence properties on a quadratic}
328 462
329\index{Han, Lixing} 463\index{Han, Lixing}
@@ -1267,53 +1401,6 @@ computed optimum is greater than a local point computed with a relative
1267epsilon equal to 1.e-3 and a step equal to the length of the initial simplex. 1401epsilon equal to 1.e-3 and a step equal to the length of the initial simplex.
1268\end{itemize} 1402\end{itemize}
1269 1403
1270In order to get an accurate view on O'Neill's factorial test,
1271we must describe explicitely the algorithm.
1272This algorithm is given a vector of lengths, stored in the
1273$step$ variable. It is also given a small value $\epsilon$.
1274The algorithm is presented in figure \ref{algo-factorialtest}.
1275
1276\begin{figure}[htbp]
1277\begin{algorithmic}
1278\STATE $\bx \gets \bx^\star$
1279\STATE $istorestart = FALSE$
1280\FOR{$i = 1$ to $n$}
1281 \STATE $\delta = step ( i ) * \epsilon$
1282 \IF { $\delta == 0.0$ }
1283 \STATE $\delta = \epsilon$
1284 \ENDIF
1285 \STATE $x ( i ) = x ( i ) + \delta$
1286 \STATE $fv = f ( x ) $
1287 \IF { $ fv < fopt $}
1288 \STATE $istorestart = TRUE$
1289 \STATE break
1290 \ENDIF
1291 \STATE $x ( i ) = x ( i ) - \delta - \delta $
1292 \STATE $fv = f ( x ) $
1293 \IF { $ fv < fopt $}
1294 \STATE $istorestart = TRUE$
1295 \STATE break
1296 \ENDIF
1297 \STATE $x ( i ) = x ( i ) + \delta$
1298\ENDFOR
1299\end{algorithmic}
1300\caption{O'Neill's factorial test}
1301\label{algo-factorialtest}
1302\end{figure}
1303
1304O'Neill's factorial test requires a large number of function evaluations, namely
1305$2^n$ function evaluations. In O'Neill's implementation, the parameter
1306$\epsilon$ is set to the constant value $1.e-3$.
1307In Scilab's implementation, this parameter can be customized,
1308thanks to the \scivar{-restarteps} option. Its default value is \scivar{\%eps},
1309the machine epsilon. In O'Neill's implementation, the parameter \scivar{step}
1310is equal to the vector of length used in order to compute the initial
1311simplex. In Scilab's implementation, the two parameters are different,
1312and the \scivar{step} used in the factorial test can be customized
1313with the \scivar{-restartstep} option. Its default value is 1.0, which is
1314expanded into a vector with size $n$.
1315
1316
1317The following tests are presented by O'Neill : 1404The following tests are presented by O'Neill :
1318\begin{itemize} 1405\begin{itemize}
1319\item Rosenbrock's parabolic valley \cite{citeulike:1903787} 1406\item Rosenbrock's parabolic valley \cite{citeulike:1903787}
@@ -1548,7 +1635,7 @@ Scilab & 4 & 616 & 3 & 3.370756e-008 & 402 & 2.949000 \\
1548\label{fig-nm-oneill-table} 1635\label{fig-nm-oneill-table}
1549\end{figure} 1636\end{figure}
1550 1637
1551\subsection{Convergence to a non stationnary point} 1638\subsection{Mc Kinnon: convergence to a non stationnary point}
1552\label{section-mcKinnon} 1639\label{section-mcKinnon}
1553\index{Mc Kinnon, K. I. M.} 1640\index{Mc Kinnon, K. I. M.}
1554 1641
@@ -1652,6 +1739,10 @@ f(x_1,x_2) &=&
1652The solution is $\bx^\star = (0 , -0.5 )^T$. 1739The solution is $\bx^\star = (0 , -0.5 )^T$.
1653 1740
1654The following Scilab script solves the optimization problem. 1741The following Scilab script solves the optimization problem.
1742We must use the "-simplex0method" option so that a
1743user-defined initial simplex is used. Then the
1744"-coords0" allows to define the coordinates of the initial
1745simplex, where each row corresponds to a vertex of the simplex
1655 1746
1656\lstset{language=scilabscript} 1747\lstset{language=scilabscript}
1657\begin{lstlisting} 1748\begin{lstlisting}
@@ -1676,21 +1767,19 @@ coords0 = [
1676lambda1 lambda2 1767lambda1 lambda2
1677]; 1768];
1678x0 = [1.0 1.0]'; 1769x0 = [1.0 1.0]';
1679nm = nmplot_new (); 1770nm = neldermead_new ();
1680nm = nmplot_configure(nm,"-numberofvariables",2); 1771nm = neldermead_configure(nm,"-numberofvariables",2);
1681nm = nmplot_configure(nm,"-function",mckinnon3); 1772nm = neldermead_configure(nm,"-function",mckinnon3);
1682nm = nmplot_configure(nm,"-x0",x0); 1773nm = neldermead_configure(nm,"-x0",x0);
1683nm = nmplot_configure(nm,"-maxiter",200); 1774nm = neldermead_configure(nm,"-maxiter",200);
1684nm = nmplot_configure(nm,"-maxfunevals",300); 1775nm = neldermead_configure(nm,"-maxfunevals",300);
1685nm = nmplot_configure(nm,"-tolfunrelative",10*%eps); 1776nm = neldermead_configure(nm,"-tolfunrelative",10*%eps);
1686nm = nmplot_configure(nm,"-tolxrelative",10*%eps); 1777nm = neldermead_configure(nm,"-tolxrelative",10*%eps);
1687nm = nmplot_configure(nm,"-simplex0method","given"); 1778nm = neldermead_configure(nm,"-simplex0method","given");
1688nm = nmplot_configure(nm,"-coords0",coords0); 1779nm = neldermead_configure(nm,"-coords0",coords0);
1689nm = nmplot_configure(nm,"-simplex0length",1.0); 1780nm = neldermead_search(nm);
1690nm = nmplot_configure(nm,"-method","variable"); 1781neldermead_display(nm);
1691nm = nmplot_search(nm); 1782nm = neldermead_destroy(nm);
1692nmplot_display(nm);
1693nm = nmplot_destroy(nm);
1694\end{lstlisting} 1783\end{lstlisting}
1695 1784
1696 1785
@@ -1726,6 +1815,92 @@ inside contractions.}
1726\label{fig-nm-numexp-mckinnon-detail} 1815\label{fig-nm-numexp-mckinnon-detail}
1727\end{figure} 1816\end{figure}
1728 1817
1818\subsection{Kelley: oriented restart}
1819\index{Kelley, C. T.}
1820
1821Kelley analyzed Mc Kinnon counter example in \cite{Kelley1999}.
1822He analyzed the evolution of the simplex gradient and found that
1823its norm begins to grow when the simplex start to degenerate.
1824Therefore, Kelley suggest to detect the stagnation of the algorithm
1825by using a termination criteria which is based on a sufficient decrease
1826condition. Once that the stagnation is detected and the algorithm is stopped,
1827restarting the algorithm with a non-degenerated simplex allows to
1828converge toward the global minimum. Kelley advocates the use of the oriented
1829restart, where the new simplex is so that it maximizes the chances of
1830producing a good descent direction at the next iteration.
1831
1832The following Scilab script solves the optimization problem.
1833We must use the "-simplex0method" option so that a
1834user-defined initial simplex is used. Then the
1835"-coords0" allows to define the coordinates of the initial
1836simplex, where each row corresponds to a vertex of the simplex.
1837
1838We also use the "-kelleystagnationflag" option, which turns on
1839the termination criteria associated with Kelley's stagnation
1840detection method. Once that the algorithm is stopped, we want
1841to automatically restart the algorithm. This is why we
1842turn on the "-restartflag" option, which enables to perform
1843automatically 3 restarts. After an optimization process, the
1844automatic restart algorithm needs to know if the algorithm
1845must restart or not. By default, the algorithm uses a
1846factorial test, due to O'Neill. This is why we configure the
1847"-restartdetection" to the "kelley" option, which uses Kelley's
1848termination condition as a criteria to determine
1849if a restart must be performed.
1850
1851\lstset{language=scilabscript}
1852\begin{lstlisting}
1853function [ f , index ] = mckinnon3 ( x , index )
1854 if ( length ( x ) ~= 2 )
1855 error ( 'Error: function expects a two dimensional input\n' );
1856 end
1857 tau = 3.0;
1858 theta = 6.0;
1859 phi = 400.0;
1860 if ( x(1) <= 0.0 )
1861 f = theta * phi * abs ( x(1) ).^tau + x(2) * ( 1.0 + x(2) );
1862 else
1863 f = theta * x(1).^tau + x(2) * ( 1.0 + x(2) );
1864 end
1865endfunction
1866lambda1 = (1.0 + sqrt(33.0))/8.0;
1867lambda2 = (1.0 - sqrt(33.0))/8.0;
1868coords0 = [
18691.0 1.0
18700.0 0.0
1871lambda1 lambda2
1872];
1873x0 = [1.0 1.0]';
1874nm = neldermead_new ();
1875nm = neldermead_configure(nm,"-numberofvariables",2);
1876nm = neldermead_configure(nm,"-function",mckinnon3);
1877nm = neldermead_configure(nm,"-x0",x0);
1878nm = neldermead_configure(nm,"-maxiter",200);
1879nm = neldermead_configure(nm,"-maxfunevals",300);
1880nm = neldermead_configure(nm,"-tolsimplexizerelative",1.e-6);
1881nm = neldermead_configure(nm,"-simplex0method","given");
1882nm = neldermead_configure(nm,"-coords0",coords0);
1883nm = neldermead_configure(nm,"-kelleystagnationflag",%t);
1884nm = neldermead_configure(nm,"-restartflag",%t);
1885nm = neldermead_configure(nm,"-restartdetection","kelley");
1886nm = neldermead_search(nm);
1887neldermead_display(nm);
1888nm = neldermead_destroy(nm);
1889\end{lstlisting}
1890
1891The figure \ref{fig-nm-numexp-mckinnonkelley} presents the first steps
1892of the algorithm in this numerical experiment. We see that the
1893algorithm converges now toward the minimum $\bx^\star = (0,-0.5)^T$.
1894
1895\begin{figure}
1896\begin{center}
1897\includegraphics[width=10cm]{neldermeadmethod/mckinnonkelley-history-simplex.png}
1898\end{center}
1899\caption{Nelder-Mead numerical experiment -- Mc Kinnon example with Kelley's stagnation detection.}
1900\label{fig-nm-numexp-mckinnonkelley}
1901\end{figure}
1902
1903
1729\subsection{Han counter examples} 1904\subsection{Han counter examples}
1730 1905
1731In his Phd thesis \cite{Han2000}, Han presents two counter examples 1906In his Phd thesis \cite{Han2000}, Han presents two counter examples