Convergence of the restricted Nelder-Mead algorithm in two dimensions

DOI10.1137/110830150MaRDI QIDQ2910882zbMATH OpenOpenAlexFDO

Authors Jeffrey C. Lagarias, Bjorn Poonen, Margaret H. Wright

Publication date 12 September 2012

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.0350

zbMATH Keywords

unconstrained optimizationdirect search methodNelder--Mead algorithmstrictly convex objective functions

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Derivative-free methods and methods using generalized derivatives (90C56)

Abstract: The Nelder-Mead algorithm, a longstanding direct search method for unconstrained optimization published in 1965, is designed to minimize a scalar-valued function f of n real variables using only function values, without any derivative information. Each Nelder-Mead iteration is associated with a nondegenerate simplex defined by n+1 vertices and their function values; a typical iteration produces a new simplex by replacing the worst vertex by a new point. Despite the method's widespread use, theoretical results have been limited: for strictly convex objective functions of one variable with bounded level sets, the algorithm always converges to the minimizer; for such functions of two variables, the diameter of the simplex converges to zero, but examples constructed by McKinnon show that the algorithm may converge to a nonminimizing point. This paper considers the restricted Nelder-Mead algorithm, a variant that does not allow expansion steps. In two dimensions we show that, for any nondegenerate starting simplex and any twice-continuously differentiable function with positive definite Hessian and bounded level sets, the algorithm always converges to the minimizer. The proof is based on treating the method as a discrete dynamical system, and relies on several techniques that are non-standard in convergence proofs for unconstrained optimization.

Recommendations

• Convergence Properties of the Nelder--Mead Simplex Method in Low Dimensions
• A convergent variant of the Nelder--Mead algorithm
• Convergence of the Nelder-Mead method
• Grid restrained Nelder-Mead algorithm
• Convergence of the Nelder--Mead Simplex Method to a Nonstationary Point

Cited in

(19)

• CNM -- a convergent method of Nelder and Mead type.
• A hyperbolic variant of the Nelder-Mead simplex method in low dimensions
• Exploiting Problem Structure in Derivative Free Optimization
• Mesh-based Nelder-Mead algorithm for inequality constrained optimization
• Convergence theorems for the Nelder-Mead method
• Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
• scientific article; zbMATH DE number 4085567 (Why is no real title available?)
• Efficient Implementation of the Nelder-Mead Search Algorithm
• A direct search method for unconstrained quantile-based simulation optimization
• Improvement of the Nelder-Mead method using direct inversion in iterative subspace
• Implementing the Nelder-Mead simplex algorithm with adaptive parameters
• Random gradient-free minimization of convex functions
• Convergence of the Nelder-Mead method
• A modified Nelder-Mead barrier method for constrained optimization
• Post-boosting of classification boundary for imbalanced data using geometric mean
• On the optimal parameter values of the Nelder-Mead simplex algorithm
• A convergent variant of the Nelder--Mead algorithm
• Grid restrained Nelder-Mead algorithm
• Derivative-free optimization methods

This page was built for publication: Convergence of the restricted Nelder-Mead algorithm in two dimensions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2910882)