34254ac26b04bdae7e8293fef569170ec0fb67c2
[scilab.git] / 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>The internal design of the system is based on 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 toolbox is based on (and therefore requires) the
76     following toolboxes </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>