44.03.02 · optimization-control / 03-unconstrained-optimization

Trust-Region Methods: The Cauchy Point and Dogleg Step

shipped3 tiersLean: none

Anchor (Master): Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §4.3 (the exact subproblem solution via $(B + λ I) p = - g$ , the hard case, and Moré-Sorensen) and §7.1 (Steihaug-Toint truncated CG); Conn, Gould & Toint 2000 Trust-Region Methods (SIAM/MPS) Ch. 6-7 (the subproblem theory, the secular equation, and the convergence analysis)

Intuition Beginner

Suppose you are standing somewhere on a hilly landscape and want to walk to the lowest point. You cannot see the whole terrain, but you can feel the slope under your feet and how the slope is changing — enough to build a small bowl-shaped guess of what the ground looks like right around you. That guess is a model. The catch is that your model is only believable nearby. A few steps away the real terrain might curl up where your bowl curls down, so trusting the model far from your feet is reckless.

A trust-region method makes this caution explicit. It draws a circle around your current position — the trust region — and says: I will only step somewhere inside this circle, because that is the only place I believe my bowl. It then picks the lowest point of the bowl within the circle and walks there.

After the step, it checks honesty. It compares the drop the model promised with the drop that actually happened. If the model was accurate, it earned more trust, so the circle grows for next time. If the model overpromised, the circle shrinks. If the model lied badly, the step is thrown out and you try again from the same spot with a smaller circle.

This is a different bargain from the usual one. Most methods first pick a direction and then ask how far to go. A trust-region method fixes how far it is willing to go and then asks which direction is best within that reach.

Visual Beginner

Picture the bowl-shaped model as a set of nested oval contour lines around a low point, and the trust region as a circle centred where you stand. The step you take is the lowest contour the circle can reach.

When the circle is small, the lowest reachable point sits on the circle's edge, and the best you can do is head roughly straight downhill. When the circle is large enough to contain the bowl's own bottom, the step lands at that interior bottom — the full model step — and the edge of the circle stops mattering.

situation	where the best step lands	what controls it
circle small	on the circle's edge, headed downhill	the radius
circle large, bowl inside	at the model's own bottom	the model
model overpromised	step rejected, circle shrinks	the honesty check

The takeaway: the radius of the circle is a dial for how bold to be, and the honesty check turns that dial automatically — more accurate models earn bigger circles, and bad surprises shrink them.

Worked example Beginner

Take a model bowl in two variables, $m (p) = g \cdot p + \frac{1}{2} p^{⊤} B p$ , with downhill data

g = (- 2 0), B = (1004),

and a trust radius $Δ = 1$ (so steps must satisfy $∥ p ∥ \leq 1$ ). The value at the centre is $m (0) = 0$ .

First, the cheap downhill step. The steepest-descent direction is $- g = (2, 0)$ , pointing along the first axis. The full model minimum is at $p^{B} = - B^{- 1} g = (2, 0)$ , which has length $2$ — outside the circle. So the model's own bottom is out of reach and the step will sit on the boundary.

Now find the best point along the downhill direction inside the circle. Moving a distance $t$ along $- g /∥ g ∥ = (1, 0)$ gives the point $(t, 0)$ , with model value

m (t, 0) = g \cdot (t, 0) + \frac{1}{2} (t, 0)^{⊤} B (t, 0) = - 2 t + \frac{1}{2} (1) t^{2} = \frac{1}{2} t^{2} - 2 t .

The unconstrained minimum of $\frac{1}{2} t^{2} - 2 t$ is at $t = 2$ , again outside the circle. Capped at $t = Δ = 1$ , the best allowed point is $(1, 0)$ .

Read off the drop. The model promised $m (1, 0) = \frac{1}{2} - 2 = - 1.5$ , a predicted reduction of $1.5$ from $m (0) = 0$ . Suppose the real function dropped by $1.35$ when we stepped there. The honesty ratio is $1.35/1.5 = 0.9$ .

What this tells us: the model predicted the drop well (ratio $0.9$ , close to $1$ ), so we accept the step and grow the circle for the next iteration. The boundary cap is what kept us from overstepping toward the out-of-reach model minimum.

Check your understanding Beginner

Exercise (easy, multiple-choice).

What does the trust region in a trust-region method represent?

The set of points where the true function is known exactly.
The region around the current point where the quadratic model is believed accurate, so steps are restricted to it.
The direction of steepest descent.
The set of all points lower than the current one.

Hint

Think about why the method limits how far it will step, not which way.

Answer

B. The trust region is the ball around the current point inside which the local quadratic model is trusted; the step is chosen as the model's best point within that ball. Feedback-correct: limiting the step length is what keeps the method from trusting the model where it is unreliable. Feedback-wrong: A overstates what is known (the model is only a guess); C names a direction, not a region; D describes a sublevel set, not the trust region.

Formal definition Intermediate+

Let $f : R^{n} \to R$ be twice continuously differentiable, and at the current iterate $x_{k}$ write $f_{k} = f (x_{k})$ , $g_{k} = \nabla f (x_{k})$ , and let $B_{k}$ be a symmetric matrix approximating $\nabla^{2} f (x_{k})$ (the exact Hessian, a quasi-Newton update, or any symmetric surrogate). The quadratic model of $f$ about $x_{k}$ is the second-order Taylor polynomial 02.05.05

m_{k} (p) = f_{k} + g_{k}^{⊤} p + \frac{1}{2} p^{⊤} B_{k} p, m_{k} (0) = f_{k} .

The trust region is the ball ${p : ∥ p ∥ \leq Δ_{k}}$ of radius $Δ_{k} > 0$ in a chosen norm (the Euclidean norm throughout, unless stated). The trust-region subproblem is

p_{k} = ar g ∥ p ∥ \leq Δ_{k} min m_{k} (p) = ar g ∥ p ∥ \leq Δ_{k} min g_{k}^{⊤} p + \frac{1}{2} p^{⊤} B_{k} p .

The predicted reduction is $pred_{k} = m_{k} (0) - m_{k} (p_{k}) \geq 0$ , and the actual reduction is $ared_{k} = f (x_{k}) - f (x_{k} + p_{k})$ . The ratio test computes

ρ_{k} = \frac{ared _{k}}{pred _{k}} = \frac{f ( x _{k} ) - f ( x _{k} + p _{k} )}{m _{k} ( 0 ) - m _{k} ( p _{k} )} .

With constants $0 \leq η < \frac{1}{4}$ , the step is accepted ( $x_{k + 1} = x_{k} + p_{k}$ ) when $ρ_{k} > η$ and rejected ( $x_{k + 1} = x_{k}$ ) otherwise, and the radius is updated by: shrink, $Δ_{k + 1} = \frac{1}{4} Δ_{k}$ , when $ρ_{k} < \frac{1}{4}$ ; expand, $Δ_{k + 1} = min (2 Δ_{k}, Δ_{m a x})$ , when $ρ_{k} > \frac{3}{4}$ and $∥ p_{k} ∥ = Δ_{k}$ ; otherwise $Δ_{k + 1} = Δ_{k}$ . The symbols $g$ (gradient), $B$ (model Hessian), $Δ$ (trust radius), $m$ (model), $ρ$ (ratio), and $λ$ (Lagrange multiplier) are recorded in _meta/NOTATION.md.

The Cauchy point $p_{k}^{C}$ is the minimiser of $m_{k}$ along the steepest-descent direction inside the region. Writing $p^{S} = - (Δ_{k} /∥ g_{k} ∥) g_{k}$ for the boundary point in the $- g_{k}$ direction, the Cauchy point is $p_{k}^{C} = τ_{k} p^{S}$ with

τ_{k} = {1, min (1, ∥ g_{k} ∥^{3} / (Δ_{k} g_{k}^{⊤} B_{k} g_{k})), g_{k}^{⊤} B_{k} g_{k} \leq 0, g_{k}^{⊤} B_{k} g_{k} > 0.

When the curvature $g_{k}^{⊤} B_{k} g_{k}$ is nonpositive, the model decreases without bound along $- g_{k}$ , so the step runs to the boundary; otherwise it stops at the line minimum if that lies inside the region.

The dogleg method applies when $B_{k} ≻ 0$ . It replaces the curved subproblem boundary with a piecewise-linear path from the origin through the unconstrained Cauchy step $p^{U} = - \frac{g _{k}^{⊤} g _{k}}{g _{k}^{⊤} B _{k} g _{k}} g_{k}$ to the full Newton step $p^{B} = - B_{k}^{- 1} g_{k}$ , and returns the point where this two-segment path first meets $∥ p ∥ = Δ_{k}$ (or $p^{B}$ itself if it lies inside). Two-dimensional subspace minimisation instead solves the subproblem exactly over the plane $span {g_{k}, B_{k}^{- 1} g_{k}}$ , a strict generalisation of the dogleg path.

Counterexamples to common slips Intermediate+

"The trust-region step is the Newton step capped to length $Δ$ ." Capping $p^{B} = - B^{- 1} g$ to the boundary by scaling is not the subproblem solution: the true constrained minimiser bends toward the steepest-descent direction as $Δ$ shrinks, which is exactly what the dogleg path and the $(B + λ I)$ characterisation capture and a naive rescaling misses.
"A trust-region method needs $B$ positive-definite." The Cauchy point and the whole convergence theory work for any symmetric $B$ , including indefinite ones; negative curvature $g^{⊤} B g \leq 0$ simply sends the Cauchy step to the boundary. Only the dogleg method requires $B ≻ 0$ , because it needs the Newton step $p^{B} = - B^{- 1} g$ to exist and to be a descent point.
"If $ρ_{k}$ is small the step direction was wrong." A small ratio means the model mispredicted the magnitude of the drop at that range, not that the direction was bad. The response is to shrink $Δ$ and re-solve, not to change methods; the same model is trusted over a shorter reach.
"The exact subproblem solution is always $- (B + λ I)^{- 1} g$ for some $λ > 0$ ." In the hard case, where $g$ is orthogonal to the eigenspace of the smallest eigenvalue of $B$ and that eigenvalue is negative, the solution at $λ = - λ_{m i n} (B)$ requires adding a multiple of the corresponding eigenvector, since $B + λ I$ is singular and $- (B + λ I)^{- 1} g$ alone does not reach the boundary.

Key theorem with proof Intermediate+

The signature result is the Cauchy sufficient-reduction bound: the cheap steepest-descent step alone guarantees a model decrease proportional to the gradient and the radius. Because every practical step is required to do at least as well as the Cauchy point, this single inequality is what makes trust-region methods globally convergent.

Theorem (Cauchy sufficient reduction). Let $m_{k} (p) = f_{k} + g_{k}^{⊤} p + \frac{1}{2} p^{⊤} B_{k} p$ with $g_{k} \neq = 0$ and $B_{k}$ symmetric, and let $p_{k}^{C}$ be the Cauchy point for radius $Δ_{k}$ . Then

m_{k} (0) - m_{k} (p_{k}^{C}) \geq \frac{1}{2} ∥ g_{k} ∥ min (Δ_{k}, \frac{∥ g _{k} ∥}{∥ B _{k} ∥}),

where $∥ B_{k} ∥$ is the spectral norm (read as $+ \infty$ , with the convention $∥ g_{k} ∥/∥ B_{k} ∥ = 0$ , only if $B_{k} = 0$ , in which case the linear term gives $m_{k} (0) - m_{k} (p_{k}^{C}) = ∥ g_{k} ∥ Δ_{k}$ ).

Proof. Along the ray $p (t) = - t g_{k} /∥ g_{k} ∥$ for $t \geq 0$ , the model is the scalar quadratic

ψ (t) := m_{k} (p (t)) - f_{k} = - ∥ g_{k} ∥ t + \frac{1}{2} (\frac{g _{k}^{⊤} B _{k} g _{k}}{∥ g _{k} ∥ ^{2}}) t^{2},

since $g_{k}^{⊤} p (t) = - ∥ g_{k} ∥ t$ and $p (t)^{⊤} B_{k} p (t) = (g_{k}^{⊤} B_{k} g_{k} /∥ g_{k} ∥^{2}) t^{2}$ . Write $γ = g_{k}^{⊤} B_{k} g_{k} /∥ g_{k} ∥^{2}$ for the curvature along $- g_{k}$ ; the Cauchy point is $p_{k}^{C} = p (t^{*})$ with $t^{*}$ the minimiser of $ψ$ on $[0, Δ_{k}]$ .

Case 1: $γ \leq 0$ . Then $ψ$ is concave (or linear) and decreasing on $[0, Δ_{k}]$ , so $t^{*} = Δ_{k}$ and

m_{k} (0) - m_{k} (p_{k}^{C}) = - ψ (Δ_{k}) = ∥ g_{k} ∥ Δ_{k} - \frac{1}{2} γ Δ_{k}^{2} \geq ∥ g_{k} ∥ Δ_{k} \geq \frac{1}{2} ∥ g_{k} ∥ Δ_{k} \geq \frac{1}{2} ∥ g_{k} ∥ min (Δ_{k}, \frac{∥ g _{k} ∥}{∥ B _{k} ∥}),

using $- \frac{1}{2} γ Δ_{k}^{2} \geq 0$ and that the minimum is at most $Δ_{k}$ .

Case 2: $γ > 0$ . The unconstrained minimiser of $ψ$ is $t_{u} = ∥ g_{k} ∥/ γ$ . If $t_{u} \leq Δ_{k}$ , then $t^{*} = t_{u}$ and

m_{k} (0) - m_{k} (p_{k}^{C}) = - ψ (t_{u}) = \frac{∥ g _{k} ∥ ^{2}}{2 γ} = \frac{∥ g _{k} ∥ ^{4}}{2 g _{k}^{⊤} B _{k} g _{k}} \geq \frac{∥ g _{k} ∥ ^{2}}{2∥ B _{k} ∥},

because $g_{k}^{⊤} B_{k} g_{k} \leq ∥ B_{k} ∥ ∥ g_{k} ∥^{2}$ . Since here $t_{u} \leq Δ_{k}$ means $∥ g_{k} ∥/ γ \leq Δ_{k}$ , and $γ \leq ∥ B_{k} ∥$ gives $∥ g_{k} ∥/∥ B_{k} ∥ \leq ∥ g_{k} ∥/ γ \leq Δ_{k}$ , the minimum equals $∥ g_{k} ∥/∥ B_{k} ∥$ and the bound reads $\frac{1}{2} ∥ g_{k} ∥ \cdot ∥ g_{k} ∥/∥ B_{k} ∥$ , matching. If instead $t_{u} > Δ_{k}$ , then $t^{*} = Δ_{k}$ and

m_{k} (0) - m_{k} (p_{k}^{C}) = - ψ (Δ_{k}) = ∥ g_{k} ∥ Δ_{k} - \frac{1}{2} γ Δ_{k}^{2} .

From $t_{u} = ∥ g_{k} ∥/ γ > Δ_{k}$ we get $γ Δ_{k} < ∥ g_{k} ∥$ , so $\frac{1}{2} γ Δ_{k}^{2} < \frac{1}{2} ∥ g_{k} ∥ Δ_{k}$ and hence $∥ g_{k} ∥ Δ_{k} - \frac{1}{2} γ Δ_{k}^{2} > \frac{1}{2} ∥ g_{k} ∥ Δ_{k} \geq \frac{1}{2} ∥ g_{k} ∥ min (Δ_{k}, ∥ g_{k} ∥/∥ B_{k} ∥)$ . In every case the stated bound holds. $□$

Bridge. This inequality is the foundational reason trust-region methods converge from any start: it certifies that even the crudest admissible step extracts a model decrease scaling like $∥ g_{k} ∥ min (Δ_{k}, ∥ g_{k} ∥/∥ B_{k} ∥)$ , and any step required to match a fixed fraction of the Cauchy decrease inherits the same guarantee — this is exactly the role the sufficient-decrease (Armijo) inequality plays for line searches, with the radius $Δ_{k}$ standing in for the step length. The central insight is that decoupling how far from which way lets the method handle indefinite $B_{k}$ that break the descent logic of Newton's method, because negative curvature merely drives the Cauchy step to the boundary rather than causing failure. The bound builds toward the global-convergence theorem of the Advanced results, where summing it across iterations forces $∥ g_{k} ∥ \to 0$ , and it appears again in the Steihaug-Toint method, whose first inner iterate is precisely the Cauchy point so the truncated solve dominates this decrease. Putting these together, the Cauchy point is to trust regions what steepest descent is to line search — the safe baseline that the Newton-like dogleg and exact steps improve upon without ever dropping below it; the bridge is that the same quantity $∥ g_{k} ∥/∥ B_{k} ∥$ measuring when curvature starts to bite reappears as the threshold separating the gradient-dominated regime from the Newton regime.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Prove that for $B ≻ 0$ the dogleg path $p (τ)$ (with $τ \in [0, 2]$ , the first segment from $0$ to $p^{U}$ and the second from $p^{U}$ to $p^{B}$ ) has $∥ p (τ) ∥$ monotonically nondecreasing in $τ$ , so it crosses the trust-region boundary at most once.

Hint

Monotonicity along the first segment is immediate. For the second, write $p (τ) = p^{U} + (τ - 1) (p^{B} - p^{U})$ and show $\frac{d}{d τ} \frac{1}{2} ∥ p (τ) ∥^{2} \geq 0$ using $(p^{B} - p^{U})^{⊤} p^{U} \geq 0$ , which follows from $p^{U} = - (g^{⊤} g / g^{⊤} B g) g$ and $p^{B} = - B^{- 1} g$ .

Answer

On the first segment $p (τ) = τ p^{U}$ , $τ \in [0, 1]$ , so $∥ p (τ) ∥ = τ ∥ p^{U} ∥$ is nondecreasing. On the second, set $h (τ) = \frac{1}{2} ∥ p^{U} + (τ - 1) (p^{B} - p^{U}) ∥^{2}$ . Then $h^{'} (τ) = (p^{B} - p^{U})^{⊤} (p^{U} + (τ - 1) (p^{B} - p^{U}))$ , which is nondecreasing in $τ$ (its derivative is $∥ p^{B} - p^{U} ∥^{2} \geq 0$ ), so it suffices that $h^{'} (1^{+}) = (p^{B} - p^{U})^{⊤} p^{U} \geq 0$ . Compute $(p^{B})^{⊤} p^{U} = (g^{⊤} g / g^{⊤} B g) g^{⊤} B^{- 1} g$ and $(p^{U})^{⊤} p^{U} = (g^{⊤} g)^{2} / (g^{⊤} B g)^{2} g^{⊤} g$ . Using the Cauchy-Schwarz-type inequality $(g^{⊤} g)^{2} \leq (g^{⊤} B g) (g^{⊤} B^{- 1} g)$ (which holds for $B ≻ 0$ , e.g. by writing $u = B^{1/2} g$ , $v = B^{- 1/2} g$ and applying Cauchy-Schwarz to $u^{⊤} v = g^{⊤} g$ ), one gets $(p^{B} - p^{U})^{⊤} p^{U} \geq 0$ . Hence $∥ p (τ) ∥$ is nondecreasing throughout, so the equation $∥ p (τ) ∥ = Δ$ has a single solution and the dogleg step is well defined. Full credit for the two-segment argument and the key inequality.

Exercise 5 (medium, symbolic).

Show that the trust-region subproblem solution $p^{*}$ with the active constraint $∥ p^{*} ∥ = Δ$ satisfies $(B + λ I) p^{*} = - g$ for some $λ \geq 0$ , by writing the Lagrangian and its stationarity condition.

Hint

Use the constraint $\frac{1}{2} (∥ p ∥^{2} - Δ^{2}) \leq 0$ and the Lagrangian $L (p, λ) = g^{⊤} p + \frac{1}{2} p^{⊤} B p + \frac{λ}{2} (∥ p ∥^{2} - Δ^{2})$ .

Answer

Form $L (p, λ) = g^{⊤} p + \frac{1}{2} p^{⊤} B p + \frac{λ}{2} (p^{⊤} p - Δ^{2})$ with multiplier $λ \geq 0$ for the inequality $\frac{1}{2} (∥ p ∥^{2} - Δ^{2}) \leq 0$ . Stationarity in $p$ gives $\nabla_{p} L = g + B p + λ p = 0$ , i.e. $(B + λ I) p^{*} = - g$ . Complementary slackness gives $λ (∥ p^{*} ∥^{2} - Δ^{2}) = 0$ , so when the solution is on the boundary ( $∥ p^{*} ∥ = Δ$ ) the multiplier $λ$ may be positive, and when it is interior $λ = 0$ and $B p^{*} = - g$ is the unconstrained stationarity. Dual feasibility requires $λ \geq 0$ ; the full global-optimality characterisation additionally needs $B + λ I ⪰ 0$ , established in the Full proof set. Full credit for the Lagrangian, the stationarity equation $(B + λ I) p^{*} = - g$ , and $λ \geq 0$ .

Exercise 6 (hard, symbolic).

Let $B$ be symmetric with eigenvalues $λ_{1} \leq \dots \leq λ_{n}$ and orthonormal eigenvectors $q_{1}, \dots, q_{n}$ , and let $g = \sum_{i} (q_{i}^{⊤} g) q_{i}$ . For $λ > - λ_{1}$ , define $p (λ) = - (B + λ I)^{- 1} g$ . Show that $∥ p (λ) ∥^{2} = \sum_{i} (q_{i}^{⊤} g)^{2} / (λ_{i} + λ)^{2}$ is strictly decreasing in $λ$ on $(- λ_{1}, \infty)$ (so the secular equation $∥ p (λ) ∥ = Δ$ has a unique root whenever $Δ$ is attainable).

Hint

Diagonalise: $(B + λ I)^{- 1} = \sum_{i} (λ_{i} + λ)^{- 1} q_{i} q_{i}^{⊤}$ . Differentiate the resulting sum term by term in $λ$ .

Answer

Since $B = \sum_{i} λ_{i} q_{i} q_{i}^{⊤}$ , we have $(B + λ I)^{- 1} = \sum_{i} (λ_{i} + λ)^{- 1} q_{i} q_{i}^{⊤}$ , so $p (λ) = - \sum_{i} (q_{i}^{⊤} g) / (λ_{i} + λ) q_{i}$ and, by orthonormality of the $q_{i}$ ,

∥ p (λ) ∥^{2} = i = 1 \sum n \frac{( q _{i}^{⊤} g ) ^{2}}{( λ _{i} + λ ) ^{2}} .

Differentiating term by term for $λ > - λ_{1}$ (each denominator positive),

\frac{d}{d λ} ∥ p (λ) ∥^{2} = - 2 i = 1 \sum n \frac{( q _{i}^{⊤} g ) ^{2}}{( λ _{i} + λ ) ^{3}} \leq 0,

and strictly negative unless every $q_{i}^{⊤} g = 0$ , i.e. unless $g = 0$ . Hence $∥ p (λ) ∥$ is strictly decreasing on $(- λ_{1}, \infty)$ , falling from $+ \infty$ as $λ ↓ - λ_{1}$ (provided $q_{1}^{⊤} g \neq = 0$ ) to $0$ as $λ \to \infty$ , so $∥ p (λ) ∥ = Δ$ has exactly one root. The case $q_{1}^{⊤} g = 0$ with $λ_{1} < 0$ is the hard case, where the supremum of $∥ p (λ) ∥$ as $λ ↓ - λ_{1}$ may be finite and below $Δ$ . Full credit for the eigen-expansion of $∥ p (λ) ∥^{2}$ and the negative derivative.

Exercise 7 (hard, symbolic).

In Steihaug-Toint truncated CG applied to $min_{p} m (p) = g^{⊤} p + \frac{1}{2} p^{⊤} B p$ from $p_{0} = 0$ , suppose at inner iteration $j$ a direction $d_{j}$ with $d_{j}^{⊤} B d_{j} \leq 0$ is found. Explain why no interior minimiser exists along $d_{j}$ and why the algorithm returns the point where the ray $p_{j} + σ d_{j}$ ( $σ \geq 0$ ) meets the trust-region boundary.

Hint

Consider $ϕ (σ) = m (p_{j} + σ d_{j})$ as a scalar quadratic in $σ$ and examine the sign of its leading coefficient.

Answer

Along the ray, $ϕ (σ) = m (p_{j} + σ d_{j}) = m (p_{j}) + σ g_{j}^{⊤} d_{j} + \frac{1}{2} σ^{2} d_{j}^{⊤} B d_{j}$ , where $g_{j} = g + B p_{j}$ is the current model gradient. The leading coefficient is $\frac{1}{2} d_{j}^{⊤} B d_{j} \leq 0$ , so $ϕ$ is concave (or linear) and has no finite minimiser for $σ \geq 0$ : it decreases without bound (or is nonincreasing) as $σ$ grows. The model therefore wants to step as far as possible along $d_{j}$ , but the trust region caps the step. The largest admissible $σ$ is the one making $∥ p_{j} + σ d_{j} ∥ = Δ$ , the positive root of the quadratic $∥ p_{j} ∥^{2} + 2 σ p_{j}^{⊤} d_{j} + σ^{2} ∥ d_{j} ∥^{2} = Δ^{2}$ . The algorithm returns $p_{j} + σ d_{j}$ at that boundary $σ$ . Because the CG iterates have monotonically increasing norm (in exact arithmetic from $p_{0} = 0$ with $B$ behaving positive-definite on the explored subspace), this boundary point also dominates the Cauchy decrease — the first inner step is the Cauchy point — so Steihaug-Toint inherits global convergence. Full credit for the concavity argument and the boundary-step conclusion.

Advanced results Master

The Cauchy bound certifies a baseline decrease; the results below build the exact theory of the subproblem on top of it — the global characterisation of the constrained minimiser through a single scalar multiplier, the hard case where that characterisation needs an eigenvector correction, the global-convergence theorem that turns the baseline decrease into $∥ g_{k} ∥ \to 0$ , and the large-scale truncated-CG solver that realises the theory at the cost of one matrix-vector product per inner step.

Theorem 1 (global characterisation of the subproblem solution). A vector $p^{*}$ is a global solution of $min_{∥ p ∥ \leq Δ} m (p) = g^{⊤} p + \frac{1}{2} p^{⊤} B p$ if and only if $∥ p^{*} ∥ \leq Δ$ and there exists $λ \geq 0$ such that

(B + λ I) p^{*} = - g, λ (Δ - ∥ p^{*} ∥) = 0, B + λ I ⪰ 0.

The condition $B + λ I ⪰ 0$ is what upgrades the first-order KKT stationarity of Exercise 5 to global optimality even when $B$ is indefinite: it forces $p^{*}$ to be the global minimiser of the convex shifted model $g^{⊤} p + \frac{1}{2} p^{⊤} (B + λ I) p$ , whose constrained minimum over the ball coincides with that of $m$ . When $B ≻ 0$ and $∥ B^{- 1} g ∥ \leq Δ$ the solution is the interior Newton step with $λ = 0$ ; otherwise $λ > 0$ is the unique root of the secular equation on the boundary ^{[Conn, A. R., Gould, N. I. M. & Toint, P. L. — Trust-Region Methods]}.

Theorem 2 (the secular equation and the hard case). With $B = \sum_{i} λ_{i} q_{i} q_{i}^{⊤}$ ( $λ_{1} \leq \dots \leq λ_{n}$ ), the boundary solution solves the secular equation

\frac{1}{∥ p ( λ ) ∥} - \frac{1}{Δ} = 0, p (λ) = - (B + λ I)^{- 1} g = - i \sum \frac{q _{i}^{⊤} g}{λ _{i} + λ} q_{i},

sought for $λ \in (max (0, - λ_{1}), \infty)$ , where $∥ p (λ) ∥$ is strictly decreasing (Exercise 6); the reciprocal form is used because $1/∥ p (λ) ∥$ is nearly linear in $λ$ , so safeguarded Newton converges rapidly. The hard case occurs when $q_{1}^{⊤} g = 0$ (more generally $g$ is orthogonal to the eigenspace of $λ_{1}$ ) and $λ_{1} < 0$ : then $∥ p (λ) ∥ \to ∥ p (- λ_{1}) ∥ < \infty$ as $λ ↓ - λ_{1}$ , and if $Δ$ exceeds this limit no $λ > - λ_{1}$ works. The resolution sets $λ = - λ_{1}$ , takes $\overset{p}{^} = - (B - λ_{1} I)^{†} g$ (the pseudoinverse, on the range of $B - λ_{1} I$ ), and adds a multiple of the leftmost eigenvector, $p^{*} = \overset{p}{^} + σ q_{1}$ , with $σ$ chosen so $∥ p^{*} ∥ = Δ$ ; this $p^{*}$ satisfies $(B + λ I) p^{*} = - g$ with $B + λ I ⪰ 0$ singular, meeting Theorem 1. The Moré-Sorensen algorithm implements this with a Cholesky factorisation of $B + λ I$ at each Newton step on the secular equation, safeguarding $λ$ to stay in the interval of definiteness ^{[Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.)]}.

Theorem 3 (global convergence to stationary points). Let $f$ be bounded below and $C^{1}$ with Lipschitz gradient, let ${B_{k}}$ be uniformly bounded ( $∥ B_{k} ∥ \leq β$ ), and let each step $p_{k}$ satisfy the fraction-of-Cauchy-decrease condition $m_{k} (0) - m_{k} (p_{k}) \geq c_{1} (m_{k} (0) - m_{k} (p_{k}^{C}))$ for a fixed $c_{1} \in (0, 1]$ and $∥ p_{k} ∥ \leq Δ_{k}$ . Then with acceptance threshold $η = 0$ , $lim inf_{k \to \infty} ∥ g_{k} ∥ = 0$ , and with $η > 0$ , $lim_{k \to \infty} ∥ g_{k} ∥ = 0$ . The proof combines the Cauchy bound (Key theorem) with the ratio test: when $∥ g_{k} ∥$ stays bounded away from zero, the predicted reduction is bounded below by $\frac{1}{2} c_{1} ∥ g_{k} ∥ min (Δ_{k}, ∥ g_{k} ∥/ β)$ , and a Taylor estimate of $ared - pred = O (∥ p_{k} ∥^{2})$ forces $ρ_{k} \to 1$ for small $Δ_{k}$ , so the radius cannot shrink to zero, and an infinite sum of strictly positive reductions contradicts $f$ being bounded below. The Cauchy step is the only step quality the theorem needs, which is why the Cauchy point, dogleg, two-dimensional subspace, and exact solves all converge — each dominates the Cauchy decrease with $c_{1} = 1$ , the dogleg and exact solutions strictly improving on it ^{[Conn, A. R., Gould, N. I. M. & Toint, P. L. — Trust-Region Methods]}.

Theorem 4 (Steihaug-Toint truncated CG). For large $n$ , factoring $B + λ I$ is prohibitive, so the subproblem is solved approximately by conjugate gradients 43.07.04 on $m (p)$ from $p_{0} = 0$ , with two extra stopping rules: terminate and return the boundary point if a CG iterate would leave the trust region, or if a search direction $d$ has nonpositive curvature $d^{⊤} B d \leq 0$ (Exercise 7). In exact arithmetic the CG iterates have strictly increasing norms $∥ p_{0} ∥ < ∥ p_{1} ∥ < \dots$ , so the first boundary crossing is unambiguous, and the very first step is the Cauchy point — hence the truncated solution satisfies the fraction-of-Cauchy-decrease condition with $c_{1} = 1$ and Theorem 3 applies. When $B ≻ 0$ and the iteration converges inside the region, it returns the exact Newton step; when truncated at the boundary it returns a step bending from the Cauchy direction toward Newton, the iterative analogue of the dogleg. Each inner iteration costs one product $B d$ and no factorisation, so the method scales to the Hessian-free regime where only matrix-vector products are available ^{[Steihaug, T. — The Conjugate Gradient Method and Trust Regions in Large Scale Optimization]}.

Synthesis. The trust-region step is one object — the constrained minimiser of the quadratic model over a ball — and the foundational reason the whole apparatus works is the Cauchy sufficient-reduction bound, which guarantees a model decrease scaling like $∥ g_{k} ∥ min (Δ_{k}, ∥ g_{k} ∥/∥ B_{k} ∥)$ from the cheapest admissible step, so that any step dominating it inherits global convergence. The central insight is that this decouples robustness from the Newton step: where line-search Newton must repair an indefinite Hessian before it can produce a descent direction, the trust-region subproblem absorbs indefiniteness through the multiplier $λ$ , the characterisation $(B + λ I) p = - g$ with $B + λ I ⪰ 0$ being exactly the convexification that makes the constrained problem well posed, and the hard case is the precise boundary where this convexification becomes singular and an eigenvector of the leftmost eigenvalue must be added. The dogleg and two-dimensional subspace methods are cheap approximations that interpolate between the Cauchy point and the Newton step $- B^{- 1} g$ , while Moré-Sorensen solves the secular equation exactly and Steihaug-Toint 43.07.04 solves it approximately by truncated conjugate gradients whose first iterate is the Cauchy point — so the same min-over-a-ball problem is dual to a one-parameter eigenvalue-shift problem in $λ$ , and that duality is the bridge from the elementary steepest-descent baseline to the large-scale Hessian-free solvers. Putting these together, the Cauchy bound generalises the Armijo sufficient-decrease condition of line search, the secular monotonicity of $∥ p (λ) ∥$ generalises the one-dimensional line-minimisation, and the convergence theorem appears again wherever a globalised Newton method must converge from far away.

Full proof set Master

Proposition 1 (Cauchy sufficient reduction). For $m (p) = f + g^{⊤} p + \frac{1}{2} p^{⊤} B p$ with $g \neq = 0$ , $B$ symmetric, and Cauchy point $p^{C}$ at radius $Δ$ , one has $m (0) - m (p^{C}) \geq \frac{1}{2} ∥ g ∥ min (Δ, ∥ g ∥/∥ B ∥)$ .

Proof. As in the Key theorem. Restricting $m$ to the ray $p (t) = - t g /∥ g ∥$ gives the scalar quadratic $ψ (t) = - ∥ g ∥ t + \frac{1}{2} γ t^{2}$ with $γ = g^{⊤} B g /∥ g ∥^{2} \leq ∥ B ∥$ . If $γ \leq 0$ , $ψ$ is nonincreasing so $t^{*} = Δ$ and $m (0) - m (p^{C}) = ∥ g ∥Δ - \frac{1}{2} γ Δ^{2} \geq ∥ g ∥Δ \geq \frac{1}{2} ∥ g ∥ min (Δ, ∥ g ∥/∥ B ∥)$ . If $γ > 0$ and $t_{u} = ∥ g ∥/ γ \leq Δ$ , then $m (0) - m (p^{C}) = ∥ g ∥^{2} / (2 γ) \geq ∥ g ∥^{2} / (2∥ B ∥) = \frac{1}{2} ∥ g ∥ (∥ g ∥/∥ B ∥) \geq \frac{1}{2} ∥ g ∥ min (Δ, ∥ g ∥/∥ B ∥)$ . If $γ > 0$ and $t_{u} > Δ$ , then $γ Δ < ∥ g ∥$ and $m (0) - m (p^{C}) = ∥ g ∥Δ - \frac{1}{2} γ Δ^{2} > \frac{1}{2} ∥ g ∥Δ \geq \frac{1}{2} ∥ g ∥ min (Δ, ∥ g ∥/∥ B ∥)$ . $□$

Proposition 2 (KKT characterisation with global optimality). $p^{*}$ solves $min_{∥ p ∥ \leq Δ} m (p)$ globally iff $∥ p^{*} ∥ \leq Δ$ and there is $λ \geq 0$ with $(B + λ I) p^{*} = - g$ , $λ (Δ - ∥ p^{*} ∥) = 0$ , and $B + λ I ⪰ 0$ .

Proof. ( $\Leftarrow$ ) Suppose such a $λ$ exists. Since $B + λ I ⪰ 0$ , the function $\overset{m}{^} (p) = g^{⊤} p + \frac{1}{2} p^{⊤} (B + λ I) p$ is convex, and $(B + λ I) p^{*} = - g$ makes $p^{*}$ its unconstrained global minimiser, so for all $p$ , $\overset{m}{^} (p) \geq \overset{m}{^} (p^{*})$ , i.e.

m (p) + \frac{λ}{2} ∥ p ∥^{2} \geq m (p^{*}) + \frac{λ}{2} ∥ p^{*} ∥^{2} .

For any feasible $p$ with $∥ p ∥ \leq Δ$ , $\frac{λ}{2} ∥ p ∥^{2} \leq \frac{λ}{2} Δ^{2} = \frac{λ}{2} ∥ p^{*} ∥^{2}$ when $λ > 0$ (complementarity forces $∥ p^{*} ∥ = Δ$ ), and the inequality $λ (Δ - ∥ p^{*} ∥) = 0$ also covers $λ = 0$ at once (the shift term vanishes); substituting gives $m (p) \geq m (p^{*})$ . So $p^{*}$ is a global minimiser. ( $\Rightarrow$ ) Conversely, if $p^{*}$ is a global solution, the constraint qualification holds (a single smooth ball constraint), so KKT gives $λ \geq 0$ with $(B + λ I) p^{*} = - g$ and complementarity. For the curvature condition: if $∥ p^{*} ∥ < Δ$ then $λ = 0$ and second-order necessity at an interior minimiser gives $B ⪰ 0$ ; if $∥ p^{*} ∥ = Δ$ , take any $w$ with $w^{⊤} p^{*} = 0$ and consider feasible arcs on the sphere through $p^{*}$ tangent to $w$ — optimality along them yields $w^{⊤} (B + λ I) w \geq 0$ , and combined with $(B + λ I) p^{*} = - g$ along the radial direction, $B + λ I ⪰ 0$ on all of $R^{n}$ . $□$

Proposition 3 (secular monotonicity). For symmetric $B$ with $λ_{1} = λ_{m i n} (B)$ and $g$ not orthogonal to the $λ_{1}$ -eigenspace, $∥ p (λ) ∥ = ∥ (B + λ I)^{- 1} g ∥$ is continuous and strictly decreasing on $(- λ_{1}, \infty)$ from $+ \infty$ to $0$ , so the secular equation $∥ p (λ) ∥ = Δ$ has a unique root for every $Δ > 0$ .

Proof. As in Exercise 6: $∥ p (λ) ∥^{2} = \sum_{i} (q_{i}^{⊤} g)^{2} / (λ_{i} + λ)^{2}$ with each denominator positive on $(- λ_{1}, \infty)$ , and $\frac{d}{d λ} ∥ p (λ) ∥^{2} = - 2 \sum_{i} (q_{i}^{⊤} g)^{2} / (λ_{i} + λ)^{3} < 0$ strictly, since some $q_{i}^{⊤} g \neq = 0$ . As $λ ↓ - λ_{1}$ the term with $q_{1}^{⊤} g \neq = 0$ blows up, giving $∥ p (λ) ∥ \to + \infty$ ; as $λ \to \infty$ every term vanishes, giving $∥ p (λ) ∥ \to 0$ . Strict monotone continuity gives the unique root. $□$

Proposition 4 (dogleg dominates the Cauchy decrease). For $B ≻ 0$ , the dogleg step $p^{d l}$ at radius $Δ$ satisfies $m (0) - m (p^{d l}) \geq m (0) - m (p^{C})$ , so it meets the fraction-of-Cauchy-decrease condition with $c_{1} = 1$ .

Proof. By Exercise 4, $∥ p (τ) ∥$ is nondecreasing along the dogleg path, and one shows $m (p (τ))$ is nonincreasing along it: on the first segment $p (τ) = τ p^{U}$ , $\frac{d}{d τ} m (τ p^{U}) = g^{⊤} p^{U} + τ (p^{U})^{⊤} B p^{U}$ , and at $τ \leq 1$ this is $\leq g^{⊤} p^{U} + (p^{U})^{⊤} B p^{U} = 0$ at $τ = 1$ by the definition of $p^{U}$ as the line minimiser, so $m$ decreases on $[0, 1]$ ; on the second segment a direct computation using $p^{B} = - B^{- 1} g$ shows $\frac{d}{d τ} m (p (τ)) \leq 0$ for $τ \in [1, 2]$ . Hence the dogleg point, taken at the boundary crossing or at $p^{B}$ , has $m$ -value no larger than the value at the unconstrained Cauchy step $p^{U}$ , and the Cauchy point $p^{C}$ lies on the same initial ray at distance $\leq ∥ p^{U} ∥$ (when $p^{U}$ is interior, $p^{C} = p^{U}$ ; when capped, $p^{C}$ is the boundary point on the first segment, which the dogleg path passes through or beyond). In every case $m (0) - m (p^{d l}) \geq m (0) - m (p^{C})$ . $□$

Proposition 5 (global convergence, $lim inf$ form). Under $f$ bounded below and $C^{1}$ with $L$ -Lipschitz gradient, $∥ B_{k} ∥ \leq β$ , the fraction-of-Cauchy-decrease condition with constant $c_{1}$ , and $η = 0$ , the iterates satisfy $lim inf_{k} ∥ g_{k} ∥ = 0$ .

Proof sketch (full argument in Conn-Gould-Toint Ch. 6). Suppose for contradiction $∥ g_{k} ∥ \geq ϵ > 0$ for all large $k$ . By Proposition 1 and the fraction condition, $pred_{k} \geq \frac{1}{2} c_{1} ϵ min (Δ_{k}, ϵ / β)$ . A second-order Taylor bound with $L$ -Lipschitz gradient gives $∣ ared_{k} - pred_{k} ∣ \leq c_{2} Δ_{k}^{2}$ for a constant $c_{2}$ depending on $L, β$ . Thus $∣ ρ_{k} - 1∣ \leq c_{2} Δ_{k}^{2} / pred_{k} \leq 2 c_{2} Δ_{k}^{2} / (c_{1} ϵ min (Δ_{k}, ϵ / β))$ , which tends to $0$ as $Δ_{k} \to 0$ ; hence there is $\overset{ˉ}{Δ} > 0$ with $ρ_{k} > \frac{1}{4}$ whenever $Δ_{k} \leq \overset{ˉ}{Δ}$ , so the radius-update rule never shrinks below $\frac{1}{4} \overset{ˉ}{Δ}$ and $Δ_{k} \geq δ > 0$ for all large $k$ . Then every accepted step (and with $η = 0$ all steps with $ρ_{k} > 0$ are accepted, which holds for small enough $Δ_{k}$ ) reduces $f$ by at least $η^{'} pred_{k} \geq \frac{1}{2} c_{1} ϵ min (δ, ϵ / β) > 0$ , and infinitely many such reductions drive $f \to - \infty$ , contradicting boundedness below. Therefore $lim inf_{k} ∥ g_{k} ∥ = 0$ . $□$

Connections Master

Convex sets, functions, and operations 44.01.01 supplies the quadratic-form machinery the subproblem rests on: the model $m (p) = g^{⊤} p + \frac{1}{2} p^{⊤} B p$ is convex exactly when $B ⪰ 0$ , and the global-optimality characterisation $(B + λ I) p^{*} = - g$ with $B + λ I ⪰ 0$ is the convexification of an indefinite model — the multiplier $λ$ is chosen to push the shifted Hessian into the positive-semidefinite cone described in that unit, after which the constrained minimum over the ball is the minimum of a genuinely convex quadratic. The supporting-line and PSD-Hessian conditions of 44.01.01 are precisely the second-order facts the proof of Proposition 2 invokes.
Multivariable Taylor and extrema 02.05.05 is the source of the quadratic model itself and of the convergence analysis: $m_{k}$ is the second-order Taylor polynomial of $f$ at $x_{k}$ , the error $ared - pred$ is the Taylor remainder controlled by the Lipschitz constant of the gradient, and the ratio test measures how faithfully that truncated expansion predicts the true decrease. The global-convergence theorem is, at its core, a quantitative statement about when the Taylor remainder is small relative to the predicted reduction.
The conjugate gradient method 43.07.04 is the engine of the large-scale solver: Steihaug-Toint truncated CG runs conjugate gradients on the model $m (p)$ from the origin, exploiting the monotone-increasing norm of the CG iterates to detect the trust-region boundary and the curvature test $d^{⊤} B d \leq 0$ to detect indefiniteness, returning the boundary step in either case. The first CG iterate is the Cauchy point, so the truncated solve inherits the sufficient-reduction bound and hence global convergence, while costing only the matrix-vector products that make CG attractive for sparse or Hessian-free problems.
Derivative computation by finite differences and automatic differentiation 44.03.08 supplies the gradients $g_{k}$ and the Hessian information $B_{k}$ (or Hessian-vector products $B_{k} v$ ) that every trust-region step consumes; the Hessian-free regime where only products $B_{k} v$ are available is exactly the setting where Steihaug-Toint truncated CG, rather than the factorisation-based Moré-Sorensen solver, is the method of choice, since reverse-mode automatic differentiation delivers $\nabla f$ cheaply and a second sweep or a finite difference of gradients delivers $B_{k} v$ .

Historical & philosophical context Master

The trust-region idea grew out of work on damped least squares and nonlinear regression. Kenneth Levenberg in 1944 and Donald Marquardt in 1963 proposed adding a multiple of the identity to the Gauss-Newton normal equations, solving $(J^{⊤} J + λ I) p = - J^{⊤} r$ — the same shift $(B + λ I)$ that appears in the exact trust-region characterisation, though Levenberg and Marquardt controlled $λ$ directly rather than through a radius ^{[Marquardt 1963]}. S. M. Goldfeldt, R. E. Quandt, and H. F. Trotter in 1966 made the radius explicit, and the modern formulation with the ratio test and adaptive radius was consolidated by M. J. D. Powell in a sequence of papers from 1970 onward, who also analysed the dogleg method as a cheap approximate subproblem solver.

The exact subproblem theory — the global-optimality characterisation through $(B + λ I) ⪰ 0$ and the resolution of the hard case — was given its definitive treatment by Jorge Moré and Danny Sorensen in 1983, whose safeguarded-Newton algorithm on the secular equation remains the standard exact solver ^{[Moré-Sorensen 1983]}. In the same year Trond Steihaug introduced the truncated-conjugate-gradient method that made trust regions practical for large-scale problems ^{[Steihaug 1983]}, independently obtained by Toint. The comprehensive synthesis is the monograph of Andrew Conn, Nicholas Gould, and Philippe Toint in 2000, which unified the convergence theory under the fraction-of-Cauchy-decrease condition and catalogued the subproblem solvers ^{[Conn-Gould-Toint 2000]}. Jorge Nocedal and Stephen Wright present the method as the natural alternative to line search, organising it around the Cauchy point and the dogleg step ^{[Nocedal-Wright 2006]}.

Bibliography Master

@book{NocedalWright2006tr,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{ConnGouldToint2000,
  author    = {Conn, Andrew R. and Gould, Nicholas I. M. and Toint, Philippe L.},
  title     = {Trust-Region Methods},
  series    = {MPS-SIAM Series on Optimization},
  publisher = {SIAM},
  year      = {2000}
}

@article{MoreSorensen1983,
  author  = {Mor\'{e}, Jorge J. and Sorensen, Danny C.},
  title   = {Computing a Trust Region Step},
  journal = {SIAM Journal on Scientific and Statistical Computing},
  volume  = {4},
  number  = {3},
  year    = {1983},
  pages   = {553--572}
}

@article{Steihaug1983,
  author  = {Steihaug, Trond},
  title   = {The Conjugate Gradient Method and Trust Regions in Large Scale Optimization},
  journal = {SIAM Journal on Numerical Analysis},
  volume  = {20},
  number  = {3},
  year    = {1983},
  pages   = {626--637}
}

@article{Marquardt1963,
  author  = {Marquardt, Donald W.},
  title   = {An Algorithm for Least-Squares Estimation of Nonlinear Parameters},
  journal = {Journal of the Society for Industrial and Applied Mathematics},
  volume  = {11},
  number  = {2},
  year    = {1963},
  pages   = {431--441}
}

@article{Powell1970,
  author    = {Powell, Michael J. D.},
  title     = {A New Algorithm for Unconstrained Optimization},
  booktitle = {Nonlinear Programming},
  editor    = {Rosen, J. B. and Mangasarian, O. L. and Ritter, K.},
  publisher = {Academic Press},
  year      = {1970},
  pages     = {31--65}
}

Prerequisites

44.01.01
02.05.05

Tier anchors

beginner: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §4.1 (the trust-region idea: trust the quadratic model only inside a ball, and grow or shrink that ball by how well the model predicted the actual drop); Shewchuk 1994 An Introduction to the Conjugate Gradient Method Without the Agonizing Pain (CMU technical report) §6 for the steepest-descent picture the Cauchy point formalises
intermediate: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §4.1-4.3 (the trust-region subproblem, the ratio test and radius update, the Cauchy point and its sufficient-reduction bound, the dogleg method for positive-definite Hessians, two-dimensional subspace minimisation, and the global-convergence theorem to stationary points)
master: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §4.3 (the exact subproblem solution via $(B + λ I) p = - g$ , the hard case, and Moré-Sorensen) and §7.1 (Steihaug-Toint truncated CG); Conn, Gould & Toint 2000 Trust-Region Methods (SIAM/MPS) Ch. 6-7 (the subproblem theory, the secular equation, and the convergence analysis)

References

Nocedal, J. & Wright, S. J. — Numerical Optimization (2nd ed.) · Springer, 2006. Chapter 4 'Trust-Region Methods': §4.1 introduces the quadratic model $m_{k} (p) = f_{k} + g_{k}^{⊤} p + \frac{1}{2} p^{⊤} B_{k} p$ on the trust region $∥ p ∥ \leq Δ_{k}$ , the trust-region subproblem $min_{∥ p ∥ \leq Δ} m_{k} (p)$ , and the ratio $ρ_{k} = (f (x_{k}) - f (x_{k} + p_{k})) / (m_{k} (0) - m_{k} (p_{k}))$ of actual to predicted reduction governing the radius update (shrink when $ρ_{k} < \frac{1}{4}$ , expand when $ρ_{k} > \frac{3}{4}$ and the step is at the boundary, accept the step only when $ρ_{k} > η \geq 0$ ). §4.1 defines the Cauchy point $p_{k}^{C}$ as the minimiser of $m_{k}$ along the steepest-descent direction inside the region, with the closed form $p_{k}^{C} = - τ_{k} (Δ_{k} /∥ g_{k} ∥) g_{k}$ , and Theorem 4.4 gives the sufficient-reduction bound $m_{k} (0) - m_{k} (p_{k}^{C}) \geq \frac{1}{2} ∥ g_{k} ∥ min (Δ_{k}, ∥ g_{k} ∥/∥ B_{k} ∥)$ , the engine of global convergence. §4.1 (the dogleg method) constructs the piecewise-linear path from the unconstrained Cauchy step $p^{U} = - (g^{⊤} g / g^{⊤} B g) g$ to the full Newton step $p^{B} = - B^{- 1} g$ when $B ≻ 0$ , intersected with the trust-region boundary. §4.1 two-dimensional subspace minimisation extends this to $span {g, B^{- 1} g}$ . §4.3 'Iterative Solution of the Subproblem' proves the characterisation that $p^{*}$ solves the subproblem iff $(B + λ I) p^{*} = - g$ with $λ \geq 0$ , $B + λ I ⪰ 0$ , and $λ (Δ - ∥ p^{*} ∥) = 0$ , treats the hard case where $g ⊥$ the eigenspace of the smallest eigenvalue, and gives the Moré-Sorensen Newton iteration on the secular equation $1/∥ p (λ) ∥ - 1/Δ = 0$ . Theorem 4.5-4.6 give global convergence: $lim inf ∥ g_{k} ∥ = 0$ when $η = 0$ and $lim ∥ g_{k} ∥ = 0$ when $η > 0$ , under bounded $∥ B_{k} ∥$ and a fraction-of-Cauchy-decrease condition on the step.
Conn, A. R., Gould, N. I. M. & Toint, P. L. — Trust-Region Methods · SIAM/MPS Series on Optimization (2000). Ch. 6 'Global Convergence of the Basic Algorithm' establishes convergence to first-order critical points under the Cauchy-decrease (fraction-of-optimal-decrease) condition and bounded model Hessians, and to second-order points under the eigenpoint condition; Ch. 7 'The Trust-Region Subproblem' develops the exact theory: the characterisation of the global solution of $min_{∥ p ∥ \leq Δ} g^{⊤} p + \frac{1}{2} p^{⊤} B p$ via the existence of $λ \geq 0$ with $(B + λ I) ⪰ 0$ , $(B + λ I) p = - g$ , complementarity $λ (Δ - ∥ p ∥) = 0$ , the convexity of $λ \mapsto ∥ p (λ) ∥$ that makes the secular equation solvable by safeguarded Newton, the hard case and its resolution by adding a multiple of the eigenvector of the leftmost eigenvalue, and the Moré-Sorensen and Gay-Sorensen algorithms; the Steihaug-Toint truncated-CG method that solves the subproblem approximately for large-scale problems by running conjugate gradients until either convergence, a boundary crossing, or a direction of negative curvature is detected.
Steihaug, T. — The Conjugate Gradient Method and Trust Regions in Large Scale Optimization · SIAM Journal on Numerical Analysis 20 (1983), 626-637: the truncated-CG (Steihaug-Toint) method for the trust-region subproblem, which applies conjugate gradients to the model $m (p)$ starting from $p_{0} = 0$ , terminating when the iterate would leave the trust region (taking the step to the boundary along the current direction) or when a direction $d$ of nonpositive curvature $d^{⊤} B d \leq 0$ is encountered (again stepping to the boundary), and the theorem that every CG iterate has monotonically increasing norm so the first boundary crossing is the step, giving a method whose first step is the Cauchy point and whose decrease dominates the Cauchy decrease, hence inheriting global convergence at the cost of one matrix-vector product per inner iteration.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m