advanced32 min studyLesson 293 in Mathematics

Trust-region subproblems and model agreement

Constrain a local quadratic model, compare prediction with reality, and handle negative curvature without an unchecked Newton step.

Before you begin

On this page

The question for today

What you’ll understand

Form a Euclidean trust-region subproblem.
Compute actual-to-predicted reduction and use an explicit acceptance rule.
Recognize the positive-semidefinite shifted-Hessian certificate for a global subproblem solution.

A quadratic approximation can be accurate close to the current point and dangerously misleading farther away. Trust-region methods make the radius of that local promise part of the algorithm. They choose a step by minimizing a model inside a ball, evaluate the original objective at the trial point, and compare actual improvement with the model's prediction. A failed model can teach the algorithm to narrow its next experiment. The subproblem is itself an optimization task, and solving it exactly is not required for every useful outer iteration.

Optimize only where the model is trusted

At the current point, construct a quadratic with the true gradient and a symmetric curvature matrix B. Restrict the step norm to a positive radius. Unlike a line search, this procedure can change direction as the allowed radius changes. An indefinite B is allowed because a continuous quadratic attains its minimum on a compact ball, even when the corresponding unconstrained quadratic is unbounded below. This compactness is the simplest reason the subproblem remains meaningful in negative curvature.

A global minimizer of the Euclidean quadratic subproblem admits a nonnegative scalar shift lambda. The shifted matrix must be positive semidefinite, its product with the chosen step equals minus the gradient, and complementarity links the shift to an active radius. These conditions are necessary and sufficient for this quadratic-on-a-ball problem. Requiring only its first-order equations can select the wrong stationary point. Singular shifted matrices and gradient orthogonality to a negative eigenspace create the so-called hard case.

\min_{\|p\|\leq\Delta}\ m(p)=f(x)+g^{\mathsf T}p+\tfrac12p^{\mathsf T}Bp;\quad (B+\lambda I)p=-g,\ B+\lambda I\succeq0,\ \lambda\geq0,\ \lambda(\Delta-\|p\|)=0

Together with feasibility, these conditions characterize a global solution of this Euclidean trust-region subproblem. They do not certify the global minimum of the original nonlinear objective.↔ Scroll wide equations horizontally.

Compare reductions rather than pictures

The predicted reduction is the model's value at zero minus its value at the proposed step. When it is positive, divide the actual objective reduction by that prediction. A ratio near one signals useful agreement; a negative ratio means the objective rose while the model promised a decrease. A ratio above one is possible when the objective decreases more than predicted. The ratio has no sensible acceptance meaning if the predicted reduction is zero or negative, so a solver must treat that case separately.

A concrete implementation chooses acceptance and radius-update thresholds rather than borrowing universal numbers from a diagram. One reasonable teaching rule accepts when the ratio exceeds 0.1, shrinks below 0.25, and considers expansion above 0.75 when the step reached the radius. These are chosen algorithmic parameters. Expansion is not automatic after any accurate tiny interior step, and a rejected trial generally leaves the current iterate unchanged while reducing the radius.

\operatorname{pred}=m(0)-m(p)>0,\qquad \rho=\frac{f(x)-f(x+p)}{m(0)-m(p)}

The numerator measures the original objective, while the denominator measures the local model. Their distinction is essential even when both are evaluated at the same trial step.↔ Scroll wide equations horizontally.

Useful approximations and qualified guarantees

The Cauchy step minimizes the model along the negative-gradient ray, truncated by the radius. It is cheap and provides a baseline amount of predicted decrease when the gradient is nonzero. Practical approximate subproblem solvers commonly require at least a fixed fraction of this decrease. Krylov methods can additionally exploit curvature through Hessian-vector products. A sequence of arbitrarily poor approximate solutions has no convergence guarantee merely because the outer method is called a trust-region method.

Standard first-order convergence results need an objective bounded below, appropriate smoothness on the relevant region, bounded model Hessians, a fraction-of-Cauchy-decrease requirement, and compatible acceptance and radius updates. Under such hypotheses one can obtain stationarity conclusions; stronger second-order results require stronger curvature treatment. Keep this separate from local Newton-like speed near a nondegenerate minimum. A method can be reliable far away and fast nearby, but those are different pieces of analysis.

Work it through

Test a quadratic against a quartic

For $f(x)=(x^2-1)^2$ at x=2, use its exact quadratic Taylor model and radius Δ=0.25. Compute the global subproblem step and the agreement ratio.

The current value is nine, the gradient is $4x(x^2-1)=24$ , and the second derivative is $12x^2-4=44$ . The unconstrained model minimizer is −24/44=−6/11, outside the interval [−0.25,0.25]. Since the model is strictly convex, the constrained minimizer is p=−0.25.
The prediction is $-24p-22p^2=6-1.375=4.625=1184/256$ . The proposed point is 7/4, where the true value is $(49/16-1)^2=1089/256$ . The actual reduction is $2304/256-1089/256=1215/256$ .
The ratio is $1215/1184\approx1.02618$ . Under the illustrative rule accepting above 0.1, accept this trial. Since the step is on the radius and agreement exceeds 0.75, expansion is a permissible next-radius decision, not an optimality certificate.

The result

The quartic improved slightly more than the model predicted. A ratio greater than one is entirely consistent with a successful trust-region trial.

The living notebook

Explore the model

Interactive lab

Interactive lab · function

A model whose agreement is exact

Pause, Reset, and set a=1 and x=1.5. Predict the tangent slope and value, then compare both readouts. This fixed quadratic has an exact second-order Taylor model, so any nonzero predicted reduction would match actual reduction. It does not expose a trust radius or implement the quartic objective; use the worked example to see imperfect model agreement.

y = ax²TangentSigned integral

y at chosen x: 0.608
Tangent slope · 2ax: 1.35
Signed area · ax³/3: 0.182

Coefficient a0.75Position x0.9

t = 0 s

This lab uses only y = ax². Playback traces the curve within the fixed integration interval from 0 to x; it does not estimate numerical error or change the chosen point. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forAn exact quadratic hides model error; nonlinear objectives require an actual-versus-predicted reduction test.

Pause & reason

Check your understanding

Interactive checks need JavaScript. You can still read the explanation.

Read the checkpoint explanation

The ratio is one divided by four. It exceeds the acceptance threshold and equals, rather than falls below, the strict shrink threshold. Radius decisions depend on the precisely stated inequalities.

Your turn

Try it yourself

Minimize $m(p)=-p^2/2$ over |p|≤2. Give all global minimizers and a shifted-Hessian certificate for one of them.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

The most negative value occurs where the magnitude is largest. The gradient term is zero, so do not rely on a Cauchy step alone.

Compare with the solution

Both p=2 and p=−2 give value −2 and are global minimizers; every interior magnitude gives a value greater than −2. Here B=−1 and g=0. For p=2 choose λ=1, so B+λ=0 is positive semidefinite, $(B+\lambda)p=0=-g$ , the radius is active, and complementarity holds. The unconstrained stationary point p=0 is instead the model's maximum, illustrating why the shifted matrix condition matters.

Keep the idea

Take it with you

A radius makes an indefinite quadratic subproblem bounded and meaningful.
Agreement ratios require a positive prediction and a separate true-objective evaluation.
Approximate subproblem quality and update rules belong in convergence assumptions.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.