Finished help for fminsearch
[scilab.git] / scilab / modules / optimization / help / en_US / neldermead / fminsearch.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="fminsearch" 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>fminsearch</refname>
18
19     <refpurpose>Computes the unconstrained minimimum of given function with
20     the Nelder-Mead algorithm.</refpurpose>
21   </refnamediv>
22
23   <refsynopsisdiv>
24     <title>SYNOPSIS</title>
25
26     <synopsis>
27       x = fminsearch ( costf , x0 )
28       x = fminsearch ( costf , x0 , options )
29       [x,fval,exitflag,output] = fminsearch ( costf , x0 , options )
30     </synopsis>
31   </refsynopsisdiv>
32
33   <refsection>
34     <title>Description</title>
35
36     <para>This function searches for the unconstrained minimum of a given cost
37     function.</para>
38
39     <para>The provided algorithm is a direct search algorithm, i.e. an
40     algorithm which does not use the derivative of the cost function. It is
41     based on the update of a simplex, which is a set of k&gt;=n+1 vertices,
42     where each vertex is associated with one point and one function value.
43     This algorithm is the Nelder-Mead algorithm.</para>
44
45     <para>This function is based on a specialized use of the more general
46     neldermead component. Users which want to have a more flexible solution
47     based on direct search algorithms should consider using the neldermead
48     component instead of the fminsearch function.</para>
49   </refsection>
50
51   <refsection>
52     <title>Parameters</title>
53
54     <variablelist>
55       <varlistentry>
56         <term>costf</term>
57
58         <listitem>
59           <para>The cost function.</para>
60         </listitem>
61       </varlistentry>
62
63       <varlistentry>
64         <term>x0</term>
65
66         <listitem>
67           <para>The initial guess.</para>
68         </listitem>
69       </varlistentry>
70
71       <varlistentry>
72         <term>options</term>
73
74         <listitem>
75           <para>A struct which contains configurable options of the algorithm
76           (see below for details).</para>
77         </listitem>
78       </varlistentry>
79
80       <varlistentry>
81         <term>x</term>
82
83         <listitem>
84           <para>The minimum.</para>
85         </listitem>
86       </varlistentry>
87
88       <varlistentry>
89         <term>fval</term>
90
91         <listitem>
92           <para>The minimum function value.</para>
93         </listitem>
94       </varlistentry>
95
96       <varlistentry>
97         <term>exitflag</term>
98
99         <listitem>
100           <para>The flag associated with exist status of the algorithm.</para>
101
102           <para>The following values are available.</para>
103
104           <variablelist>
105             <varlistentry>
106               <term>-1</term>
107
108               <listitem>
109                 <para>The maximum number of iterations has been
110                 reached.</para>
111               </listitem>
112             </varlistentry>
113
114             <varlistentry>
115               <term>0</term>
116
117               <listitem>
118                 <para>The maximum number of function evaluations has been
119                 reached.</para>
120               </listitem>
121             </varlistentry>
122
123             <varlistentry>
124               <term>1</term>
125
126               <listitem>
127                 <para>The tolerance on the simplex size and function value
128                 delta has been reached. This signifies that the algorithm has
129                 converged, probably to a solution of the problem.</para>
130               </listitem>
131             </varlistentry>
132           </variablelist>
133         </listitem>
134       </varlistentry>
135
136       <varlistentry>
137         <term>output</term>
138
139         <listitem>
140           <para>A struct which stores detailed information about the exit of
141           the algorithm. This struct contains the following fields.</para>
142
143           <variablelist>
144             <varlistentry>
145               <term>output.algorithm</term>
146
147               <listitem>
148                 <para>A string containing the definition of the algorithm
149                 used, i.e. 'Nelder-Mead simplex direct search'.</para>
150               </listitem>
151             </varlistentry>
152
153             <varlistentry>
154               <term>output.funcCount</term>
155
156               <listitem>
157                 <para>The number of function evaluations.</para>
158               </listitem>
159             </varlistentry>
160
161             <varlistentry>
162               <term>output.iterations</term>
163
164               <listitem>
165                 <para>The number of iterations.</para>
166               </listitem>
167             </varlistentry>
168
169             <varlistentry>
170               <term>output.message</term>
171
172               <listitem>
173                 <para>A string containing a termination message.</para>
174               </listitem>
175             </varlistentry>
176           </variablelist>
177         </listitem>
178       </varlistentry>
179     </variablelist>
180   </refsection>
181
182   <refsection>
183     <title>Options</title>
184
185     <para>In this section, we describe the options input argument which have
186     an effect on the algorithm used by fminsearch.</para>
187
188     <para>The options input argument is a data structure which drives the
189     behaviour of fminsearch. It allows to handle several options in a
190     consistent and simple interface, without the problem of managing many
191     input arguments.</para>
192
193     <para>The fminsearch function is sensitive to the following
194     options.</para>
195
196     <variablelist>
197       <varlistentry>
198         <term>options.MaxIter</term>
199
200         <listitem>
201           <para>The maximum number of iterations. The default is 200 * n,
202           where n is the number of variables.</para>
203         </listitem>
204       </varlistentry>
205
206       <varlistentry>
207         <term>options.MaxFunEvals</term>
208
209         <listitem>
210           <para>The maximum number of evaluations of the cost function. The
211           default is 200 * n, where n is the number of variables.</para>
212         </listitem>
213       </varlistentry>
214
215       <varlistentry>
216         <term>options.TolFun</term>
217
218         <listitem>
219           <para>The absolute tolerance on function value. The default value is
220           1.e-4.</para>
221         </listitem>
222       </varlistentry>
223
224       <varlistentry>
225         <term>options.TolX</term>
226
227         <listitem>
228           <para>The absolute tolerance on simplex size. The default value is
229           1.e-4.</para>
230         </listitem>
231       </varlistentry>
232     </variablelist>
233   </refsection>
234
235   <refsection>
236     <title>Termination criteria</title>
237
238     <para>In this section, we describe the termination criteria used by
239     fminsearch.</para>
240
241     <para>The criteria is based on the following variables:</para>
242
243     <variablelist>
244       <varlistentry>
245         <term>ssize</term>
246
247         <listitem>
248           <para>the current simplex size,</para>
249         </listitem>
250       </varlistentry>
251
252       <varlistentry>
253         <term>shiftfv</term>
254
255         <listitem>
256           <para>the absolute value of the difference of function value between
257           the highest and lowest vertices.</para>
258         </listitem>
259       </varlistentry>
260     </variablelist>
261
262     <para>If both the following conditions</para>
263
264     <programlisting role="example">ssize &lt; options.TolX</programlisting>
265
266     <para>and</para>
267
268     <programlisting role="example">shiftfv &lt; options.TolFun</programlisting>
269
270     <para>are true, then the iterations stop.</para>
271
272     <para>The size of the simplex is computed using the "sigmaplus" method of
273     the optimsimplex component. The "sigmamplus" size is the maximum length of
274     the vector from each vertex to the first vertex. It requires one loop over
275     the vertices of the simplex.</para>
276   </refsection>
277
278   <refsection>
279     <title>The initial simplex</title>
280
281     <para>The fminsearch algorithm uses a special initial simplex, which is an
282     heuristic depending on the initial guess. The strategy chosen by
283     fminsearch corresponds to the -simplex0method flag of the neldermead
284     component, with the "pfeffer" method. It is associated with the
285     -simplex0deltausual = 0.05 and -simplex0deltazero = 0.0075 parameters.
286     Pfeffer's method is an heuristic which is presented in "Global
287     Optimization Of Lennard-Jones Atomic Clusters" by Ellen Fan. It is due to
288     L. Pfeffer at Stanford. See in the help of optimsimplex for more
289     details.</para>
290   </refsection>
291
292   <refsection>
293     <title>The number of iterations</title>
294
295     <para>In this section, we present the default values for the number of
296     iterations in fminsearch.</para>
297
298     <para>The <parameter>options</parameter> input argument is an optionnal
299     data structure which can contain the
300     <parameter>options.MaxIter</parameter> field. It stores the maximum number
301     of iterations. The default value is 200n, where n is the number of
302     variables. The factor 200 has not been chosen by chance, but is the result
303     of experiments performed against quadratic functions with increasing space
304     dimension.</para>
305
306     <para>This result is presented in "Effect of dimensionality on the
307     nelder-mead simplex method" by Lixing Han and Michael Neumann. This paper
308     is based on Lixing Han's PhD, "Algorithms in Unconstrained Optimization".
309     The study is based on numerical experiment with a quadratic function where
310     the number of terms depends on the dimension of the space (i.e. the number
311     of variables). Their study shows that the number of iterations required to
312     reach the tolerance criteria is roughly 100n. Most iterations are based on
313     inside contractions. Since each step of the Nelder-Mead algorithm only
314     require one or two function evaluations, the number of required function
315     evaluations in this experiment is also roughly 100n.</para>
316   </refsection>
317
318   <refsection>
319     <title>Example</title>
320
321     <para>In the following example, we use the fminsearch function to compute
322     the minimum of the Rosenbrock function. We first define the function
323     "banana", and then use the fminsearch function to search the minimum,
324     starting with the initial guess [-1.2 1.0].</para>
325
326     <programlisting role="example">
327       function y = banana (x)
328       y = 100*(x(2)-x(1)^2)^2 + (1-x(1))^2;
329       endfunction
330       [x , fval , exitflag , output] = fminsearch ( banana , [-1.2 1] );
331     </programlisting>
332   </refsection>
333
334   <refsection>
335     <title>Bibliography</title>
336
337     <para>"Sequential Application of Simplex Designs in Optimisation and
338     Evolutionary Operation", Spendley, W. and Hext, G. R. and Himsworth, F.
339     R., American Statistical Association and American Society for Quality,
340     1962</para>
341
342     <para>"A Simplex Method for Function Minimization", Nelder, J. A. and
343     Mead, R., The Computer Journal, 1965</para>
344
345     <para>"Iterative Methods for Optimization", C. T. Kelley, SIAM Frontiers
346     in Applied Mathematics, 1999</para>
347
348     <para>"Algorithm AS47 - Function minimization using a simplex procedure",
349     O'Neill, R., Applied Statistics, 1971</para>
350
351     <para>"Effect of dimensionality on the nelder-mead simplex method", Lixing
352     Han and Michael Neumann, Optimization Methods and Software, 21, 1, 1--16,
353     2006.</para>
354
355     <para>"Algorithms in Unconstrained Optimization", Lixing Han, Ph.D., The
356     University of Connecticut, 2000.</para>
357   </refsection>
358
359   <refsection>
360     <title>Authors</title>
361
362     <para>Michael Baudin, 2008-2009</para>
363   </refsection>
364
365   <refsection>
366     <title>Acknowledgements</title>
367
368     <para>Michael Baudin would like to thank Lixing Han, who kindly sent his
369     PhD thesis.</para>
370   </refsection>
371 </refentry>