scilab/modules/optimization/help/en_US/neldermead/overview.xml

   1 <?xml version="1.0" encoding="ISO-8859-1"?>
   2 <!--
   3  * Ajouter ici d'éventuels commentaires sur le fichier XML
   4 -->
   5 <refentry version="5.0-subset Scilab" xml:id="neldermead_overview" xml:lang="fr"
   6           xmlns="http://docbook.org/ns/docbook"
   7           xmlns:xlink="http://www.w3.org/1999/xlink"
   8           xmlns:svg="http://www.w3.org/2000/svg"
   9           xmlns:ns4="http://www.w3.org/1999/xhtml"
  10           xmlns:mml="http://www.w3.org/1998/Math/MathML"
  11           xmlns:db="http://docbook.org/ns/docbook">
  12   <info>
  13     <pubdate>$LastChangedDate: 16-12-2008 $</pubdate>
  14   </info>
  15
  16   <refnamediv>
  17     <refname>overview</refname>
  18
  19     <refpurpose>An overview of the Nelder-Mead toolbox.</refpurpose>
  20   </refnamediv>
  21
  22   <refsection>
  23     <title>Purpose</title>
  24
  25     <para>The goal of this toolbox is to provide a Nelder-Mead direct search
  26     optimization method. That Nelder-Mead algorithm may be used in the
  27     following optimization context :<itemizedlist>
  28         <listitem>
  29           <para>there is no need to provide the derivatives of the objective
  30           function,</para>
  31         </listitem>
  32
  33         <listitem>
  34           <para>the number of parameters is small (up to 10-20),</para>
  35         </listitem>
  36
  37         <listitem>
  38           <para>there are bounds and/or non linear constraints.</para>
  39         </listitem>
  40       </itemizedlist></para>
  41   </refsection>
  42
  43   <refsection>
  44     <title>Design</title>
  45
  46     <para>This package provides the following
  47     components :</para>
  48
  49     <itemizedlist>
  50       <listitem>
  51         <para>&#8220;neldermead&#8221; provides various Nelder-Mead variants
  52         and manages for Nelder-Mead specific settings, such as the method to
  53         compute the initial simplex, the specific termination criteria,</para>
  54       </listitem>
  55
  56       <listitem>
  57         <para>&#8220;fminsearch&#8221; provides a Scilab commands which aims
  58         at behaving as Matlab's fminsearch. Specific terminations criteria,
  59         initial simplex and auxiliary settings are automatically configured so
  60         that the behaviour of Matlab's fminsearch is exactly
  61         reproduced.</para>
  62       </listitem>
  63
  64       <listitem>
  65         <para>&#8220;optimset&#8221;, &#8220;optimget&#8221; provides Scilab
  66         commands to emulate their Matlab counterparts.</para>
  67       </listitem>
  68
  69       <listitem>
  70         <para>&#8220;nmplot&#8221; provides a high-level component which
  71         provides directly output pictures for Nelder-Mead algorithm.</para>
  72       </listitem>
  73     </itemizedlist>
  74
  75     <para>The current component is based on the
  76     following components </para>
  77
  78     <itemizedlist>
  79       <listitem>
  80         <para>&#8220;optimbase&#8221; provides an abstract class for a general
  81         optimization component, including the number of variables, the minimum
  82         and maximum bounds, the number of non linear inequality constraints,
  83         the loggin system, various termination criteria, the cost function,
  84         etc...</para>
  85       </listitem>
  86
  87       <listitem>
  88         <para>&#8220;optimsimplex&#8221; provides a class to manage a simplex
  89         made of an arbitrary number of vertices, including the computation of
  90         a simplex by various methods (axes, regular, Pfeffer's, randomized
  91         bounds), the computation of the size by various methods (diameter,
  92         sigma +, sigma-, etc...),</para>
  93       </listitem>
  94     </itemizedlist>
  95   </refsection>
  96
  97   <refsection>
  98     <title>Features</title>
  99
 100     <para>The following is a list of features the Nelder-Mead prototype
 101     algorithm currently provides :</para>
 102
 103     <itemizedlist>
 104       <listitem>
 105         <para>Manage various simplex initializations</para>
 106
 107         <itemizedlist>
 108           <listitem>
 109             <para>initial simplex given by user,</para>
 110           </listitem>
 111
 112           <listitem>
 113             <para>initial simplex computed with a length and along the
 114             coordinate axes,</para>
 115           </listitem>
 116
 117           <listitem>
 118             <para>initial regular simplex computed with Spendley et al.
 119             formula</para>
 120           </listitem>
 121
 122           <listitem>
 123             <para>initial simplex computed by a small perturbation around the
 124             initial guess point</para>
 125           </listitem>
 126         </itemizedlist>
 127       </listitem>
 128
 129       <listitem>
 130         <para>Manage cost function</para>
 131
 132         <itemizedlist>
 133           <listitem>
 134             <para>optionnal additionnal argument</para>
 135           </listitem>
 136
 137           <listitem>
 138             <para>direct communication of the task to perform : cost function
 139             or inequality constraints</para>
 140           </listitem>
 141         </itemizedlist>
 142       </listitem>
 143
 144       <listitem>
 145         <para>Manage various termination criteria, including maximum number of
 146         iterations, tolerance on function value (relative or absolute),
 147         <itemizedlist>
 148             <listitem>
 149               <para>tolerance on x (relative or absolute),</para>
 150             </listitem>
 151
 152             <listitem>
 153               <para>tolerance on standard deviation of function value
 154               (original termination criteria in [3]),</para>
 155             </listitem>
 156
 157             <listitem>
 158               <para>maximum number of evaluations of cost function,</para>
 159             </listitem>
 160
 161             <listitem>
 162               <para>absolute or relative simplex size,</para>
 163             </listitem>
 164           </itemizedlist></para>
 165       </listitem>
 166
 167       <listitem>
 168         <para>Manage the history of the convergence, including</para>
 169
 170         <itemizedlist>
 171           <listitem>
 172             <para>history of function values,</para>
 173           </listitem>
 174
 175           <listitem>
 176             <para>history of optimum point,</para>
 177           </listitem>
 178
 179           <listitem>
 180             <para>history of simplices,</para>
 181           </listitem>
 182
 183           <listitem>
 184             <para>history of termination criterias,</para>
 185           </listitem>
 186         </itemizedlist>
 187       </listitem>
 188
 189       <listitem>
 190         <para>Provide a plot command which allows to graphically see the
 191         history of the simplices toward the optimum,</para>
 192       </listitem>
 193
 194       <listitem>
 195         <para>Provide query features for the status of the optimization
 196         process number of iterations, number of function evaluations, status
 197         of execution, function value at initial point, function value at
 198         optimal point, etc...</para>
 199       </listitem>
 200
 201       <listitem>
 202         <para>Spendley et al. fixed shaped algorithm,</para>
 203       </listitem>
 204
 205       <listitem>
 206         <para>Kelley restart based on simplex gradient,</para>
 207       </listitem>
 208
 209       <listitem>
 210         <para>O'Neill restart based on factorial search around optimum,</para>
 211       </listitem>
 212
 213       <listitem>
 214         <para>Box-like method managing bounds and nonlinear inequality
 215         constraints based on arbitrary number of vertices in the
 216         simplex.</para>
 217       </listitem>
 218     </itemizedlist>
 219   </refsection>
 220
 221   <refsection>
 222     <title>TODO</title>
 223
 224     <para><itemizedlist>
 225         <listitem>
 226           <para>implement "optimget"</para>
 227         </listitem>
 228
 229         <listitem>
 230           <para>provide the original Box method</para>
 231         </listitem>
 232
 233         <listitem>
 234           <para>implement parabolic line search</para>
 235         </listitem>
 236       </itemizedlist></para>
 237   </refsection>
 238
 239   <refsection>
 240     <title>Example : Optimizing the Rosenbrock function</title>
 241
 242     <para>In the following example, one searches the minimum of the 2D
 243     Rosenbrock function. One begins by defining the function "rosenbrock"
 244     which computes the Rosenbrock function. The traditionnal initial guess
 245     [-1.2 1.0] is used. The initial simplex is computed along the axes with a
 246     length equal to 0.1. The Nelder-Mead algorithm with variable simplex size
 247     is used. The verbose mode is enabled so that messages are generated during
 248     the algorithm. After the optimization is performed, the optimum is
 249     retrieved with quiery features.</para>
 250
 251     <programlisting role="example">
 252 function y = rosenbrock (x)
 253   y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
 254 endfunction
 255
 256 nm = neldermead_new ();
 257 nm = neldermead_configure(nm,"-x0",[-1.2 1.0]');
 258 nm = neldermead_configure(nm,"-simplex0method","axes");
 259 nm = neldermead_configure(nm,"-simplex0length",0.1);
 260 nm = neldermead_configure(nm,"-method","variable");
 261 nm = neldermead_configure(nm,"-verbose",1);
 262 nm = neldermead_configure(nm,"-function",rosenbrock);
 263 nm = neldermead_search(nm);
 264 xopt = neldermead_get(nm,"-xopt");
 265 fopt = neldermead_get(nm,"-fopt");
 266 historyfopt = neldermead_get(nm,"-historyfopt");
 267 iterations = neldermead_get(nm,"-iterations");
 268 historyxopt = neldermead_get(nm,"-historyxopt");
 269 historysimplex = neldermead_get(nm,"-historysimplex");
 270 fx0 = neldermead_get(nm,"-fx0");
 271 status = neldermead_get(nm,"-status");
 272 nm = neldermead_destroy(nm);
 273     </programlisting>
 274   </refsection>
 275
 276   <refsection>
 277     <title>Authors</title>
 278
 279     <para>Michael Baudin, 2008-2009</para>
 280   </refsection>
 281
 282   <refsection>
 283     <title>Bibliography</title>
 284
 285     <para>&#8220;Sequential Application of Simplex Designs in Optimisation and
 286     Evolutionary Operation&#8221;, Spendley, W. and Hext, G. R. and Himsworth,
 287     F. R., American Statistical Association and American Society for Quality,
 288     1962</para>
 289
 290     <para>&#8220;A Simplex Method for Function Minimization&#8221;, Nelder, J.
 291     A. and Mead, R., The Computer Journal, 1965</para>
 292
 293     <para>"A New Method of Constrained Optimization and a Comparison With
 294     Other Methods", M. J. Box, The Computer Journal 1965 8(1):42-52, 1965 by
 295     British Computer Society</para>
 296
 297     <para>&#8220;Convergence Properties of the Nelder--Mead Simplex Method in
 298     Low Dimensions&#8221;, Jeffrey C. Lagarias and James A. Reeds and Margaret
 299     H. Wright and Paul E. Wright, SIAM Journal on Optimization, 1998</para>
 300
 301     <para>&#8220;Compact numerical methods for computers : linear algebra and
 302     function minimisation&#8221;, Nash, J. C., Hilger, Bristol, 1979</para>
 303
 304     <para>&#8220;Iterative Methods for Optimization&#8221;, C. T. Kelley,
 305     1999</para>
 306
 307     <para>&#8220;Iterative Methods for Optimization: Matlab Codes&#8221;,
 308     http://www4.ncsu.edu/~ctk/matlab_darts.html</para>
 309
 310     <para>&#8220;Sequential Simplex Optimization: A Technique for Improving
 311     Quality and Productivity in Research, Development, and
 312     Manufacturing&#8221;, Walters, Fred H. and Jr, Lloyd R. and Morgan,
 313     Stephen L. and Deming, Stanley N., 1991</para>
 314
 315     <para>&#8220;Numerical Recipes in C, Second Edition&#8221;, W. H. Press
 316     and Saul A. Teukolsky and William T. Vetterling and Brian P. Flannery,
 317     1992</para>
 318
 319     <para>&#8220;Detection and Remediation of Stagnation in the Nelder--Mead
 320     Algorithm Using a Sufficient Decrease Condition&#8221;, SIAM J. on
 321     Optimization, Kelley,, C. T., 1999</para>
 322
 323     <para>Matlab &#8211; fminsearch ,
 324     http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/fminsearch.html</para>
 325
 326     <para>GAMS, A19A20 - description,
 327     http://gams.nist.gov/serve.cgi/Module/NASHLIB/A19A20/11238/</para>
 328
 329     <para>asa047.f,
 330     http://people.sc.fsu.edu/~burkardt/f77_src/asa047/asa047.f</para>
 331
 332     <para>optim1.f,
 333     http://www.stat.uconn.edu/~mhchen/survbook/example51/optim1.f</para>
 334
 335     <para>as47,f, http://lib.stat.cmu.edu/apstat/47</para>
 336
 337     <para>&#8220;Algorithm AS47 - Function minimization using a simplex
 338     procedure, O'Neill, R., 1971, Applied Statistics</para>
 339   </refsection>
 340 </refentry>