This directory contains NelderMead and variations thereof. Currently, I have implemented two algorithms, described below. The code in this directory is under the same MIT license as the rest of my code in NLopt (see ../COPYRIGHT). Steven G. Johnson November 2008  First, (almost) the original NelderMead simplex algorithm (NLOPT_LN_NELDERMEAD), as described in: J. A. Nelder and R. Mead, "A simplex method for function minimization," The Computer Journal 7, p. 308313 (1965). This method is simple and has demonstrated enduring popularity, despite the later discovery that it fails to converge at all for some functions. Anecdotal evidence suggests that it often performs well even for noisy and/or discontinuous objective functions. I would tend to recommend the Subplex method (below) instead, however. The main variation is that I implemented explicit support for bound constraints, using essentially the method described in: J. A. Richardson and J. L. Kuester, "The complex method for constrained optimization," Commun. ACM 16(8), 487489 (1973). implementing the method described by: M. J. Box, "A new method of constrained optimization and a comparison with other methods," Computer J. 8 (1), 4252 (1965). Whenever a new point would lie outside the bound constraints, Box advocates moving it "just inside" the constraints. I couldn't see any advantage to using a fixed distance inside the constraints, especially if the optimum is on the constraint, so instead I move the point exactly onto the constraint in that case. The danger with implementing bound constraints in this way (or by Box's method) is that you may collapse the simplex into a lowerdimensional subspace. I'm not aware of a better way, however. In any case, this collapse of the simplex is ameliorated by restarting, such as when NelderMead is used within the Subplex algorithm below.  Second, I reimplemented Tom Rowan's "Subplex" algorithm. As Rowan expressed a preference that other implementations of his algorithm use a different name, I called my implementation "Sbplx" (NLOPT_LN_SBPLX). Subplex (a variant of NelderMead that uses NelderMead on a sequence of subspaces) is claimed to be much more efficient and robust than the original NelderMead, while retaining the latter's facility with discontinuous objectives, and in my experience these claims seem to be true. (However, I'm not aware of any proof that Subplex is globally convergent, and may fail for some objectives like NelderMead; YMMV.) I used the description of Rowan's algorithm in his PhD thesis: T. Rowan, "Functional Stability Analysis of Numerical Algorithms", Ph.D. thesis, Department of Computer Sciences, University of Texas at Austin, 1990. I would have preferred to use Rowan's original implementation, posted by him on Netlib: http://www.netlib.org/opt/subplex.tgz Unfortunately, the legality of redistributing or modifying this code is unclear. Rowan didn't include any license statement at all with the original code, which makes it technically illegal to redistribute. I contacted Rowan about getting a clear opensource/freesoftware license for it, and he was very agreeable, but he said he had to think about the specific license choice and would get back to me. Unfortunately, a year later I still haven't heard from him, and his old email address no longer seems to work, so I don't know how to contact him for permission. Since the algorithm is not too complicated, however, I just rewrote it. There seem to be slight differences between the behavior of my implementation and his (probably due to different choices of initial subspace and other slight variations, where his paper was ambiguous), but the number of iterations to converge on my test problems seems to be quite close (within 10% for most problems). The only major difference between my implementation and Rowan's, as far as I can tell, is that I implemented explicit support for bound constraints (via the method in the Box paper as described above). This seems to be a big improvement in the case where the optimum lies against one of the constraints.  Future possibilities: C. J. Price, I. D. Coope, and D. Byatt, "A convergent variant of the NelderMead algorithm," J. Optim. Theory Appl. 113 (1), p. 519 (2002). A. Burmen, J. Puhan, and T. Tuma, "Grid restrained NelderMead algorithm," Computational Optim. Appl. 34(3), 359375 (2006). Both of these are provably convergent variations of NelderMead; the latter authors claim that theirs is superior.
Source
BayesOpt / nlopt / neldermead /
Filename  Size  Date modified  Message 

..  
4.7 KB

…  
2.2 KB

…  
10.3 KB

…  
8.1 KB

… 