Engineering Optimization: Theory and Practice, Fourth Edition

354 Nonlinear Programming II: Unconstrained Optimization Techniques

4.It has been shown that the BFGS method exhibits superlinear convergence near

X∗[6.17].

5 .Numerical experience indicates that the BFGS method is the best unconstrained

variable metric method and is less influenced by errors in findingλ∗icompared

to the DFP method.

6.The methods discussed in this section are also known as secant methods since

Eqs. (6.99) and (6.102) can be considered as secant equations (see Section 5.12).

The DFP and BFGS iterative methods are described in detail in the following sections.

6.14 Davidon–Fletcher–Powell Method

The iterative procedure of the Davidon–Fletcher–Powell (DFP) method can be

described as follows:

1.Start with an initial pointX 1 and an×npositive definite symmetric matrix

[B 1 ] to approximate the inverse of the Hessian matrix off.Usually, [B 1 ] is

taken as the identity matrix [I]. Set the iteration number asi=1.

2.Compute the gradient of the function,∇fi, at pointXi, and set

Si= −[Bi]∇fi (6.128)

3 .Find the optimal step lengthλ∗i in the directionSiand set

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

4 .Test the new pointXi+ 1 for optimality. IfXi+ 1 is optimal, terminate the iterative

process. Otherwise, go to step 5.

5.Update the matrix [Bi] using Eq. (6.119) as

[Bi+ 1 ]=[Bi]+[Mi]+[Ni] (6.130)

where

[Mi]=λ∗i

SiSTi

STigi

(6.131)

[Ni] =−

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

gTi[Bi]gi

(6.132)

gi = ∇f(Xi+ 1 ) −∇f (Xi) =∇fi+ 1 − ∇fi (6.133)

6 .Set the new iteration number asi=i+1, and go to step 2.

Note:The matrix [Bi+ 1 ], given by Eq. (6.130), remains positive definite only ifλ∗i

is found accurately. Thus ifλ∗iis not found accurately in any iteration, the matrix [Bi]

should not be updated. There are several alternatives in such a case. One possibility is to

compute a better value ofλ∗iby using more number of refits in the one-dimensional min-

imization procedure (until the productSTi∇fi+ 1 becomes sufficiently small). However,