Convergencepropertiesofthenelder-meadsimplexmethodinlowdimens资源-CSDN文库

5星 · 超过95%的资源需积分: 16 143 浏览量 2014-07-07 11:36:25 上传评论 1 收藏 554KB PDF 举报

根据给定文件的信息，我们可以提炼出以下知识点：文件标题“Convergence properties of the nelder-mead simplex method in low dimensions”涉及的主题是“Nelder-Mead单纯形法的收敛性质”，并且特别强调了该方法在低维空间中的应用。Nelder-Mead单纯形算法是一种用于无约束多维最小化问题的直接搜索方法。直接搜索方法是指不使用梯度信息的优化技术，而单纯形算法则是通过在搜索空间中构造和迭代一个单纯形（一个n维几何体）来逼近问题的最小值。在文件描述中提到，“Nelder-Mead非线性单纯型法,一种非线性优化算法，可广泛应用在各种工程优化中。”这说明Nelder-Mead方法不仅在理论上具有重要性，而且在实际工程应用中也极为重要。Nelder-Mead算法首次发表于1965年，由于其在许多领域的广泛使用而变得极其流行。尽管如此，关于Nelder-Mead算法的理论结果几乎是空白，这一点在文件中得到了强调。文件中进一步提到该论文展示了Nelder-Mead算法在严格凸函数上应用于一维和二维时的收敛性质。在文章中，研究者证明了该算法在寻找一维最小化问题解时的收敛性，并且对于二维情况，给出了限定的收敛性结果。另外，论文中引用了McKinnon提供的例子，该例子展示了一组严格凸函数以及一组初始条件，对于这些条件，Nelder-Mead算法可能不会收敛到最小化问题的解。这表明，尽管Nelder-Mead算法在某些情况下表现出良好的性能，但其在更多复杂情况下的收敛性仍然是一个未解决的问题。此外，文件中还提到了Nelder-Mead算法与Dantzig用于线性规划的单纯形算法的区别。虽然两者都使用了单纯形序列，但它们在方法和应用场景上完全不同，特别是Nelder-Mead方法是专为无约束优化设计的。Nelder-Mead算法尤其受到化学、化学工程和医学等领域的欢迎，相关的参考资料在文献中数以千计。Nelder-Mead算法的普及程度可通过其出现在如《数值食谱》（Numerical Recipes）这样的畅销手册中，以及其在MATLAB软件中的实现来体现。文件中提到的关键词包括“直接搜索方法”、“Nelder-Mead单纯形方法”和“无导数优化”，这些都指向了Nelder-Mead算法的几个关键特性：作为直接搜索方法，它不依赖于目标函数的导数信息；作为单纯形方法，它涉及到单纯形结构；而无导数优化则进一步强调了该算法在处理导数难以计算或不存在的情况下的适用性。至于文件中提到的数学符号和公式，由于上下文不完整，无法获得准确信息。但可以推测，文件中可能包含了与Nelder-Mead算法收敛性证明相关的一系列数学推导和证明过程。总结以上信息，我们得到了关于Nelder-Mead单纯形方法的基础知识点，其在低维空间中应用的收敛性质，及其在实际工程优化问题中的重要性和流行性。同时，也指出了该方法在理论研究上的空白和潜在的研究方向。这些知识点对于理解和评价Nelder-Mead算法在不同领域的应用和进一步的理论研究都具有重要的价值。

资源推荐

资源详情

资源评论

CONVERGENCE PROPERTIES OF THE

NELDER–MEAD SIMPLEX METHOD IN LOW DIMENSIONS

∗

JEFFREY C. LAGARIAS

†

, JAMES A. REEDS

‡

, MARGARET H. WRIGHT

, AND

PAUL E. WRIGHT

SIAM J. O

PTIM.

1998 Society for Industrial and Applied Mathematics

Vol. 9, No. 1, pp. 112–147

Abstract. The Nelder–Mead simplex algorithm, ﬁrst published in 1965, is an enormously pop-

ular 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 algo-

rithm 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.

Key words. direct search methods, Nelder–Mead simplex methods, nonderivative optimization

AMS subject classiﬁcations. 49D30, 65K05

PII. S1052623496303470

1. Introduction. Since its publication in 1965, the Nelder–Mead “simplex” al-

gorithm [6] has become one of the most widely used methods for nonlinear uncon-

strained optimization. The Nelder–Mead algorithm should not be confused with the

(probably) more famous simplex algorithm of Dantzig for linear programming; both

algorithms employ a sequence of simplices but are otherwise completely diﬀerent and

unrelated—in particular, the Nelder–Mead method is intended for unconstrained op-

timization.

The Nelder–Mead algorithm is especially popular in the ﬁelds of chemistry, chem-

ical engineering, and medicine. The recent book [16], which contains a bibliography

with thousands of references, is devoted entirely to the Nelder–Mead method and vari-

ations. Two measures of the ubiquity of the Nelder–Mead method are that it appears

in the best-selling handbook Numerical Recipes [7], where it is called the “amoeba

algorithm,” and in Matlab [4].

The Nelder–Mead method attempts to minimize a scalar-valued nonlinear func-

tion of n real variables using only function values, without any derivative information

(explicit or implicit). The Nelder–Mead method thus falls in the general class of di-

rect search methods; for a discussion of these methods, see, for example, [13, 18]. A

large subclass of direct search methods, including the Nelder–Mead method, maintain

at each step a nondegenerate simplex, a geometric ﬁgure in n dimensions of nonzero

volume that is the convex hull of n + 1 vertices.

Each iteration of a simplex-based direct search method begins with a simplex,

speciﬁed by its n + 1 vertices and the associated function values. One or more test

points are computed, along with their function values, and the iteration terminates

∗

Received by the editors May 13, 1996; accepted for publication (in revised form) November 24,

1997; published electronically December 2, 1998.

http://www.siam.org/journals/siopt/9-1/30347.html

†

AT&T Labs–Research, Florham Park, NJ 07932 (jcl@research.att.com).

‡

AT&T Labs–Research, Florham Park, NJ 07932 (reeds@research.att.com).

Bell Laboratories, Murray Hill, NJ 07974 (mhw@research.bell-labs.com).

AT&T Labs–Research, Florham Park, NJ 07932 (pew@research.att.com).

112

Downloaded 07/06/14 to 222.195.132.86. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

PROPERTIES OF NELDER–MEAD 113

with a new (diﬀerent) simplex such that the function values at its vertices satisfy some

form of descent condition compared to the previous simplex. Among such algorithms,

the Nelder–Mead algorithm is particularly parsimonious in function evaluations per

iteration, since in practice it typically requires only one or two function evaluations

to construct a new simplex. (Several popular direct search methods use n or more

function evaluations to obtain a new simplex.) There is a wide array of folklore

about the Nelder–Mead method, mostly along the lines that it works well in “small”

dimensions and breaks down in “large” dimensions, but very few careful numerical

results have been published to support these perceptions. Apart from the discussion

in [12], little attention has been paid to a systematic analysis of why the Nelder–Mead

algorithm fails or breaks down numerically, as it often does.

Remarkably, there has been no published theoretical analysis explicitly treating

the original Nelder–Mead algorithm in the more than 30 years since its publication.

Essentially no convergence results have been proved, although in 1985 Woods [17]

studied a modiﬁed

Nelder–Mead algorithm applied to a strictly convex function.

The few known facts about the original Nelder–Mead algorithm consist mainly of

negative results. Woods [17] displayed a nonconvex example in two dimensions for

which the Nelder–Mead algorithm converges to a nonminimizing point. Very recently,

McKinnon [5] gave a family of strictly convex functions and a starting conﬁguration

in two dimensions for which all vertices in the Nelder–Mead method converge to a

nonminimizing point.

The theoretical picture for other direct search methods is much clearer. Torczon

[13] proved that “pattern search” algorithms converge to a stationary point when ap-

plied to a general smooth function in n dimensions. Pattern search methods, including

multidirectional search methods [12, 1], maintain uniform linear independence of the

simplex edges (i.e., the dihedral angles are uniformly bounded away from zero and π)

and require only simple decrease in the best function value at each iteration. Rykov

[8, 9, 10] introduced several direct search methods that converge to a minimizer for

strictly convex functions. In the methods proposed by Tseng [15], a “fortiﬁed descent”

condition—stronger than simple descent—is required, along with uniform linear in-

dependence of the simplex edges. Depending on a user-speciﬁed parameter, Tseng’s

methods may involve only a small number of function evaluations at any given itera-

tion and are shown to converge to a stationary point for general smooth functions in

n dimensions.

Published convergence analyses of simplex-based direct search methods impose

one or both of the following requirements: (i) the edges of the simplex remain uni-

formly linearly independent at every iteration; (ii) a descent condition stronger than

simple decrease is satisﬁed at every iteration. In general, the Nelder–Mead algorithm

fails to have either of these properties; the resulting diﬃculties in analysis may explain

the long-standing lack of convergence results.

Because the Nelder–Mead method is so widely used by practitioners to solve

important optimization problems, we believe that its theoretical properties should be

understood as fully as possible. This paper presents convergence results in one and two

dimensions for the original Nelder–Mead algorithm applied to strictly convex functions

with bounded level sets. Our approach is to consider the Nelder–Mead algorithm

The modiﬁcations in [17] include a contraction acceptance test diﬀerent from the one given

in the Nelder–Mead paper and a “relative decrease” condition (stronger than simple decrease) for

accepting a reﬂection step. Woods did not give any conditions under which the iterates converge to

the minimizer.

Downloaded 07/06/14 to 222.195.132.86. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

114 J. C. LAGARIAS, J. A. REEDS, M. H. WRIGHT, AND P. E. WRIGHT

as a discrete dynamical system whose iterations are “driven” by the function values.

Combined with strict convexity of the function, this interpretation implies restrictions

on the allowed sequences of Nelder–Mead moves, from which convergence results can

be derived. Our main results are as follows:

1. In dimension 1, the Nelder–Mead method converges to a minimizer (Theorem 4.1),

and convergence is eventually M-step linear

when the reﬂection parameter ρ =1

(Theorem 4.2).

2. In dimension 2, the function values at all simplex vertices in the standard Nelder–

Mead algorithm converge to the same value (Theorem 5.1).

3. In dimension 2, the simplices in the standard Nelder–Mead algorithm have diam-

eters converging to zero (Theorem 5.2).

Note that Result 3 does not assert that the simplices converge to a single point x

∗

No example is known in which the iterates fail to converge to a single point, but the

issue is not settled.

For the case of dimension 1, Torczon [14] has recently informed us that some

convergence results for the original Nelder–Mead algorithm can be deduced from the

results in [13]; see section 4.4. For dimension 2, our results may appear weak, but the

McKinnon example [5] shows that convergence to a minimizer is not guaranteed for

general strictly convex functions in dimension 2. Because the smoothest McKinnon

example has a point of discontinuity in the fourth derivatives, a logical question is

whether or not the Nelder–Mead method converges to a minimizer in two dimensions

for a more specialized class of strictly convex functions—in particular, for smooth

functions. This remains a challenging open problem. At present there is no function

in any dimension greater than 1 for which the original Nelder–Mead algorithm has

been proved to converge to a minimizer.

Given all the known ineﬃciencies and failures of the Nelder–Mead algorithm (see,

for example, [12]), one might wonder why it is used at all, let alone why it is so

extraordinarily popular. We oﬀer three answers. First, in many applications, for ex-

ample in industrial process control, one simply wants to ﬁnd parameter values that

improve some performance measure; the Nelder–Mead algorithm typically produces

signiﬁcant improvement for the ﬁrst few iterations. Second, there are important ap-

plications where a function evaluation is enormously expensive or time-consuming,

but derivatives cannot be calculated. In such problems, a method that requires at

least n function evaluations at every iteration (which would be the case if using ﬁnite-

diﬀerence gradient approximations or one of the more popular pattern search meth-

ods) is too expensive or too slow. When it succeeds, the Nelder–Mead method tends

to require substantially fewer function evaluations than these alternatives, and its rel-

ative “best-case eﬃciency” often outweighs the lack of convergence theory. Third, the

Nelder–Mead method is appealing because its steps are easy to explain and simple to

program.

In light of weaknesses exposed by the McKinnon counterexample and the analysis

here, future work involves developing methods that retain the good features of the

Nelder–Mead method but are more reliable and eﬃcient in theory and practice; see,

for example, [2].

The contents of this paper are as follows. Section 2 describes the Nelder–Mead

algorithm, and section 3 gives its general properties. For a strictly convex function

By M -step linear convergence we mean that there is an integer M, independent of the function

being minimized, such that the simplex diameter is reduced by a factor no less than 1/2 after M

iterations.

Downloaded 07/06/14 to 222.195.132.86. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

PROPERTIES OF NELDER–MEAD 115

with bounded level sets, section 4 analyzes the Nelder–Mead method in one dimen-

sion, and section 5 presents limited convergence results for the standard Nelder–Mead

algorithm in two dimensions. Finally, section 6 discusses open problems.

2. The Nelder–Mead algorithm. The Nelder–Mead algorithm [6] was pro-

posed as a method for minimizing a real-valued function f(x) for x ∈R

. Four scalar

parameters must be speciﬁed to deﬁne a complete Nelder–Mead method: coeﬃcients

of reﬂection (ρ), expansion (χ), contraction (γ), and shrinkage (σ). According to the

original Nelder–Mead paper, these parameters should satisfy

ρ>0,χ>1, χ>ρ, 0 <γ<1, and 0 <σ<1.(2.1)

(The relation χ>ρ, while not stated explicitly in the original paper, is implicit in

the algorithm description and terminology.) The nearly universal choices used in the

standard Nelder–Mead algorithm are

ρ =1,χ=2,γ=

, and σ =

.(2.2)

We assume the general conditions (2.1) for the one-dimensional case but restrict our-

selves to the standard case (2.2) in the two-dimensional analysis.

2.1. Statement of the algorithm. At the beginning of the kth iteration, k ≥ 0,

a nondegenerate simplex ∆

is given, along with its n + 1 vertices, each of which is

apointinR

. It is always assumed that iteration k begins by ordering and labeling

these vertices as x

(k)

, ..., x

(k)

n+1

, such that

(k)

≤ f

(k)

≤···≤f

(k)

n+1

,(2.3)

where f

(k)

denotes f(x

(k)

). The kth iteration generates a set of n + 1 vertices that

deﬁne a diﬀerent simplex for the next iteration, so that ∆

k+1

6=∆

. Because we seek

to minimize f, we refer to x

(k)

as the best point or vertex, to x

(k)

n+1

as the worst point,

and to x

(k)

as the next-worst point. Similarly, we refer to f

(k)

n+1

as the worst function

value, and so on.

The 1965 paper [6] contains several ambiguities about strictness of inequalities

and tie-breaking that have led to diﬀerences in interpretation of the Nelder–Mead

algorithm. What we shall call “the” Nelder–Mead algorithm (Algorithm NM) includes

well-deﬁned tie-breaking rules, given below, and accepts the better of the reﬂected

and expanded points in step 3 (see the discussion in section 3.1 about property 4 of

the Nelder–Mead method).

A single generic iteration is speciﬁed, omitting the superscript k to avoid clutter.

The result of each iteration is either (1) a single new vertex—the accepted point—

which replaces x

n+1

in the set of vertices for the next iteration, or (2) if a shrink is

performed, a set of n new points that, together with x

, form the simplex at the next

iteration.

One iteration of Algorithm NM (the Nelder–Mead algorithm).

1. Order. Order the n + 1 vertices to satisfy f(x

) ≤ f(x

) ≤···≤f(x

n+1

using the tie-breaking rules given below.

2. Reﬂect. Compute the reﬂection point x

from

x + ρ(

x − x

n+1

)=(1+ρ)

x − ρx

n+1

,(2.4)

Downloaded 07/06/14 to 222.195.132.86. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

116 J. C. LAGARIAS, J. A. REEDS, M. H. WRIGHT, AND P. E. WRIGHT

where

x =

i=1

/n is the centroid of the n best points (all vertices except for

n+1

). Evaluate f

= f(x

If f

≤ f

, accept the reﬂected point x

and terminate the iteration.

3. Expand. If f

, calculate the expansion point x

x + χ(x

−

x)=

x + ρχ(

x − x

n+1

)=(1+ρχ)

x − ρχx

n+1

,(2.5)

and evaluate f

= f(x

). If f

, accept x

and terminate the iteration; otherwise

(if f

≥ f

), accept x

and terminate the iteration.

4. Contract. If f

≥ f

perform a contraction between

x and the better of x

n+1

and x

a. Outside. If f

≤ f

n+1

(i.e., x

is strictly better than x

n+1

), perform an

outside contraction: calculate

x + γ(x

−

x)=

x + γρ(

x − x

n+1

)=(1+ργ)

x − ργx

n+1

,(2.6)

and evaluate f

= f(x

). If f

≤ f

, accept x

and terminate the iteration; otherwise,

go to step 5 (perform a shrink).

b. Inside. If f

≥ f

n+1

, perform an inside contraction: calculate

x − γ(

x − x

n+1

)=(1− γ)

x + γx

n+1

,(2.7)

and evaluate f

= f(x

). If f

n+1

, accept x

and terminate the iteration;

otherwise, go to step 5 (perform a shrink).

5. Perform a shrink step. Evaluate f at the n points v

= x

+ σ(x

− x

i =2, ..., n + 1. The (unordered) vertices of the simplex at the next iteration consist

of x

, v

, ..., v

n+1

Figures 1 and 2 show the eﬀects of reﬂection, expansion, contraction, and shrink-

age for a simplex in two dimensions (a triangle), using the standard coeﬃcients ρ =1,

χ =2,γ =

, and σ =

. Observe that, except in a shrink, the one new vertex always

lies on the (extended) line joining ¯x and x

n+1

. Furthermore, it is visually evident that

the simplex shape undergoes a noticeable change during an expansion or contraction

with the standard coeﬃcients.

The Nelder–Mead paper [6] did not describe how to order points in the case of

equal function values. We adopt the following tie-breaking rules, which assign to

the new vertex the highest possible index consistent with the relation f(x

(k+1)

) ≤

f(x

(k+1)

) ≤···≤f(x

(k+1)

n+1

Nonshrink ordering rule. When a nonshrink step occurs, the worst vertex

(k)

n+1

is discarded. The accepted point created during iteration k, denoted by v

(k)

becomes a new vertex and takes position j + 1 in the vertices of ∆

k+1

, where

j = max

0≤`≤n

{ ` | f(v

(k)

) <f(x

(k)

`+1

) };

all other vertices retain their relative ordering from iteration k.

Shrink ordering rule. If a shrink step occurs, the only vertex carried over

from ∆

to ∆

k+1

is x

(k)

. Only one tie-breaking rule is speciﬁed, for the case in which

(k)

and one or more of the new points are tied as the best point: if

min{f(v

(k)

),...,f(v

(k)

n+1

)} = f(x

(k)

Downloaded 07/06/14 to 222.195.132.86. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

剩余35页未读，继续阅读

评论收藏

内容反馈

backswimming

2015-08-19

不错啊，经典的算法

wangxiaomin88

粉丝: 16
资源: 8

Convergence properties of the nelder-mead simplex method in low ...

最新资源

Convergence properties of the nelder-mead simplex method in low ...

nelder-mead算法

nelder-mead.zip_The Various_nelder mead matlab

Convergence Of Peer-To-Peer And Grid Computing

Convergence Analysis on a Derivative-Free Descent Method for Nonlinear Complementarity Problems

On Local and Global Convergence of a Nonsmooth Newton-type Method for Nonlinear Semidefinite Programs

parallel-in-time algorithm: MGRIT

Expanding the Range of Convergence of the CORDIC Algorithm

Gauss-Seidel-Method.zip_To the Letter

Convergence analysis of an adaptive finite element method for the elasto-plastic torsion problem

Strong Convergence Properties of Jamison Weighted Sums of ruo{~}-Mixing Random Sequences

Convergence rate of the Asymmetric Deuant-Weisbuch Dynamics

ifs-37-ifs190294.pdf

Gauss-Seidel-method.zip_After Method_liebmann

数字信号处理英文版课件：Chapter6 z-Transform第四版.ppt

A Weak Convergence Approach to the Theory of Large Deviations

The convergence guarantees of a non-convex approach for sparse recovery using regularized least squares

An Efficient Global Optimization Algorithm.pdf

Introduction_to_Optimum_Design.pdf

spectral hashing

Based on the high-speed electronic energy convergence phenomena to put forward the electro-ultimate particles

Convergence Rates of the Distributions of Error Variance Estimates in Linear Models" (1983年)

Simulation models with correct statistical properties

最新资源