The Davidon–Fletcher–Powell formula (or DFP; named after
William C. Davidon
William Cooper Davidon (March 18, 1927 – November 8, 2013) was an American professor of physics and mathematics, and a peace activist. As the mastermind of the March 8, 1971, FBI office break-in, in Media, Pennsylvania, Davidon was the informal ...
,
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 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 to a multidimensional problem. This update maintains the symmetry and positive definiteness of the
Hessian matrix.
Given a function
, 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 gradi ...
(
), and
positive-definite In mathematics, positive definiteness is a property of any object to which a bilinear form or a sesquilinear form may be naturally associated, which is positive-definite. See, in particular:
* Positive-definite bilinear form
* Positive-definite fu ...
Hessian matrix , 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 serie ...
is
:
and 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 serie ...
of the gradient itself (secant equation)
:
is used to update
.
The DFP formula finds a solution that is symmetric, positive-definite and closest to the current approximate value of
:
:
where
:
:
and
is a symmetric and
positive-definite matrix.
The corresponding update to the inverse Hessian approximation
is given by
:
is assumed to be positive-definite, and the vectors
and
must satisfy the curvature condition
:
The DFP formula is quite effective, but it was soon superseded by the
Broyden–Fletcher–Goldfarb–Shanno formula, which is its
dual
Dual or Duals may refer to:
Paired/two things
* Dual (mathematics), a notion of paired concepts that mirror one another
** Dual (category theory), a formalization of mathematical duality
*** see more cases in :Duality theories
* Dual (grammatical ...
(interchanging the roles of ''y'' and ''s'').
See also
*
Newton's method
In numerical analysis, Newton's method, also known as the Newton–Raphson method, named after Isaac Newton and Joseph Raphson, is a root-finding algorithm which produces successively better approximations to the roots (or zeroes) of a real-valu ...
*
Newton's method in optimization
*
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. ...
*
Broyden–Fletcher–Goldfarb–Shanno (BFGS) method
*
Limited-memory BFGS method
*
Symmetric rank-one formula
*
Nelder–Mead method
The Nelder–Mead method (also downhill simplex method, amoeba method, or polytope method) is a numerical method used to find the minimum or maximum of an objective function in a multidimensional space. It is a direct search method (based on ...
References
Further reading
*
*
*
*
*
{{DEFAULTSORT:Davidon-Fletcher-Powell formula
Optimization algorithms and methods