Engineering Optimization: Theory and Practice, Fourth Edition

352 Nonlinear Programming II: Unconstrained Optimization Techniques

using Eq. (6.111) and the new pointX 3 is determined from Eq. (6.94). This iterative

process is continued until convergence is achieved. If [Bi] is symmetric, Eq. (6.111)

ensures that [Bi+ 1 ] is also symmetric. However, there is no guarantee that [Bi+ 1 ]

remains positive definite even if [Bi] is positive definite. This might lead to a breakdown

of the procedure, especially when used for the optimization of nonquadratic functions.

It can be verified easily that the columns of the matrix [

Bi] given by Eq. (6.111) are

multiples of each other. Thus the updating matrix has only one independent column and

hence the rank of the matrix will be 1. This is the reason why Eq. (6.111) is considered

to be a rank 1 updating formula. Although the Broyden formula, Eq. (6.111), is not

robust, it has the property of quadratic convergence [6.17]. The rank 2 update formulas

given next guarantee both symmetry and positive definiteness of the matrix [Bi+ 1 ]

and are more robust in minimizing general nonlinear functions, hence are preferred in

practical applications.

6.13.2 Rank 2 Updates

In rank 2 updates we choose the update matrix [

Bi] as the sum of two rank 1

updates as

[

Bi]=c 1 z 1 zT 1 +c 2 z 2 zT 2 (6.112)

where the constantsc 1 andc 2 and then-componentvectorsz 1 andz 2 are to be deter-

mined. Equations (6.103) and (6.112) lead to

[Bi+ 1 ]=[Bi]+c 1 z 1 zT 1 +c 2 z 2 zT 2 (6.113)

By forcing Eq. (6.113) to satisfy the quasi-Newton condition, Eq. (6.106), we obtain

di=[Bi]gi+c 1 z 1 (zT 1 gi)+c 2 z 2 (zT 2 gi) (6.114)

where(zT 1 gi) nda (zT 2 gi) an be identified as scalars. Although the vectorsc z 1 andz 2 in

Eq. (6.114) are not unique, the following choices can be made to satisfy Eq. (6.114):

z 1 =di (6.115)

z 2 =[Bi]gi (6.116)

c 1 =

1

zT 1 gi

(6.117)

c 2 = −

1

zT 2 gi

(6.118)

Thus the rank 2 update formula can be expressed as

[Bi+ 1 ]=[Bi] +[ Bi]≡[Bi]+

didTi

dTigi

−

([Bi]gi)([Bi]gi)T

([Bi]gi)Tgi

(6.119)

This equation is known as the Davidon–Fletcher–Powell (DFP) formula [6.20, 6.21].

Since

Xi+ 1 =Xi+λ∗iSi (6.120)