Continuous Optimisation HT26, Quasi-Newton methods

You can determine the $i$th column via the approximation

• If $h$ is too large, you have inaccurate approximations
• If $h$ is too small, you have numerical cancellation errors

At the start of line search, choose some $B^0$ (e.g. $I$). After computing $s^k = -(B^k)^{-1} \nabla f(x^k)$ and $x^{k+1} = x^k + \alpha^k s^k$, compute an update $B^{k+1}$ of $B^k$ in terms of already computed quantities $\nabla f(x^{k+1})$, $\nabla f(x^k)$, $\nabla f(x^0)$, etc.

We would like:

• $B^{k+1}$ should be symmetric, nonsingular and positive definite
• $B^{k+1}$ should be close to $B^k$
• $B^{k+1}$ should be cheap to compute
• $B^k \to \nabla^2 f(x^k)$

We choose $B^{k+1}$ such that

Let $f(x) = g^\top x + \frac 1 2 x^\top H x$. Then $\nabla f(x) = Hx + g$ and $\nabla^2 f = H$. Thus $\nabla f(x^{k+1}) - \nabla f(x^k) = H(x^{k+1} - x^k)$ and hence the secant equation holds with $B^{k+1} := \nabla^2 f$.

We implicitly have the quadratic model

We want the quadratic model in the next iteration

to correctly predict the change in gradient between iterations given by $\gamma^k := \nabla f(x^{k+1}) - \nabla f(x^k)$:

Choose $B^{k+1} := B^k + u^k (u^k)^\top$, where

• $u^k = \frac{\gamma^k - B^k \delta^k}{\rho^k}$
• $\delta^k := x^{k+1} - x^k = \alpha^k s^k$
• $(\rho^k)^2 := (\gamma^k - B^k \delta^k)^\top \delta^k > 0$

• $B^k$ may not be positive definite
• $s^k$ may not be a descent direction
• $\rho^k$ may be close to zero

via Sherman-Morrison-Woodbury formula.

Set

where $\delta^k := x^{k+1} - x^k$ and $\gamma^k := \nabla f(x^{k+1}) - \nabla f(x^k)$. This is a rank-2 update of $B^k$.

via the Sherman-Morrison-Woodbury formula.

If $B^k$ is symmetric positive definite and the curvature condition $(\delta^k)^\top \gamma^k > 0$ holds, then $B^{k+1}$ is symmetric positive definite.

The curvature condition is enforced by Wolfe linesearch but not by backtracking Armijo, which is why BFGS in practice is paired with Wolfe.

A generic linesearch method with

where $B^k$ is updated by the BFGS formula on each iteration.

We require Wolfe linesearch (∆wolfe-conditions) rather than backtracking Armijo.

Why: global convergence of BFGS in the GLM framework needs $B^k$ to stay positive definite — so that $s^k = -(B^k)^{-1}\nabla f(x^k)$ stays a descent direction and the umbrella ∆general-second-order-glm-global-convergence theorem applies (its eigenvalue hypothesis requires PD $B^k$). BFGS preserves PD iff the curvature condition $(\delta^k)^\top \gamma^k > 0$ holds (see ∆bfgs-preserves-positive-definiteness, ∆bite-bfgs-curvature-condition).

Wolfe enforces this. The curvature half (W2) says $\nabla f(x^{k+1})^\top s^k \ge c _ 2 \nabla f(x^k)^\top s^k$. Subtracting $\nabla f(x^k)^\top s^k$ from both sides:

where the second inequality uses $c _ 2 - 1 < 0$ and $\nabla f(x^k)^\top s^k < 0$ (descent direction). Multiplying by $\alpha^k > 0$ gives $(\delta^k)^\top \gamma^k = \alpha^k (s^k)^\top \gamma^k > 0$ — the curvature condition holds at every iteration.

Armijo doesn’t. Backtracking Armijo only enforces (W1) — sufficient decrease on $f(x^{k+1})$ — and says nothing about $\nabla f(x^{k+1})^\top s^k$. So $(\delta^k)^\top \gamma^k > 0$ can fail, $B^{k+1}$ can become indefinite, the next $s^{k+1}$ may not be descent, and the umbrella convergence theorem’s hypothesis breaks down.

The BFGS method has local Q-superlinear convergence.

Suppose:

• $f$ is a strictly convex quadratic, $f(x) = c + g^\top x + \tfrac{1}{2} x^\top H x$ with $H \in \mathbb R^{n \times n}$ symmetric positive definite — so $\nabla^2 f(x) \equiv H$ is constant in $x$
• the BFGS method uses exact linesearch

Then after at most $n$ iterations:

• $B^n = H$ (the BFGS approximation equals the true, constant Hessian of $f$); and
• $x^n = x^\ast = -H^{-1} g$ (the iterates terminate at the unique global minimiser).

In practice, BFGS maintains a Cholesky factor $L^k$ of $B^k$:

The rank-2 BFGS update for $B^k$ corresponds to a rank-2 update of $L^k$, computable in $O(n^2)$ flops.

Benefits over storing $B^k$ explicitly:

• Solving the Newton system $B^k s^k = -\nabla f(x^k)$ becomes two triangular solves: $L^k v = -\nabla f(x^k)$ (forward substitution), then $(L^k)^\top s^k = v$ (back substitution). Cost $O(n^2)$ instead of $O(n^3)$ for a generic dense solve.
• Positive-definiteness preservation is automatic: as long as $L^k$ stays nonsingular (no zero diagonal entry), $B^k = L^k (L^k)^\top$ is positive definite by construction. No need to verify PD-ness separately after each each update.
• Numerical stability: avoids forming $B^k$ or its inverse explicitly, which would amplify round-off from the secant update.

Cost summary: BFGS via Cholesky factors achieves $O(n^2)$ per iteration, matching the SMW (Sherman-Morrison-Woodbury) inverse-update approach but with better numerical stability.

1. Computable from already-known quantities ($\nabla f(x^{k+1}), \nabla f(x^k), \ldots, B^k, s^k$) — no second derivatives.
2. Symmetric and positive definite (so the resulting search direction $s^k = -(B^k)^{-1} \nabla f(x^k)$ is well-defined and descent).
3. Cheap update of $B^k$: $O(n^2)$ per iteration, not $O(n^3)$ as for forming/inverting from scratch.
4. Asymptotic convergence: $B^k \to \nabla^2 f(x^\ast)$ along the iterates, so the local rate approaches Newton’s.

These rule out “approximate the Hessian with finite differences each iteration” ($O(n^2)$ extra gradient evaluations) in favour of recurrence-based updates like ∆sr1-update and ∆bfgs-update-formula.

• Rank: SR1 is rank-1 ($B^{k+1} = B^k + uu^\top$, one outer product); BFGS is rank-2 (one term subtracted, one added).
• PD preservation: BFGS preserves PD when the curvature condition $\delta^\top \gamma > 0$ holds (enforced by Wolfe linesearch). SR1 does not preserve PD in general — $B^k$ may become indefinite, making $s^k$ ascent rather than descent.
• Reliability: SR1 has a denominator $\rho^k = ((\gamma - B\delta)^\top \delta)^{1/2}$ that can be near zero, causing the update to blow up; BFGS has more stable denominators. BFGS is preferred in practice; SR1 is used when an indefinite $B^k$ is acceptable (e.g. trust-region methods).

Cost: both $O(n^2)$ per iteration via Sherman-Morrison-Woodbury (∆sherman-morrison-woodbury).