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. 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}+\dots ,}$

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

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

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

See also

• Newton's method
• Newton's method in optimization
• Quasi-Newton method
• Broyden–Fletcher–Goldfarb–Shanno (BFGS) method
• Limited-memory BFGS method
• Symmetric rank-one formula
• Nelder–Mead method

References

Further reading

• Davidon, W. C. (1959). "Variable Metric Method for Minimization". AEC Research and Development Report ANL-5990. doi:10.2172/4252678. hdl:2027/mdp.39015078508226.
• Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-91547-8.
• Kowalik, J.; Osborne, M. R. (1968). Methods for Unconstrained Optimization Problems. New York: Elsevier. pp. 45–48. ISBN 0-444-00041-0.
• Nocedal, Jorge; Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.
• Walsh, G. R. (1975). Methods of Optimization. London: John Wiley & Sons. pp. 110–120. ISBN 0-471-91922-5.

• v
• t
• e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

Functions Golden-section search Interpolation methods Line search Nelder–Mead method Successive parabolic interpolation Gradients Convergence Trust region Wolfe conditions Quasi–Newton Berndt–Hall–Hall–Hausman Broyden–Fletcher–Goldfarb–Shanno and L-BFGS Davidon–Fletcher–Powell Symmetric rank-one (SR1) Other methods Conjugate gradient Gauss–Newton Gradient Mirror Levenberg–Marquardt Powell's dog leg method Truncated Newton Hessians Newton's method

Constrained nonlinear
General Barrier methods Penalty methods Differentiable Augmented Lagrangian methods Sequential quadratic programming Successive linear programming

Convex optimization
Convex minimization Cutting-plane method Reduced gradient (Frank–Wolfe) Subgradient method Linear and quadratic Interior point Affine scaling Ellipsoid algorithm of Khachiyan Projective algorithm of Karmarkar Basis-exchange Simplex algorithm of Dantzig Revised simplex algorithm Criss-cross algorithm Principal pivoting algorithm of Lemke

Combinatorial
Paradigms Approximation algorithm Dynamic programming Greedy algorithm Integer programming Branch and bound/cut Graph algorithms Minimum spanning tree Borůvka Prim Kruskal Shortest path Bellman–Ford SPFA Dijkstra Floyd–Warshall Network flows Dinic Edmonds–Karp Ford–Fulkerson Push–relabel maximum flow

Metaheuristics
Evolutionary algorithm Hill climbing Local search Parallel metaheuristics Simulated annealing Spiral optimization algorithm Tabu search

• Software