summaryrefslogtreecommitdiffstats log msg author committer range
blob: 150f0efd1f742d12466d52a7cf56c7f57157b083 (plain)
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225  \chapter{Implementations of the Nelder-Mead algorithm} In the following sections, we analyse the various implementations of the Nelder-Mead algorithm. We analyse the Matlab implementation provided by the \emph{fminsearch} command. We analyse the matlab algorithm provided by C.T. Kelley and the Scilab port by Y. Collette. We present the Numerical Recipes implementations. We analyse the O'Neill fortran 77 implementation "AS47". The Burkardt implementation is also covered. The implementation provided in the NAG collection is detailed. The Nelder-Mead algorithm from the Gnu Scientific Library is analysed. \section{Matlab : fminsearch} The Matlab command fminsearch implements the Nelder-Mead algorithm \cite{MatlabFminsearch}. It provides features such as \begin{itemize} \item maximum number of function evaluations, \item maximum number of iterations, \item termination tolerance on the function value, \item termination tolerance on $x$, \item output command to display the progress of the algorithm. \end{itemize} \section{Kelley and the Nelder-Mead algorithm} C.T. Kelley has written a book \cite{Kelley1999} on optimization method and devotes a complete chapter to direct search algorithms, especially the Nelder-Mead algorithm. Kelley provides in \cite{KelleyMethodsOptimizationMatlabCodes} the Matlab implementation of the Nelder-Mead algorithm. That implementation uses the restart strategy that Kelley has published in \cite{589283} and which improves the possible stagnation of the algorithm on non local optimization points. No tests are provided. The following is extracted from the README provided with these algorithms. \begin{verbatim} These files are current as of December 9, 1998. ----------------- MATLAB/FORTRAN software for Iterative Methods for Optimization by C. T. Kelley These M-files are implementations of the algorithms from the book "Iterative Methods for Optimization", to be published by SIAM, by C. T. Kelley. The book, which describes the algorithms, is available from SIAM (service@siam.org). These files can be modified for non-commercial purposes provided that the authors: C. T. Kelley for all MATLAB codes, P. Gilmore and T. D. Choi for iffco.f J. M. Gablonsky for DIRECT are acknowledged and clear comment lines are inserted that the code has been changed. The authors assume no no responsibility for any errors that may exist in these routines. Questions, comments, and bug reports should be sent to Professor C. T. Kelley Department of Mathematics, Box 8205 North Carolina State University Raleigh, NC 27695-8205 (919) 515-7163 (919) 515-3798 (FAX) Tim_Kelley@ncsu.edu \end{verbatim} From Scilab's point of view, that ?licence? is a problem since it prevents the use of the source for commercial purposes. \section{Nelder-Mead Scilab Toolbox : Lolimot} The Lolimot project by Yann Collette provide two Scilab-based Nelder- Mead implementations \cite{LolimotColletteURL}. The first implementation is a Scilab port of the Kelley script. The licence problem is therefore not solved by this script. The second implementation \cite{NelderMeadColletteURL} implements the restart strategy by Kelley. No tests are provided. \section{Numerical Recipes} The Numerical Recipes \cite{NumericalRecipes} provides the C source code of an implementation of the Nelder-Mead algorithm. Of course, this is a copyrighted material which cannot be included in Scilab. \section{NASHLIB : A19} Nashlib is a collection of Fortran subprograms from "Compact Numerical Methods for Computers; Linear Algebra and Function Minimisation, " by J.C. Nash. The subprograms are written without many of the extra features usually associated with commercial mathematical software, such as extensive error checking, and are most useful for those applications where small program size is particularly important. The license is public domain. Nahslib includes one implementation of the Nelder-Mead algorithm \cite{GAMS-A19A20-Desc}, \cite{GAMS-A19A20-Source}. It is written in fortran 77. The coding style is "goto"-based and may not be easy to maintain. \section{O'Neill implementations} The paper \cite{O'Neill1971AAF} by R. O'Neil in the journal of Applied Statistics presents a fortran 77 implementation of the Nelder-Mead algorithm. The source code itself is available in \cite{O'NeillAS47}. Many of the following implementations are based on this primary source code. We were not able to get the paper \cite{O'Neill1971AAF} itself. On his website, John Burkardt gives a fortran 77 source code of the Nelder-Mead algorithm \cite{Burkardtasa047}. The following are the comments in the header of the source code. \begin{verbatim} c Discussion: c c This routine seeks the minimum value of a user-specified function. c c Simplex function minimisation procedure due to Nelder+Mead(1965), c as implemented by O'Neill(1971, Appl.Statist. 20, 338-45), with c subsequent comments by Chambers+Ertel(1974, 23, 250-1), Benyon(1976, c 25, 97) and Hill(1978, 27, 380-2) c c The function to be minimized must be defined by a function of c the form c c function fn ( x, f ) c double precision fn c double precision x(*) c c and the name of this subroutine must be declared EXTERNAL in the c calling routine and passed as the argument FN. c c This routine does not include a termination test using the c fitting of a quadratic surface. c c Modified: c c 27 February 2008 c c Author: c c FORTRAN77 version by R ONeill c Modifications by John Burkardt \end{verbatim} The "Bayesian Survival Analysis" book by Joseph G. Ibrahim, Ming-Hui Chen, and Debajyoti Sinha provides in \cite{SurvivalBookOptim} a fortran 77 implementation of the Nelder-Mead algorithm. The following is the header of the source code. \begin{verbatim} c Simplex function minimisation procedure due to Nelder+Mead(1965), c as implemented by O'Neill(1971, Appl.Statist. 20, 338-45), with c subsequent comments by Chambers+Ertel(1974, 23, 250-1), Benyon(1976, c 25, 97) and Hill(1978, 27, 380-2) \end{verbatim} The O'Neill implementation uses a restart procedure which is based on a local axis by axis search for the optimality of the computed optimum. \section{Burkardt implementations} John Burkardt gives several implementations of the Nelder-Mead algorithm \begin{itemize} \item in fortran 77 \cite{Burkardtasa047} \item in Matlab by Jeff Borggaard \cite{BurkardtNelderMeadMatlab}. \end{itemize} \section{NAG Fortran implementation} The NAG Fortran library provides the E04CCF/E04CCA routines \cite{NAGE04CCF} which implements the simplex optimization method. E04CCA is a version of E04CCF that has additional parameters in order to make it safe for use in multithreaded applications. As mentioned in the documentation, "The method tends to be slow, but it is robust and therefore very useful for functions that are subject to inaccuracies.". The termination criteria is based on the standard deviation of the function values of the simplex. The specification of the cost function for E04CCA is: \begin{verbatim} SUBROUTINE FUNCT ( N, XC, FC, IUSER, RUSER) \end{verbatim} where IUSER and RUSER and integer and double precision array, which allow the user to supply information to the cost function. An output routine, called MONIT is called once every iteration in E04CCF/E04CCA. It can be used to print out the current values of any selection of its parameters but must not be used to change the values of the parameters. \section{GSL implementation} The Gnu Scientific Library provides two Nelder-Mead implementations. The authors are Tuomo Keskitalo, Ivo Alxneit and Brian Gough. The size of the simplex is the root mean square sum of length of vectors from simplex center to corner points. The termination criteria is based on the size of the simplex. The C implementation of the minimization algorithm is original. The communication is direct, in the sense that the specific optimization algorithm calls back the cost function. A specific optimization implementation provides four functions : "alloc", "free", "iterate" and "set". A generic optimizer is created by connecting it to a specific optimizer. The user must write the loop over the iterations, making successive calls to the generic "iterate" function, which, in turns, calls the specific "iterate" associated with the specific optimization algorithm. The cost function can be provided as three function pointers \begin{itemize} \item the cost function $f$, \item the gradient $g$, \item both the cost function and the gradient. \end{itemize} Some additional parameters can be passed to these functions.