×

Implementing the Nelder-Mead simplex algorithm with adaptive parameters. (English) Zbl 1245.90121

Summary: In this paper, we first prove that the expansion and contraction steps of the Nelder-Mead simplex algorithm possess a descent property when the objective function is uniformly convex. This property provides some new insights on why the standard Nelder-Mead algorithm becomes inefficient in high dimensions. We then propose an implementation of the Nelder-Mead method in which the expansion, contraction, and shrink parameters depend on the dimension of the optimization problem. Our numerical experiments show that the new implementation outperforms the standard Nelder-Mead method for high dimensional problems.

MSC:

90C30 Nonlinear programming
90C49 Extreme-point and pivoting methods
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Andrei, N.: Convex functions. Adv. Model. Optim. 9(2), 257–267 (2007) · Zbl 1157.90499
[2] Byatt, D.: Convergent variants of the Nelder-Mead algorithm. Master’s Thesis, University of Canterbury, Christchurch, New Zealand (2000)
[3] Byrd, R., Nocedal, J., Zhu, C.: Towards a discrete Newton method with memory for large-scale optimization. In: Di Pillo, G., Giannessi, F. (eds.) Nonlinear Optimization and Applications. Plenum, New York (1996) · Zbl 0976.90100
[4] Dennis, J.E. Jr., Torczon, V.: Direct search methods on parallel machines. SIAM J. Optim. 1, 448–474 (1991) · Zbl 0754.90051
[5] Dennis, J.E. Jr., Woods, D.J.: Optimization on microcomputers: The Nelder-Mead simplex algorithm. In: Wouk, A. (ed.) New Computing Environments: Microcomputers in Large-Scale Scientific Computing. SIAM, Philadelphia (1987)
[6] Han, L., Neumann, M.: Effect of dimensionality on the Nelder-Mead simplex method. Optim. Methods Softw. 21(1), 1–16 (2006) · Zbl 1181.90290
[7] Kelley, C.T.: Iterative Methods for Optimization. SIAM Publications, Philadelphia (1999) · Zbl 0934.90082
[8] Kelley, C.T.: Detection and remediation of stagnation in the Nelder-Mead algorithm using a sufficient decrease condition. SIAM J. Optim. 10, 43–55 (2000) · Zbl 0962.65048
[9] Kolda, T.G., Lewis, R.M., Torczon, V.: Optimization by direct search: new perspectives on some classical and modern methods. SIAM Rev. 45, 385–482 (2003) · Zbl 1059.90146
[10] Lagarias, J.C., Reeds, J.A., Wright, M.H., Wright, P.: Convergence properties of the Nelder-Mead simplex algorithm in low dimensions. SIAM J. Optim. 9, 112–147 (1998) · Zbl 1005.90056
[11] Math Works: MATLAB 6, Release 12, The Math Works, Natick, MA (2000)
[12] Mckinnon, K.I.M.: Convergence of the Nelder-Mead simplex method to a nonstationary point. SIAM J. Optim. 9, 148–158 (1998) · Zbl 0962.65049
[13] MorĂ©, J.J., Garbow, B.S., Hillstrom, B.E.: Testing unconstrained optimization software. ACM Trans. Math. Softw. 7(1), 17–41 (1981) · Zbl 0454.65049
[14] Nelder, J.A., Mead, R.: A simplex method for function minimization. Comput. J. 7, 308–313 (1965) · Zbl 0229.65053
[15] Price, C.J., Coope, I.D., Byatt, D.: A convergent variant of the Nelder-Mead algorithm. JOTA 113, 5–19 (2002) · Zbl 1172.90508
[16] Torczon, V.: Multi-directional Search: A Direct Search Algorithm for Parallel Machines. Ph.D. Thesis, Rice University, TX (1989)
[17] Tseng, P.: Fortified-descent simplicial search method: a general approach. SIAM J. Optim. 10, 269–288 (2000) · Zbl 1030.90122
[18] Woods, D.J.: An Iterative Approach for Solving Multi-objective Optimization Problems. Ph.D. Thesis, Rice University, TX (1985)
[19] Wright, M.H.: Direct search methods: Once scorned, now respectable. In: Griffiths, D.F., Watson, G.A. (eds.) Numerical Analysis 1995: Proceedings of the 1995 Dundee Biennial Conference in Numerical Analysis, pp. 191–208. Addison Wesley Longman, Harlow (1996) · Zbl 0844.65057
[20] Wright, M.H.: N&M@42: Nelder-Mead at 42”, a talk given at University of Waterloo, June 2007
[21] Zalinescu, C.: On uniformly convex functions. J. Math. Anal. Appl. 95, 344–374 (1983) · Zbl 0519.49010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.