Motivation
A Newton step minimizes a local quadratic model when the Hessian is positive definite, but the model may be inaccurate far from its center. With an indefinite Hessian the unrestricted quadratic can even decrease without bound. A trust region reverses the usual line-search question: first restrict the distance over which the model is trusted, then compare its predicted improvement with the improvement actually observed. An unsuccessful comparison shrinks the region and tries again.
The restriction makes every continuous quadratic model attain a minimum, even if its curvature is negative. A practical algorithm need not solve that subproblem exactly. It can instead demand a definite fraction of the improvement obtainable along the negative gradient. We will distinguish the exact model solution, a cheap safeguarded Cauchy step, and the assumptions needed to turn repeated accepted steps into a first-order convergence theorem. None of these claims proves convergence to a global minimum of a nonconvex objective.
Definitions
Definition 10.1.1
(Trust-region model, predicted decrease and agreement ratio)
At , write and . Choose a symmetric matrix and radius . The model and predicted decrease of a trial step are
For positive predicted decrease define the agreement ratio
The ratio compares the actual decrease with the decrease the model promised. The radius policy then decides what to do with the trial. Take constants and . Reject the trial and set , when . Otherwise accept it, set , and leave the radius unchanged except that, if and , it may be enlarged to . A rejected trial changes no iterate, but it is still an iteration of the analysis. If , the algorithm stops; the step and ratio below are defined only when .
Definition 10.1.2
(Safeguarded Cauchy step)
Assume for a known , and define . For , the safeguarded Cauchy step is
The extra cap limits the length when the gradient is small. The exact minimizer of the model along the feasible negative-gradient ray achieves at least as much model decrease, but may not obey this length cap. The global theorem below states the cap explicitly rather than silently imposing it on every trust-region method.
Theorem/Proposition
Theorem 10.1.3
(Global minimizer of the quadratic model)
For symmetric and , minimizes over if and only if there is such that
Theorem 10.1.4
(First-order convergence for safeguarded Cauchy steps)
Suppose is continuously differentiable on , bounded below, and has an -Lipschitz gradient with . Suppose each symmetric obeys , and use the radius policy and safeguarded Cauchy steps above. Unless the algorithm stops at a stationary point, .
The first result characterizes the global model minimizer, including indefinite and singular cases. The second proves stationarity for a specific step rule, not for an arbitrary model solver. Stronger solvers need their own decrease and step-control hypotheses. Boundedness of the iterates, convexity, and existence of a minimizer are not required for this gradient conclusion; a cluster point, if one exists, is stationary by continuity.
Concept lensAnalytic
The exact step as a curve from Newton to steepest descent
Outside the hard case, the model minimizer for radius lies on the curve , , with as in the proof below. Its norm is nonincreasing in , so shrinking moves a boundary solution along the curve toward larger . If , the curve starts at the Newton step at ; as , . Small trust regions therefore turn the exact step toward the steepest-descent direction that the Cauchy step uses.
Proof sketch or proof idea
Model optimality, including the hard case
Proof
(Expanding the model difference, then constructing a multiplier)
If the displayed conditions hold, expand the model difference for any feasible :
The first term is nonnegative. If , complementarity puts on the boundary and the second term is nonnegative; if , it vanishes. This proves sufficiency even if itself is indefinite.
For necessity, diagonalize and put . Let . For the stationary solution has components , and its norm is continuous and nonincreasing in , tending to zero at infinity. If , lies in its range, and the minimum-norm solution at has norm at most , it satisfies the conditions with .
Otherwise, if the limiting norm as exceeds or is infinite, continuity gives a root with and . In the remaining case , is orthogonal to the eigenspace at and the minimum-norm limiting solution has norm at most . Add a vector in that eigenspace to reach the boundary; it remains a solution of . This is the singular hard case. The constructed point satisfies the sufficient conditions, so it is a global minimizer. Any other global minimizer has the same value; the nonnegative terms in the difference formula must vanish. For , a zero quadratic form gives , hence ; if , the second term also forces . Thus the same stationarity and complementarity conditions hold. This proves necessity without assuming the Hessian is invertible.
The proof of the convergence theorem has two parts. The first shows that small radii are eventually accepted; the second converts accepted decrease into vanishing gradients.
Cauchy decrease and reliable small radii
Proof
(Cauchy decrease and the acceptance threshold)
For , symmetry and the norm bound give
Indeed . The step also satisfies . The Lipschitz-gradient descent estimate and give, with ,
Fix . If and , then the Cauchy bound implies . Such a step is accepted. Therefore a rejected step while the gradient is at least cannot shrink the radius below times this threshold.
From accepted decrease to vanishing gradients
Proof
(A lower limit, then finite travel)
First suppose eventually. From the preceding paragraph, after that time the radii have a positive lower bound: accepted steps do not shrink them, and a rejection cannot cross below the stated positive threshold except by one factor . Every accepted step then decreases by at least a fixed positive amount, using the Cauchy bound and . There cannot be infinitely many accepted steps because is bounded below; nor can there be infinitely many successive rejections, because shrinking eventually makes the ratio acceptable. This contradiction proves .
To strengthen this to a limit, fix . On accepted steps with and , the accepted decrease is at least . Accepted steps with and have decrease at least , so there are only finitely many, each with finite length. Consequently the total length of accepted steps starting with gradient at least is finite. Rejections have zero displacement.
Choose small enough that . By the safeguarded length bound and Lipschitz continuity, a step starting with gradient below ends with gradient below . If gradients reached infinitely often while their liminf were zero, select an index with gradient at least after an index below , and let be the last index below before . Then , and steps start with gradient at least . Lipschitz continuity forces their total travel to be at least . Infinitely many disjoint excursions contradict the finite total length. Hence gradients tend to zero. The length cap is used precisely at the transition into an excursion.
Reading the two error estimates together
Proof X-ray
Why a smaller radius restores agreement
The hypotheses enter at separate places. The uniform bound is used twice: in the Cauchy inequality, where it keeps , and in the discrepancy estimate, where it controls the model curvature. Lipschitz continuity of the gradient supplies the other half of that estimate and later converts a change in gradient norm into a distance traveled. Boundedness below is used only to make the accepted decreases summable.
The key move compares orders. The Cauchy inequality is a lower bound on what the model predicts; the Lipschitz estimate is an upper bound on how far reality can deviate from that prediction. When the gradient is bounded away from zero, the guaranteed prediction is proportional to a small radius, whereas the discrepancy is proportional to its square, so sufficiently small radii force . Merely saying that the model is locally accurate would not suffice without knowing that its predicted decrease does not vanish even faster.
This comparison alone yields only . The argument closes by turning decrease into length: accepted steps with large gradients have finite total length, while each excursion from a gradient below to one at least must travel at least . The cap prevents an excursion from beginning with a single long jump.
The theorem permits a singular or indefinite at every iteration because the Cauchy argument uses only its uniform norm bound. It also permits rejecting many consecutive trials, but not forever at a fixed nonstationary point: the radius is repeatedly multiplied by until the preceding comparison forces acceptance. The upper bound is a convenient standing policy; it is not essential to this finite-travel argument, because the large-radius accepted steps are finite in number.
A rejected model and the meaning of the ratio
Consider at , and deliberately choose the model curvature rather than the true Hessian. With radius one, the exact model minimizer is : the model change is , whose smaller endpoint value is . The predicted decrease is , while the actual decrease from to zero is only . Thus and an acceptance threshold rejects the trial. The model offered an optimistic prediction; rejection prevents that prediction from being mistaken for actual progress.
If the radius is then reduced to , the exact model step is . The prediction is , while the actual decrease is . Its ratio is , so this particular trial is accepted. This computation illustrates the ratio policy, not the global theorem: does not have globally Lipschitz gradient on the entire real line, and the example uses exact model steps rather than the safeguarded Cauchy rule.
Why the trust-region multiplier is not a penalty parameter
Concept lensStructural
A multiplier local to the model
The multiplier belongs to one fixed quadratic subproblem. For a boundary solution, it shifts the Hessian enough that the shifted curvature is nonnegative while stationarity and the boundary norm condition both hold. It can vary between iterations even if the radius is unchanged. It is not the multiplier of an original constraint on the decision variable, and its numerical value should not be confused with a penalty coefficient chosen for a different constrained problem.
For a one-dimensional convex model with , the unconstrained minimizer is . If its magnitude does not exceed , choose . Otherwise the minimizer is the endpoint and stationarity gives . The formula shows how the multiplier increases as the permitted displacement shrinks. At the transition , the unconstrained minimizer lies on the boundary but : boundary activity does not imply a strictly positive multiplier.
A stationary point of the original objective can still have negative curvature. Our first-order rule explicitly allows stopping when , so it may stop at a saddle or maximum. A method seeking second-order stationarity would instead inspect negative curvature and require an additional decrease condition and convergence proof. The indefinite model example demonstrates that a trust-region subproblem can exploit such curvature, but it does not make the first-order theorem a second-order theorem.
Worked examples
Worked example 10.1.5
(An indefinite model has a finite ball minimizer)
Let on . Both and minimize it. Here , and make and satisfy all four conditions. The unconstrained model is unbounded below; the ball changes the problem fundamentally.
Worked example 10.1.6
(The singular hard case)
Take , and . At , stationarity gives and leaves free. The boundary requires . Since is positive semidefinite, both points are global model minimizers. Inverting would miss them.
Worked example 10.1.7
(A Newton step safeguarded by the ball)
For at , take the exact Hessian . The unrestricted Newton step is . With radius one, the exact model step is and gives . Model and objective coincide, so predicted and actual decreases are both and . A later larger radius can permit the full Newton step.
Common mistakes
Common mistake
(Accepting every step with a positive ratio)
A positive ratio means that the objective decreased, but the rule above accepts only when . In the rejected-model computation, is positive, yet with the trial is rejected. The convergence proof uses to turn predicted decrease into a fixed fraction of actual decrease; a merely positive ratio gives no such fraction.
Common mistake
(Treating a boundary minimizer as a Newton step)
When and , the minimizer solves , not . In the safeguarded Newton example, , and ; the boundary step has , since . The Newton equation would give , which is infeasible.
Common mistake
(Inverting the shifted Hessian in the hard case)
It is tempting to compute and adjust until . For , and , every admissible gives , whose norm is below , so no inverse reaches the boundary. The minimizers use the singular shift together with the eigenvector component .
The semidefinite condition in the model certificate is not decoration: without it, the remaining conditions can certify the worst point of the ball.
Counterexample mode
Stationarity and complementarity without curvature
Claim: if a feasible satisfies and for some , then minimizes the model on the ball. Take , so and , with . The boundary point satisfies with , and complementarity holds trivially. Yet and ; since on , the point is in fact the maximizer. The omitted condition fails: is not positive semidefinite. At , stationarity gives and , so the full certificate identifies the true minimizer.
This proof uses the step-length cap. Other analyses can establish the same gradient conclusion using fraction-of-Cauchy decrease by a different argument, which is not developed here.
Summary
A trust region makes the quadratic subproblem finite and permits a global certificate even for negative curvature. A shifted positive semidefinite Hessian and complementary radius multiplier characterize exact model minimizers. Safeguarded Cauchy steps achieve a quantified predicted decrease; sufficiently small regions make the model reliable, and accepted decrease plus a length-control argument forces the gradient to zero under the stated global assumptions.
Exercises
Quick check
(Minimize over and find its radius multiplier.)
Check the sign of on the interval.
Solution
The unconstrained minimizer is , outside the ball. Since on , the model is increasing there and the constrained minimizer is . Stationarity gives ; the shifted Hessian is positive, and complementarity holds because is on the boundary.
Quick check
(For , and radius , compute the safeguarded Cauchy step using as the norm bound, and its predicted decrease.)
Compare the two candidates in the definition of .
Solution
Here and , so . The predicted decrease is . The Cauchy bound guarantees , and indeed .
Quick check
(For on , check the certificate at , and explain the failure.)
Test all four conditions, not only stationarity and complementarity.
Solution
At with , stationarity reads and complementarity holds, but is not positive semidefinite. The certificate is therefore incomplete, and indeed : zero is the maximizer, not the minimizer.
Quick check
(If , , and , give a radius threshold sufficient to ensure acceptance by the proof.)
Take in the acceptance threshold of the proof.
Solution
Here and . With the threshold is . Any positive radius at most gives , hence , under the stated assumptions.