Davidon–Fletcher–Powell formula

From The Right Wiki
Jump to navigationJump to search

The Davidon–Fletcher–Powell formula (or DFP; named after William C. Davidon, Roger Fletcher, and Michael J. D. Powell) finds the solution to the secant equation that is closest to the current estimate and satisfies the curvature condition. It was the first quasi-Newton method to generalize the secant method to a multidimensional problem. This update maintains the symmetry and positive definiteness of the Hessian matrix. Given a function f(x), its gradient (f), and positive-definite Hessian matrix B, the Taylor series is

f(xk+sk)=f(xk)+f(xk)Tsk+12skTBsk+,

and the Taylor series of the gradient itself (secant equation)

f(xk+sk)=f(xk)+Bsk+

is used to update B. The DFP formula finds a solution that is symmetric, positive-definite and closest to the current approximate value of Bk:

Bk+1=(IγkykskT)Bk(IγkskykT)+γkykykT,

where

yk=f(xk+sk)f(xk),
γk=1ykTsk,

and Bk is a symmetric and positive-definite matrix. The corresponding update to the inverse Hessian approximation Hk=Bk1 is given by

Hk+1=HkHkykykTHkykTHkyk+skskTykTsk.

B is assumed to be positive-definite, and the vectors skT and y must satisfy the curvature condition

skTyk=skTBsk>0.

The DFP formula is quite effective, but it was soon superseded by the Broyden–Fletcher–Goldfarb–Shanno formula, which is its dual (interchanging the roles of y and s).[1]

Compact representation

By unwinding the matrix recurrence for Bk, the DFP formula can be expressed as a compact matrix representation. Specifically, defining Sk=[s0s1sk1], Yk=[y0y1yk1], and upper triangular and diagonal matrices (Rk)ij:=(RkSY)ij=si1Tyj1,(RkYS)ij=yi1Tsj1,(Dk)ii:=(DkSY)ii=si1Tyi1 for 1ijk the DFP matrix has the equivalent formula Bk=B0+JkNk1JkT, Jk=[YkYkB0Sk] Nk=[0k×kRkYS(RkYS)TRk+RkT(Dk+SkTB0Sk)] The inverse compact representation can be found by applying the Sherman-Morrison-Woodbury inverse to Bk. The compact representation is particularly useful for limited-memory and constrained problems.[2]

See also

References

  1. Avriel, Mordecai (1976). Nonlinear Programming: Analysis and Methods. Prentice-Hall. pp. 352–353. ISBN 0-13-623603-0.
  2. Brust, J. J. (2024). "Useful Compact Representations for Data-Fitting". arXiv:2403.12206 [math.OC].

Further reading