Davidon–Fletcher–Powell formula explained

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 (\nabla f ), and positive-definite Hessian matrix B , the Taylor series isf(x _{k+s} _{k)} = f(x _{k)} + \nabla f(x ^{T} _{k)} s _{k} + (1)/(2) s ^{T} _{k} {B} s _{k} + ... ,

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

\nabla f(x _{k+s} _{k)} = \nabla f(x _{k)} + B s _{k} + ...

is used to update

B .

The DFP formula finds a solution that is symmetric, positive-definite and closest to the current approximate value of

B _{k} :B _{k+1} = (I - \gamma _{k} y _{k} s ^{T)} _{k} B _{k} (I - \gamma _{k} s _{k} y ^{T)} _{k} + \gamma _{k} y _{k} y ^{T,} _{k}

where

y _{k} = \nabla f(x _{k+s} _{k)} - \nabla f(x _{k),} \gamma _{k} = (1)/(y ^{T} _{k} s _{k}) ,

and

B _{k} is a symmetric and positive-definite matrix.

The corresponding update to the inverse Hessian approximation

H _{k} = B ^{-1} _{k} is given byH _{k+1} = H _{k} - (H _{k} y _{k} y ^{T} _{k} H _{k})/(y ^{T} _{k} H _{k} y _{k}) + (s _{k} s ^{T} _{k})/(y ^{T} _{k} s _{k}) . B is assumed to be positive-definite, and the vectors s ^{T} _{k} and y must satisfy the curvature conditions ^{T} _{k} y _{k} = s ^{T} _{k} B s _{k} > 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]

See also

• Newton's method
• Newton's method in optimization
• Quasi-Newton method
• Broyden–Fletcher–Goldfarb–Shanno (BFGS) method
• Limited-memory BFGS method
• Symmetric rank-one formula
• Nelder–Mead method

Further reading

• 10.2172/4252678 . W. C. . Davidon . Variable Metric Method for Minimization . AEC Research and Development Report ANL-5990 . 1959 . 2027/mdp.39015078508226 . free .
• Book: Fletcher . Roger . Practical methods of optimization . John Wiley & Sons . New York . 2nd . 978-0-471-91547-8 . 1987 . registration .
• Book: Kowalik . Osborne . M. R. . Methods for Unconstrained Optimization Problems . New York . Elsevier . 1968 . 0-444-00041-0 . 45–48 . registration .
• Book: Nocedal . Jorge . Wright . Stephen J. . 1999. Numerical Optimization. Springer-Verlag. 0-387-98793-2.
• Book: Walsh, G. R. . Methods of Optimization . London . John Wiley & Sons . 1975 . 0-471-91922-5 . 110–120 .

Notes and References

1. Book: Avriel, Mordecai . Nonlinear Programming: Analysis and Methods . Prentice-Hall . 1976 . 0-13-623603-0 . 352–353 .