What an inner solver must deliver
The trust-region model is a small optimization problem inside a larger one. Its exact global minimizer has the shifted-Hessian certificate derived in the preceding unit, but finding that minimizer can require more work than the outer iteration needs. If a matrix is available only through products with vectors, a method that diagonalizes it is particularly unattractive. We therefore ask a more modest question: can a finite sequence of matrix-vector products produce a feasible step with a definite amount of model decrease?
The negative-gradient ray gives a baseline, the Cauchy point. Truncated conjugate gradient (CG) improves on that baseline while curvature remains positive, stops on the ball boundary, and turns detected nonpositive curvature into a descending boundary step. The word “detected” matters. A Krylov space may never encounter a negative-curvature direction elsewhere in the ambient space. We will prove a model-decrease guarantee, rather than confuse the algorithm with a global quadratic solver.
Throughout, omit the constant term in the model and write
The norm is Euclidean and the matrix norm is its induced spectral norm. Unless stated otherwise, and every algorithmic operation uses exact arithmetic. If , the first-order routine below returns zero; it makes no second-order claim.
The Cauchy point and its decrease
Put and . On the ray , feasibility means , and
If , this function is strictly decreasing on the feasible interval, so choose its right endpoint. If , its unrestricted minimum is at . Thus
The Cauchy point minimizes along one ray, not over the whole ball. Nevertheless its decrease has the correct scale for a global first-order argument.
Proposition 10.2.1
(Cauchy decrease)
If and , then
Proof
(Comparison with a short ray step)
Compare with the feasible ray point , where . Since minimizes on the feasible part of the ray, and ,
This is positive because and .
Using avoids a special division convention when . The comparison point is exactly the safeguarded ray step of the preceding unit. The Cauchy point may be longer; it is the decrease, rather than that step's length bound, which transfers automatically.
Reaching the boundary without crossing it
Suppose and . There is exactly one positive for which . Set
This is the positive root of ; the other root is negative because the product of the roots is . Convexity of the ball keeps the segment before the positive root feasible. In floating-point work the equivalent formula avoids cancellation when , but the proof here uses the exact positive root. A tolerance for declaring boundary contact changes the implemented policy and needs its own error account.
A precise truncated-CG policy
Choose a relative residual tolerance . Start with
Here is the gradient of the quadratic model, not a measure of original-objective feasibility. At an iteration with nonzero , use the following order.
- Compute . If , return . The zero-curvature case follows the same rule as negative curvature.
- If , form . If , return . Equality is a boundary return, before any residual test.
- Otherwise set and . If , return ; this includes an exactly zero residual.
- If the residual is still nonzero, set and , then continue.
The residual stopping test follows a completed step, so the algorithm performs at least its Cauchy comparison. Every state from which a new direction is taken is strictly inside the ball, so the boundary-root formula always has . This policy chooses the forward intersection in a nonpositive-curvature direction. Comparing both intersections could improve a model value, but is not necessary for the guarantee below.
Theorem 10.2.2
(Finite termination and Cauchy decrease)
For symmetric , , and , this exact-arithmetic routine returns after at most direction iterations. Its output is feasible and satisfies . Consequently, if ,
The statement does not assert that is a global minimizer of the ball-constrained model.
Why the CG identities remain valid before truncation
Proof
(Conjugacy and orthogonality by induction)
We prove the identities while positive-curvature steps remain strictly interior. Inductively, the existing directions are mutually -conjugate and the current residual is orthogonal to every earlier direction. The recurrence gives . The exact line step therefore makes
For , follows from and . Thus the new residual is orthogonal to all directions so far. Earlier residuals lie in their span, because and . Hence nonzero residuals are mutually orthogonal.
To prove conjugacy for the new direction, use . For , the orthogonality just proved gives , and the preceding direction's conjugacy gives . For the adjacent direction,
so the two terms in cancel. This closes the induction. No positive definiteness on the whole space was used: only the positive directional curvatures of the steps already completed.
Mutually conjugate directions with are linearly independent: multiplying a linear relation by each forces each coefficient to vanish. If positive-curvature interior steps occur, their directions span and is orthogonal to that entire space, hence zero. Otherwise the routine has already returned at a tolerance, boundary or nonpositive-curvature test. No division by a zero residual is reached.
Concept lensAlgebraic
Interior CG iterates minimize the model over Krylov subspaces
Let . While every completed step is interior with , induction on the recurrences shows that span . In this -conjugate basis, splits into strictly convex one-dimensional terms, and makes the minimizer of its own term. Hence is the unique minimizer of over . The counterexample below is a case in which never leaves one coordinate axis.
Why later steps preserve the first decrease
Proof
(Monotone descent from the Cauchy step)
At the beginning of any direction, the model derivative along that direction is
For it is strictly negative on the entire forward ray. For it stays nonpositive up to , and a boundary truncation takes . Each returned or completed segment decreases the model. On the first direction , the first step is exactly the Cauchy point, either at the ray minimum or at the boundary. If the routine continues, subsequent segments reduce the value further. This proves both and the theorem's decrease bound.
Proof X-ray
Two independent halves of the termination theorem
Finite termination and sufficient decrease are proved by different mechanisms. For termination, the induction keeps the nonzero residuals mutually orthogonal, so at most of them fit in ; the subtle point is that it uses only the curvatures of steps already completed, never positive definiteness of on the whole space. For decrease, the key move is that the first direction is , so the first segment ends exactly at the Cauchy point, whether at the ray minimum or at the boundary. Afterwards the derivative is nonpositive on every segment actually taken: on the whole forward ray when , and up to when . That is why the boundary rule uses the forward root. Neither half says anything about global optimality: a boundary return can have a large residual, and a zero residual can miss negative curvature outside the generated subspace.
Worked calculations
Worked example 10.2.3
(An SPD model solved in two interior steps)
Take , , and . Then , , and , whose norm is . The residual is , and gives . Its curvature is , so . Thus , , and . The model value is , so the predicted decrease is .
If the same model has radius , the first unconstrained ray minimum lies outside the ball. The boundary root from zero is , giving and predicted decrease . The second direction is never formed.
Worked example 10.2.4
(Negative curvature after one positive-curvature step)
Let , , and . The first direction is , with curvature , so and is interior. Now , and . Its curvature is , triggering the nonpositive-curvature rule.
Here , and . The boundary root is , so the returned point is with norm five. The model value changes from to . This is a useful descending step. It is not the exact global solution: the first coordinate of would require , which violates the necessary nonnegative-multiplier condition.
Counterexample mode
A zero residual can miss the hard case
Set , and . CG explores only the second coordinate, takes , and returns with and . But has norm one and value . The shifted-Hessian certificate holds there with and . The unvisited first coordinate carries negative curvature. Repair the false claim “small residual proves a global model solution” by adding a valid curvature and boundary certificate, or retain only the sufficient-decrease conclusion actually proved for truncated CG.
What residuals certify
Proposition 10.2.5
(Residual bounds for a positive definite model)
For SPD with known , let and . Then
Proof
(Expanding about the stationary point)
Both bounds follow from : first , and since , expanding about gives .
If is feasible it is also the ball minimizer. Even when it is outside, any feasible has model gap to the constrained minimizer at most the displayed unconstrained gap.
Common mistake
(Treating the relative residual test as an error bound)
The bounds above depend on a positive spectral lower bound; the relative condition alone does not supply one. A truncated-CG return at a small residual says nothing about the distance to the solution unless such a bound is known.
Worked example 10.2.6
(A boundary minimizer with a nonzero unshifted residual)
Take , , and , so on . Since on , the minimizer is the boundary point , with . Its unshifted residual is , so unshifted stationarity is the wrong test on a boundary. With the multiplier , and , while the complementarity term vanishes because . The approximate certificate below therefore bounds the gap by : the point is an exact global minimizer.
A useful approximate certificate is available with explicit curvature information.
Proposition 10.2.7
(Approximate optimality certificate)
Suppose is feasible, , , and . Then for any global ball minimizer ,
Proof
(Expansion with a shifted Hessian)
Expand into , discard the nonnegative quadratic, and use .
At an exactly feasible boundary point the last term vanishes. A small without the positive-semidefinite check or without control of the complementarity term is not this certificate. Truncated CG does not automatically compute a suitable or establish global positive semidefiniteness.
Connecting to the outer convergence proof
The preceding unit proves gradient convergence for a safeguarded ray step.
Common mistake
(Citing the outer theorem for unguarded truncated CG)
Unmodified truncated CG inherits its Cauchy-decrease bound but need not inherit its length cap . Therefore that theorem cannot be cited merely because both methods are called trust-region methods.
There is a precise guarded variant. At outer iteration , run the routine on the smaller ball
Its output satisfies both
Keep the outer acceptance and radius policy of the preceding unit, including enlargement only when its original boundary condition holds. Under the same globally Lipschitz gradient, lower objective bound and uniform symmetric-model norm bound, the proof there applies to these two inequalities: its model-error estimate uses feasibility, its small-radius acceptance uses the decrease inequality, and its finite-excursion argument uses the length cap. Hence this guarded variant also has , or stops at a stationary point. This argument deliberately retains the cap; it neither proves the unrestricted truncated-CG outer method nor a second-order stationarity theorem.
Exercises
Quick check
(For , and , compute the Cauchy point and the first truncated-CG return.)
Start with .
Solution · Answer
, so and . For CG, and , so the nonpositive-curvature rule returns that same boundary point. Its model value is .
Quick check
(If , and , compute the positive boundary root and explain why the negative root is not used.)
Form , and for the boundary quadratic.
Solution · Answer
Here , , , so the roots are . The forward root is , producing on the ball. The negative root goes backward along the direction, whereas the descent proof controls the forward segment.
Quick check
(Suppose and an interior approximation has . Bound its distance and objective gap to the unrestricted quadratic minimizer.)
Use the residual bounds with .
Solution · Answer
gives distance at most and objective gap at most . These are rigorous upper bounds using a known spectral lower bound; residual size alone would not determine them.
Quick check
(In the scalar boundary model , , , take , . Compute and both terms in the approximate certificate. Does zero complementarity error follow just from ?)
Compare the certificate with the true gap to the minimizer .
Solution
and . The residual term is , and the complementarity term is . The bound is loose but valid: the actual gap is . A nonnegative multiplier need not satisfy complementarity; here the point is strictly inside and the multiplier is positive.
Quick check
(With , and , find the guarded radius and guaranteed predicted decrease. Explain which additional hypothesis is supplied by the guard.)
The guarded radius is .
Solution
and . The guaranteed decrease is . The guard supplies in addition to ordinary ball feasibility and sufficient decrease, allowing the stated outer finite-excursion proof to apply.