Davidon-Fletcher-Powell formula

From Wikipedia, the free encyclopedia

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 ( $\nabla f$ ), and positive definite Hessian matrix $B$ , the Taylor series is:

$f(x_k+s_k)=f(x_k)+\nabla 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):

$\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_k^T) B_k (I-\gamma_k s_k y_k^T)+\gamma_k y_k y_k^T$ ,

where

$y_k=\nabla f(x_k+\Delta x_k)-\nabla 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.

[edit] See also

[edit] 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.

Categories: Optimization algorithms

Davidon-Fletcher-Powell formula

From Wikipedia, the free encyclopedia

[edit] See also

[edit] References

Views

Navigation

Interaction

Search