Quasi-Newton Methods

Quasi-Newton methods are a class of optimization algorithms that approximate the Hessian matrix (or its inverse) to achieve faster convergence than first-order methods while avoiding the computational cost of computing and inverting the exact Hessian as in Newton’s method.

Motivation

Newton’s method has excellent convergence properties but requires:

1. Computing second derivatives to form the Hessian matrix $\mathbf{H}$
2. Solving a linear system or inverting the Hessian at each iteration

For large-scale problems, these operations can be prohibitively expensive. Quasi-Newton methods address this by:

• Using only gradient information to build an approximation of the Hessian or its inverse
• Updating this approximation at each iteration using the observed changes in gradients

General Framework

Quasi-Newton methods follow the update rule:

${\theta }_{k+1}={\theta }_k-{\alpha }_k{\mathbf{B}}_k^{-1}\nabla L({\theta }_k)$

where:

• ${\theta }_k$ is the parameter vector at iteration $k$
• ${\alpha }_k$ is the step size determined by line search
• ${\mathbf{B}}_k$ is an approximation to the Hessian matrix
• ${\mathbf{B}}_k^{-1}$ is an approximation to the inverse Hessian

Alternatively, some methods directly approximate the inverse Hessian, denoted as ${\mathbf{H}}_k\approx [{\nabla }^{2}L({\theta }_k){]}^{-1}$:

${\theta }_{k+1}={\theta }_k-{\alpha }_k{\mathbf{H}}_k\nabla L({\theta }_k)$

Secant Condition and Curvature Information

Quasi-Newton methods are based on the secant equation, which captures curvature information:

Define:

• ${\mathbf{s}}_k={\theta }_{k+1}-{\theta }_k$ (change in parameters)
• ${\mathbf{y}}_k=\nabla L({\theta }_{k+1})-\nabla L({\theta }_k)$ (change in gradients)

For a quadratic function, the exact Hessian would satisfy ${\mathbf{y}}_k=\mathbf{H}{\mathbf{s}}_k$.

Quasi-Newton methods update the approximate Hessian (or its inverse) to satisfy:

${\mathbf{B}}_{k+1}{\mathbf{s}}_k={\mathbf{y}}_k$

This is known as the secant condition or quasi-Newton condition.

Major Quasi-Newton Methods

BFGS (Broyden-Fletcher-Goldfarb-Shanno)

The most popular quasi-Newton method, which directly approximates the inverse Hessian:

${\mathbf{H}}_{k+1}=\left(I-\frac{{\mathbf{s}}_k{\mathbf{y}}_k^T}{{\mathbf{y}}_k^T{\mathbf{s}}_k}\right){\mathbf{H}}_k\left(I-\frac{{\mathbf{y}}_k{\mathbf{s}}_k^T}{{\mathbf{y}}_k^T{\mathbf{s}}_k}\right)+\frac{{\mathbf{s}}_k{\mathbf{s}}_k^T}{{\mathbf{y}}_k^T{\mathbf{s}}_k}$

BFGS Algorithm

1. Initialize ${\theta }_0$ and ${\mathbf{H}}_0$ (often ${\mathbf{H}}_0=\mathbf{I}$)
2. For each iteration $k$:
   • Compute search direction: ${\mathbf{p}}_k=-{\mathbf{H}}_k\nabla L({\theta }_k)$
   • Determine step size ${\alpha }_k$ via line search
   • Update parameters: ${\theta }_{k+1}={\theta }_k+{\alpha }_k{\mathbf{p}}_k$
   • Compute ${\mathbf{s}}_k={\theta }_{k+1}-{\theta }_k$ and ${\mathbf{y}}_k=\nabla L({\theta }_{k+1})-\nabla L({\theta }_k)$
   • Update the inverse Hessian approximation using the BFGS formula
3. Repeat until convergence

L-BFGS (Limited-memory BFGS)

A memory-efficient variant of BFGS for large-scale problems:

• Instead of storing the full $n\times n$ approximation matrix, L-BFGS stores only the last $m$ pairs of ${\mathbf{s}}_i,{\mathbf{y}}_i$
• The matrix-vector product ${\mathbf{H}}_k\nabla L({\theta }_k)$ is computed implicitly using these vectors
• Typically $m$ is between 3 and 20, regardless of the problem dimension

DFP (Davidon-Fletcher-Powell)

An earlier quasi-Newton method that also approximates the inverse Hessian:

${\mathbf{H}}_{k+1}={\mathbf{H}}_k-\frac{{\mathbf{H}}_k{\mathbf{y}}_k{\mathbf{y}}_k^T{\mathbf{H}}_k}{{\mathbf{y}}_k^T{\mathbf{H}}_k{\mathbf{y}}_k}+\frac{{\mathbf{s}}_k{\mathbf{s}}_k^T}{{\mathbf{y}}_k^T{\mathbf{s}}_k}$

SR1 (Symmetric Rank-One)

A simpler update that satisfies the secant condition:

${\mathbf{B}}_{k+1}={\mathbf{B}}_k+\frac{({\mathbf{y}}_k-{\mathbf{B}}_k{\mathbf{s}}_k)({\mathbf{y}}_k-{\mathbf{B}}_k{\mathbf{s}}_k{)}^T}{({\mathbf{y}}_k-{\mathbf{B}}_k{\mathbf{s}}_k{)}^T{\mathbf{s}}_k}$

• SR1 can produce indefinite Hessian approximations
• Often used in trust region methods rather than line search methods

Broyden’s Method

A generalization for non-symmetric matrices, useful in solving systems of nonlinear equations:

${\mathbf{B}}_{k+1}={\mathbf{B}}_k+\frac{({\mathbf{y}}_k-{\mathbf{B}}_k{\mathbf{s}}_k){\mathbf{s}}_k^T}{{\mathbf{s}}_k^T{\mathbf{s}}_k}$

Properties of Quasi-Newton Methods

Convergence Properties

• BFGS and DFP: Superlinear convergence rate for smooth, strongly convex functions
• L-BFGS: Slightly slower convergence than BFGS but much lower memory requirements
• SR1: Can have faster convergence but may encounter numerical difficulties

Positive Definiteness

• BFGS: Maintains positive definiteness of ${\mathbf{H}}_k$ if the initial approximation is positive definite and ${\mathbf{y}}_k^T{\mathbf{s}}_k>0$
• DFP: Similar to BFGS but more sensitive to line search accuracy
• SR1: Does not guarantee positive definiteness

Advantages

1. Efficiency: Avoids the $O(n^3)$ cost of computing and inverting the Hessian
2. Superlinear Convergence: Faster than first-order methods
3. Robustness: Less sensitive to poor scaling than gradient descent
4. Adaptivity: Automatically builds curvature information during optimization

Limitations

1. Memory Requirements: Standard BFGS requires $O(n^2)$ storage
2. Initialization Sensitivity: Performance can depend on the initial approximation
3. Non-Convex Problems: May struggle with highly non-convex functions
4. Numerical Stability: Updates can lead to ill-conditioned approximations

Implementation Considerations

Initial Hessian Approximation

Common choices for the initial inverse Hessian approximation:

• Identity matrix: ${\mathbf{H}}_0=\mathbf{I}$
• Scaled identity: ${\mathbf{H}}_0=\gamma \mathbf{I}$ where $\gamma >0$
• Diagonal approximation based on early curvature information

Curvature Condition

The condition ${\mathbf{y}}_k^T{\mathbf{s}}_k>0$ is necessary for positive definiteness of the BFGS update. If this condition is violated:

• Skip the update for that iteration
• Use a damped update: replace ${\mathbf{y}}_k$ with ${\mathbf{y}}_k^{\text{damp}}=\theta {\mathbf{y}}_k+(1-\theta ){\mathbf{B}}_k{\mathbf{s}}_k$
• Restart with a new initial approximation

Line Search

Quasi-Newton methods rely on accurate line searches to ensure the curvature information is valid:

• Wolfe conditions are typically used
• Inexact line searches can significantly degrade performance

L-BFGS Implementation

An efficient “two-loop recursion” algorithm for computing ${\mathbf{H}}_k\nabla L({\theta }_k)$ without explicitly forming ${\mathbf{H}}_k$:

q = ∇L(θk)
for i = k-1, k-2, ..., k-m:
    ρi = 1/(yi^T si)
    αi = ρi si^T q
    q = q - αi yi
r = H0 q
for i = k-m, k-m+1, ..., k-1:
    β = ρi yi^T r
    r = r + si(αi - β)
return r  # This is Hk ∇L(θk)

Applications

Quasi-Newton methods are widely used in:

• Machine Learning: Training models with moderate numbers of parameters
• Nonlinear Optimization: Engineering design, control systems
• Statistics: Maximum likelihood estimation
• Structural Optimization: Shape and topology optimization
• Energy Minimization: Molecular dynamics, computational chemistry

Related Pages

• Numerical Methods
• Newton-Raphson Method
• Gradient-Based Methods
• Line Search Methods
• Trust Region Methods
• L-BFGS Algorithm