6.6 Powell’s Method 323Example 6.5 Consider the minimization of the function
f (x 1 , x 2 )= 6 x 12 + 2 x 22 − 6 x 1 x 2 −x 1 − 2 x 2IfS 1 =
{ 1
2}
denotes a search direction, find a directionS 2 that is conjugate to the
directionS 1.
SOLUTION The objective function can be expressed in matrix form as
f (X)=BTX+1
2
XT[A]X
={− 1 − 2 }
{
x 1
x 2}
+
1
2
{x 1 x 2 }[
12 − 6
−6 4
]{
x 1
x 2}
and the Hessian matrix [A] can be identified as
[A]=
[
12 − 6
−6 4
]
The directionS 2 =
{s 1
s 2}
will be conjugate toS 1 ={ 1
2}
ifST 1 [A]S 2 =(^12 )
[
12 − 6
−6 4
]{
s 1
s 2}
= 0
which upon expansion gives 2s 2 or= 0 s 1 = rbitrary anda s 2 =. Since 0 s 1 can have
any value, we selects 1 = and the desired conjugate direction can be expressed as 1
S 2 =
{ 1
0}
6.6.2 Algorithm
The basic idea of Powell’s method is illustrated graphically for a two-variable func-
tion in Fig. 6.8. In this figure the function is first minimized once along each of the
coordinate directions starting with the second coordinate direction and then in the cor-
responding pattern direction. This leads to point 5. For the next cycle of minimization,
we discard one of the coordinate directions (thex 1 direction in the present case) in
favor of the pattern direction. Thus we minimize alongu 2 andS 1 and obtain point 7.
Then we generate a new pattern directionS 2 as shown in the figure. For the next
cycle of minimization, we discard one of the previously used coordinate directions
(thex 2 direction in this case) in favor of the newly generated pattern direction. Then,
by starting from point 8, we minimize along directionsS 1 andS 2 , thereby obtaining
points 9 and 10, respectively. For the next cycle of minimization, since there is no
coordinate direction to discard, we restart the whole procedure by minimizing along
thex 2 direction. This procedure is continued until the desired minimum point is found.
The flow diagram for the version of Powell’s method described above is given
in Fig. 6.9. Note that the search will be made sequentially in the directionsSn;
S 1 ,S 2 ,S 3 ,... ,Sn− 1 ,Sn;S(p^1 );S 2 ,S 3 ,... ,Sn− 1 ,Sn,S(p^1 );S(p^2 );S 3 ,S 4 ,... ,Sn− 1 ,Sn,
S(p^1 ),S(p^2 );S(p^3 ),... until the minimum point is found. HereSi indicates the coordi-
nate directionuiandS(j )p the jth pattern direction. In Fig. 6.9, the previous base point