# Davidon–Fletcher–Powell formula

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 (see below). 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 ${\displaystyle f(x)}$, its gradient (${\displaystyle \nabla f}$), and positive definite Hessian matrix ${\displaystyle B}$, the Taylor series is:

${\displaystyle f(x_{k}+s_{k})=f(x_{k})+\nabla f(x_{k})^{T}s_{k}+{\frac {1}{2}}s_{k}^{T}{B}s_{k},}$

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

${\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k},}$

is used to update ${\displaystyle B}$. The DFP formula finds a solution that is symmetric, positive definite and closest to the current approximate value of ${\displaystyle B_{k}}$:

${\displaystyle B_{k+1}=(I-\gamma _{k}y_{k}s_{k}^{T})B_{k}(I-\gamma _{k}s_{k}y_{k}^{T})+\gamma _{k}y_{k}y_{k}^{T},}$

where

${\displaystyle y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k}),}$
${\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}}.}$

and ${\displaystyle B_{k}}$ is a symmetric and positive definite matrix. The corresponding update to the inverse Hessian approximation ${\displaystyle H_{k}=B_{k}^{-1}}$ is given by:

${\displaystyle H_{k+1}=H_{k}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}y_{k}}}+{\frac {s_{k}s_{k}^{T}}{y_{k}^{T}s_{k}}}.}$

${\displaystyle B}$ is assumed to be positive definite, and the vectors ${\displaystyle s_{k}^{T}}$ and ${\displaystyle y}$ must satisfy the curvature condition:

${\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0.\,}$

The DFP formula is quite effective, but it was soon superseded by the BFGS formula, which is its dual (interchanging the roles of y and s).

## References

• Davidon, W. C. (1991), "Variable metric method for minimization", SIAM Journal on Optimization, 1: 1–17, doi:10.1137/0801001
• Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999), Numerical Optimization, Springer-Verlag, ISBN 0-387-98793-2
Retrieved from "https://en.wikipedia.org/w/index.php?title=Davidon–Fletcher–Powell_formula&oldid=722698843"
This content was retrieved from Wikipedia : http://en.wikipedia.org/wiki/Davidon–Fletcher–Powell_formula
This page is based on the copyrighted Wikipedia article "Davidon–Fletcher–Powell formula"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA