θ(x)„ + (x)2 + (x)2 , (x)1 > 0.

1 2

The examples in [188] consider the parameter sets

±

(3, 6, 400),

(2, 6, 60),

(„, θ, φ) =

(1, 15, 10).

The initial simplex was

√

x1 = (1, 1)T , x2 = (»+ , »’ )T , x3 = (0, 0)T , where »± = (1 ± 33)/8.

With this data, the Nelder“Mead iteration will stagnate at the origin, which is not a critical point

for f . The stagnation mode is repeated inside contractions that leave the best point (which is not

a minimizer) unchanged.

We terminated the iteration when the difference between the best and worst function values

was < 10’8 .

We illustrate the behavior of the Nelder“Mead algorithm in Figures 8.2, 8.3, and 8.4. In all

the ¬gures we plot, as functions of the iteration index, the difference between the best and worst

function values, σ+ , the maximum oriented length, the norm of the simplex gradient, and the l2

condition number of the matrix of simplex directions. In all three problems stagnation is evident

from the behavior of the simplex gradients. Note also how the simplex condition number is

growing rapidly.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright ©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

140 ITERATIVE METHODS FOR OPTIMIZATION

Function Differences Max Oriented Length

2 1

10 10

0

10

0

10

1

10

2

10

2

10

4

10 3

10

6

10 4

10

8 5

10 10

0 20 40 60 0 20 40 60

Simplex Gradient Norm Simplex Condition

5 10

10 10

4 8

10 10

3 6

10 10

2 4

10 10

1 2

10 10

0 0

10 10

0 20 40 60 0 20 40 60

Figure 8.3: Unmodi¬ed Nelder“Mead, („, θ, φ) = (2, 6, 60)

Function Differences Simplex Diameter

2 1

10 10

0

10 0

10

2

10

1

10

4

10

2

10

6

10

8 3

10 10

0 10 20 30 40 0 10 20 30 40

Simplex Gradient Norm Simplex Condition

1 8

10 10

6

10

0 4

10 10

2

10

1 0

10 10

0 10 20 30 40 0 10 20 30 40

Figure 8.4: Unmodi¬ed Nelder“Mead, („, θ, φ) = (3, 6, 400)

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright ©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 141

8.1.4 Restarting the Nelder“Mead Algorithm

When the Nelder“Mead iteration stagnates, a restart with the same best point and a different set

of directions can help sometimes. In order to formulate a restart scheme, one must ¬rst develop

a strategy for detecting stagnation. One might think that a large simplex condition would suf¬ce

for this. However [204], the ability of the Nelder“Mead simplices to drastically vary their shape

is an important feature of the algorithm and looking at the simplex condition alone would lead

to poor results. Failure of (8.4), however, seems to indicate that something is wrong, and we

will use that as our stagnation detector.

Having detected stagnation, one must modify the simplex. Simply performing a shrink

step is not effective. The method we advocate here, from [155], is the oriented restart. The

motivation is that if the simplex gradient can be trusted to be in the correct orthant in RN , a new,

smaller simplex with orthogonal edges oriented with that quadrant should direct the iteration in

a productive direction.

We propose performing an oriented restart when (8.4) fails but f k+1 ’ f k < 0. This means

replacing the current simplex with vertices {xj }N +1 , ordered so that (8.1) holds, with a new

j=1

smaller simplex having vertices (before ordering!) {yj }N +1 with y1 = x1 and

j=1

yj = y1 ’ βj’1 ej’1 for 2 ¤ j ¤ N + 1,

(8.7)

where, for 1 ¤ l ¤ N , el is the lth coordinate vector,

±

σ (S k )sign((Dk f )l ), (Dk f )l = 0,

1 ’

βl =

2

σ’ (S k ), (Dk f )l = 0,

and (Dk f )l is the lth component of Dk f . If Dk f = 0 we assume that the Nelder“Mead iteration

would have been terminated at iteration k because there is no difference between best and worst

values.

So, before ordering, the new simplex has the same ¬rst point as the old. The diameter of the

new simplex has not been increased since the diameter of the new simplex is at most σ+ (S k ).

Moreover all edge lengths have been reduced. So after reordering σ+ (S k+1 ) ¤ σ’ (S k ). As for

κ, after the oriented shrink, but before reordering, κ(V ) = 1. After reordering, of course, the

best point may no longer be x1 . In any case the worst-case bound on κ is

√2

k+1 k+1 2

κ(V )= V ¤ (1 + N ) .

(8.8)

In any case, the new simplex is well conditioned.

Returning to the McKinnon examples, we ¬nd that an oriented restart did remedy stagnation

for the smooth examples. The graphs in Figures 8.5, 8.6, and 8.7 report the same data as for the

unmodi¬ed algorithm, with stars on the plots denoting oriented restarts.

For the smoothest example, („, θ, φ) = (3, 6, 400), the modi¬ed form of Nelder“Mead took a

single oriented restart at the 21st iteration. For the less smooth of these two, („, θ, φ) = (2, 6, 60),

a single restart was taken on the 19th iteration. As one can see from Figures 8.6 and 8.7 the

restart had an immediate effect on the simplex gradient norm and overcame the stagnation.

For the nonsmooth example, („, θ, φ) = (1, 15, 10), in Figure 8.5, the modi¬ed algorithm

terminated with failure after restarting on the 44th, 45th, and 46th iterations. Since the objective

is not smooth at the stagnation point, this is the best we can expect and is far better than the

behavior of the unmodi¬ed algorithm, which stagnates with no warning of the failure.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright ©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

142 ITERATIVE METHODS FOR OPTIMIZATION

Function Differences Max Oriented Length

2 2

10 10

0 0

10 10

2 2

10 10

4 4

10 10

0 10 20 30 40 50 0 10 20 30 40 50

Simplex Gradient Norm Simplex Condition

3 8

10 10

6

10

2 4

10 10

2

10

1 0

10 10

0 10 20 30 40 50 0 10 20 30 40 50

Figure 8.5: Modi¬ed Nelder“Mead, („, θ, φ) = (1, 15, 10)

Function Differences Max Oriented Length

5 2

10 10

0 0

10 10

5 2

10 10

10 4

10 10

0 20 40 60 0 20 40 60

Simplex Gradient Norm Simplex Condition

2 3

10 10

0 2

10 10

2 1

10 10

4 0

10 10

0 20 40 60 0 20 40 60

Figure 8.6: Modi¬ed Nelder“Mead, („, θ, φ) = (2, 6, 60)

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright ©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 143

Function Differences Max Oriented Length

5 2

10 10

0 0

10 10

5 2

10 10

10 4

10 10

0 20 40 60 0 20 40 60

Simplex Gradient Norm Simplex Condition

2 4

10 10

0 3

10 10

2 2

10 10

4 1

10 10

6 0

10 10

0 20 40 60 0 20 40 60

Figure 8.7: Modi¬ed Nelder“Mead, („, θ, φ) = (3, 6, 400)

8.2 Multidirectional Search

8.2.1 Description and Implementation

One way to address the possible ill-conditioning in the Nelder“Mead algorithm is to require that

the condition numbers of the simplices be bounded. The multidirectional search (MDS) method

[85], [261], [262] does this by making each new simplex congruent to the previous one. The

results in this section, mostly taken from [29], show that MDS has convergence properties like

those of implicit ¬ltering.

In the special case of equilateral simplices, V k is a constant multiple of V 0 and the simplex

condition number is constant. If the simplices are not equilateral, then κ(V ) may vary depending

on which vertex is called x1 , but (6.6) will hold in any case.

Figure 8.8 illustrates the two-dimensional case for two types of simplices. Beginning with

the ordered simplex S c with vertices x1 , x2 , x3 one ¬rst attempts a re¬‚ection step, leading to a

simplex S r with vertices x1 , r2 , r3 .

If the best function value of the vertices of S r is better than the best f (x1 ) in S 0 , S r is

(provisionally) accepted and expansion is attempted. The expansion step differs from that in

the Nelder“Mead algorithm because N new points are needed to make the new, larger simplex

similar to the old one. The expansion simplex S e has vertices x1 , e2 , e3 and is accepted over S r

if the best function value of the vertices of S e is better than the best in S r . If the best function

value of the vertices of S r is not better than the best in S c , then the simplex is contracted and

the new simplex has vertices x1 , c2 , c3 . After the new simplex is identi¬ed, the vertices are

reordered to create the new ordered simplex S + .

Similar to the Nelder“Mead algorithm, there are expansion and contraction parameters µe

and µc . Typical values for these are 2 and 1/2.

Algorithm 8.2.1. mds(S, f, „, kmax)

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright ©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

144 ITERATIVE METHODS FOR OPTIMIZATION

Right Simplex

Equilateral Simplex

x3

x2

c3

x3

c2

e2 r2

c3

x1

x1 c2 x2