Deleted vectorized computation feature. Deleted neldermead_contour. Fixed the demos.
[scilab.git] / scilab / modules / optimization / help / en_US / neldermead / neldermead.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" 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>neldermead</refname>
18
19     <refpurpose>Provides several direct search optimization algorithms based
20     on the simplex method.</refpurpose>
21   </refnamediv>
22
23   <refsynopsisdiv>
24     <title>SYNOPSIS</title>
25
26     <synopsis>
27 newobj = neldermead_new ()
28 this = neldermead_destroy (this)
29 this = neldermead_configure (this,key,value)
30 value = neldermead_cget (this,key)
31 this = neldermead_display ( this )
32 value = neldermead_get ( this , key )
33 this = neldermead_search ( this )
34 this = neldermead_restart ( this )
35 </synopsis>
36   </refsynopsisdiv>
37
38   <refsection>
39     <title>Description</title>
40
41     <para>This class provides several direct search optimization algorithms
42     based on the simplex method.</para>
43
44     <para>The optimization problem to solve is the minimization of a cost
45     function, with bounds and nonlinear constraints</para>
46
47     <programlisting role="example"> 
48 min f(x)
49 l_i &lt;= x_i &lt;= h_i, i = 1,n
50 g_i(x) &lt;= 0, i = 1,nbineq
51  </programlisting>
52
53     <para>where</para>
54
55     <variablelist>
56       <varlistentry>
57         <term>n</term>
58
59         <listitem>
60           <para>number of variables</para>
61         </listitem>
62       </varlistentry>
63
64       <varlistentry>
65         <term>nbineq</term>
66
67         <listitem>
68           <para>number of inequality constraints</para>
69         </listitem>
70       </varlistentry>
71     </variablelist>
72
73     <para>The provided algorithms are direct search algorithms, i.e.
74     algorithms which do not use the derivative of the cost function. They are
75     based on the update of a simplex, which is a set of k&gt;=n+1 vertices,
76     where each vertex is associated with one point and one function
77     value.</para>
78
79     <para>The following algorithms are available :</para>
80
81     <variablelist>
82       <varlistentry>
83         <term>Spendley, Hext and Himsworth fixed size simplex method</term>
84
85         <listitem>
86           <para>This algorithm solves an unconstrained optimization problem
87           with a fixed sized simplex made of k=n+1 vertices.</para>
88         </listitem>
89       </varlistentry>
90
91       <varlistentry>
92         <term>Nelder and Mead variable size simplex method</term>
93
94         <listitem>
95           <para>This algorithm solves an unconstrained optimization problem
96           with a variable sized simplex made of k=n+1 vertices.</para>
97         </listitem>
98       </varlistentry>
99
100       <varlistentry>
101         <term>Box complex method</term>
102
103         <listitem>
104           <para>This algorithm solves an constrained optimization problem with
105           a variable sized simplex made of an arbitrary k number of vertices
106           (k=2n is recommended by Box).</para>
107         </listitem>
108       </varlistentry>
109     </variablelist>
110   </refsection>
111
112   <refsection>
113     <title>Design</title>
114
115     <para>The neldermead component is built on top of the <link
116     linkend="optimbase">optimbase</link> and <link
117     linkend="optimsimplex">optimsimplex</link> components.</para>
118   </refsection>
119
120   <refsection>
121     <title>Functions</title>
122
123     <para>The following functions are available.</para>
124
125     <variablelist>
126       <varlistentry>
127         <term>newobj = neldermead_new ()</term>
128
129         <listitem>
130           <para>Creates a new neldermead object.</para>
131
132           <variablelist>
133             <varlistentry>
134               <term>newobj</term>
135
136               <listitem>
137                 <para>The new object.</para>
138               </listitem>
139             </varlistentry>
140           </variablelist>
141         </listitem>
142       </varlistentry>
143
144       <varlistentry>
145         <term>this = neldermead_destroy (this)</term>
146
147         <listitem>
148           <para>Destroy the given object.</para>
149
150           <variablelist>
151             <varlistentry>
152               <term>this</term>
153
154               <listitem>
155                 <para>The current object.</para>
156               </listitem>
157             </varlistentry>
158           </variablelist>
159         </listitem>
160       </varlistentry>
161
162       <varlistentry>
163         <term>this = neldermead_configure (this,key,value)</term>
164
165         <listitem>
166           <para>Configure the current object with the given value for the
167           given key.</para>
168
169           <variablelist>
170             <varlistentry>
171               <term>this</term>
172
173               <listitem>
174                 <para>The current object.</para>
175               </listitem>
176             </varlistentry>
177
178             <varlistentry>
179               <term>key</term>
180
181               <listitem>
182                 <para>the key to configure. The following keys are
183                 available.</para>
184
185                 <variablelist>
186                   <varlistentry>
187                     <term>-verbose</term>
188
189                     <listitem>
190                       <para>set to 1 to enable verbose logging. (default is
191                       0)</para>
192                     </listitem>
193                   </varlistentry>
194
195                   <varlistentry>
196                     <term>-verbosetermination</term>
197
198                     <listitem>
199                       <para>set to 1 to enable verbose termination logging.
200                       (default is 0)</para>
201                     </listitem>
202                   </varlistentry>
203
204                   <varlistentry>
205                     <term>-x0</term>
206
207                     <listitem>
208                       <para>the initial guess, as a n x 1 column vector, where
209                       n is the number of variables.</para>
210                     </listitem>
211                   </varlistentry>
212
213                   <varlistentry>
214                     <term>-maxfunevals</term>
215
216                     <listitem>
217                       <para>the maximum number of function evalutations
218                       (default is 100). If this criteria is triggered, the
219                       status of the optimization is set to
220                       "maxfuneval".</para>
221                     </listitem>
222                   </varlistentry>
223
224                   <varlistentry>
225                     <term>-maxiter</term>
226
227                     <listitem>
228                       <para>the maximum number of iterations (default is 100).
229                       If this criteria is triggered, the status of the
230                       optimization is set to "maxiter".</para>
231                     </listitem>
232                   </varlistentry>
233
234                   <varlistentry>
235                     <term>-tolfunabsolute</term>
236
237                     <listitem>
238                       <para>the absolute tolerance for the function value
239                       (default is 0.0).</para>
240                     </listitem>
241                   </varlistentry>
242
243                   <varlistentry>
244                     <term>-tolfunrelative</term>
245
246                     <listitem>
247                       <para>the relative tolerance for the function value
248                       (default is %eps).</para>
249                     </listitem>
250                   </varlistentry>
251
252                   <varlistentry>
253                     <term>-tolfunmethod</term>
254
255                     <listitem>
256                       <para>the method used for the tolerance on function
257                       value in the termination criteria.</para>
258
259                       <para>The following values are available :
260                       "absolute+relative", "relative", "absolute", "disabled"
261                       (default is "disabled"). If this criteria is triggered,
262                       the status of the optimization is set to "tolf".</para>
263                     </listitem>
264                   </varlistentry>
265
266                   <varlistentry>
267                     <term>-tolxabsolute</term>
268
269                     <listitem>
270                       <para>the absolute tolerance on x (default is
271                       0.0).</para>
272                     </listitem>
273                   </varlistentry>
274
275                   <varlistentry>
276                     <term>-tolxrelative</term>
277
278                     <listitem>
279                       <para>the relative tolerance on x (default is
280                       %eps).</para>
281                     </listitem>
282                   </varlistentry>
283
284                   <varlistentry>
285                     <term>-tolxmethod</term>
286
287                     <listitem>
288                       <para>the method used for the tolerance on x in the
289                       termination criteria.</para>
290
291                       <para>The following values are available : "relative",
292                       "absolute", "disabled" (default is "relative"). If this
293                       criteria is triggered, the status of the optimization is
294                       set to "tolx".</para>
295                     </listitem>
296                   </varlistentry>
297
298                   <varlistentry>
299                     <term>-function</term>
300
301                     <listitem>
302                       <para>the objective function, which computes the value
303                       of the cost and the non linear constraints, if
304                       any.</para>
305
306                       <para>See below for the details of the communication
307                       between the optimization system and the cost
308                       function.</para>
309                     </listitem>
310                   </varlistentry>
311
312                   <varlistentry>
313                     <term>-costfargument</term>
314
315                     <listitem>
316                       <para>an additionnal argument, passed to the cost
317                       function.</para>
318                     </listitem>
319                   </varlistentry>
320
321                   <varlistentry>
322                     <term>-outputcommand</term>
323
324                     <listitem>
325                       <para>a command which is called back for output.</para>
326
327                       <para>See below for the details of the communication
328                       between the optimization system and the output command
329                       function.</para>
330                     </listitem>
331                   </varlistentry>
332
333                   <varlistentry>
334                     <term>-outputcommandarg</term>
335
336                     <listitem>
337                       <para>an additionnal argument, passed to the output
338                       command.</para>
339                     </listitem>
340                   </varlistentry>
341
342                   <varlistentry>
343                     <term>-numberofvariables</term>
344
345                     <listitem>
346                       <para>the number of variables to optimize (default is
347                       0).</para>
348                     </listitem>
349                   </varlistentry>
350
351                   <varlistentry>
352                     <term>-storehistory</term>
353
354                     <listitem>
355                       <para>set to 1 to enable the history storing (default is
356                       0).</para>
357                     </listitem>
358                   </varlistentry>
359
360                   <varlistentry>
361                     <term>-boundsmin</term>
362
363                     <listitem>
364                       <para>the minimum bounds for the parameters, as an array
365                       of values (default is empty, i.e. there are no
366                       bounds).</para>
367                     </listitem>
368                   </varlistentry>
369
370                   <varlistentry>
371                     <term>-boundsmax</term>
372
373                     <listitem>
374                       <para>the maximum bounds for the parameters, as an array
375                       of values (default is empty, i.e. there are no
376                       bounds).</para>
377                     </listitem>
378                   </varlistentry>
379
380                   <varlistentry>
381                     <term>-nbineqconst</term>
382
383                     <listitem>
384                       <para>the number of inequality constraints (default is
385                       0)</para>
386                     </listitem>
387                   </varlistentry>
388
389                   <varlistentry>
390                     <term>-method</term>
391
392                     <listitem>
393                       <para>the name of the algorithm to use. The following
394                       methods are available :</para>
395
396                       <variablelist>
397                         <varlistentry>
398                           <term>"fixed"</term>
399
400                           <listitem>
401                             <para>the Spendley et al. fixed simplex shape
402                             algorithm. This algorithm is for unconstrained
403                             problems (i.e. bounds and non linear constraints are
404                             not taken into account)</para>
405                           </listitem>
406                         </varlistentry>
407
408                         <varlistentry>
409                           <term>"variable"</term>
410
411                           <listitem>
412                             <para>the Nelder-Mead variable simplex shape
413                             algorithm. This algorithm is for unconstrained
414                             problems (i.e. bounds and non linear constraints are
415                             not taken into account)</para>
416                           </listitem>
417                         </varlistentry>
418
419                         <varlistentry>
420                           <term>"box"</term>
421
422                           <listitem>
423                             <para>the Box complex algorithm. This algorithm
424                             takes into account bounds and nonlinear inequality
425                             constraints.</para>
426                           </listitem>
427                         </varlistentry>
428                       </variablelist>
429                     </listitem>
430                   </varlistentry>
431
432                   <varlistentry>
433                     <term>-simplex0method</term>
434
435                     <listitem>
436                       <para>the method to use to compute the initial simplex.
437                       The first vertex in the simplex is always the initial
438                       guess associated with the -x0 option. The following
439                       methods are available :</para>
440
441                       <variablelist>
442                         <varlistentry>
443                           <term>"given"</term>
444
445                           <listitem>
446                             <para>the coordinates associated with the -coords0
447                             option are used to compute the initial simplex, with
448                             arbitrary number of vertices.</para>
449
450                             <para>This allow the user to setup the initial
451                             simplex by a specific method which is not provided
452                             by the current component (for example with a simplex
453                             computed from a design of experiments). This allows
454                             also to configure the initial simplex so that a
455                             specific behaviour of the algorithm an be reproduced
456                             (for example the Mac Kinnon test case).</para>
457
458                             <para>The given matrix is expected to have n rows
459                             and k columns, where n is the dimension of the
460                             problem and k is the number of vertices.</para>
461                           </listitem>
462                         </varlistentry>
463
464                         <varlistentry>
465                           <term>"axes"</term>
466
467                           <listitem>
468                             <para>the simplex is computed from the coordinate
469                             axes and the length associated with the
470                             -simplex0length option.</para>
471                           </listitem>
472                         </varlistentry>
473
474                         <varlistentry>
475                           <term>"spendley"</term>
476
477                           <listitem>
478                             <para>the simplex is computed so that it is regular
479                             with the length associated with the -simplex0length
480                             option (i.e. all the edges have the same
481                             length).</para>
482                           </listitem>
483                         </varlistentry>
484
485                         <varlistentry>
486                           <term>"pfeffer"</term>
487
488                           <listitem>
489                             <para>the simplex is computed from an heuristic, in
490                             the neighborhood of the initial guess. This initial
491                             simplex depends on the -simplex0deltausual and
492                             -simplex0deltazero.</para>
493                           </listitem>
494                         </varlistentry>
495
496                         <varlistentry>
497                           <term>"randbounds"</term>
498
499                           <listitem>
500                             <para>the simplex is computed from the bounds and a
501                             random number. This option is available only if
502                             bounds are available : if bounds are not available,
503                             an error is generated. This method is usually
504                             associated with Box's algorithm. The number of
505                             vertices in the simplex is taken from the
506                             -boxnbpoints option.</para>
507                           </listitem>
508                         </varlistentry>
509                       </variablelist>
510                     </listitem>
511                   </varlistentry>
512
513                   <varlistentry>
514                     <term>-coords0</term>
515
516                     <listitem>
517                       <para>the coordinates of the vertices of the initial
518                       simplex. If the -simplex0method option is set to
519                       "given", these coordinates are used to compute the
520                       initial simplex. This matrix is expected to have shape
521                       nbve x n where nbve is the number of vertices and n is
522                       the number of variables.</para>
523                     </listitem>
524                   </varlistentry>
525
526                   <varlistentry>
527                     <term>-simplex0length</term>
528
529                     <listitem>
530                       <para>the length to use when the initial simplex is
531                       computed with the "axes" or "spendley" methods. If the
532                       initial simplex is computed from "spendley" method, the
533                       length is expected to be a scalar value. If the initial
534                       simplex is computed from "axes" method, it may be either
535                       a scalar value or a vector of values, with rank n, where
536                       n is the number of variables.</para>
537                     </listitem>
538                   </varlistentry>
539
540                   <varlistentry>
541                     <term>-simplex0deltausual</term>
542
543                     <listitem>
544                       <para>the relative delta for non-zero parameters in
545                       "pfeffer" method. The default value is 0.05.</para>
546                     </listitem>
547                   </varlistentry>
548
549                   <varlistentry>
550                     <term>-simplex0deltazero</term>
551
552                     <listitem>
553                       <para>the absolute delta for non-zero parameters in
554                       "pfeffer" method. The default value is 0.0075.</para>
555                     </listitem>
556                   </varlistentry>
557
558                   <varlistentry>
559                     <term>-rho</term>
560
561                     <listitem>
562                       <para>the reflection coefficient. This parameter is used
563                       when the -method option is set to "fixed" or "variable".
564                       The default value is 1.0.</para>
565                     </listitem>
566                   </varlistentry>
567
568                   <varlistentry>
569                     <term>-chi</term>
570
571                     <listitem>
572                       <para>the expansion coefficient. This parameter is used
573                       when the -method option is set to "variable". The
574                       default value is 2.0.</para>
575                     </listitem>
576                   </varlistentry>
577
578                   <varlistentry>
579                     <term>-gamma</term>
580
581                     <listitem>
582                       <para>the contraction coefficient. This parameter is
583                       used when the -method option is set to "variable". The
584                       default value is 0.5.</para>
585                     </listitem>
586                   </varlistentry>
587
588                   <varlistentry>
589                     <term>-sigma</term>
590
591                     <listitem>
592                       <para>the shrinkage coefficient. This parameter is used
593                       when the -method option is set to "fixed" or "variable".
594                       The default value is 0.5.</para>
595                     </listitem>
596                   </varlistentry>
597
598                   <varlistentry>
599                     <term>-tolfstdeviationmethod</term>
600
601                     <listitem>
602                       <para>set to "enabled" to enable the termination
603                       criteria based on the standard deviation of the function
604                       values in the simplex. The default value is "disabled".
605                       If this criteria is triggered, the status of the
606                       optimization is set to "tolfstdev".</para>
607
608                       <para>This criteria is suggested by Nelder and
609                       Mead.</para>
610                     </listitem>
611                   </varlistentry>
612
613                   <varlistentry>
614                     <term>-tolfstdeviation</term>
615
616                     <listitem>
617                       <para>the absolute tolerance on standard deviation. The
618                       default value is 0.0.</para>
619                     </listitem>
620                   </varlistentry>
621
622                   <varlistentry>
623                     <term>-tolsimplexizemethod</term>
624
625                     <listitem>
626                       <para>set to "disabled" to disable the tolerance on the
627                       simplex size. The default value is "enabled". If this
628                       criteria is triggered, the status of the optimization is
629                       set to "tolsize".</para>
630
631                       <para>When this criteria is enabled, the values of the
632                       options -tolsimplexizeabsolute and
633                       -tolsimplexizerelative are used in the termination
634                       criteria. The method to compute the size is the
635                       "sigmaplus" method.</para>
636                     </listitem>
637                   </varlistentry>
638
639                   <varlistentry>
640                     <term>-tolsimplexizeabsolute</term>
641
642                     <listitem>
643                       <para>the absolute tolerance on the simplex size. The
644                       default value is 0.0.</para>
645                     </listitem>
646                   </varlistentry>
647
648                   <varlistentry>
649                     <term>-tolsimplexizerelative</term>
650
651                     <listitem>
652                       <para>the relative tolerance on the simplex size. The
653                       default value is %eps.</para>
654                     </listitem>
655                   </varlistentry>
656
657                   <varlistentry>
658                     <term>-tolssizedeltafvmethod</term>
659
660                     <listitem>
661                       <para>set to "enabled" to enable the termination
662                       criteria based on the size of the simplex and the
663                       difference of function value in the simplex. The default
664                       value is "disabled". If this criteria is triggered, the
665                       status of the optimization is set to
666                       "tolsizedeltafv".</para>
667
668                       <para>This termination criteria uses the values of the
669                       options -tolsimplexizeabsolute and -toldeltafv. This
670                       criteria is identical to Matlab's fminsearch.</para>
671                     </listitem>
672                   </varlistentry>
673
674                   <varlistentry>
675                     <term>-toldeltafv</term>
676
677                     <listitem>
678                       <para>the absolute tolerance on the difference between
679                       the highest and the lowest function values.</para>
680                     </listitem>
681                   </varlistentry>
682
683                   <varlistentry>
684                     <term>-kelleystagnationflag</term>
685
686                     <listitem>
687                       <para>set to 1 to enable the termination criteria using
688                       Kelley's stagnation detection, based on sufficient
689                       decrease condition. The default value is 0. If this
690                       criteria is triggered, the status of the optimization is
691                       set to "kelleystagnation".</para>
692                     </listitem>
693                   </varlistentry>
694
695                   <varlistentry>
696                     <term>-kelleynormalizationflag</term>
697
698                     <listitem>
699                       <para>set to 0 to disable the normalization of the alpha
700                       coefficient in Kelley's stagnation detection, i.e. use
701                       the value of the option -kelleystagnationalpha0 as is.
702                       Default value is 1, i.e. the simplex gradient of the
703                       initial simplex is taken into account in the stagnation
704                       detection.</para>
705                     </listitem>
706                   </varlistentry>
707
708                   <varlistentry>
709                     <term>-kelleystagnationalpha0</term>
710
711                     <listitem>
712                       <para>the parameter used in Kelley's stagnation
713                       detection. The default value is 1.e-4.</para>
714                     </listitem>
715                   </varlistentry>
716
717                   <varlistentry>
718                     <term>-restartflag</term>
719
720                     <listitem>
721                       <para>set to 1 to enable the automatic restart of the
722                       algorithm. Default value is 0.</para>
723                     </listitem>
724                   </varlistentry>
725
726                   <varlistentry>
727                     <term>-restartdetection</term>
728
729                     <listitem>
730                       <para>the method to detect if the automatic restart must
731                       be performed. The following methods are available
732                       :</para>
733
734                       <variablelist>
735                         <varlistentry>
736                           <term>"oneill"</term>
737
738                           <listitem>
739                             <para>the factorial local optimality test by O'Neill
740                             is used. If the test finds a local point which is
741                             better than the computed optimum, a restart is
742                             performed.</para>
743                           </listitem>
744                         </varlistentry>
745
746                         <varlistentry>
747                           <term>"kelley"</term>
748
749                           <listitem>
750                             <para>the sufficient decrease condition by O'Neill
751                             is used. If the test finds that the status of the
752                             optimization is "kelleystagnation", a restart is
753                             performed. This status may be generated if the
754                             -kelleystagnationflag option is set to 1.</para>
755                           </listitem>
756                         </varlistentry>
757                       </variablelist>
758
759                       <para>The default method is "oneill".</para>
760                     </listitem>
761                   </varlistentry>
762
763                   <varlistentry>
764                     <term>-restartmax</term>
765
766                     <listitem>
767                       <para>the maximum number of restarts, when automatic
768                       restart is enabled via the -restartflag option. Default
769                       value is 3.</para>
770                     </listitem>
771                   </varlistentry>
772
773                   <varlistentry>
774                     <term>-restarteps</term>
775
776                     <listitem>
777                       <para>the absolute epsilon value used to check for
778                       optimality in the factorial O'Neill restart detection.
779                       The default value is %eps.</para>
780                     </listitem>
781                   </varlistentry>
782
783                   <varlistentry>
784                     <term>-restartstep</term>
785
786                     <listitem>
787                       <para>the absolute step length used to check for
788                       optimality in the factorial O'Neill restart detection.
789                       The default value is 1.0.</para>
790                     </listitem>
791                   </varlistentry>
792
793                   <varlistentry>
794                     <term>-restartsimplexmethod</term>
795
796                     <listitem>
797                       <para>the method to compute the initial simplex after a
798                       restart. The following methods are available.</para>
799
800                       <variablelist>
801                         <varlistentry>
802                           <term>"given"</term>
803
804                           <listitem>
805                             <para>the coordinates associated with the -coords0
806                             option are used to compute the initial simplex, with
807                             arbitrary number of vertices.</para>
808
809                             <para>This allow the user to setup the initial
810                             simplex by a specific method which is not provided
811                             by the current component (for example with a simplex
812                             computed from a design of experiments). This allows
813                             also to configure the initial simplex so that a
814                             specific behaviour of the algorithm an be reproduced
815                             (for example the Mac Kinnon test case).</para>
816
817                             <para>The given matrix is expected to have n rows
818                             and k columns, where n is the dimension of the
819                             problem and k is the number of vertices.</para>
820                           </listitem>
821                         </varlistentry>
822
823                         <varlistentry>
824                           <term>"axes"</term>
825
826                           <listitem>
827                             <para>the simplex is computed from the coordinate
828                             axes and the length associated with the
829                             -simplex0length option.</para>
830                           </listitem>
831                         </varlistentry>
832
833                         <varlistentry>
834                           <term>"spendley"</term>
835
836                           <listitem>
837                             <para>the simplex is computed so that it is regular
838                             with the length associated with the -simplex0length
839                             option (i.e. all the edges have the same
840                             length).</para>
841                           </listitem>
842                         </varlistentry>
843
844                         <varlistentry>
845                           <term>"pfeffer"</term>
846
847                           <listitem>
848                             <para>the simplex is computed from an heuristic, in
849                             the neighborhood of the initial guess. This initial
850                             simplex depends on the -simplex0deltausual and
851                             -simplex0deltazero.</para>
852                           </listitem>
853                         </varlistentry>
854
855                         <varlistentry>
856                           <term>"randbounds"</term>
857
858                           <listitem>
859                             <para>the simplex is computed from the bounds and a
860                             random number. This option is available only if
861                             bounds are available : if bounds are not available,
862                             an error is generated. This method is usually
863                             associated with Box's algorithm. The number of
864                             vertices in the simplex is taken from the
865                             -boxnbpoints option.</para>
866                           </listitem>
867                         </varlistentry>
868
869                         <varlistentry>
870                           <term>"oriented"</term>
871
872                           <listitem>
873                             <para>the simplex is computed so that it is
874                             oriented, as suggested by C.T. Kelley.</para>
875                           </listitem>
876                         </varlistentry>
877                       </variablelist>
878
879                       <para>The default method is "oriented".</para>
880                     </listitem>
881                   </varlistentry>
882
883                   <varlistentry>
884                     <term>-boxnbpoints</term>
885
886                     <listitem>
887                       <para>the number of points in the initial simplex, when
888                       the -restartsimplexmethod option is set to "randbounds".
889                       The default value is so that the number of points is
890                       twice the number of variables of the problem.</para>
891                     </listitem>
892                   </varlistentry>
893
894                   <varlistentry>
895                     <term>-nbineqloops</term>
896
897                     <listitem>
898                       <para>the number of loops to perform in Box and Box-Guin
899                       algorithms to scale the trial point for function
900                       improvement or into the constraints. Default value is
901                       10.</para>
902                     </listitem>
903                   </varlistentry>
904
905                   <varlistentry>
906                     <term>-ineqscaling</term>
907
908                     <listitem>
909                       <para>the scaling coefficient used to scale the trial
910                       point for function improvement or into the constraints.
911                       Default value is 0.5</para>
912                     </listitem>
913                   </varlistentry>
914                 </variablelist>
915               </listitem>
916             </varlistentry>
917
918             <varlistentry>
919               <term>value</term>
920
921               <listitem>
922                 <para>the value.</para>
923               </listitem>
924             </varlistentry>
925           </variablelist>
926         </listitem>
927       </varlistentry>
928
929       <varlistentry>
930         <term>value = neldermead_cget (this,key)</term>
931
932         <listitem>
933           <para>Get the value for the given key. If the key is unknown,
934           generates an error.</para>
935
936           <variablelist>
937             <varlistentry>
938               <term>this</term>
939
940               <listitem>
941                 <para>The current object.</para>
942               </listitem>
943             </varlistentry>
944
945             <varlistentry>
946               <term>key</term>
947
948               <listitem>
949                 <para>the name of the key to quiery. The list of available
950                 keys is the same as for the neldermead_configure
951                 function.</para>
952               </listitem>
953             </varlistentry>
954           </variablelist>
955         </listitem>
956       </varlistentry>
957
958       <varlistentry>
959         <term>value = neldermead_get ( this , key )</term>
960
961         <listitem>
962           <para>Get the value for the given key. If the key is unknown,
963           generates an error.</para>
964
965           <variablelist>
966             <varlistentry>
967               <term>this</term>
968
969               <listitem>
970                 <para>The current object.</para>
971               </listitem>
972             </varlistentry>
973
974             <varlistentry>
975               <term>key</term>
976
977               <listitem>
978                 <para>the key to get.</para>
979
980                 <para>The following keys are available :</para>
981
982                 <variablelist>
983                   <varlistentry>
984                     <term>-funevals</term>
985
986                     <listitem>
987                       <para>the number of function evaluations</para>
988                     </listitem>
989                   </varlistentry>
990
991                   <varlistentry>
992                     <term>-iterations</term>
993
994                     <listitem>
995                       <para>the number of iterations</para>
996                     </listitem>
997                   </varlistentry>
998
999                   <varlistentry>
1000                     <term>-xopt</term>
1001
1002                     <listitem>
1003                       <para>the x optimum, as a n x 1 column vector, where n
1004                       is the number of variables.</para>
1005                     </listitem>
1006                   </varlistentry>
1007
1008                   <varlistentry>
1009                     <term>-fopt</term>
1010
1011                     <listitem>
1012                       <para>the optimum cost function value</para>
1013                     </listitem>
1014                   </varlistentry>
1015
1016                   <varlistentry>
1017                     <term>-historyxopt</term>
1018
1019                     <listitem>
1020                       <para>an array, with nbiter values, containing the
1021                       history of x during the iterations.</para>
1022
1023                       <para>This array is available after optimization if the
1024                       history storing was enabled with the -storehistory
1025                       option.</para>
1026                     </listitem>
1027                   </varlistentry>
1028
1029                   <varlistentry>
1030                     <term>-historyfopt</term>
1031
1032                     <listitem>
1033                       <para>an array, with nbiter values, containing the
1034                       history of the function value during the
1035                       iterations.</para>
1036
1037                       <para>This array is available after optimization if the
1038                       history storing was enabled with the -storehistory
1039                       option.</para>
1040                     </listitem>
1041                   </varlistentry>
1042
1043                   <varlistentry>
1044                     <term>-fx0</term>
1045
1046                     <listitem>
1047                       <para>the function value for the initial guess</para>
1048                     </listitem>
1049                   </varlistentry>
1050
1051                   <varlistentry>
1052                     <term>-status</term>
1053
1054                     <listitem>
1055                       <para>a string containing the status of the
1056                       optimization. See below for details about the
1057                       optimization status.</para>
1058                     </listitem>
1059                   </varlistentry>
1060
1061                   <varlistentry>
1062                     <term>-historysimplex</term>
1063
1064                     <listitem>
1065                       <para>a matrix containing the history of the simplex
1066                       during the iterations. This matrix has rank nbiter x
1067                       nbve x n, where nbiter is the number of iterations, nbve
1068                       is the number of vertices in the simplex and n is the
1069                       number of variables.</para>
1070                     </listitem>
1071                   </varlistentry>
1072
1073                   <varlistentry>
1074                     <term>-simplexopt</term>
1075
1076                     <listitem>
1077                       <para>the optimum simplex. This is a simplex object,
1078                       which is suitable for processing with the simplex
1079                       interface.</para>
1080                     </listitem>
1081                   </varlistentry>
1082
1083                   <varlistentry>
1084                     <term>-restartnb</term>
1085
1086                     <listitem>
1087                       <para>the number of actual restarts performed.</para>
1088                     </listitem>
1089                   </varlistentry>
1090                 </variablelist>
1091
1092                 <para>Most fields are available only after an optimization has
1093                 been performed with one call to the neldermead_search
1094                 method.</para>
1095               </listitem>
1096             </varlistentry>
1097           </variablelist>
1098         </listitem>
1099       </varlistentry>
1100
1101       <varlistentry>
1102         <term>this = neldermead_display ( this )</term>
1103
1104         <listitem>
1105           <para>Display the current settings in the console.</para>
1106
1107           <variablelist>
1108             <varlistentry>
1109               <term>this</term>
1110
1111               <listitem>
1112                 <para>The current object.</para>
1113               </listitem>
1114             </varlistentry>
1115           </variablelist>
1116         </listitem>
1117       </varlistentry>
1118
1119       <varlistentry>
1120         <term>this = neldermead_search ( this )</term>
1121
1122         <listitem>
1123           <para>Performs the optimization associated with the method
1124           associated with the -method option and find the optimum.</para>
1125
1126           <variablelist>
1127             <varlistentry>
1128               <term>this</term>
1129
1130               <listitem>
1131                 <para>The current object.</para>
1132               </listitem>
1133             </varlistentry>
1134           </variablelist>
1135
1136           <para>If the -restartflag option is enabled, automatic restarts are
1137           performed, based on the -restartdetection option.</para>
1138         </listitem>
1139       </varlistentry>
1140
1141       <varlistentry>
1142         <term>this = neldermead_restart ( this )</term>
1143
1144         <listitem>
1145           <para>Restarts the optimization by updating the simplex and
1146           performing a new search.</para>
1147
1148           <variablelist>
1149             <varlistentry>
1150               <term>this</term>
1151
1152               <listitem>
1153                 <para>The current object.</para>
1154               </listitem>
1155             </varlistentry>
1156           </variablelist>
1157         </listitem>
1158       </varlistentry>
1159     </variablelist>
1160   </refsection>
1161
1162   <refsection>
1163     <title>The cost function</title>
1164
1165     <para>The option -function allows to configure the cost function. The cost
1166     function is used to compute the cost and the value of the nonlinear
1167     inequality constraints.</para>
1168
1169     <para>In the more general case, the cost function is expected to have the
1170     following header</para>
1171
1172     <programlisting role="example"> 
1173 function y = myfunction(x, index, data)
1174  </programlisting>
1175
1176     <para>where</para>
1177
1178     <variablelist>
1179       <varlistentry>
1180         <term>x</term>
1181
1182         <listitem>
1183           <para>the current point</para>
1184         </listitem>
1185       </varlistentry>
1186
1187       <varlistentry>
1188         <term>index</term>
1189
1190         <listitem>
1191           <para>optional, an integer representing the value to compute</para>
1192         </listitem>
1193       </varlistentry>
1194
1195       <varlistentry>
1196         <term>data</term>
1197
1198         <listitem>
1199           <para>optional, a user-defined data.</para>
1200
1201           <para>This argument is configured with the -costfargument
1202           option.</para>
1203         </listitem>
1204       </varlistentry>
1205
1206       <varlistentry>
1207         <term>y</term>
1208
1209         <listitem>
1210           <para>the result</para>
1211         </listitem>
1212       </varlistentry>
1213     </variablelist>
1214
1215     <para>The index input parameter has the following meaning</para>
1216
1217     <variablelist>
1218       <varlistentry>
1219         <term>index = 1 (or no index)</term>
1220
1221         <listitem>
1222           <para>the result is the value of the cost function</para>
1223         </listitem>
1224       </varlistentry>
1225
1226       <varlistentry>
1227         <term>index = 2</term>
1228
1229         <listitem>
1230           <para>the result is the value of the non-linear inequality
1231           constraints, as an array of values</para>
1232         </listitem>
1233       </varlistentry>
1234
1235       <varlistentry>
1236         <term>index = 3</term>
1237
1238         <listitem>
1239           <para>the result is an array, which content is the following. At
1240           index #1, the value of the cost function. At index #2 to the end,
1241           the list of values of the nonlinear inequality constraints.</para>
1242         </listitem>
1243       </varlistentry>
1244     </variablelist>
1245
1246     <para>In the most simple case, the cost function is expected to have the
1247     following header</para>
1248
1249     <programlisting role="example"> 
1250 function y = myfunction(x)
1251  </programlisting>
1252
1253     <para>where x is the current point and y is the value of the cost. This
1254     case is associated with an unconstrained problem without any additionnal
1255     parameter.</para>
1256   </refsection>
1257
1258   <refsection>
1259     <title>The output function</title>
1260
1261     <para>The option -outputcommand allows to configure a command which is
1262     called back at the start of the optimization, at each iteration and at the
1263     end of the optimization.</para>
1264
1265     <para>The output function must have the following header</para>
1266
1267     <programlisting role="example"> 
1268 function outputcmd(state, data, myobj)
1269  </programlisting>
1270
1271     <para>where</para>
1272
1273     <variablelist>
1274       <varlistentry>
1275         <term>state</term>
1276
1277         <listitem>
1278           <para>a string representing the current state of the algorithm.
1279           Available values are "init", "iter", "done".</para>
1280         </listitem>
1281       </varlistentry>
1282
1283       <varlistentry>
1284         <term>data</term>
1285
1286         <listitem>
1287           <para>a tlist containing at least the following entries</para>
1288
1289           <variablelist>
1290             <varlistentry>
1291               <term>x</term>
1292
1293               <listitem>
1294                 <para>the current optimum</para>
1295               </listitem>
1296             </varlistentry>
1297
1298             <varlistentry>
1299               <term>fval</term>
1300
1301               <listitem>
1302                 <para>the current function value</para>
1303               </listitem>
1304             </varlistentry>
1305
1306             <varlistentry>
1307               <term>iteration</term>
1308
1309               <listitem>
1310                 <para>the current iteration index</para>
1311               </listitem>
1312             </varlistentry>
1313
1314             <varlistentry>
1315               <term>funccount</term>
1316
1317               <listitem>
1318                 <para>the number of function evaluations</para>
1319               </listitem>
1320             </varlistentry>
1321           </variablelist>
1322         </listitem>
1323       </varlistentry>
1324
1325       <varlistentry>
1326         <term>myobj</term>
1327
1328         <listitem>
1329           <para>a user-defined parameter.</para>
1330
1331           <para>This input parameter is defined with the -outputcommandarg
1332           option.</para>
1333         </listitem>
1334       </varlistentry>
1335     </variablelist>
1336
1337     <para>The output function may be used when debugging the specialized
1338     optimization algorithm, so that a verbose logging is produced. It may also
1339     be used to write one or several report files in a specialized format
1340     (ASCII, LaTeX, Excel, Hdf5, etc...). The user-defined parameter may be
1341     used in that case to store file names or logging options.</para>
1342
1343     <para>The data tlist argument may contain more fields than the current
1344     presented ones. These additionnal fields may contain values which are
1345     specific to the specialized algorithm, such as the simplex in a
1346     Nelder-Mead method, the gradient of the cost function in a BFGS method,
1347     etc...</para>
1348   </refsection>
1349
1350   <refsection>
1351     <title>Termination</title>
1352
1353     <para>The current component takes into account for several generic
1354     termination criterias. Specialized termination criterias should be
1355     implemented in specialized optimization algorithms, by calling the
1356     optimization_termination function and adding external criterias, rather
1357     than by modification of this function.</para>
1358
1359     <para>The optimization_terminate function uses a set of rules to compute
1360     if the termination occurs, which leads to an optimization status which is
1361     equal to one of the following : "continue", "maxiter", "maxfunevals",
1362     "tolf", "tolx", "tolfstdev", "tolsize", "tolsizedeltafv",
1363     "kelleystagnation". The set of rules is the following.</para>
1364
1365     <itemizedlist>
1366       <listitem>
1367         <para>By default, the status is "continue" and the terminate flag is
1368         0.</para>
1369       </listitem>
1370
1371       <listitem>
1372         <para>The number of iterations is examined and compared to the
1373         -maxiter option : if the following condition</para>
1374
1375         <programlisting role="example"> 
1376 iterations &gt;= maxiter
1377  </programlisting>
1378
1379         <para>is true, then the status is set to "maxiter" and terminate is
1380         set to 1.</para>
1381       </listitem>
1382
1383       <listitem>
1384         <para>The number of function evaluations and compared to the
1385         -maxfunevals option is examined : if the following condition</para>
1386
1387         <programlisting role="example"> 
1388 funevals &gt;= maxfunevals
1389  </programlisting>
1390
1391         <para>is true, then the status is set to "maxfuneval" and terminate is
1392         set to 1.</para>
1393       </listitem>
1394
1395       <listitem>
1396         <para>The tolerance on function value is examined depending on the
1397         value of the -tolfunmethod.</para>
1398
1399         <variablelist>
1400           <varlistentry>
1401             <term>"disabled"</term>
1402
1403             <listitem>
1404               <para>then the criteria is just ignored.</para>
1405             </listitem>
1406           </varlistentry>
1407
1408           <varlistentry>
1409             <term>"enabled"</term>
1410
1411             <listitem>
1412               <para>if the following condition</para>
1413
1414               <programlisting role="example"> 
1415 abs(currentfopt) &lt; tolfunrelative * abs(previousfopt) + tolfunabsolute
1416  </programlisting>
1417
1418               <para>is true, then the status is set to "tolf" and terminate is
1419               set to 1.</para>
1420             </listitem>
1421           </varlistentry>
1422         </variablelist>
1423
1424         <para>The relative termination criteria on the function value works
1425         well if the function value at optimum is near zero. In that case, the
1426         function value at initial guess fx0 may be used as
1427         previousfopt.</para>
1428
1429         <para>The absolute termination criteria on the function value works if
1430         the user has an accurate idea of the optimum function value.</para>
1431       </listitem>
1432
1433       <listitem>
1434         <para>The tolerance on x is examined depending on the value of the
1435         -tolxmethod.</para>
1436
1437         <variablelist>
1438           <varlistentry>
1439             <term>"disabled"</term>
1440
1441             <listitem>
1442               <para>then the criteria is just ignored.</para>
1443             </listitem>
1444           </varlistentry>
1445
1446           <varlistentry>
1447             <term>"enabled"</term>
1448
1449             <listitem>
1450               <para>if the following condition</para>
1451
1452               <programlisting role="example"> 
1453 norm(currentxopt - previousxopt) &lt; tolxrelative * norm(currentxopt) + tolxabsolute
1454  </programlisting>
1455
1456               <para>is true, then the status is set to "tolx" and terminate is
1457               set to 1.</para>
1458             </listitem>
1459           </varlistentry>
1460         </variablelist>
1461
1462         <para>The relative termination criteria on the function value works
1463         well if x at optimum is different from zero. In that case, the
1464         condition measures the distance between two iterates.</para>
1465
1466         <para>The absolute termination criteria on the function value works if
1467         the user has an accurate idea of the scale of the optimum x. If the
1468         optimum x is near 0, the relative tolerance will not work and the
1469         absolute tolerance is more appropriate.</para>
1470       </listitem>
1471
1472       <listitem>
1473         <para>The absolute tolerance on standard deviation of the function
1474         value is examined depending on the value of the -tolfstdeviationmethod
1475         option.</para>
1476
1477         <variablelist>
1478           <varlistentry>
1479             <term>"disabled"</term>
1480
1481             <listitem>
1482               <para>then the criteria is just ignored.</para>
1483             </listitem>
1484           </varlistentry>
1485
1486           <varlistentry>
1487             <term>"enabled"</term>
1488
1489             <listitem>
1490               <para>if the following condition</para>
1491
1492               <programlisting role="example"> 
1493 st_deviation(fv) &lt; tolfstdeviation
1494  </programlisting>
1495
1496               <para>is true where fv is an array containing the function
1497               values in the simplex, then the status is set to "tolfstdev" and
1498               terminate is set to 1.</para>
1499             </listitem>
1500           </varlistentry>
1501         </variablelist>
1502       </listitem>
1503
1504       <listitem>
1505         <para>The absolute tolerance on simplex size is examined depending on
1506         the value of the -tolsimplexizemethod option.</para>
1507
1508         <variablelist>
1509           <varlistentry>
1510             <term>"disabled"</term>
1511
1512             <listitem>
1513               <para>then the criteria is just ignored.</para>
1514             </listitem>
1515           </varlistentry>
1516
1517           <varlistentry>
1518             <term>"enabled"</term>
1519
1520             <listitem>
1521               <para>if the following condition</para>
1522
1523               <programlisting role="example"> 
1524 ssize &lt; tolsimplexizerelative * simplexsize0 + tolsimplexizeabsolute
1525  </programlisting>
1526
1527               <para>is true where simplexsize0 is the size of the simplex at
1528               iteration 0, then the status is set to "tolsize" and terminate
1529               is set to 1.</para>
1530             </listitem>
1531           </varlistentry>
1532         </variablelist>
1533       </listitem>
1534
1535       <listitem>
1536         <para>The absolute tolerance on simplex size and absolute difference
1537         of function value is examined depending on the value of the
1538         -tolssizedeltafvmethod option.</para>
1539
1540         <variablelist>
1541           <varlistentry>
1542             <term>"disabled"</term>
1543
1544             <listitem>
1545               <para>then the criteria is just ignored.</para>
1546             </listitem>
1547           </varlistentry>
1548
1549           <varlistentry>
1550             <term>"enabled"</term>
1551
1552             <listitem>
1553               <para>if both the following conditions</para>
1554
1555               <programlisting role="example"> 
1556 ssize &lt; tolsimplexizeabsolute 
1557  </programlisting>
1558
1559               <programlisting role="example"> 
1560 shiftfv &lt; toldeltafv
1561  </programlisting>
1562
1563               <para>is true where ssize is the current simplex size and
1564               shiftfv is the absolute value of the difference of function
1565               value between the highest and lowest vertices, then the status
1566               is set to "tolsizedeltafv" and terminate is set to 1.</para>
1567             </listitem>
1568           </varlistentry>
1569         </variablelist>
1570       </listitem>
1571
1572       <listitem>
1573         <para>The stagnation condition based on Kelley sufficient decrease
1574         condition is examined depending on the value of the
1575         -kelleystagnationflag option.</para>
1576
1577         <variablelist>
1578           <varlistentry>
1579             <term>"disabled"</term>
1580
1581             <listitem>
1582               <para>then the criteria is just ignored.</para>
1583             </listitem>
1584           </varlistentry>
1585
1586           <varlistentry>
1587             <term>"enabled"</term>
1588
1589             <listitem>
1590               <para>if the following condition</para>
1591
1592               <programlisting role="example"> 
1593 newfvmean &lt;= oldfvmean - alpha * sg' * sg
1594  </programlisting>
1595
1596               <para>is true where newfvmean (resp. oldfvmean) is the function
1597               value average in the current iteration (resp. in the previous
1598               iteration), then the status is set to "kelleystagnation" and
1599               terminate is set to 1. Here, alpha is a non-dimensional
1600               coefficient and sg is the simplex gradient.</para>
1601             </listitem>
1602           </varlistentry>
1603         </variablelist>
1604       </listitem>
1605     </itemizedlist>
1606   </refsection>
1607
1608   <refsection>
1609     <title>Kelley's stagnation detection</title>
1610
1611     <para>The stagnation detection criteria suggested by Kelley is based on a
1612     sufficient decrease condition, which requires a parameter alpha &gt; 0 to
1613     be defined. The -kelleynormalizationflag option allows to configure the
1614     method to use to compute this alpha parameter : two methods are available,
1615     where each method corresponds to a different paper by Kelley :</para>
1616
1617     <variablelist>
1618       <varlistentry>
1619         <term>constant</term>
1620
1621         <listitem>
1622           <para>In "Detection and Remediation of Stagnation in the
1623           Nelder--Mead Algorithm Using a Sufficient Decrease Condition",
1624           Kelley uses a constant alpha, with the suggested value 1.e-4, which
1625           is is typical choice for line search method.</para>
1626         </listitem>
1627       </varlistentry>
1628
1629       <varlistentry>
1630         <term>normalized</term>
1631
1632         <listitem>
1633           <para>in "Iterative Methods for Optimization", Kelley uses a
1634           normalized alpha, computed from the following formula</para>
1635
1636           <programlisting role="example"> 
1637 alpha = alpha0 * sigma0 / nsg
1638  </programlisting>
1639
1640           <para>where sigma0 is the size of the initial simplex and nsg is the
1641           norm of the simplex gradient for the initial guess point.</para>
1642         </listitem>
1643       </varlistentry>
1644     </variablelist>
1645   </refsection>
1646
1647   <refsection>
1648     <title>O'Neil factorial optimality test</title>
1649
1650     <para>In "Algorithm AS47 - Function minimization using a simplex
1651     procedure", R. O'Neil presents a fortran 77 implementation of the simplex
1652     method. A factorial test is used to check if the computed optimum point is
1653     a local minimum. If the -restartdetection option is set to "oneill", that
1654     factorial test is used to see if a restart should be performed.</para>
1655   </refsection>
1656
1657   <refsection>
1658     <title>Spendley et al. implementation notes</title>
1659
1660     <para>The original paper may be implemented with several variations, which
1661     might lead to different results. This section defines what algorithmic
1662     choices have been used.</para>
1663
1664     <para>The paper states the following rules.</para>
1665
1666     <itemizedlist>
1667       <listitem>
1668         <para>"Rule 1. Ascertain the lowest reading y, of yi ... yk+1 Complete
1669         a new simplex Sp by excluding the point Vp corresponding to y, and
1670         replacing it by V* defined as above."</para>
1671       </listitem>
1672
1673       <listitem>
1674         <para>"Rule 2. If a result has occurred in (k + 1) successive
1675         simplexes, and is not then eliminated by application of Rule 1, do not
1676         move in the direction indicated by Rule 1, or at all, but discard the
1677         result and replace it by a new observation at the same point."</para>
1678       </listitem>
1679
1680       <listitem>
1681         <para>"Rule 3. If y is the lowest reading in So , and if the next
1682         observation made, y* , is the lowest reading in the new simplex S , do
1683         not apply Rule 1 and return to So from Sp . Move out of S, by
1684         rejecting the second lowest reading (which is also the second lowest
1685         reading in So)."</para>
1686       </listitem>
1687     </itemizedlist>
1688
1689     <para>We implement the following "rules" of the Spendley et al.
1690     method.</para>
1691
1692     <itemizedlist>
1693       <listitem>
1694         <para>Rule 1 is strictly applied, but the reflection is done by
1695         reflection the high point, since we minimize a function instead of
1696         maximizing it, like Spendley.</para>
1697       </listitem>
1698
1699       <listitem>
1700         <para>Rule 2 is NOT implemented, as we expect that the function
1701         evaluation is not subject to errors.</para>
1702       </listitem>
1703
1704       <listitem>
1705         <para>Rule 3 is applied, ie reflection with respect to next to high
1706         point. </para>
1707       </listitem>
1708     </itemizedlist>
1709
1710     <para>The original paper does not mention any shrink step. When the
1711     original algorithm cannot improve the function value with reflection
1712     steps, the basic algorithm stops. In order to make the current
1713     implementation of practical value, a shrink step is included, with
1714     shrinkage factor sigma. This perfectly fits into to the spirit of the
1715     original paper. Notice that the shrink step make the rule #3 (reflection
1716     with respect to next-to-worst vertex) unnecessary. Indeed, the minimum
1717     required steps are the reflection and shrinkage. Never the less, the rule
1718     #3 has been kept in order to make the algorithm as close as it can be to
1719     the original.</para>
1720   </refsection>
1721
1722   <refsection>
1723     <title>Example #1</title>
1724
1725     <para>In the following example, we solve the Rosenbrock test case. We
1726     begin by defining the Rosenbrock function, which takes 2 input arguments
1727     and returns the objective. The classical starting point [-1.2 1.0] is
1728     used. The neldermead_new creates a new neldermead object. Then we use the
1729     neldermead_configure method to configure the parameters of the problem.
1730     The initial simplex is computed from the axes and the single length 1.0
1731     (this is the default, but is explicitely written here as an example). The
1732     variable simplex algorithm by Nelder and Mead is used, which corresponds
1733     to the -method "variable" option. The neldermead_search function performs
1734     the search for the minimum. Once the minimum is found, the
1735     neldermead_contour allows to compute the data required by the contour
1736     function. This is possible since our problem involves only 2 parameters.
1737     This function uses the cost function previously configured to compute the
1738     required data. The contour plot is directly drawn from the data provided
1739     by neldermead_contour. Then we plot the initial guess on the contour plot
1740     as a blue dot. The neldermead_get function is used to get the optimum,
1741     which is associated with the -xopt option. The optimum is plot on the
1742     contour plot as a red dot.</para>
1743
1744     <programlisting role="example">
1745 mprintf("Defining Rosenbrock function...\n");
1746 function y = rosenbrock (x)
1747   y = 100*(x(2)-x(1)^2)^2+(1-x(1))^2;
1748 endfunction
1749 x0 = [-1.2 1.0]';
1750 mprintf("x0=%s\n",strcat(string(x0)," "));
1751 mprintf("Creating object...\n");
1752 nm = neldermead_new ();
1753 mprintf("Configuring object...\n");
1754 nm = neldermead_configure(nm,"-numberofvariables",2);
1755 nm = neldermead_configure(nm,"-function",rosenbrock);
1756 nm = neldermead_configure(nm,"-x0",x0);
1757 nm = neldermead_configure(nm,"-maxiter",200);
1758 nm = neldermead_configure(nm,"-maxfunevals",300);
1759 nm = neldermead_configure(nm,"-tolfunrelative",10*%eps);
1760 nm = neldermead_configure(nm,"-tolxrelative",10*%eps);
1761 nm = neldermead_configure(nm,"-simplex0method","axes");
1762 nm = neldermead_configure(nm,"-simplex0length",1.0);
1763 nm = neldermead_configure(nm,"-method","variable");
1764 nm = neldermead_configure(nm,"-verbose",0);
1765 nm = neldermead_configure(nm,"-verbosetermination",0);
1766 mprintf("Searching for minimum...\n");
1767 nm = neldermead_search(nm);
1768 mprintf("Plot contour...\n");
1769 xmin = -2.0 ; xmax = 2.0 ; ymin = -2.0 ; ymax = 2.0 ; nx = 100 ; ny = 100;
1770 stepx = (xmax - xmin)/nx
1771 xdata = xmin:stepx:xmax;
1772 stepy = (ymax - ymin)/ny
1773 ydata = ymin:stepy:ymax;
1774 for ix = 1:length(xdata)
1775   for iy = 1:length(ydata)
1776     experiment = [xdata(ix) ydata(iy)];
1777     [ nm , fiexp ] = neldermead_function ( nm , experiment );
1778     zdata ( ix , iy ) = fiexp;
1779   end
1780 end
1781 wnum = 100001;
1782 my_handle             = scf(wnum);
1783 contour ( xdata , ydata , zdata , [1 10 100 500 1000 2000] )
1784 // Plot starting point
1785 mprintf("x0 : blue dot\n");
1786 plot(x0(1),x0(2));
1787 my_handle.children.children(1).children.mark_mode="on";
1788 my_handle.children.children(1).children.mark_size = 5;
1789 my_handle.children.children(1).children.mark_foreground = 2;
1790 mprintf("xopt : red dot\n");
1791 xopt = neldermead_get(nm,"-xopt");
1792 plot(xopt(1),xopt(2));
1793 my_handle.children.children(1).children.mark_mode="on";
1794 my_handle.children.children(1).children.mark_size = 5;
1795 my_handle.children.children(1).children.mark_foreground = 5;
1796
1797 nm = neldermead_destroy(nm);
1798 </programlisting>
1799
1800     <para>The -verbose option allows to get detailed informations about the
1801     current optimization process. The following is a sample output for an
1802     optimization based on the Nelder and Mead variable-shape simplex
1803     algorithm. Only the output corresponding to the iteration #156 is
1804     displayed. In order to display specific outputs (or to create specific
1805     output files and graphics), the -outputcommand option should be
1806     used.</para>
1807
1808     <programlisting role="example">
1809 =================================================================
1810 Iteration #156 (total = 156)
1811 Function Eval #297
1812 Xopt : 1 1
1813 Fopt : 6.871176e-027
1814 DeltaFv : 2.880999e-026
1815 Center : 1 1
1816 Size : 2.548515e-013
1817 Vertex #1/3 : fv=0.000000, x=1.000000 1.000000
1818 Vertex #2/3 : fv=0.000000, x=1.000000 1.000000
1819 Vertex #3/3 : fv=0.000000, x=1.000000 1.000000
1820 nmplot_outputcmd (1)
1821 Reflect
1822 xbar=1 1
1823 Function Evaluation #298 is [1.155D-25] at [1 1]
1824 xr=[1 1], f(xr)=0.000000
1825 Contract - inside
1826 Function Evaluation #299 is [6.023D-27] at [1 1]
1827 xc=1 1, f(xc)=0.000000
1828   &gt; Perform Inside Contraction
1829 Sort
1830 </programlisting>
1831   </refsection>
1832
1833   <refsection>
1834     <title>TODO</title>
1835
1836     <itemizedlist>
1837       <listitem>
1838         <para>add the Box-Guin algoritm as a 4th method.</para>
1839
1840         <para>This algorithm solves an constrained optimization problem with a
1841         variable sized simplex made of an arbitrary k number of vertices. This
1842         is an update of Box's algorithm.</para>
1843       </listitem>
1844
1845       <listitem>
1846         <para>add the optimization of the Rosenbrock test case, with the
1847         interactive plot thanks to the -outputcommand option</para>
1848       </listitem>
1849     </itemizedlist>
1850   </refsection>
1851
1852   <refsection>
1853     <title>Bibliography</title>
1854
1855     <para>"Sequential Application of Simplex Designs in Optimisation and
1856     Evolutionary Operation", Spendley, W. and Hext, G. R. and Himsworth, F.
1857     R., American Statistical Association and American Society for Quality,
1858     1962</para>
1859
1860     <para>"A Simplex Method for Function Minimization", Nelder, J. A. and
1861     Mead, R., The Computer Journal, 1965</para>
1862
1863     <para>"A New Method of Constrained Optimization and a Comparison With
1864     Other Methods", M. J. Box, The Computer Journal 1965 8(1):42-52, 1965 by
1865     British Computer Society</para>
1866
1867     <para>"Discussion and correspondence: modification of the complex method
1868     of constrained optimization", J. A. Guin, The Computer Journal,
1869     1968</para>
1870
1871     <para>"Detection and Remediation of Stagnation in the Nelder--Mead
1872     Algorithm Using a Sufficient Decrease Condition", Kelley C. T., SIAM J. on
1873     Optimization, 1999</para>
1874
1875     <para>"Iterative Methods for Optimization", C. T. Kelley, SIAM Frontiers
1876     in Applied Mathematics, 1999</para>
1877
1878     <para>"Algorithm AS47 - Function minimization using a simplex procedure",
1879     O'Neill, R., Applied Statistics, 1971</para>
1880   </refsection>
1881
1882   <refsection>
1883     <title>Authors</title>
1884
1885     <para>Michael Baudin - INRIA - 2008-2009</para>
1886
1887     <para>Michael Baudin - Digiteo - 2009</para>
1888   </refsection>
1889
1890   <refsection>
1891     <title>See Also</title>
1892
1893     <simplelist type="inline">
1894       <member><link linkend="optimbase">optimbase</link></member>
1895
1896       <member><link linkend="optimsimplex">optimsimplex</link></member>
1897
1898       <member><link linkend="optimsimplex">nmplot</link></member>
1899     </simplelist>
1900   </refsection>
1901 </refentry>