Convergence of the Nelder--Mead Simplex Method to a Nonstationary Point

SIAM Journal on OptimizationPublished 1 January 1998

K. I. M. McKinnon

DOI10.1137/s1052623496303482

Source URL

Citations472

SJR quartileQ1

SJR score1.39

SNIP1.79

TL;DR

This paper analyzes the behavior of the Nelder--Mead simplex method for a family of examples which cause the method to converge to a nonstationary point and shows that this behavior cannot occur for functions with more than three continuous derivatives.

Abstract

This paper analyzes the behavior of the Nelder--Mead simplex method for a family of examples which cause the method to converge to a nonstationary point. All the examples use continuous functions of two variables. The family of functions contains strictly convex functions with up to three continuous derivatives. In all the examples the method repeatedly applies the inside contraction step with the best vertex remaining fixed. The simplices tend to a straight line which is orthogonal to the steepest descent direction. It is shown that this behavior cannot occur for functions with more than three continuous derivatives. The stability of the examples is analyzed.

Keywords

Computer ScienceMathematics

The Computer JournalA Simplex Method for Function Minimization

28,856 Citations1965J. A. Nelder, R. Mead

A method is described for the minimization of a function of n variables, which depends on the comparison of function values at the (n 41) vertices of a general simplex, followed by the replacement of the vertex with the highest value by another point.

SIAM Journal on OptimizationConvergence Properties of the Nelder--Mead Simplex Method in Low Dimensions

7,417 Citations1998Jeffrey C. Lagarias, James A. Reeds +2 more

This paper presents convergence properties of the Nelder--Mead algorithm applied to strictly convex functions in dimensions 1 and 2, and proves convergence to a minimizer for dimension 1, and various limited convergence results for dimension 2.

SIAM Journal on OptimizationOn the Convergence of Pattern Search Algorithms

1,298 Citations1997Virginia Torczon

The characterization of pattern search methods is exploited to establish a global convergence theory that does not enforce a notion of sufficient decrease, and is possible because the iterates of a pattern search method lie on a scaled, translated integer lattice.

TechnometricsSequential Application of Simplex Designs in Optimisation and Evolutionary Operation

1,285 Citations1962W. Spendley, G. R. Hext +1 more

A technique for empirical optimisation is presented in which a sequence of experimental designs each in the form of a regular or irregular simplex is used, each simplex having all vertices but one in common with the preceding simplex, and being completed by one new point.

Direct Search Methods on Parallel Machines

281 Citations1992J. E. Dennis, Virginia Torczon

SIAM Journal on OptimizationOn the Convergence of the Multidirectional Search Algorithm

259 Citations1991Virginia Torczon

It is shown how a general convergence theory can be developed for an entire class of direct search methods—which includes such methods as the factorial design algorithm and the pattern search algorithm—that share a key feature of the multidirectional search algorithm.

SIAM Journal on OptimizationDirect Search Methods on Parallel Machines

245 Citations1991J. E. Dennis, Virginia Torczon

Direct search methods are methods designed to solve unconstrained minimization problems of the form min x in R n f(x), distinguished by the fact that they neither use nor require explicit derivative information; the search for a local minimizer is driven solely by function information.

Rice University's digital scholarship archive (Rice University)Multidirectional search: a direct search algorithm for parallel machines

201 Citations1989Virginia Torczon, J. E. Dennis

View PDF

Optimization on Microcomputers: The Nelder-Mead Simplex Algorithm

94 Citations1985J. E. Dennis, J. Woods +1 more

The Nelder-Mead simplex method for obtaining the minimizer of a function has several properties that make it a natural choice for implementation and utilization on microcomputers.

SIAM Journal on OptimizationFortified-Descent Simplicial Search Method: A General Approach

81 Citations1999Paul Tseng

A new simplex-based direct search method for unconstrained minimization of a real-valued function f of n variables to iteratively improve an n-dimensional simplex through certain reflection/expansion/contraction steps is proposed.