Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions

TLDR

The Nelder–Mead simplex algorithm, introduced in 1965, is a widely used direct search method for unconstrained minimization, yet no explicit theoretical convergence results exist, and it remains unclear whether it converges to a minimizer for specialized convex functions in two dimensions. The study aims to establish convergence properties of Nelder–Mead on strictly convex functions in one and two dimensions. The authors analyze the algorithm’s behavior on strictly convex functions in 1‑D and 2‑D, deriving convergence results and counterexamples. They prove convergence to a minimizer in one dimension, provide limited convergence results in two dimensions, and present a McKinnon counterexample showing convergence to a nonminimizer for certain strictly convex functions.

Abstract

The Nelder--Mead simplex algorithm, first published in 1965, is an enormously popular direct search method for multidimensional unconstrained minimization. Despite its widespread use, essentially no theoretical results have been proved explicitly for the Nelder--Mead algorithm. This paper presents convergence properties of the Nelder--Mead algorithm applied to strictly convex functions in dimensions 1 and 2. We prove convergence to a minimizer for dimension 1, and various limited convergence results for dimension 2. A counterexample of McKinnon gives a family of strictly convex functions in two dimensions and a set of initial conditions for which the Nelder--Mead algorithm converges to a nonminimizer. It is not yet known whether the Nelder--Mead method can be proved to converge to a minimizer for a more specialized class of convex functions in two dimensions.