share/nelder_mead/README.txt

   1                   Common-Lisp implementations of the
   2                   ==================================
   3
   4                    grid-restrained and traditional
   5                    ===============================
   6
   7                         Nelder-Mead algorithms
   8                         ======================
   9
  10
  11
  12 Introduction
  13 ------------
  14
  15   These common lisp sources contain two variants of the Nelder-Mead
  16   algorithm. The original algorithm [1] and a provably convergent,
  17   reliable variant by A. Bürmen et al [4], called the "Grid Restrained
  18   Nelder Mead Algorithm" (GRNMA).
  19
  20   It should be mentioned that other, provably convergent variant exist
  21   [2,3], which aren't included here. The only reasons are lack of
  22   time, and the fact that the implemented variant does not require a
  23   simple descent condition, putting it closer to the original.
  24
  25   Other than that, and based on the article [4], the performance of
  26   these methods seems to be about equal in terms of number of function
  27   evaluations. As a side effect of the additional reliability, both
  28   tend to be a lot more efficient than the original algorithm even
  29   when it does not fail. In particular when the number of dimensions
  30   increases. As a test, one might try the GRNM,
  31
  32   (grnm-optimize #'standard-quadratic
  33                   (make-array 30 :initial-element 1.0d0) :verbose t)
  34
  35   and compare with the original Nelder-Mead,
  36
  37   (nm-optimize #'standard-quadratic
  38                 (make-array 30 :initial-element 1.0d0) :verbose t)
  39
  40   and observe the difference in number of function evaluations (the
  41   last value returned).
  42
  43   (This exercise also serves to illustrate the overall deficiencies of
  44   direct search algorithms when applied to higher dimensional
  45   problems.)
  46
  47   This software is provided under the MIT licence; see COPYING.txt for
  48   details.
  49
  50 Usage
  51 -----
  52
  53   This implementation of the grid restrained Nelder-Mead algorithm
  54   expects at least two parameters: the objective function, and an
  55   initial guess. It returns four values;
  56
  57    * the minimizer,
  58    * the minimum,
  59    * the last simplex,
  60    * and the number of function evaluations.
  61
  62   The objective function should accept a double-float array as its
  63   argument.
  64
  65   The initial guess will usually be an array of double-float numbers
  66   (but instead an object of the class NM-SIMPLEX may also be provided;
  67   see below). For example,
  68
  69     (grnm-optimize #'rosenbrock #(40.0d0 40.0d0))
  70
  71   finds the minimum of the Rosenbrock function, and
  72
  73     (grnm-optimize #'standard-quadratic
  74                    (make-array 30 :initial-element 1.0d0))
  75
  76   finds the minimum of the standard quadratic function in 30
  77   dimensions.
  78
  79   A few keyword arguments can customize the behavior. These are
  80
  81     :verbose  (default: NIL)
  82     :converged-p (default: (burmen-et-al-convergence-test))
  83     :max-function-calls (default: NIL; => as many as needed)
  84
  85
  86   :verbose (default: NIL)
  87
  88     Pass T here if you want to see some progress report. The amount of
  89     output can be controlled by setting *verbose-level* to 1 or 2. The
  90     difference is that with 1 (the default) only the best value of the
  91     simplex is shown, while with 2 the whole simplex is printed on
  92     each iteration.
  93
  94   :converged-p (default: (burmen-et-al-convergence-test))
  95
  96     The burmen-et-al-convergence-test is, as the name suggests, the
  97     convergence test used in the article by Burmen et al. It accepts a
  98     few parameters: tol-x, tol-f and rel; please see the article for
  99     further details.
 100
 101     Another convergence criterion that can be given is (pp-volume-test
 102     <tol>), which returns true once the parallelogram(!) spanned by the
 103     vertices of the simplex has a volume lower than <tol> to the power
 104     of N, where N is the dimension of the problem. This is a rather
 105     expensive test, as it involves computing a QR decomposition of an N
 106     by N matrix on each call.
 107
 108     If you are not in the mood of taking prisoners, you might as well
 109     pass (constantly NIL) as the convergence criterion. This has as a
 110     consequence that the iteration continues until the simplex
 111     collapses, which in floating-point arithmetic happens in finite
 112     time. The grid restrained Nelder-Mead algorithm should have
 113     converged by then.
 114
 115   :max-function-calls (default: NIL)
 116
 117     Maximum number of objective function evaluations. After that many
 118     function evaluations, this implementation of the algorithm will
 119     declare convergence to have occurred.
 120
 121     The actual number of function calls might be slightly larger (at
 122     most by N), as the relevant condition is only checked in certain
 123     situations.
 124
 125 Utilities/Misc
 126 --------------
 127
 128   NM-optimize
 129
 130     Apart from the grid-restrained Nelder Mead algorithm, the
 131     traditional variant is also provided. The corresponding function
 132     is named NM-optimize, and its usage is the same as for
 133     GRNM-optimize.
 134
 135     The only difference is that :max-function-calls has a default
 136     value of 100000. Otherwise the algorithm might well iterate
 137     forever.
 138
 139   Initial-simplex <initial guess> :displace <displacement>
 140
 141     Constructs an initial simplex with the double-float array <initial
 142     guess> as on of its corners.
 143
 144     The displacement can be a an array of double floats or a
 145     number. In the first case, the additional vertices of the simplex
 146     are build by adding to each component of the <initial guess> the
 147     corresponding component in <displacement>. If it is a number, then
 148     the additional vertices are build by adding <displacement> to each
 149     component of the <initial guess>.
 150
 151 Tips & Tricks
 152 -------------
 153
 154   * One can try to solve constrained optimization problems by returning
 155
 156       MOST-POSITIVE-DOUBLE-FLOAT
 157
 158     whenever the objective function is called with an argument that
 159     violates the constraints. Mathematically, this falls out of the
 160     theory, but it works most of the time.
 161
 162   * If your objective function is noisy or not smooth (for instance, if
 163     its first derivatives are not continuous) it is a good idea to
 164     restart the algorithm. Remember that convergence is only
 165     guaranteed if the objective function is at least C^1.
 166
 167 References
 168 ----------
 169
 170 [1] J.A. Nelder and R. Mead, "A simplex method for function
 171     minimization," The Computer Journal, vol. 7, pp. 308-313, 1965.
 172
 173
 174 [2] P. Tseng, "Fortified-descent simplicial search method: A general
 175     approach," SIAM Journal on Optimization, vol. 10, pp. 269-288,
 176     1999.
 177
 178 [3] C.J. Price, I.D. Coope, and D. Byatt, "A convergent variant of the
 179     Nelder-Mead algorithm," Journal of Optimization Theory and
 180     Applications, vol. 113, pp. 5-19, 2002.
 181
 182 [4] A. Bürmen, J. Puhan and T. Tuma, "Grid Restrained Nelder-Mead
 183     Algorithm", Computational Optimization and Applications, vol.
 184     34, no. 3, pp. 359 - 375, 2006.
 185
 186
 187 --------
 188 Mario S. Mommer, November 2006