Continuous Optimisation HT26, Trust-region methods

• Linesearch methods
  • Choose descent direction $s^k$
  • Compute stepsize $\alpha^k$ to reduce $f(x^k + \alpha s^k)$
  • Update $x^{k+1} = x^k + \alpha^k s^k$
• Trust region methods:
  • Pick direction $s^k$ to reduce local model of $f(x^k + s^k)$
  • Accept $x^{k+1} = x^k + s^k$ if decrease in model is also achieved by $f(x^k + s^k)$
  • Otherwise, set $x^{k+1} = x^k$ and refine the model

Linear model:

Quadratic model:

Problems:

• Models may not resemble $f(x^k + s)$ when $s$ is large
• Models may be unbounded from below
  • $l _ k(s)$ is always unbounded below, unless $\nabla f(x^k) = 0$
  • $q _ k(s)$ is always unbounded below if $\nabla^2 f(x^k)$ is negative definite or indefinite, and sometimes if $\nabla^2 f(x^k)$ is positive semidefinite

We trust the models only in a trust region, defined by a trust region constraint

for some radius $\Delta _ k > 0$. Thus we have the trust region subproblem

where $m _ k$ is our local model.

It is chosen based on the value of

where $s^k$ is a (approximate) minimiser of $s _ k$ (i.e. the ratio of the true function decrease to the predicted model decrease). Then if:

• $\rho _ k$ is not too much smaller than $1$: $x^{k+1} := x^k + s^k$, $\Delta _ {k+1} \ge \Delta _ k$
• $\rho _ k$ close to or $\ge 1$: $\Delta _ k$ is increased
• $\rho _ k$ is much smaller than $1$: $x^{k+1} = x^k$, and $\Delta _ k$ is reduced

Suppose we have:

• $\Delta _ 0 > 0$
• $x^0 \in \mathbb R^n$, $\epsilon > 0$

Then while $ \vert \vert \nabla f(x^k) \vert \vert \ge \epsilon$, do the following:

• Form the local quadratic model $m _ k(s)$ of $f(x^k + s)$
• Solve (approximately) the trust region subproblem for $s^k$ with $m _ k(s^k) < f(x^k)$. Compute $\rho _ k := \frac{f(x^k) - f(x^k + s^k)}{f(x^k) - m _ k(s^k)}$.
• Then:
  • (Very successful) If $\rho _ k \ge 0.9$ then: set $x^{k+1} := x^k + s^k$, and $\Delta _ {k+1} = 2\Delta _ k$
  • (Successful) Else if $\rho _ k \ge 0.1$, then: set $x^{k+1} := x^k + s^k$, and $\Delta _ {k+1} := \Delta _ k$
  • (Unsuccessful) Else set $x^{k+1} = x^k$ and $\Delta _ {k+1} := \frac 1 2 \Delta _ k$
• Let $k := k+1$.

Assume $\nabla f(x^k) \ne 0$ (guaranteed inside the GTR loop by the termination test $\|\nabla f(x^k)\| \ge \epsilon$; without this the argmin below is degenerate, see remark). The Cauchy step is

This is a linesearch along the steepest-descent direction of $m_k$ at $x^k$, restricted to the trust region (the upper bound on $\alpha$ comes from $\|\alpha \nabla f(x^k)\| = \alpha \|\nabla f(x^k)\| \le \Delta_k$, using $\alpha > 0$). The Cauchy point itself is

Why useful: it gives the “minimal” condition for sufficient decrease in the model — the Cauchy decrease condition

Any reasonable subproblem solver (CG, dogleg, etc.) does at least as well as the Cauchy point per iteration, so this condition is easy to enforce while pinning down the global-convergence guarantee (∆gtr-global-convergence-theorem).

Remark (why $\nabla f(x^k) \ne 0$ matters): if $\nabla f(x^k) = 0$, then $-\alpha \nabla f(x^k) = 0$ for every $\alpha$, so $m _ k(0) = f(x^k)$ is constant in $\alpha$ and the constraint $\|\alpha \cdot 0\| \le \Delta _ k$ holds for every $\alpha > 0$; the argmin is then the whole set $(0, \infty)$, not a single value. The GTR termination test rules this out before the Cauchy point is ever computed.

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$
• $f$ is bounded below on $\mathbb R^n$
• $\nabla f$ is Lipschitz continuous on $\mathbb R^n$
• $\{x^k\}$ is generated by the generic trust region method
• The computation of $s^k$ is such that $m _ k(s^k) \le m _ k(s^k _ c)$ for all $k$

Then either:

• There exists $k \ge 0$ such that $\nabla f(x^k) = 0$, or
• $\liminf _ {k \to \infty} \vert \vert \nabla f(x^k) \vert \vert = 0$

Let $\overline \alpha := \frac{\Delta _ k}{ \vert \vert \nabla f(x^k) \vert \vert }$ and $h^k := \nabla f(x^k)^\top \nabla^2 f(x^k) \nabla f(x^k)$. Then:

• If $h^k > 0$: $\alpha^k _ c = \min(\frac{ \vert \vert \nabla f(x^k) \vert \vert ^2}{h^k}, \overline \alpha)$
• If $h^k \le 0$: $\alpha^k _ c = \overline \alpha$

Expanding our local quadratic model $m _ k$, we have

and we aim to find $\alpha _ c^k$ as the global solution of

given that $\nabla f(x^k) \ne 0$.

The conditions that $\alpha > 0$ and $ \vert \vert \alpha \nabla f(x^k) \vert \vert \le \Delta _ k$ imply $0 < \alpha \le \frac{\Delta _ k}{ \vert \vert \nabla f(x^k) \vert \vert } := \overline \alpha$. Define

where $h^k := \nabla f(x^k)^\top \nabla^2 f(x^k) \nabla f(x^k)$. Then

so decreasing from $\alpha = 0$ for sufficiently small $\alpha$, thus $\alpha^k_c > 0$ (i.e. the minimum exists, since this rules out the case that any step $\alpha$ would strictly increase the objective).

Therefore if $h^k > 0$, it follows we may take $\alpha _ \min = \frac{ \vert \vert \nabla f(x^k) \vert \vert ^2}{h^k} = \arg\min _ {\alpha > 0} \psi(\alpha)$ and so $\alpha^k _ c = \min(\alpha _ \min, \overline \alpha)$ (i.e. we are basically switching on whether $\alpha _ \min < \overline \alpha$. If this is the case, then the unconstrained minimiser is within the trust region and we should move directly to the unconstrained minimiser. If not, then the best we can do is move right up to the trust region boundary).

If $h^k \le 0$, $\psi(\alpha)$ is unbounded below on $\mathbb R$ and so $\alpha _ c^k = \overline \alpha$. (One way to think about this case is that $\alpha _ \min$ is basically $\infty$, so the $\min(\alpha _ \min, \overline \alpha)$) formula still holds.)

Suppose:

• $m _ k(s^k) \le m _ k(s^k _ c)$ for all $k$

Then for every $k$:

Define

where $h^k := \nabla f(x^k)^\top \nabla^2 f(x^k) \nabla f(x^k)$.

If $h^k \le 0$, then the definition of $\psi$ implies

and in this case, since the function is unbounded below (by increasing $\alpha^k _ c$), the constraint must be tight and so we also have

and hence

Otherwise, $h^k > 0$. Then $\alpha^k _ c = \min\{\alpha _ \min, \overline \alpha\}$ where $\alpha _ \min = \vert \vert \nabla f(x^k) \vert \vert ^2 / h^k$. Assume first that $\alpha^k _ c = \overline \alpha$. Then $\alpha^k _ c \le \alpha _ \min$, which from the expression of $\alpha _ \min$, implies $\alpha _ c^k h^k \le \vert \vert \nabla f(x^k) \vert \vert ^2$. Using this bound in the expression of $\psi(\alpha)$, we obtain

and from the expression of $\overline \alpha$, we find

Assume now that $h^k > 0$ and $\alpha^k _ c = \alpha _ \min = \vert \vert \nabla f(x^k) \vert \vert ^2 / h^k$ (i.e. the constraint is not active, so we may obtain this minimum by differentiating and setting to zero, see ∆exact-linesearch-quadratic-optimal-stepsize-proof). Replacing this value in the model decrease, we obtain

and hence by Cauchy-Schwarz and the Rayleigh quotient inequalities, we have

Hence

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$
• $\nabla f$ is Lipschitz continuous on $\mathbb R^n$ with Lipschitz constant $L$
• $m _ k(s^k) \le m _ k(s^k _ c)$ for all $k$
• For all $k$, there exists $\epsilon > 0$ such that $ \vert \vert \nabla f(x^k) \vert \vert \ge \epsilon$

Then there exists a constant $c \in (0, 1)$ independent of $k$ such that

for all $k \ge 0$.

Suppose:

• $f \in \mathcal C^2 (\mathbb R^n)$
• $f$ is bounded below on $\mathbb R^n$
• $\nabla f$ is Lipschitz continuous on $\mathbb R^n$ with Lipschitz constant $L$
• $\{x^k\}$ is generated by the generic trust region method
• $m _ k(s^k) \le m _ k(s^k _ c)$ for all $k$

Then either:

• there exists $k \ge 0$ such that $\nabla f(x^k) = 0$, or
• $\lim \inf _ {k \to \infty} \vert \vert \nabla f(x^k) \vert \vert = 0$

If there exists $k$ such that $\nabla f(x^k) = 0$, then the method terminates.

Assume instead that there exists $\epsilon > 0$ such that $ \vert \vert \nabla f(x^k) \vert \vert \ge \epsilon$ for all $k$. Hence there are infinite many successful iterations $k$, which we say belong to a set $\mathcal S$. Hence by definition of $\rho _ k$, we obtain

where the second inequality is justified by ∆sufficient-model-decrease-given-cauchy-condition. This holds for all $k \in \mathcal S$.

As $\nabla f$ is Lipschitz continuous with Lipschitz constant $L$, it follows that $ \vert \vert \nabla^2 f(x) \vert \vert \le L$ for all $x$ (by general results about Lipschitz functions). Hence since $ \vert \vert \nabla f(x^k) \vert \vert \ge \epsilon$ for all $K$, it follows for all $k \in \mathcal S$ that

where we have used ∆lower-bound-on-trust-region-radius. Hence by the fact $c \in (0, 1)$, it follows that for all $k \in \mathcal S$,

Since $f(x^k) \ge f _ \text{low}$ for all $k$, it follows that for all $k \ge 0$,

where we used $f(x^k) = f(x^{k+1})$ on unsuccessful $k$. Let $k \to \infty$. Then

where we used $(\star)$ and that $ \vert \mathcal S \vert $ is the number of successful iterations. Since the left hand side of $(\star\star)$ is finite whereas the right hand side is infinite (since $ \vert \mathcal S \vert = \infty$). Hence there must exist some $k$ such that $ \vert \vert \nabla f(x^k) \vert \vert < \epsilon$, and so it follows that $\lim\inf _ {k \to \infty} \vert \vert \nabla f(x^k) \vert \vert = 0$.

$s^\ast$ is a global minimiser iff there exists $\lambda^\ast \ge 0$ such that

1. $(H + \lambda^\ast I) s^\ast = -g$
2. $H + \lambda^\ast I \succeq 0$
3. $\lambda^\ast ( \vert \vert s^\ast \vert \vert - \Delta) = 0$
4. $ \vert \vert s^\ast \vert \vert \le \Delta$

Moreover, if $H + \lambda^\ast I$ is positive definite, then $s^\ast$ is the unique global minimiser.

Step 1: First check if $H$ is positive semidefinite, i.e. $\lambda _ \min(H) \ge 0$. If this is the case:

• Compute the minimum norm solution $s$ of $Hs = -g$. This gives $-H^{-1} g$ if $H \succ 0$, or $-H^+ g$ if $H$ is singular and $g \in \text{range}(H)$.
• If such an $s$ exists and $\|s\| \le \Delta$, we are done, then $s^\ast = s$ and $\lambda^\ast = 0$ (i.e. we are on the interior of the trust region).

(Why? If $H$ is positive semidefinite, then $\lambda^\ast$ might equal $0$. In this case we can try solving directly for $s^\ast$ and see if all the conditions are satisfies).

Step 2: If $H$ is not positive semidefinite, then it has a strictly negative eigenvalue and so we know that for $H + \lambda^\ast I \ge 0$ to hold we require $\lambda^\ast > 0$. If $H$ was positive semidefinite but such an $s$ didn’t exist, then we know we have to pick $\lambda^\ast > 0$ to make it work. So the constraint is active in either case. This gives us that

We know by the requirement that $H + \lambda^\ast I \succeq 0$, we must have $\lambda \ge -\lambda _ \min(H) =: \overline\lambda$. Hence we can set $s(\lambda) = -(H + \lambda I)^{-1} g$ and try and solve for

If this equation has a solution $\lambda^\ast$, then we are done, since we may calculate $s^\ast = -(H + \lambda I)^{-1}g$.

There is still the possibility that this equation has no root.

Suppose $H$ is positive definite and if we compute $s = -H^{-1}g$, we find that $ \vert \vert s \vert \vert \le \Delta$. Then $s^\ast = s$ uniquely and $\lambda^\ast = 0$.

Case 2: If $H$ is not positive definite, then we know that $\lambda^\ast \ge 0$

If $H$ is not positive definite, or $H$ is positive definite but $s = -H^{-1}g$ gives $ \vert \vert s \vert \vert \ge \Delta$. Then by the above ∆exact-conditions-for-solving-trust-region-subproblem we have that

and we know by positive semidefiniteness that $\lambda \ge \max\{0, -\lambda _ \min(H)\} := \underline \lambda$. Define

for any $\lambda > \underline \lambda$. Then $s^\ast = s(\lambda^\ast)$ where $\lambda^\ast \ge \underline \lambda$ is a solution of

which is a nonlinear equation in one variable $\lambda$ for which we can use Newton’s method to solve.

Setup: let $H = U^\top \Lambda U$ be the spectral decomposition of $H$, with $U$ orthogonal, $\Lambda = \mathrm{diag}(\lambda _ 1, \ldots, \lambda _ n)$ in increasing order, and define $\gamma := Ug \in \mathbb R^n$ so that $\gamma _ i = v _ i^\top g$ is the projection of $g$ onto the $i$-th eigenvector $v _ i$ of $H$. Then

(see ∆trust-region-secular-equation-proof).

Secular equation: rather than solving $\|s(\lambda)\| = \Delta$ directly, define

and solve $\phi(\lambda) = 0$ for $\lambda \in (\max\{0, -\lambda _ 1\}, \infty)$.

Why useful: $\phi$ has no poles on $(-\lambda _ 1, \infty)$ and is analytic there, unlike $\|s(\lambda)\|$ which blows up at $\lambda = -\lambda _ 1$. Newton’s method on $\phi$ is therefore globally well-behaved and locally quadratic — except in the ∆trust-region-hard-case, where $\gamma _ 1 = 0$, the $i = 1$ term in the sum drops out, and the secular equation has no solution on $\lambda > -\lambda _ 1$.

Since $H$ is symmetric, we know it has spectral decomposition $H = U^\top \Lambda U$ where $U$ is an orthonormal matrix of eigenvectors of $H$ and $\Lambda$ is a diagonal matrix of eigenvalues of $H$ given by $\lambda _ 1 \le \lambda _ 2 \le \cdots \le \lambda _ n$, where $\lambda _ 1 = \lambda _ \min(H)$.

By ∆exact-conditions-for-solving-trust-region-subproblem, we know that

is positive semidefinite. Hence $\lambda _ 1 + \lambda \ge 0$, and so $\lambda \ge -\lambda _ 1$ and thus $\lambda \ge \max\{0, -\lambda _ 1\}$. Thus

Let $g = U^\top \gamma$ for some $\gamma = (\gamma _ 1, \ldots, \gamma _ n) \in \mathbb R^n$. As $U U^\top = U^\top U = I$, we have

Hence the minimising the secular equation is equivalent to solving for $\lambda$. $\phi$ is a convenient form as it has no poles and is analytic on $(-\lambda, \infty)$.

Hard case: occurs when both

• $H$ has $\lambda _ \min (H) < 0$, and
• $g$ is orthogonal to the eigenspace of $\lambda_\min(H)$.

In the ordinary nonconvex case ($g$ has a component along the negative-eigenvalue eigenspace), we find $\lambda^\ast > \underline \lambda := \max \{0, -\lambda _ \min(H)\}$ such that $\|s(\lambda^\ast)\| = \Delta$, where $s(\lambda) = -(H + \lambda I)^{-1} g$ (see ∆trust-region-subproblem-solving-recipe). In the hard case this fails: $\lambda \to \underline \lambda^+$, $s(\lambda)$ stays bounded (the singularity in $(H + \lambda I)^{-1}$ along the bad eigenspace doesn’t blow up because $g$ has zero component there), so the secular equation has no solution for $\lambda > \underline \lambda$.

Recipe: set $\lambda^\ast := -\lambda _ \min(H) = \underline \lambda$, so $H + \lambda^\ast I \succ 0$ with non-trivial null space (the eigenspace of $\lambda _ \min(H)$). Then $(H + \lambda^\ast I)s = -g$ is solvable (since $g$ lies in the range of $H + \lambda^\ast I$, which is the orthogonal complement of the null space). Solve for the components of $s$ orthogonal to the null-space; the null-space component is free to choose. Fix its magnitude using $\|s\| = \Delta$.

Uniqueness fails: since $H + \lambda^\ast I$ is only PSD (not PD), ∆exact-conditions-for-solving-trust-region-subproblem only guarantees existence and the global minimiser is not unique. See ∆trust-region-hard-case exampe.

Check the hard-case conditions:

• $\lambda _ \min(H) = -2 < 0$
• Eigenspace of $\lambda _ \min(H)$ is $\text{span}\{e _ 1\}$, so $g = (0, 0, 1)^\top$ is orthogonal to $e _ 1$

So set $\lambda^\ast = 2$, giving $H + 2I = \text{diag}(0, 1, 1)$. Solve $(H + 2I)s = -g$:

Hence $s _ 2 = 0$, $s _ 3 = -1$, and $s _ 1$ is free (it lies in the null space of $H + \lambda^\ast I)$.

Imposing $\|s\| = \sqrt 2$ gives $s _ 1^2 + 0 + 1 = 2$, so $s _ 1 = \pm 1$. Hence there are two global minimisers:

Recall also the ∆exact-conditions-for-solving-trust-region-subproblem, i.e. that $s^\ast$ is a global minimiser iff there exists $\lambda^\ast \ge 0$ such that

1. $(H + \lambda^\ast I) s^\ast = -g$
2. $H + \lambda^\ast I \succeq 0$
3. $\lambda^\ast ( \vert \vert s^\ast \vert \vert - \Delta) = 0$
4. $ \vert \vert s^\ast \vert \vert \le \Delta$

and moreover, if $H + \lambda^\ast I$ is positive definite, then $s^\ast$ is the unique global minimiser.

Since $H \succ 0$, we are in case 1 of ∆trust-region-subproblem-solving-recipe. Try the unconstrained minimiser:

Since $\|s _ N\| < 2 = \Delta$, the trust-region constraint is inactive. By ∆exact-conditions-for-solving-trust-region-subproblem, $\lambda^\ast = 0$ and the unique global minimiser is

Recall also the ∆exact-conditions-for-solving-trust-region-subproblem, i.e. that $s^\ast$ is a global minimiser iff there exists $\lambda^\ast \ge 0$ such that

1. $(H + \lambda^\ast I) s^\ast = -g$
2. $H + \lambda^\ast I \succeq 0$
3. $\lambda^\ast ( \vert \vert s^\ast \vert \vert - \Delta) = 0$
4. $ \vert \vert s^\ast \vert \vert \le \Delta$

and moreover, if $H + \lambda^\ast I$ is positive definite, then $s^\ast$ is the unique global minimiser.

Since $H \succ 0$, we are in case 1 of ∆trust-region-subproblem-solving-recipe. Try the unconstrained minimiser:

This fails since $\sqrt{5}/2 > 5/12 = \Delta$ (see ∆trust-region-case-1-example), so the constraint is active. By ∆exact-conditions-for-solving-trust-region-subproblem, we look for $\lambda^\ast > 0$ with

and $\|s(\lambda)\| = \Delta$, i.e.

We note that $\lambda = 2$ is a root. Since $\lambda^\ast = 2 > 0$ and $H + 2I \succ 0$, this is the unique global minimiser:

Recall also the ∆exact-conditions-for-solving-trust-region-subproblem, i.e. that $s^\ast$ is a global minimiser iff there exists $\lambda^\ast \ge 0$ such that

1. $(H + \lambda^\ast I) s^\ast = -g$
2. $H + \lambda^\ast I \succeq 0$
3. $\lambda^\ast ( \vert \vert s^\ast \vert \vert - \Delta) = 0$
4. $ \vert \vert s^\ast \vert \vert \le \Delta$

and moreover, if $H + \lambda^\ast I$ is positive definite, then $s^\ast$ is the unique global minimiser.

$H$ has $\lambda _ \min(H) = -2 < 0$, and $g$ has nonzero component along $e _ 1$ (the eigenspace of $\lambda _ \min$), so we are in the ordinary nonconvex case, not the hard case (∆trust-region-hard-case). By ∆exact-conditions-for-solving-trust-region-subproblem, $\lambda^\ast = -\lambda _ \min(H) = 2$ and $\|s^\ast\| = \Delta$. Write

and we require $\|s(\lambda)\|^2 = 25/144$:

Substitute $u := \lambda - 3$, so $\lambda - 2 = u + 1$ and $\lambda - 1 = u + 2$. Then the equation becomes

the same equation as ∆trust-region-case-2-pd-example, with root $u = 2$. Hence $\lambda^\ast = 5$, and

Suppose:

• $f \in \mathcal C^2(\mathbb R^n)$, bounded below on $\mathbb R^n$
• $\nabla f$ Lipschitz continuous with constant $L$
• $\{x^k\}$ generated by GTR with model $m _ k(s)$ above
• $m _ k(s^k) \le m _ k(s^k _ c)$ for all $k$ (Cauchy decreases)
• New hypothesis: $\|B^k\| \le \kappa _ B$ uniformly in $k$

Then either:

• there exists $k \ge 0$ with $\nabla f(x^k) = 0$, or
• $\lim \inf _ {k \to \infty} \|\nabla f(x^k)\| = 0$.

Where the hypothesis enters: the proof of ∆one-limit-point-of-gtr-method-stationary generalises with $\nabla^2 f(x^k)$ replaced by $B^k$ throughout, with two changes:

• ∆sufficient-model-decrease-given-cauchy-condition becomes

• The bound $ \vert f(x^k + s^k) - m _ k(s^k) \vert \le \tfrac 1 2 [L + \kappa _ B]\Delta^2 _ k$ replaces the $L$-only bound in the original proof of ∆lower-bound-on-trust-region-radius, and the lower bound on $\Delta _ k$ weakens to $\Delta _ k \ge c/(L + \kappa _ B) \cdot \epsilon$ for some $c \in (0, 1)$.

The hypothesis $\|B^k\| \le \kappa _ B$ is what makes both these bounds finite. Without it, $B^k$ could be unboundedly indefinite and the Cauchy decrease becomes useless.

Why useful: this covers quasi-Newton trust-region methods (where $B^k$ is a Hessian approximation, not necessarily PD) and methods using approximate derivatives, without requiring PD-ness of $B^k$ (compare with ∆general-second-order-glm-global-convergence for the linesearch case, which did need PD).

Purpose: it provides the minimal model decrease needed for the global convergence proof (∆gtr-global-convergence-theorem). Without it, an approximate solver could pick $s^k$ that decreases $m _ k$ trivially and the proof’s “sufficient decrease per iteration” step would fail.

Easy in practice: $s^k _ c$ is just the Cauchy point — a steepest-descent step inside the trust region, computable in closed form (∆cauchy-point-computation) from one gradient and one Hessian-vector product. Any reasonable iterative solver (conjugate gradient, dogleg, two-dimensional subspace minimisation) does better than $s^k _ c$ on every iteration. So requiring $m _ k(s^k) \le m _ k(s^k _ c)$ doesn’t constrain the algorithm — it just nails down the worst-case guarantee.

• Linesearch: choose a (descent) direction first, then choose the stepsize along it to control how much we trust the local model. Liberal in direction, conservative in stepsize.
• Trust-region: choose a region around $x^k$ in which we trust the local model, then minimise the model over that region. Conservative in step size (bounded by $\Delta _ k$), liberal in direction (anywhere in the trust region, including non-descent directions for non-PD Hessians).

Both reduce a global problem to a tractable local subproblem; they differ only in which axis (direction or stepsize) is committed to first.

• Reduce to a 1D problem in $\alpha$: define $\psi(\alpha) := m _ k(-\alpha \nabla f(x^k)) = f(x^k) - \alpha \|\nabla f(x^k)\|^2 + \tfrac 1 2 \alpha^2 h^k$, where $h^k := \nabla f(x^k)^\top \nabla^2 f(x^k) \nabla f(x^k)$.
• Note $\psi'(0) = -\|\nabla f(x^k)\|^2 < 0$ so $\alpha^k_c > 0$.
• Feasibility window: $\alpha \in (0, \overline\alpha]$ with $\overline\alpha := \Delta _ k / \|\nabla f(x^k)\|$.
• Case-split on sign of $h^k$:
  • $h^k > 0$: $\psi$ is a convex parabola; unconstrained minimiser at $\alpha _ \min = \|\nabla f\|^2 / h^k$. Hence $\alpha^k _ c = \min(\alpha _ \min, \overline\alpha)$.
  • $h^k \le 0$: $\psi$ is concave (or linear); unbounded below on $\mathbb R$, so constrained min lies on the boundary, $\alpha^k _ c = \overline\alpha$.

• The Cauchy-decrease hypothesis $m _ k(s^k) \le m _ k(s^k _ c)$ reduces the task to bounding $f(x^k) - m _ k(s^k _ c)$.
• Split into three cases based on which regime of ∆cauchy-point-computation produced $\alpha^k _ c$:
  • Case A ($h^k \le 0$): $\alpha^k _ c = \overline\alpha = \Delta _ k / \|\nabla f(x^k)\|$. Since $\psi(\alpha^k _ c) \le f(x^k) - \alpha^k _ c \|\nabla f\|^2$ (drop the $h^k$ term), get $f(x^k) - m _ k(s^k _ c) \ge \Delta _ k \|\nabla f(x^k)\|$.
  • Case B ($h^k > 0$, $\alpha^k _ c = \overline\alpha$): $\alpha^k _ c \le \alpha _ \min$, so $\alpha^k _ c h^k \le \|\nabla f\|^2$. Using this in $\psi$, $f(x^k) - m _ k(s^k _ c) \ge \tfrac{1}{2} \alpha^k _ c \|\nabla f\|^2 = \tfrac{1}{2} \Delta _ k \|\nabla f(x^k)\|$.
  • Case C ($h^k > 0$, $\alpha^k _ c = \alpha _ \min = \|\nabla f\|^2/h^k$): plug in to get $f(x^k) - m _ k(s^k _ c) = \|\nabla f\|^4 / (2 h^k)$, then bound $h^k \le \|\nabla^2 f\| \|\nabla f\|^2$ by Rayleigh–Ritz to give $\|\nabla f\|^2 / (2 \|\nabla^2 f\|)$.
• All three lower bounds dominate $\tfrac{1}{2} \|\nabla f\| \min\{\Delta _ k, \|\nabla f\| / \|\nabla^2 f\|\}$.

• Argue by contradiction: assume $\|\nabla f(x^k)\| \ge \epsilon > 0$ for all $k$ (else done).
• On every successful step $k \in \mathcal S$, the radius-update rule gives $\rho _ k \ge 0.1$, so $f(x^k) - f(x^{k+1}) \ge 0.1 (f(x^k) - m _ k(s^k))$.
• Apply ∆sufficient-model-decrease-given-cauchy-condition (Lemma 12) to bound the model decrease; combine with the $\|\nabla^2 f\| \le L$ bound (from Lipschitz $\nabla f$) and ∆lower-bound-on-trust-region-radius (Lemma 13: $\Delta _ k \ge c\epsilon/L$) to get a uniform per-successful-step decrease $\ge 0.05 c \epsilon^2 / L$.
• Telescope over successful iterations: bounded-below $f$ gives finite LHS but $ \vert \mathcal S \vert = \infty$ gives infinite RHS — contradiction.
• Hence the standing assumption fails, so $\liminf \|\nabla f(x^k)\| = 0$.

• The contradiction in the proof uses $ \vert \mathcal S \vert = \infty$ to make the RHS of the telescoped sum infinite while the LHS $\le f(x^0) - f _ {\text{low}}$ stays finite. Without infinite $\mathcal S$, this contradiction fails.
• However, the case of finitely many successful iterations is handled separately (∆lower-bound-on-trust-region-radius, remark 2): after the last successful step, all subsequent steps are unsuccessful, so $\Delta _ k \to 0$. Combined with Lemma 13 (which says $\Delta _ k \ge c\epsilon/L$ under $\|\nabla f(x^k)\| \ge \epsilon$), this forces $\|\nabla f(x^k)\| < \epsilon$ for some $k$, so in fact the last successful iterate has zero gradient.
• Either way, the conclusion holds: either GTR terminates with $\nabla f(x^k) = 0$, or $\liminf \|\nabla f(x^k)\| = 0$.

• Spectral-decompose $H = U^\top \Lambda U$ with $U$ orthonormal and $\Lambda$ diagonal of eigenvalues $\lambda _ 1 \le \cdots \le \lambda _ n$.
• Note ∆exact-conditions-for-solving-trust-region-subproblem requires $H + \lambda I \succeq 0$, which translates to $\lambda \ge -\lambda _ 1 = -\lambda _ \min(H)$, hence $\lambda \ge \max\{0, -\lambda _ 1\}$.
• Compute $\|s(\lambda)\|^2 = g^\top (H + \lambda I)^{-2} g$, change variables $g = U^\top \gamma$ and use $UU^\top = I$ to get $\|s(\lambda)\|^2 = \sum _ i \gamma _ i^2 / (\lambda + \lambda _ i)^2$.
• Set $\|s(\lambda)\|^2 = \Delta^2$ as the equation to solve.
• Switch to $\phi(\lambda) := 1/\|s(\lambda)\| - 1/\Delta$ for numerical stability — it has no poles on $(-\lambda _ 1, \infty)$ and is analytic there, unlike $\|s(\lambda)\|$ which blows up at $\lambda = -\lambda _ 1$.