The Davidon–Fletcher–Powell formula (or DFP; named after William C. Davidon, Roger Fletcher, and

Michael J. D. Powell Michael James David Powell (29 July 193619 April 2015) was a British mathematician, who worked in the Department of Applied Mathematics and Theoretical Physics (DAMTP) at the University of Cambridge. Education and early life Born in London, Pow ...

) 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 Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. ...

to generalize the

secant method In numerical analysis, the secant method is a root-finding algorithm that uses a succession of roots of secant lines to better approximate a root of a function ''f''. The secant method can be thought of as a finite-difference approximation o ...

to a multidimensional problem. This update maintains the symmetry and positive definiteness of the

Hessian matrix In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a scalar-valued function, or scalar field. It describes the local curvature of a function of many variables. The Hessian matrix was developed ...

. Given a function

f(x)

, its

gradient In vector calculus, the gradient of a scalar-valued differentiable function of several variables is the vector field (or vector-valued function) \nabla f whose value at a point p is the "direction and rate of fastest increase". If the gr ...

(

\nabla f

), and positive-definite

B

, the

Taylor series In mathematics, the Taylor series or Taylor expansion of a function is an infinite sum of terms that are expressed in terms of the function's derivatives at a single point. For most common functions, the function and the sum of its Taylor ser ...

is :

f(x_k+s_k) = f(x_k) + \nabla f(x_k)^T s_k + \frac s^T_k  s_k + \dots,

and the

of the gradient itself (secant equation) :

\nabla f(x_k+s_k) = \nabla f(x_k) + B s_k + \dots

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

\gamma_k = \frac,

and

B_k

is a symmetric and

positive-definite matrix In mathematics, a symmetric matrix M with real entries is positive-definite if the real number z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a ...

. The corresponding update to the inverse Hessian approximation

H_k = B_k^

is given by :

H_ = H_k - \frac + \frac.

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 Broyden–Fletcher–Goldfarb–Shanno formula, which is its dual (interchanging the roles of ''y'' and ''s'').

See also

References

Further reading