Engineering Optimization: Theory and Practice, Fourth Edition

322 Nonlinear Programming II: Unconstrained Optimization Techniques

whereλ∗i is found by minimizingQ(Xi+λiSi) thatso †

STi∇Q(Xi+ 1 )= 0 (6.39)

Since the gradient ofQat the pointXi+ 1 is given by

∇Q(Xi+ 1 ) =B+AXi+ 1 (6.40)

Eq. (6.39) can be written as

STi{B+A(Xi+λ∗iSi) =} 0 (6.41)

This equation gives

λ∗i= −

(B+AXi)TSi

STiASi

(6.42)

From Eq. (6.38), we can expressXias

Xi=X 1 +

∑i−^1

j= 1

λ∗jSj (6.43)

so that

XTiASi=XT 1 ASi+

∑i−^1

j= 1

λ∗jSTjASi

=XT 1 ASi (6.44)

usingthe relation (6.25). Thus Eq. (6.42) becomes

λ∗i= − (B+AX 1 )T

Si

STiASi

(6.45)

which can be seen to be identical to Eq. (6.37). Hence the minimizing step lengths are

given byβiorλ∗i. Since the optimal pointX∗is originally expressed as a sum ofn

quantitiesβ 1 , β 2 ,... , βn, which have been shown to be equivalent to the minimizing

step lengths, the minimization process leads to the minimum point innsteps or less.

Since we have not made any assumption regardingX 1 and the order ofS 1 ,S 2 ,... ,Sn,

the process converges innsteps or less, independent of the starting point as well as

the order in which the minimization directions are used.

†STi∇Q(Xi+ 1 ) = 0 is equivalent todQ/dλi= at 0 Y=Xi+ 1 :

dQ

dλi

=

∑n

j= 1

∂Q

∂yj

∂yj

∂λi

whereyjare the components ofY=Xi+ 1.