Grid-restrained Nelder-Mead simplex algorithm

About
The Nelder-mead simplex algorithm is a very popular algorithm for unconstrained optimization. Unfortunately it suffers from serious convergence problems which are more pronounced for higher-dimensional problems [1], but also occur at lower dimensions (e.g. McKinnon function with n=2) [2]. The algorithm is very popular in practice because it is simple to implement and very intuitive to understand. Despite its popularity only very limited convergence results were published [3].

There were several attempts to improve the convergence properties of the algorithm, most notably the one by Coope, Price and Byatt [4]. The downside of their approach is the use of a sufficient descent condition which to some extent breaks the "beauty" of the original algorithm.

The grid-restrained version of the algorithm uses the same mechanism as [4] for preventing the simplex from degenerating. But instead of enforcing a sufficient descent condition iterates are forced to lie on a grid. This grid is gradually refined. With an approach similar to the one applied to pattern search [5] it can be proved that the algorithm converges to stationary points of C¹ functions [6].

Files
PDF file of the paper [6] introducing the algorithm
MATLAB implementation (ZIP)

License
The implementation is licensed under LGPLv2.1. To put it short - send changes back to me so I can publish them in the official implementation. You can use it any way you want as long as you give me proper credit for the implementation.

Short instructions for using the MATLAB implementation
gridnm.m
The implementation of the algorithm. See comments on how to call the implementation. If you want to change the parameters of the algorithm, look at the beginning of gridnm() implementation.
rb.m
Implementation of the Rosenbrock test function.
nmtest.m
Example that demonstrates how to call gridnm() on the Rosenbrock function.

References
[1] Effect of dimensionality on the Nelder-Mead simplex method, Han L. X., Neumann M., OPTIMIZATION METHODS & SOFTWARE, vol. 21, issue 1, p.p. 1--16, 2006.
[2] Convergence of the Nelder-Mead simplex method to a nonstationary point, Mckinnon K. I. M., SIAM JOURNAL ON OPTIMIZATION, vol. 9, issue 1, p.p. 148--158, 1998.
[3] Convergence properties of the Nelder-Mead simplex method in low dimensions, Lagarias J. C., Reeds J. A., Wright M. H., et al., SIAM JOURNAL ON OPTIMIZATION, vol. 9, issue 1, p.p. 112--147, 1998.
[4] A convergent variant of the Nelder-Mead algorithm, Price C. J., Coope I. D., Byatt D., JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, vol. 113, issue 1, p.p. 5--19, 2002.
[5] On the convergence of pattern search algorithms, Torczon V., SIAM JOURNAL ON OPTIMIZATION, vol. 7, issue 1, p.p. 1--25, 1997.
[6] Grid restrained Nelder-Mead algorithm, Burmen A., Puhan J., Tuma T., COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, vol. 34, issue 3, p.p. 359--375, 2006.

Last update: May 12 2011