David G. Luenberger, Yinyu Ye - Linear and Nonlinear Programming International Series Episode 2 Part

292 Chapter 10 Quasi-Newton Methods

Finite Step Convergence

We assume now that f is quadratic with (constant) Hessian F. We show in this

case that the Davidon–Fletcher–Powell method produces direction vectors pk that

are F-orthogonal and that if the method is carried n steps then Hn = F−1.

Theorem. If f is quadratic with positive definite Hessian F, then for the

Davidon–Fletcher–Powell method

pT

i Fpj = 0 0 i<j k (23)

Hk+1Fpi = pi for 0 i k (24)

Proof. We note that for the quadratic case

qk = gk+1 −gk = Fxk+1 −Fxk = Fpk (25)

Also

Hk+1Fpk = Hk+1qk = pk (26)

from (17).

We now prove (23) and (24) by induction. From (26) we see that they are true

for k = 0. Assuming they are true for k−1, we prove they are true for k. We have

gk = gi+1 +Fpi+1 +···+pk−1

Therefore from (23) and (20)

pT

i gk = pT

i gi+1 = 0 for 0 i < k (27)

Hence from (24)

pT

i FHkgk = 0 (28)

Thus since pk = −kHkgk and since k = 0, we obtain

pT

i Fpk = 0 for i < k (29)

which proves (23) for k.

Now since from (24) for k−1, (25) and (29)

qT

k HkFpi = qT

k pi = pT

k Fpi = 0 0 i<k

we have

Hk+1Fpi = HkFpi = pi 0 i < k

This together with (26) proves (24) for k.

10.4 The Broyden Family 293

Since the pk’s are F-orthogonal and since we minimize f successively in these

directions, we see that the method is a conjugate direction method. Furthermore,

if the initial approximation H0 is taken equal to the identity matrix, the method

becomes the conjugate gradient method. In any case the process obtains the overall

minimum point within n steps.

Finally, (24) shows that p0, p1, p2pk are eigenvectors corresponding to

unity eigenvalue for the matrix Hk+1F. These eigenvectors are linearly independent,

since they are F-orthogonal, and therefore Hn = F−1.

10.4 THE BROYDEN FAMILY

The updating formulae for the inverse Hessian considered in the previous two

sections are based on satisfying

Hk+1qi = pi 0 i k (30)

which is derived from the relation

qi = Fpi 0 i k (31)

which would hold in the purely quadratic case. It is also possible to update approx￾imations to the Hessian F itself, rather than its inverse. Thus, denoting the kth

approximation of F by Bk, we would, analogously, seek to satisfy

qi = Bk+1pi 0 i k (32)

Equation (32) has exactly the same form as (30) except that qi and pi are

interchanged and H is replaced by B. It should be clear that this implies that

any update formula for H derived to satisfy (30) can be transformed into a corre￾sponding update formula for B. Specifically, given any update formula for H, the

complementary formula is found by interchanging the roles of B and H and of q

and p. Likewise, any updating formula for B that satisfies (32) can be converted

by the same process to a complementary formula for updating H. It is easily seen

that taking the complement of a complement restores the original formula.

To illustrate complementary formulae, consider the rank one update of

Section 10.2, which is

Hk+1 = Hk + pk −Hkqk pk −Hkqk

T

qT

k pk −Hkqk  (33)

The corresponding complementary formula is

Bk+1 = Bk + qk −Bkpk qk −Bkpk

T

pT

k qk −Bkpk  (34)