Engineering Optimization: Theory and Practice, Fourth Edition

6.6 Powell’s Method 321

different starting pointsXaandXb, respectively, the line(X 1 −X 2 ) ill be conjugatew
to the search directionS.

Theorem 6.2If a quadratic function

Q(X)=^12 XTAX+BTX+C (6.31)

is minimized sequentially, once along each direction of a set ofnmutually conjugate
directions, the minimum of the functionQwill be found at or before thenth step
irrespective of the starting point.

Proof: LetX∗minimize the quadratic functionQ(X). Then

∇Q(X∗) =B+AX∗= 0 (6.32)

Given a pointX 1 and a set of linearly independent directionsS 1 ,S 2 ,... ,Sn, constants
βican always be found such that

X∗=X 1 +

∑n

i= 1

βiSi (6.33)

where the vectorsS 1 ,S 2 ,... ,Snhave been used as basis vectors. If the directionsSi
are A-conjugate and none of them is zero, theSican easily be shown to be linearly
independent and theβican be determined as follows.

Equations (6.32) and (6.33) lead to

B+AX 1 +A

( n

∑

i= 1

βiSi

)

= 0 (6.34)

Multiplying this equation throughout bySTj, we obtain

STj( B+AX 1 )+STjA

( n

∑

i= 1

βiSi

)

= 0 (6.35)

Equation (6.35) can be rewritten as

(B+AX 1 )TSj+βjSTjASj= 0 (6.36)

that is,

βj= −

(B+AX 1 )TSj

STjASj

(6.37)

Nowconsider an iterative minimization procedure starting at pointX 1 , and successively
minimizing the quadraticQ(X)in the directionsS 1 ,S 2 ,... ,Sn, where these directions
satisfyEq. (6.25). The successive points are determined by the relation

Xi+ 1 =Xi+λ∗iSi, i = 1 ton (6.38)