Davidon-Fletcher-Powell formula

The Davidon-Fletcher-Powell formula (DFP) 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 which 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 ($abla\; f$), and positive definite Hessian matrix $B$, the Taylor series is::$f(x\_k+s\_k)=f(x\_k)+\; abla\; f(x\_k)^T\; s\_k+frac\{1\}\{2\}\; s^T\_k\; \{B\}\; s\_k$,and the Taylor series of the gradient itself (secant equation)::$abla\; f(x\_k+s\_k)=\; abla\; 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\_k^T)\; B\_k\; (I-gamma\_k\; s\_k\; y\_k^T)+gamma\_k\; y\_k\; y\_k^T$,where:$y\_k=\; abla\; f(x\_k+Delta\; x\_k)-\; abla\; f(x\_k)$,:$gamma\_k\; =frac\{1\}\{y\_k^T\; s\_k\}$.and $B\_k$ is a symmetric and positive definite matrix.The corresponding update to the inverse Hessian approximation $H\_k=B\_k^\{-1\}$ is given by::$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\}$.

$B$ is assumed to be positive definite, and the vectors $s\_k^T$ and $y$ must satisfy the curvature condition:: $s\_k^T\; y\_k=s\_k^T\; B\; s\_k>0$.The DFP formula is quite effective, but it was soon superseded by the BFGS formula.

ee also

* Newton's method
* Newton's method in optimization
* Quasi-Newton method
* Broyden-Fletcher-Goldfarb-Shanno (BFGS) method
* L-BFGS method
* SR1 formula

References

* W. C. Davidon, Variable metric method for minimization, SIAM Journal on Optimization 1, 1-17 (1991).
* Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.