Quasi-Newton method

In optimization, quasi-Newton methods (also known as variable metric methods) are well-known algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on Newton's method to find the stationary point of a function, where the gradient is 0. Newton's method assumes that the function can be locally approximated as a quadratic in the region around the optimum, and use the first and second derivatives (gradient and Hessian) to find the stationary point.

In Quasi-Newton methods the Hessian matrix of second derivatives of the function to be minimized does not need to be computed. The Hessian is updated by analyzing successive gradient vectors instead. Quasi-Newton methods are a generalization of the secant method to find the root of the first derivative for multidimensional problems. In multi-dimensions the secant equation is under-determined, and quasi-Newton methods differ in how they constrain the solution, typically by adding a simple low-rank update to the current estimate of the Hessian.

The first quasi-Newton algorithm was proposed by W.C. Davidon, a physicist working at Argonne National Laboratory. He developed the first quasi-Newton algorithm in 1959: the DFP updating formula, which was later popularized by Fletcher and Powell in 1963, but is rarely used today. The most common quasi-Newton algorithms are currently the SR1 formula (for symmetric rank one) and the widespread BFGS method, that was suggested independently by Broyden, Fletcher, Goldfarb, and Shanno, in 1970. The Broyden's class is a linear combination of the DFP and BFGS methods.

The SR1 formula does not guarantee the update matrix to maintain positive-definiteness and can be used for indefinite problems. The Broyden's method does not require the update matrix to be symmetric and it is used to find the root of a general system of equations (rather than the gradient) by updating the Jacobian (rather than the Hessian).

Description of the method

As in Newton's method, one uses a second order approximation to find the minimum of a function $f(x)$. The Taylor series of $f(x)$ around an iterate is:

$f(x_{k}+\Delta x)\approx f(x_{k})+\nabla f(x_{k})^{T}\Delta x+{\frac {1}{2}}\Delta x^{T}{B}\Delta x$,

where ($\nabla f$) is the gradient and $B$ an approximation to the Hessian matrix. The gradient of this approximation (with respect to $\Delta x$) is

$\nabla f(x_{k}+\Delta x)\approx \nabla f(x_{k})+B\Delta x$

and setting this gradient to zero provides the Newton step:

$\Delta x=-B^{-1}\nabla f(x_{k})$,

The Hessian approximation $B$ is chosen to satisfy

$\nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\Delta x$,

which is called the secant equation. but this condition is not sufficient to determine $B$. In one dimension, solving for $B$ and applying the Newton's step with the updated value is equivalent to the secant method. In multidimensions $B$ is under determined. Various methods are used to find the solution to the secant equation that is symmetric ($B^{T}=B$) and closest to the current approximate value $B_{k}$ according to some metric $min_{B}||B-B_{k}||$. An approximate initial value of $B_{0}=I$ is often sufficient to achieve rapid convergence. The unknown $x_{k}$ is updated applying the Newton's step calculated using the current approximate Hessian matrix $B_{k}$

• $\Delta x_{k}=-\alpha _{k}B_{k}^{-1}\nabla f(x_{k})$, with $\alpha$ chosen to satisfy the Wolfe conditions;
• $x_{k+1}=x_{k}+\Delta x_{k}$;
• The gradient computed at the new point $\nabla f(x_{k+1})$, and

$y_{k}=\nabla f(x_{k+1})-\nabla f(x_{k})$,

• is used to update the Hessian $\displaystyle B_{k+1}$, or directly its inverse $\displaystyle H_{k+1}=B_{k+1}^{-1}$ using the Sherman-Morrison formula.
• A key property of the BFGS and DFP updates is that if $B_{k}$ is positive definite and $\alpha _{k}$ is chosen to satisfy the Wolfe conditions then $\displaystyle B_{k+1}$ is also positive definite.

The most popular update formulas are:

Method	$\displaystyle B_{k+1}=$	$H_{k+1}=B_{k+1}^{-1}=$
DFP	$\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}$	$H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}-{\frac {H_{k}y_{k}y_{k}^{T}H_{k}^{T}}{y_{k}^{T}H_{k}y_{k}}}$
BFGS	$B_{k}+{\frac {y_{k}y_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{T}}{\Delta x_{k}^{T}B_{k}\Delta x_{k}}}$	$\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)^{T}H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{T}}{y_{k}^{T}\Delta x_{k}}}$
Broyden	$B_{k}+{\frac {y_{k}-B_{k}\Delta x_{k}}{\Delta x_{k}^{T}\Delta x_{k}}}\Delta x_{k}^{T}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})y_{k}^{T}H_{k}}{y_{k}^{T}H_{k}\Delta x_{k}}}$
Broyden Family	$(1-\varphi _{k})B_{k+1}^{BFGS}+\varphi _{k}B_{k+1}^{DFP}$, $\varphi \in [0,1]$
SR1	$B_{k}+{\frac {(y_{k}-B_{k}\Delta x_{k})(y_{k}-B_{k}\Delta x_{k})^{T}}{(y_{k}-B_{k}\Delta x_{k})^{T}\Delta x_{k}}}$	$H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{T}}{(\Delta x_{k}-H_{k}y_{k})^{T}y_{k}}}$

See also

• Newton's method in optimization
• Newton's method
• DFP updating formula
• BFGS method
• SR1 formula
• Broyden's Method

References

• Eventually W.C. Davidon's paper published. William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991.
• Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.
• Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.