Engineering Optimization: Theory and Practice, Fourth Edition

6.13 Quasi-Newton Methods 353

whereSiis the search direction,di=Xi+ 1 −Xican be rewritten as

di=λ∗iSi (6.121)

Thus Eq. (6.119) can be expressed as

[Bi+ 1 ]=[Bi]+

λ∗iSiSTi

STigi

−

[Bi]gigTi[Bi]

gTi[Bi]gi

(6.122)

Remarks:

1.Equations (6.111) and (6.119) are known asinverse update formulassince these

equations approximate the inverse of the Hessian matrix off.

2.It is possible to derive a family of direct update formulas in which approx-

imations to the Hessian matrix itself are considered. For this we express the

quasi-Newton condition as [see Eq. (6.99)]

gi=[Ai]di (6.123)

The procedure used in deriving Eqs. (6.111) and (6.119) can be followed

by using [Ai], di, andgi in place of [Bi], gi, anddi, respectively. This

leads to the rank 2 update formula (similar to Eq. (6.119), known as the

Broydon–Fletcher–Goldfarb–Shanno (BFGS) formula [6.22–6.25]:

[Ai+ 1 ]=[Ai]+

gigTi

gTidi

−

([Ai]di)([Ai]di)T

([Ai]di)Tdi

(6.124)

In practical computations, Eq. (6.124) is rewritten more conveniently in terms

of [Bi], as

[Bi+ 1 ]=[Bi]+

didTi

dTigi

(

1 +

gTi[Bi]gi

dTigi

)

−

[Bi]gidTi

dTigi

−

digTi[Bi]

dTigi

(6.125)

3 .The DFP and the BFGS formulas belong to a family of rank 2 updates known

asHuang’s family of updates[6.18], which can be expressed for updating the

inverse of the Hessian matrix as

[Bi+ 1 ]=ρi

(

[Bi]−

[Bi]gigTi[Bi]

gTi[Bi]gi

+θiyiyTi

)

+

didTi

dTigi

(6.126)

where

yi=(gTi[Bi]gi)^1 /^2

(

di

dTigi

−

[Bi]gi

gTi[Bi]gi

)

(6.127)

andρiandθiare constant parameters. It has been shown [6.18] that Eq. (6.126)

maintains the symmetry and positive definiteness of [Bi+ 1 ] if [Bi] is symmetric

and positive definite. Different choices ofρi andθi in Eq. (6.126) lead to

different algorithms. For example, whenρi= and 1 θi= , Eq. (6.126) gives 0

the DFP formula, Eq. (6.119). Whenρi= and 1 θi= , Eq. (6.126) yields the 1

BFGS formula, Eq. (6.125).