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 smooth function ${\displaystyle f(x)}${\displaystyle f(x)}, its gradient (${\displaystyle \nabla f}${\displaystyle \nabla f}), and positive-definite Hessian matrix ${\displaystyle B}${\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 ,}${\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 }${\displaystyle \nabla f(x_{k}+s_{k})=\nabla f(x_{k})+Bs_{k}+\dots }

is used to update ${\displaystyle B}${\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}}:

${\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},}${\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 y_{k}=\nabla f(x_{k}+s_{k})-\nabla f(x_{k}),}

${\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}},}${\displaystyle \gamma _{k}={\frac {1}{y_{k}^{T}s_{k}}},}

and ${\displaystyle B_{k}}${\displaystyle B_{k}} is a symmetric and positive-definite matrix.

The corresponding update to the inverse Hessian approximation ${\displaystyle H_{k}=B_{k}^{-1}}${\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 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}${\displaystyle B} is assumed to be positive-definite, and the vectors ${\displaystyle s_{k}^{T}}${\displaystyle s_{k}^{T}} and ${\displaystyle y}${\displaystyle y} must satisfy the curvature condition

${\displaystyle s_{k}^{T}y_{k}=s_{k}^{T}Bs_{k}>0.}${\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]

By unwinding the matrix recurrence for ${\displaystyle B_{k}}${\displaystyle B_{k}}, the DFP formula can be expressed as a compact matrix representation. Specifically, defining

$${\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},}$${\displaystyle S_{k}={\begin{bmatrix}s_{0}&s_{1}&\ldots &s_{k-1}\end{bmatrix}},} $${\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},}$${\displaystyle Y_{k}={\begin{bmatrix}y_{0}&y_{1}&\ldots &y_{k-1}\end{bmatrix}},}

and upper triangular and diagonal matrices

$${\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{YS}}{\big )}_{ij}=y_{i-1}^{T}s_{j-1},\quad (D_{k})_{ii}:={\big (}D_{k}^{\text{SY}}{\big )}_{ii}=s_{i-1}^{T}y_{i-1}\quad \quad {\text{ for }}1\leq i\leq j\leq k}$${\displaystyle {\big (}R_{k}{\big )}_{ij}:={\big (}R_{k}^{\text{SY}}{\big )}_{ij}=s_{i-1}^{T}y_{j-1},\quad {\big (}R_{k}^{\text{YS}}{\big )}_{ij}=y_{i-1}^{T}s_{j-1},\quad (D_{k})_{ii}:={\big (}D_{k}^{\text{SY}}{\big )}_{ii}=s_{i-1}^{T}y_{i-1}\quad \quad {\text{ for }}1\leq i\leq j\leq k}

the DFP matrix has the equivalent formula

$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},}$${\displaystyle B_{k}=B_{0}+J_{k}N_{k}^{-1}J_{k}^{T},}

$${\displaystyle J_{k}={\begin{bmatrix}Y_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}}$${\displaystyle J_{k}={\begin{bmatrix}Y_{k}&Y_{k}-B_{0}S_{k}\end{bmatrix}}}

$${\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{YS}}\\{\big (}R_{k}^{\text{YS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}}$${\displaystyle N_{k}={\begin{bmatrix}0_{k\times k}&R_{k}^{\text{YS}}\\{\big (}R_{k}^{\text{YS}}{\big )}^{T}&R_{k}+R_{k}^{T}-(D_{k}+S_{k}^{T}B_{0}S_{k})\end{bmatrix}}}

The inverse compact representation can be found by applying the Sherman-Morrison-Woodbury inverse to ${\displaystyle B_{k}}${\displaystyle B_{k}}. The compact representation is particularly useful for limited-memory and constrained problems.^[2]

• 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
• Compact quasi-Newton representation

• Davidon, W. C. (1959). "Variable Metric Method for Minimization". AEC Research and Development Report ANL-5990. doi:10.2172/4252678. hdl:2027/mdp.39015078508226 . OSTI 4252678.
• 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.

• Optimization algorithms and methods