<< . .

. 25
( : 32)



. . >>

f (x) =

θ(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


<< . .

. 25
( : 32)



. . >>