src/algs/neldermead/README

   1 This directory contains Nelder-Mead and variations thereof.
   2
   3 Currently, I have implemented two algorithms, described below.
   4
   5 The code in this directory is under the same MIT license as the rest
   6 of my code in NLopt (see ../COPYRIGHT).
   7
   8 Steven G. Johnson
   9 November 2008
  10
  11 -----------------------------------------------------------------------
  12
  13 First, (almost) the original Nelder-Mead simplex algorithm
  14 (NLOPT_LN_NELDERMEAD), as described in:
  15
  16         J. A. Nelder and R. Mead, "A simplex method for function
  17         minimization," The Computer Journal 7, p. 308-313 (1965).
  18
  19 This method is simple and has demonstrated enduring popularity,
  20 despite the later discovery that it fails to converge at all for some
  21 functions.  Anecdotal evidence suggests that it often performs well
  22 even for noisy and/or discontinuous objective functions.  I would tend
  23 to recommend the Subplex method (below) instead, however.
  24
  25 The main variation is that I implemented explicit support for bound
  26 constraints, using essentially the method described in:
  27
  28         J. A. Richardson and J. L. Kuester, "The complex method for
  29         constrained optimization," Commun. ACM 16(8), 487-489 (1973).
  30
  31         implementing the method described by:
  32
  33         M. J. Box, "A new method of constrained optimization and a
  34         comparison with other methods," Computer J. 8 (1), 42-52 (1965).
  35
  36 Whenever a new point would lie outside the bound constraints, Box
  37 advocates moving it "just inside" the constraints.  I couldn't see any
  38 advantage to using a fixed distance inside the constraints, especially
  39 if the optimum is on the constraint, so instead I move the point
  40 exactly onto the constraint in that case.
  41
  42 The danger with implementing bound constraints in this way (or by
  43 Box's method) is that you may collapse the simplex into a
  44 lower-dimensional subspace.  I'm not aware of a better way, however.
  45 In any case, this collapse of the simplex is ameliorated by
  46 restarting, such as when Nelder-Mead is used within the Subplex
  47 algorithm below.
  48
  49 -----------------------------------------------------------------------
  50
  51 Second, I re-implemented Tom Rowan's "Subplex" algorithm.  As Rowan
  52 expressed a preference that other implementations of his algorithm use
  53 a different name, I called my implementation "Sbplx" (NLOPT_LN_SBPLX).
  54 Subplex (a variant of Nelder-Mead that uses Nelder-Mead on a sequence
  55 of subspaces) is claimed to be much more efficient and robust than the
  56 original Nelder-Mead, while retaining the latter's facility with
  57 discontinuous objectives, and in my experience these claims seem to be
  58 true.  (However, I'm not aware of any proof that Subplex is globally
  59 convergent, and may fail for some objectives like Nelder-Mead; YMMV.)
  60
  61 I used the description of Rowan's algorithm in his PhD thesis:
  62
  63      T. Rowan, "Functional Stability Analysis of Numerical Algorithms",
  64      Ph.D. thesis, Department of Computer Sciences, University of Texas
  65      at Austin, 1990.
  66
  67 I would have preferred to use Rowan's original implementation, posted
  68 by him on Netlib:
  69
  70      http://www.netlib.org/opt/subplex.tgz
  71
  72 Unfortunately, the legality of redistributing or modifying this code
  73 is unclear.  Rowan didn't include any license statement at all with
  74 the original code, which makes it technically illegal to redistribute.
  75 I contacted Rowan about getting a clear open-source/free-software
  76 license for it, and he was very agreeable, but he said he had to think
  77 about the specific license choice and would get back to me.
  78 Unfortunately, a year later I still haven't heard from him, and his
  79 old email address no longer seems to work, so I don't know how to
  80 contact him for permission.
  81
  82 Since the algorithm is not too complicated, however, I just rewrote
  83 it.  There seem to be slight differences between the behavior of my
  84 implementation and his (probably due to different choices of initial
  85 subspace and other slight variations, where his paper was ambiguous),
  86 but the number of iterations to converge on my test problems seems to
  87 be quite close (within 10% for most problems).
  88
  89 The only major difference between my implementation and Rowan's, as
  90 far as I can tell, is that I implemented explicit support for bound
  91 constraints (via the method in the Box paper as described above).
  92 This seems to be a big improvement in the case where the optimum lies
  93 against one of the constraints.
  94
  95 -----------------------------------------------------------------------
  96
  97 Future possibilities:
  98
  99         C. J. Price, I. D. Coope, and D. Byatt, "A convergent variant
 100         of the Nelder-Mead algorithm," J. Optim. Theory Appl. 113 (1),
 101         p. 5-19 (2002).
 102
 103         A. Burmen, J. Puhan, and T. Tuma, "Grid restrained Nelder-Mead
 104         algorithm," Computational Optim. Appl. 34(3), 359-375 (2006).
 105
 106 Both of these are provably convergent variations of Nelder-Mead; the
 107 latter authors claim that theirs is superior.