11. Newton and Quasi-Newton Methods — Using Curvature while Controlling Cost

// CORE 5/7 — Newton, quasi-Newton, DFP, BFGS

Gradient descent looks only at first-order information. The Newton family uses second-order curvature to construct more intelligent steps, but calculating the Hessian and solving linear systems is costly.

Newton

Newton's method minimizes the second-order Taylor model:

$$m_k(p)=f(x_k)+\nabla f(x_k)^\top p+\frac{1}{2}p^\top \nabla^2 f(x_k)p.$$

Minimizing this quadratic model with respect to $p$ gives the Newton equation:

$$\nabla^2 f(x_k)p_k=-\nabla f(x_k).$$

The update is

$$x_{k+1}=x_k+p_k.$$

Under good conditions it converges extremely quickly, but if the Hessian is not positive definite, $p_k$ may not be a descent direction.

Damped Newton

In practice, line search is usually added:

$$x_{k+1}=x_k+\alpha_k p_k.$$

This combines the fast local convergence of the Newton direction with the stability of line search.

Quasi-Newton

Quasi-Newton methods do not calculate the Hessian or inverse Hessian directly; they approximate it during iteration.

Define the changes in position and gradient:

$$s_k=x_{k+1}-x_k,$$ $$y_k=\nabla f(x_{k+1})-\nabla f(x_k).$$

A good Hessian approximation should satisfy the secant equation:

$$B_{k+1}s_k=y_k.$$

DFP

DFP is a classical quasi-Newton method that updates an inverse-Hessian approximation $H_k\approx (\nabla^2 f(x_k))^{-1}$. It obtains the direction as

$$p_k=-H_k\nabla f(x_k).$$

DFP is historically important, but BFGS is generally used more often in practice because it is more stable.

BFGS

BFGS is a quasi-Newton update that preserves positive definiteness well. If $s_k^\top y_k>0$ and $B_k$ is positive definite, then $B_{k+1}$ also remains positive definite.

This property makes a BFGS direction likely to be a descent direction and works well with Wolfe line search.

Large-scale problems frequently use L-BFGS, which does not store the full matrix.

Comparison

Method	Information	Advantage	Cost
Gradient descent	Gradient	Cheap and simple	Many iterations
Newton	Gradient + Hessian	Extremely fast locally	Expensive Hessian/linear solve
DFP	Gradient history	Approximates inverse Hessian	Requires matrix storage
BFGS	Gradient history	Stable and strong in practice	Requires matrix storage
L-BFGS	Recent history	Supports large scale	Approximation quality depends on history

Next: Coordinate Descent and Conjugate Gradient