Continuous Optimisation HT26, Newton's method

Recall that a ∆descent-direction is such that $\nabla f(x^k)^\top s^k < 0$. Since

Then whenever $\nabla f(x^k) \ne 0$, by positive definiteness we have that $\nabla f(x^k)^\top s^k < 0$.

$s^k$ uniquely solves

where $m _ k(s)$ is a convex quadratic function in $s$. Sensible choices might e.g. pick $s$ as the minimiser of the second-order Taylor approximation around $x^k$.

• Choose $\epsilon > 0$ and $x^0 \in \mathbb R^n$.
• While $ \vert \vert \nabla f(x^k) \vert \vert > \epsilon$, repeat:
  • Solve the linear system $\nabla^2 f(x^k) s^k = -\nabla f(x^k)$
  • Set $x^{k+1} = x^k + \alpha^k s^k$, where $\alpha^k \in (0, 1]$ (computed by e.g. exact linesearch)
  • Set $k := k+1$

where we hope $\nabla^2 f(x^k)$ is positive definite so that $s^k$ is a descent direction.

$s^k$ is minimises the second-order Taylor approximation of $f$ around $x^k$.

$\alpha^k = 1$ for all $k$.

This is equivalent to applying Newton’s method to $\nabla f(x)$.

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$
• $\nabla f(x^\ast) = 0$
• $\nabla^2 f(x^\ast)$ nonsingular
• $\nabla^2 f$ is locally Lipschitz continuous at $x^\ast$
• For some $k _ 0 \ge 0$, $x^{k _ 0}$ is sufficiently close to $x^\ast$

Then:

• $x^k$ is well-defined for all $k \ge k^0$
• $x^k \to x^\ast$ as $k \to \infty$ at a quadratic rate
• $\nabla f(x^k) \to 0$ at a quadratic rate

Consider the Taylor expansion of $\nabla f$ around $x$:

where $x$ is sufficiently close to $x^\ast$ and $O(\cdot)$ depends on the Lipschitz constant of $\nabla^2 f(x^\ast)$. Then by $\nabla f(x^\ast) = 0$ and $x = x^k$ whenever $x^k$ sufficiently close to $x^\ast$, we have

Then as $\nabla^2 f(x^\ast)$ nonsingular, we have that $\nabla^2 f(x^k)$ is nonsingular whenever $x^k$ is sufficiently close to $x^\ast$. Hence the above implies that

Letting $s^k$ be the Newton direction and $x^{k+1} = x^k + s^k$, it follows that

Hence

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$
• $\nabla^2 f$ is Lipschitz continuous and positive definite at the iterates
• $\alpha _ {(0)} = 1$ and $\beta \le 0.5$ in the ∆armijo-condition
• $x^k \to x^\ast$ as $k \to \infty$
• $\nabla f(x^\ast) = 0$
• $\nabla^2 f(x^\ast) \succ 0$

Then:

• $\alpha^k = 1$ for all $k$ sufficiently large
• $x^k \to x^\ast$ converges quadratically

Newton’s method is scale invariant with respect to linear transformations of variables.

Let $\mathbf A \in \mathbb R^{n \times n}$ is a nonsingular matrix and let $y = \mathbf A x$. Write $\mathbf B = \mathbf A^{-1}$ and consider

We aim to show that minimising $\bar f$ with respect to $y$ is equivalent to minimising $f$ with respect to $x$.

From the definitions, we have that

Hence the ∆newton-direction at $y$ is given by

Hence $y + \alpha s _ y = \mathbf A(x + \alpha s _ x)$.

• Advantages
  • Quadratic local convergence: $ \vert \vert x^{k+1} - x^\ast \vert \vert = O( \vert \vert x^k - x^\ast \vert \vert ^2)$
  • Scale invariance: is invariant to linear transformations
  • Automatic step size: once close to the solution, the step size needs no adaptation or backtracking
• Disadvantages
  • Newton direction $s^k$ is not well-defined if $\nabla^2 f(x^k)$ is singular
  • Iterates can get attracted to local maxima or saddle points
  • Iterates may fail to converge if $x^0$ is too far from solution

Then $x^\ast = 0$ is a local minimiser and $x = \pm \sqrt{(1 + \sqrt{17})/2}$ is a global maximum. Then if Newton’s method is applied to $f$ with $x^0 = 1$, $x^{2k} = 1$ and $x^{2k+1} = -1$ for all $k$.

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$
• $\nabla f$ is Lipschitz continuous
• We minimise $f$ with Newton’s method and backtracking Armijo linesearch, with the GLM termination tolerance $\epsilon$ (from the loop “while $\|\nabla f(x^k)\| > \epsilon$” in ∆newtons-method / ∆generic-linesearch-method) set to $\epsilon := 0$, so the iteration runs forever unless an exact stationary point is hit
• For all $x^k$, suppose the eigenvalues of $\nabla^2 f(x^k)$ at the iterates $x^k$ are positive and uniformly bounded below away from $0$ independently of $k$

Then either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$ (the algorithm hits an exact stationary point at iterate $l$) or $\|\nabla f(x^k)\| \to 0$ as $k \to \infty$ (the iterates’ gradient norms decay asymptotically to zero).

$f$ being strongly convex is sufficient to imply the fourth condition above.

Note that these conditions satisfy the prerequisites for ∆global-convergence-of-backtracking-armijo. Hence there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, or

Assume now that $\nabla f(x^k) \ne 0$ for all $k \ge 0$. Then we are left showing that $(\ast)$ result implies $\nabla f(x^k) \to 0$ as $k \to \infty$. To do this, we will express the terms in $(\ast)$ in terms of $\nabla f(x^k)$.

Let $\nabla^2 f(x^k) := H _ k$. The eigenvalues of $\nabla^2 f(x^k) = H^k$ are positive and uniformly bounded below, away from zero for all $k$, and by ∆lipschitz-continuous-iff-bounded-hessian we have that the eigenvalues of $\nabla^2 f$ are bounded above by $L$. Thus by the ∆rayleigh-ritz-theorem returning to $(\ast)$, we see from the definition of $s^k$ and $\nabla f(x^k)$ that

Then $s^k = -H _ k^{-1}\nabla f(x^k)$ implies

and thus

Furthermore, by the previous results we have that

for all $k$. This and $(\ast)$ then imply that $\nabla f(x^k) \to 0$ as $k \to \infty$.

Suppose:

• $f \in \mathcal C^1 (\mathbb R^n)$
• $f$ is bounded below on $\mathbb R^n$
• $\nabla f$ is Lipschitz continuous
• We minimise $f$ via backtracking Armijo linesearch with $s^k$ chosen according to $B^k s^k = -\nabla f(x^k)$, where $B^k$ is any symmetric matrix
• For all $k$, the eigenvalues of $B^k$ are uniformly bounded above and below away from $0$ independently of $k$ (in particular, $B^k$ is PD with $s^k$ a descent direction)

Then either there exists $l \ge 0$ such that $\nabla f(x^l) = 0$ or $ \vert \vert \nabla f(x^k) \vert \vert \to 0$ as $k \to \infty$.

Specialisations:

• $B^k := \nabla^2 f(x^k)$ recovers the Newton-bArmijo result ∆newton-barmijo-global-convergence.
• $B^k := \nabla^2 f(x^k) + M^k$ for the modified-Newton shifts (∆modified-damped-newton-overview).
• $B^k$ updated by BFGS / SR1 secant recurrences (∆bfgs-update-formula, ∆sr1-update) — the eigenvalue bound is the substantive assumption here (BFGS automatically preserves PD given the curvature condition; the uniform upper/lower bounds are needed to apply this theorem).

The argument is identical to ∆newton-barmijo-global-convergence-proof with $B^k$ in place of $H _ k := \nabla^2 f(x^k)$; the only change is that the eigenvalue bounds are now hypotheses rather than consequences of $\nabla f$ being Lipschitz.

Since $B^k$ has positive eigenvalues, $s^k = -(B^k)^{-1}\nabla f(x^k)$ is a descent direction, so the conditions satisfy the prerequisites for ∆global-convergence-of-backtracking-armijo. Hence there exists $l \ge 0$ such that $\nabla f(x^l) = 0$, or

Assume now that $\nabla f(x^k) \ne 0$ for all $k \ge 0$; we express the terms in $(\ast)$ via $\nabla f(x^k)$.

By hypothesis there exist $0 < \lambda_\min \le \lambda_\max$, independent of $k$, with $\lambda_\min \le \lambda_\min(B^k)$ and $\lambda_\max(B^k) \le \lambda_\max$. (Unlike ∆newton-barmijo-global-convergence-proof, the upper bound is assumed, not supplied by ∆lipschitz-continuous-iff-bounded-hessian — $B^k$ need not be the Hessian.) Thus by the ∆rayleigh-ritz-theorem, returning to $(\ast)$,

Then $s^k = -(B^k)^{-1}\nabla f(x^k)$ implies

and thus

Combining the two bounds,

for all $k$. This and $(\ast)$ then imply that $\nabla f(x^k) \to 0$ as $k \to \infty$.

We instead solve

where:

• $M^k$ is chosen such that $\nabla^2 f(x^k) + M^k$ is sufficiently positive definite
• $M^k := 0$ when $\nabla^2 f(x^k)$ is sufficiently positive definite

As $\nabla^2 f(x^k)$ is symmetric, we may factor

where $Q^k$ is orthogonal and $D^k$ is diagonal. Then we may set

for some small $\epsilon > 0$.

(this is expensive for large problems)

Estimate $\lambda _ \min(\nabla^2 f(x^k))$ and set

(this is biased to overemphasise large negative eigenvalues at the expense of small, positive ones).

Compute the Cholesky factorisation

where $L^k$ is a lower triangular matrix, and we modify the generated $L^k$ if the factorisation is in danger of failing.

Step 1: $\alpha^k = 1$ eventually accepted.

Let $s^k = -[\nabla^2 f(x^k)]^{-1} \nabla f(x^k)$ be the Newton direction. Then

By Taylor’s theorem,

where in the second condition we use the fact that $(s^k)^\top \nabla^2 f(x^k) s^k$ partially cancels due to the definition of $s^k$. The Armijo condition at $\alpha = 1$ requires $f(x^k + s^k) \le f(x^k) + \beta \nabla f(x^k)^\top s^k$, which is equivalent to

Since $\beta < 1/2$, the coefficient $\tfrac 1 2 - \beta > 0$, and $\nabla f(x^k)^\top s^k < 0$ (Newton’s direction is descent under $\nabla^2 f(x^k) \succ 0$), so the leading term is strictly negative. As $x^k \to x^\ast$ with $\nabla f(x^\ast) = 0$ an $\nabla^2 f(x^\ast) \succ 0$, $s^k = -[\nabla^2 f(x^k)]^{-1} \nabla f(x^k) \to 0$, so the $o(\|s^k\|^2)$ term is negligible relative to the leading term. The inequality therefore holds for all $k$ sufficiently large, and since $\alpha _ {(0)} = 1$ is the first trial step, bArmijo terminates immediately with $\alpha^k = 1$.

Step 2: quadratic convergence.

Once $\alpha^k = 1$ for all large $k$, the iteration is pure Newton: $x^{k+1} = x^k - [\nabla^2 f(x^k)]^{-1} \nabla f(x^k)$. The hypotheses (Lipschitz $\nabla^2 f$ near $x^\ast$, $\nabla^2 f(x^\ast)$ nonsingular, $x^k$ sufficiently close to $x^\ast$) match those of ∆newtons-method-convergence, so $x^k \to x^\ast$ at a quadratic rate.

The neighbourhood $\mathcal N(x^\ast, \delta)$ in which the theorem holds depends on $x^\ast$ (unknown), the local Lipschitz constant of $\nabla^2 f$, and other problem-dependent constants — none of which are known in advance. So we cannot pick $x^0$ to guarantee membership in $\mathcal N$.

In practice this is why pure Newton is usually wrapped in a globalisation: either a linesearch (∆newtons-method, with $\alpha^k$ chosen by bArmijo) or a trust-region scheme. Globalisation makes the iterates approach $x^\ast$ from anywhere, and the proof of ∆newtons-method-using-backtracking-armijo-convergence then shows the fast quadratic rate kicks in once $x^k$ enters the (still unknown) basin.

• Taylor-expand $\nabla f$ around $x^k$ and evaluate at $x^\ast$, using $\nabla f(x^\ast) = 0$: $0 = \nabla f(x^k) + \nabla^2 f(x^k)(x^\ast - x^k) + O(\|x^\ast - x^k\|^2)$, where the $O$ constant comes from the local Lipschitz constant of $\nabla^2 f$.
• Argue $\nabla^2 f(x^k)$ is nonsingular for $x^k$ near $x^\ast$ (from $\nabla^2 f(x^\ast)$ nonsingular and continuity), so we can solve.
• Rearrange: $x^k - x^\ast = (\nabla^2 f(x^k))^{-1} \nabla f(x^k) + O(\|x^k - x^\ast\|^2)$.
• Identify the inverse-gradient term with $-s^k = x^k - x^{k+1}$ (definition of the Newton direction).
• Conclude $x^{k+1} - x^\ast = O(\|x^k - x^\ast\|^2)$, i.e. quadratic convergence.

• Lipschitz enters in the remainder of the Taylor expansion of $\nabla f$. With Lipschitz $\nabla^2 f$ (constant $L _ H$ locally), the remainder is bounded by $\tfrac{1}{2} L _ H \|x^\ast - x^k\|^2$ — i.e. genuinely $O(\|x^\ast - x^k\|^2)$ with an explicit constant.
• With only continuity of $\nabla^2 f$, the remainder is $o(\|x^\ast - x^k\|)$ but not $O(\|x^\ast - x^k\|^2)$. The conclusion weakens from quadratic to merely superlinear convergence.

• It ensures $\nabla^2 f(x^k)$ is also nonsingular for $x^k$ sufficiently close to $x^\ast$ (matrix-invertibility is open, plus $\nabla^2 f$ is continuous). This is what makes the Newton iterate well-defined for all $k \ge k _ 0$.
• Algebraically, it lets us multiply the Taylor identity $0 = \nabla f(x^k) + \nabla^2 f(x^k)(x^\ast - x^k) + O(\|x^\ast - x^k\|^2)$ through by $(\nabla^2 f(x^k))^{-1}$ to extract the Newton-direction expression.
• Note this is weaker than positive-definiteness: pure Newton can converge to maxima and saddles too (cf. ∆pure-newton-failure-oscillation-example). Positive-definiteness becomes essential only when we need a descent direction for globalisation.

@bite~ @proofsupport~

• Set up: let $A$ be nonsingular, $y = Ax$, $B = A^{-1}$, and $\bar f(y) := f(By)$. Aim to show $y + \alpha s _ y = A(x + \alpha s _ x)$, i.e. iterates in the two coordinate systems are related by $A$.
• Chain-rule the derivatives: $\nabla \bar f(y) = B^\top \nabla f(x)$, $\nabla^2 \bar f(y) = B^\top \nabla^2 f(x) B$.
• Substitute into the Newton-direction formula $s _ y = -(\nabla^2 \bar f(y))^{-1} \nabla \bar f(y)$ and use $(B^\top M B)^{-1} = B^{-1} M^{-1} B^{-\top}$ to cancel the $B^\top$ factors.
• Read off $s _ y = A s _ x$, hence $y + \alpha s _ y = A(x + \alpha s _ x)$ for any $\alpha$.

• Apply ∆global-convergence-of-backtracking-armijo (Theorem 4): hypotheses (bounded-below $f$, Lipschitz $\nabla f$, descent $s^k$) hold, so either $\nabla f(x^l) = 0$ for some $l$, or $E _ k := \min\{ \vert \nabla f^\top s^k \vert /\|s^k\|, \vert \nabla f^\top s^k \vert \} \to 0$.
• The remaining task: convert $E _ k \to 0$ into $\|\nabla f(x^k)\| \to 0$.
• Use Rayleigh–Ritz (∆rayleigh-ritz-theorem) on $H _ k := \nabla^2 f(x^k)$ to bound the descent term $ \vert \nabla f^\top s^k \vert = \nabla f^\top H _ k^{-1} \nabla f$ below by $\|\nabla f\|^2 / \lambda _ \max(H _ k) \ge \|\nabla f\|^2 / \lambda _ \max$ (using Lipschitz $\nabla f$ ⟺ bounded Hessian ⟺ ∆lipschitz-continuous-iff-bounded-hessian).
• Use Rayleigh–Ritz on $H _ k^{-2}$ to bound $\|s^k\|^2 \le \|\nabla f\|^2 / \lambda _ \min(H _ k)^2 \le \|\nabla f\|^2 / \lambda _ \min^2$, hence $1/\|s^k\| \ge \lambda _ \min / \|\nabla f\|$.
• Combine: $E _ k \ge \min\{(\lambda _ \min / \lambda _ \max) \|\nabla f\|, \|\nabla f\|^2 / \lambda _ \max\}$, both positive multiples of $\|\nabla f\|$ or $\|\nabla f\|^2$.
• $E _ k \to 0$ then forces $\|\nabla f(x^k)\| \to 0$.

• Positivity ⟹ Newton direction $s^k = -H _ k^{-1} \nabla f(x^k)$ is descent (since $H _ k^{-1} \succ 0$), so the hypotheses of ∆global-convergence-of-backtracking-armijo (Theorem 4) are met.
• Uniform lower bound $\lambda _ \min(H _ k) \ge \lambda _ \min > 0$ is what lets us upper-bound $\|s^k\|$ by $\|\nabla f(x^k)\| / \lambda _ \min$ (the direction-length step). Without uniformity, $\|s^k\|$ could blow up at iterates where $H _ k$ is nearly singular, and the implication $E _ k \to 0 \Rightarrow \|\nabla f(x^k)\| \to 0$ would break.

(The upper bound on eigenvalues comes for free from Lipschitz $\nabla f$ via ∆lipschitz-continuous-iff-bounded-hessian, so it doesn’t have to be a separate hypothesis.)

• Step 1 (unit step accepted): at the Newton direction, $(s^k)^\top \nabla^2 f(x^k) s^k = -\nabla f(x^k)^\top s^k$, so Taylor gives the “half-decrease” identity $f(x^k + s^k) = f(x^k) + \tfrac{1}{2} \nabla f(x^k)^\top s^k + o(\|s^k\|^2)$. Armijo at $\alpha = 1$ reduces to $(\tfrac{1}{2} - \beta) \nabla f(x^k)^\top s^k + o(\|s^k\|^2) \le 0$, whose leading term is strictly negative (using $\beta < 1/2$ and $s^k$ descent). As $s^k \to 0$, the $o$-term is dominated, so bArmijo terminates at $i = 0$ with $\alpha^k = 1$.
• Step 2 (quadratic rate): once $\alpha^k = 1$ for all large $k$, iteration is pure Newton. Apply ∆newtons-method-convergence (Theorem 7) — its hypotheses (Lipschitz $\nabla^2 f$, $\nabla^2 f(x^\ast)$ nonsingular, $x^k$ close to $x^\ast$) are subsumed by ours — to get quadratic convergence.

• $\beta$ enters when comparing the “half-decrease” identity $f(x^k + s^k) = f(x^k) + \tfrac{1}{2} \nabla f(x^k)^\top s^k + o(\|s^k\|^2)$ to the Armijo bound $f(x^k) + \beta \nabla f(x^k)^\top s^k$. Rearranging, Armijo at $\alpha = 1$ is equivalent to $(\tfrac{1}{2} - \beta) \nabla f(x^k)^\top s^k + o(\|s^k\|^2) \le 0$.
• $\beta < 1/2$ makes the coefficient $\tfrac{1}{2} - \beta$ strictly positive, so combined with $\nabla f(x^k)^\top s^k < 0$ the leading term is strictly negative and dominates the $o(\|s^k\|^2)$ remainder near $x^\ast$.
• At $\beta = 1/2$ exactly, the leading term vanishes and the sign depends entirely on the $o(\|s^k\|^2)$ remainder, which can go either way — bArmijo may need to backtrack from $\alpha _ {(0)} = 1$ infinitely often, and the “automatic step size” property is lost.