Descent and Globalization

Define Test Function and Derivatives¶

Let’s get started by defining a test function we will use throughout the notebook.

Consider a scalar function $f(x): \mathbb{R} \rightarrow \mathbb{R}$ to allow for easier visualization. Let

Geometric Insights into Newton Steps¶

Motivation¶

We can interpret Newton-type methods for unconstrained optimization as root finding of $\nabla f(\mathbf{x}) = \mathbf{0}$.

At iteration $k$, we assemble an approximation to $f(\mathbf{x})$ using a Taylor series expansion:

Set the gradient of this quadratic model to zero, $\nabla f(\mathbf{x}^k)+\mathbf{B}^k\mathbf{p}^k=\mathbf{0}$. For nonsingular $\mathbf{B}^k$, the resulting linear solve gives:

The choice of $\mathbf{B}^k$ determines the algorithm classification:

• Pure Newton Method, $\mathbf{B}^k = \nabla^2 f(\mathbf{x}^k)$

• Steepest Descent, $\mathbf{B}^k = \frac{1}{\alpha} \mathbf{I}$, where scalar $\alpha$ is sometimes known as the dampening factor

• Levenberg-Marquardt, $\mathbf{B}^k = \nabla^2 f(\mathbf{x}^k) + \delta \mathbf{I}$, where scalar $\delta$ is chosen to ensure $\mathbf{B}^k$ is positive definite.

• Broyden Methods, $\mathbf{B}^{k}$ is approximated using history of gradient evaluations, i.e., $\nabla f(\mathbf{x}^0), ... \nabla f(\mathbf{x}^k)$. We will study the SR1 and BFGS formulas in this family of methods.

This section explores how choosing $\mathbf{B}^k$ impacts the shape of the approximation and calculated step.

Compute and Plot Steps¶

Define a function that:

• Computes the i. Newton, ii. Levenberg-Marquardt and iii. Steepest Descent Step for a given starting point $x_0$

• Plots the step in terms of $f(x)$ and $f'(x)$

Consider $x_0 = -3$¶

Discussion

• In this case, do we expect the Newton and LM steps to be the same? Explain.

• Why does $f(x)$ increase with a steepest descent ($B^k = I$) step? I thought the main idea was that because $B^k$ is positive definite the step is in a descent direction!

Consider $x_0 = 0$¶

Discussion

• Why does $f(x)$ increase for all of the steps?

• Explain Newton-type method in the context of root finding for $\nabla f(x) = 0$ using the second plot.

Descent Properties¶

For $\mathbf{p}^k=-(\mathbf{B}^k)^{-1}\nabla f(\mathbf{x}^k)$, positive definiteness of $\mathbf{B}^k$ gives

Thus $\mathbf{p}^k$ is a descent direction whenever $\nabla f(\mathbf{x}^k)\ne\mathbf{0}$. A line search still chooses a step length that produces sufficient decrease. (Biegler, Eqs. 3.2--3.5, p. 41.)

Line Search¶

Excerpts from Section 3.4 in Biegler (2010).

Sufficient decrease and curvature conditions¶

Let $f\in C^1(D)$ on an open $D$, with $\mathbf{x}\in D$. At a fixed direction, define $\phi(\alpha)=f(\mathbf{x}+\alpha\mathbf{p})$ and $d=\phi'(0)=\nabla f(\mathbf{x})^T\mathbf{p}<0$. For fixed $0<\eta<1$, the Armijo condition for a feasible positive length $\alpha$ is

Here feasible means that the trial point lies in the objective domain. The condition requires a fraction of the initial linear-model decrease. Since $\phi(\alpha)-\phi(0)=\alpha d+o(\alpha)$, sufficiently short positive steps pass. It also permits unnecessarily small steps if the selection rule has no lower-size control.

Use $0<\eta<1/2$ for the Goldstein--Armijo conditions, which add the lower value bound:

Near zero the actual curve initially drops faster than the lower line, so that line excludes very short steps. For the profile $\phi(\alpha)-\phi(0)=-\alpha+\alpha^2/2$, $\eta=1/4$, the positive accepted interval is $[1/2,3/2]$.

Alternatively, choose $\eta<\zeta<1$. Wolfe combines Armijo with $\phi'(\alpha)\ge\zeta d$; strong Wolfe combines it with $|\phi'(\alpha)|\le\zeta|d|$. These require a directional derivative at a trial point. Goldstein uses function values. On a nonconvex ray the accepted set need not be one connected interval; the brackets in a particular figure describe that example.

Sources: Biegler (2010), Eqs. (3.31)--(3.34), pp. 47--48, with the ordering correction in the errata; Nocedal and Wright (2006), Eqs. (3.4), (3.6)--(3.7), (3.11), pp. 33--36. The general Armijo range is $0<\eta<1$; the strict $\eta<1/2$ choice also supplies the margin used in the unit-step result below.

Global convergence: gradient norms and the descent angle¶

Use Euclidean vector norms and their induced matrix norm. Consider a nonterminated sequence of descent steps, with $f$ bounded below and continuously differentiable, and its gradient uniformly Lipschitz on an open set containing the initial sublevel set. Lipschitz continuity means that some $L>0$ satisfies $\|\nabla f(\mathbf{u})-\nabla f(\mathbf{v})\|\le L\|\mathbf{u}-\mathbf{v}\|$ for every pair $\mathbf{u},\mathbf{v}$ in that open set. The acceptance parameters are fixed across the sequence. Write

For Goldstein--Armijo steps, the Zoutendijk sum is finite:

Here is the value-based proof. Fix an iteration and let $\beta$ be the first positive crossing of the Goldstein lower line before the accepted $\alpha$. Such a crossing exists because the curve starts below that line and the accepted value lies at or above it. On $[0,\beta]$, the curve lies below that line and therefore within the initial sublevel set. The gradient Lipschitz bound gives

At the crossing the left side is $(1-\eta)\beta d$, so

Armijo now supplies

Summing telescopes the actual decreases, and $f$ has a lower bound. The resulting sum is finite. Biegler’s mean-value proof uses a looser constant; the conclusion is the same. A Wolfe proof instead compares the directional derivatives at the two endpoints, yielding the analogous Zoutendijk result.

For $\mathbf{p}=-\mathbf{B}^{-1}\mathbf{g}$, with symmetric $\mathbf{B}\succ0$,

A uniform condition-number bound therefore forces $\|\mathbf{g}^k\|\to0$. Every accumulation point is stationary by gradient continuity. This does not by itself prove convergence of the whole iterate sequence, second-order conditions, or global optimality.

Sources: Biegler (2010), Theorem 3.3 and Eqs. (3.35)--(3.42), pp. 48--49; Nocedal and Wright (2006), Theorem 3.2, p. 38, for Wolfe steps. The eigenvalue/norm estimates have their existing home in Quasi-Newton Methods; they are applied here to the search angle.

Armijo backtracking and the actual visualization code¶

The standard reference procedure starts with a descent direction, tries $\alpha=1$, and, while Armijo fails, replaces $\alpha$ by $\rho_{\mathrm{ls}}\alpha$, with fixed $0<\rho_{\mathrm{ls}}<1$. It accepts the first trial that passes Armijo. The local argument above ensures finite termination along a descent ray. The previous rejected trial prevents uncontrolled overshrinking by the selection rule. If contractions vary, safeguard them between fixed positive lower and upper bounds below one.

This is not a rule to keep shrinking until both Goldstein bounds pass. For $\phi(\alpha)-\phi(0)=-\alpha+10\alpha^2$, $\eta=0.1$, Goldstein--Armijo accepts $[0.01,0.09]$. Halving from one first passes Armijo at $1/16$. A contraction by 10^-3 jumps to 0.001, below the Goldstein interval; every further contraction remains below it. To require Goldstein or Wolfe, use a suitable bracketing/selection method that can increase a trial when the lower-size test fails.

The function plot_alpha below is a graphical experiment: it evaluates a finite, linearly spaced grid, scans it downward, exempts its initial full trial from the Goldstein check, and reports a lower-bound failure on later trials. It is not the geometric backtracking algorithm just stated or a general Wolfe solver. Its deliberate ascent-direction and restricted-grid failures remain part of the exercise.

A condition-number bound alone is sufficient in the Goldstein theorem above, but is not sufficient for a unit-step-capped Armijo method: directions can shrink summably even with condition number one. A conventional global Armijo result also controls the scale of the direction, for example by uniform positive lower and upper eigenvalue bounds on $\mathbf{B}^k$.

Sources: Nocedal and Wright (2006), Algorithm 3.1 and discussion, p. 37; Dennis and Schnabel (1996), Algorithm 6.3.5, p. 126; Biegler (2010), Algorithm 3.2 and the additional Goldstein discussion, p. 50. Safeguarded quadratic/cubic interpolation is detailed below.

Recovery of the fast local rate¶

Suppose $f\in C^2(D)$ on an open neighborhood $D$ of the limit, and a nonterminated descent sequence with nonzero directions converges to $\mathbf{x}^*$, $\nabla f(\mathbf{x}^*)=\mathbf{0}$, and $\nabla^2 f(\mathbf{x}^*)\succ0$. Use fixed Wolfe parameters $0<\eta<1/2$ and $\eta<\zeta<1$. Let the directions satisfy

For Newton-type solves this is the Dennis--Moré directional condition. Nondegeneracy and the residual condition imply $\mathbf{p}^k\to0$. They also give $d_k=(\mathbf{g}^k)^T\mathbf{p}^k\le-c\|\mathbf{p}^k\|^2$ eventually, for some $c>0$.

Taylor expansion and the small residual give

Thus Armijo has negative slack $(1/2-\eta)d_k+o(\|\mathbf{p}^k\|^2)$ when $0<\eta<1/2$; the curvature condition also passes for fixed $\eta<\zeta<1$. Unit steps are eventually admissible. The search must try and accept them to obtain the superlinear rate. Admissibility alone does not force that selection.

The endpoint $\eta=1/2$ has no Taylor-error margin. For $f(x)=x^2+x^3$, $x<0$ near zero, exact Newton gives $p=-(2x+3x^2)/(2+6x)$. Its unit step fails endpoint Armijo, but its half step satisfies Wolfe with $\zeta=0.9$ for sufficiently small negative $x$. The half-step recurrence is

It stays negative near zero and converges only linearly despite zero Newton directional residual. We therefore use the conservative strict parameter bound in the handout/reference. The whole-iterate versus directional-error equivalence has its existing full proof in Quasi-Newton Methods; the local Newton error proof is in Newton Methods.

Sources: Nocedal and Wright (2006), Theorems 3.6--3.7, pp. 46--47; Biegler (2010), Theorem 3.4, p. 50, with nondegeneracy explicit. The endpoint example is an independently derived illustration.

Visualization Code¶

The line search conditions, as one picture¶

This is Biegler Figure 3.2 for our test function. It is rendered from figures/plots/line-search-conditions.py and is the same image printed in the course pack, so what you annotate in lecture and what you see here cannot drift apart.

The cells below are the live version: plot_alpha redraws this for any $x^k$, any algorithm and any $\alpha_{\max}$, so you can explore cases the static figure does not cover -- including one where the line search fails.

Goal: Visualize Armijo and Goldstein conditions for an example.

Newton Step, $x^k = -3$¶

Discussion

• Why did the backtracking line search stop at $\alpha^k =$ alpha_max?

• Is it possible to find a larger improvement in $f(x)$ with $\alpha^k > 1$?

Steepest Descent Step, $x^k = -3$¶

Discussion

• Why did the line search stop where the Armijo conditions are satisfied?

• Why not further decrease $\alpha^k$ to achieve a greater improvement in the objective?

Newton Step, $x^k = 0$¶

Discussion

• Why does the line search fail?

• How could we modify Newton’s method to improve robustness?

Steepest Descent Step, $x^k = 0$¶

Discussion

• How does the region where the Armijo and Goldstein conditions are satisfied change for different values of eta_ls?

Trust Regions¶

Excerpts from Section 3.5 in Biegler (2010).

Main Idea and General Algorithm¶

At iteration $k$, with $\Delta^k>0$, the closed ball is $\overline B(0,\Delta^k)=\{\mathbf{p}\in\mathbb R^n:\|\mathbf p\|\le\Delta^k\}$. A line search instead restricts its nonzero fixed direction to $\{\alpha\mathbf p:\alpha>0\}$. With symmetric $\mathbf{B}^k$, use the Euclidean-ball subproblem

The constant $f(\mathbf{x}^k)$ is omitted because it changes neither the minimizer nor the predicted reduction. Weierstrass states that a continuous function on a nonempty compact set attains its minimum and maximum; its existing existence discussion is in Unconstrained Optimality Conditions. A continuous quadratic therefore attains a minimum on this compact ball even when $\mathbf{B}^k$ is indefinite.

The radius is updated by comparing actual objective reduction with predicted model reduction. Source: Biegler (2010), Eq. (3.49), p. 53; Nocedal and Wright (2006), pp. 68--70.

Choose $0<\kappa_1<\kappa_2<1$, $0<\gamma<\min\{1/4,\kappa_1\}$, and $0<\Delta^0\le\bar\Delta$. Evaluate the current gradient before testing it; a small gradient reports a stationary candidate. For a nonterminated iteration:

1. Compute a feasible, sufficiently model-reducing step $\mathbf{p}^k$. Report stagnation together with the gradient norm if its movement is too small.

2. Compute $\operatorname{pred}=m^k(0)-m^k(\mathbf{p}^k)>0$. A nonpositive prediction signals a failed subproblem step; do not form a meaningless ratio.

3. Evaluate $\operatorname{ared}=f(\mathbf{x}^k)-f(\mathbf{x}^k+\mathbf{p}^k)$ and $\rho^k=\operatorname{ared}/\operatorname{pred}$.

4. If $\rho^k<\kappa_1$, set $\Delta^{k+1}=\kappa_1\|\mathbf{p}^k\|$. If $\rho^k>\kappa_2$ and the step reaches the boundary, set $\Delta^{k+1}=\min(2\Delta^k,\bar\Delta)$. Otherwise retain the radius.

5. Accept the trial iterate only if $\rho^k>\gamma$; otherwise retain the old iterate and recompute a step with the new radius.

Acceptance and radius change have different thresholds. With prediction 10, actual decrease 1.5, $\gamma=0.1$, $\kappa_1=0.25$, and step norm 2, the ratio is 0.15: accept the step but shrink the next radius to 0.5. A good interior step need not enlarge the radius because the current bound did not restrict it.

Source: Biegler (2010), Algorithm 3.3, p. 53, adapted to test evaluated quantities and report failed diagnostics. Nocedal and Wright’s Algorithm 4.1, p. 69, uses the closely related shrink rule $\Delta^{k+1}=\Delta^k/4$, rather than Biegler’s step-norm rule; do not silently mix the two.

Why order the thresholds? Every rejected trial has $\rho\le\gamma<\kappa_1$, so it triggers a radius decrease. The strict inequality also handles $\rho=\gamma$. Biegler’s usual choice $\kappa_1=1/4$ with $0<\gamma<1/4$ has this property. His more general parameter list in Algorithm 3.3 does not explicitly state the ordering; the following independently derived example shows why that broader list needs qualification for this update rule.

Consider $f(x)=19x^2/20$, starting at $x=1$, with exact gradient $g=19/10$, model curvature $B=1$, and radius $\Delta=2$. The exact model minimizer is the interior step $p=-19/10$, giving

Choose $\gamma=1/5$, $\kappa_1=1/20$, and $\kappa_2=3/4$. The trial is rejected because $\rho<\gamma$, but the radius is retained because $\rho\ge\kappa_1$ and the expansion condition fails. Reusing the same model repeats the identical rejected step indefinitely, with gradient $19/10$. The objective is smooth and bounded below, the model matrices are bounded, and the exact step gives sufficient model reduction. Thus those assumptions alone do not establish stationarity when the thresholds allow rejected steps to keep the radius. This example motivates the strict ordering used above; it does not alter the numerical activity’s default parameters.

Trust Region Variations¶

The Levenberg--Marquardt path varies a multiplier continuously; dogleg uses straight segments connecting the origin, Cauchy step, and Newton step.

$\mathbf{p}^C$: Cauchy step

$\mathbf{p}^N$: Newton step

Levenberg-Marquardt¶

Let $\mathbf B=\mathbf B^T\in\mathbb R^{n\times n}$, $\mathbf g\in\mathbb R^n$, and $\Delta>0$. A feasible vector $\mathbf{p}^*$ is a global minimum of the quadratic model over the ball if and only if some $\delta\ge0$ satisfies

Feasibility $\|\mathbf{p}^*\|\le\Delta$ is essential. If $\delta>0$, the boundary is active. The converse fails: a Newton minimum may lie exactly on the boundary with $\delta=0$. At a singular shifted matrix, use the linear system and an appropriate null-space component, not an undefined inverse.

For sufficiency, put $\mathbf{h}=\mathbf{v}-\mathbf{p}^*$, where $\mathbf{v}$ is any feasible comparison point. Expanding the quadratic and using stationarity yields

The first term is nonnegative by positive semidefiniteness. The second is zero if $\delta=0$; otherwise complementarity puts the candidate on the boundary and feasibility bounds the comparison norm. This certifies the model minimum, not a global minimum of the actual objective. The converse characterization is proved in Nocedal and Wright, pp. 89--91.

Sources: Nocedal and Wright (2006), Theorem 4.1, p. 70; Biegler (2010), Theorem 3.6 and Eq. (3.50), p. 54, with the missing feasibility condition supplied.

Powell Dogleg¶

For $\mathbf{g}\ne\mathbf{0}$, the Cauchy point minimizes the quadratic on the feasible steepest-descent ray. Write $q=\mathbf{g}^T\mathbf{B}\mathbf{g}$. Then

If $q\le0$, the ray model keeps decreasing, so its best feasible point is the boundary. With $q>0$, the unconstrained ray minimum is used only when it fits. Define that untruncated vector as $\mathbf{p}^U=-\|\mathbf{g}\|^2\mathbf{g}/q$.

Biegler Eq. (3.52) calls the untruncated positive-curvature vector a Cauchy step and clips it in the later dogleg rule. Nocedal and Wright’s Cauchy point is already clipped. The formulas above distinguish these roles explicitly.

Sources: Biegler (2010), Eq. (3.52), p. 54; Nocedal and Wright (2006), Eqs. (4.11)--(4.12), p. 72.

For $\mathbf{B}\succ0$, calculate $\mathbf{p}^N=-\mathbf{B}^{-1}\mathbf{g}$ by a solve, and let $\mathbf{p}^U$ be the untruncated ray minimum:

• If $\|\mathbf{p}^N\|\le\Delta$, take the full model minimum.

• Otherwise, if $\Delta\le\|\mathbf{p}^U\|$, take $\Delta\mathbf{p}^U/\|\mathbf{p}^U\|$, the first-leg boundary point.

• Otherwise take $\mathbf{p}^U+\theta\mathbf{d}$, where $\mathbf{d}=\mathbf{p}^N-\mathbf{p}^U$ and the second segment intersects the boundary.

The intermediate condition gives $0<\theta<1$. Expanding the norm constraint produces

The applicable root is

This avoids a scalar iteration. In the shared figure, $\mathbf{B}=\operatorname{diag}(1,10)$, $\mathbf{g}=(-2,-6)^T$, and $\Delta=1.5$. The inputs give $\mathbf{p}^N=(2,0.6)^T$, $\mathbf{p}^U=\mathbf{p}^C=(20/91,60/91)^T$, and $\theta\approx0.6434961$. The dogleg boundary point and the exact L--M boundary point generally differ; the former approximates the full subproblem.

Both norm growth and model decrease along this path rely on positive definiteness. An indefinite exact Hessian needs a method that can use negative curvature, as detailed in the hard-case reference below.

Sources: Biegler (2010), §3.5.1 and Figure 3.4, p. 55; Nocedal and Wright (2006), Eqs. (4.15)--(4.16), p. 74, and Lemma 4.2, p. 75. The generated picture and numerical implementation have one source in the course figure pipeline.

Reference: monotone decrease without stationarity¶

For $f(x)=x^2$, $x^0=2$, the sequence $x^k=(-1)^k(1+2^{-k})$ has decreasing objective values but two limit points, -1 and 1. Its displacement stays large while the actual decrease tends to zero. Let $p_k=x^{k+1}-x^k$ and take $\alpha_k=1$. These are descent directions, but their predicted linear decrease has a nonzero asymptotic magnitude. Thus any fixed positive Armijo fraction eventually rejects them.

For $x^k=1+2^{-k}$, use $p_k=-1$ and $\alpha_k=2^{-(k+1)}$. Direct subtraction verifies the recurrence, and the geometric series totals one. The iterates reach the nonstationary limit 1. Actual decrease relative to the initial directional derivative tends to one, so Armijo permits these arbitrarily small steps, while Goldstein or Wolfe eventually rejects them.

The second exponent corrects the inconsistent printed step sequence in Dennis and Schnabel, p. 118. It follows from subtracting consecutive displayed iterates, rather than adopting an index convention silently.

Sources: Dennis and Schnabel (1996), §6.3 and Figure 6.3.2, pp. 117--118; Biegler (2010), §3.4, pp. 47--48.

Reference: safeguarded interpolation for backtracking¶

Write $\phi_0=\phi(0)$, $d=\phi'(0)<0$, and suppose the positive trial $a_1$ fails Armijo. Fit

If $A>0$, its minimizer is $a_q=-d/(2A)$. This uses only the initial value/slope and one rejected value. If the fit has no useful positive minimum, use a contraction instead.

After two distinct positive rejected trials, define

The cubic fit $q_3(a)=\phi_0+da+Aa^2+Ba^3$ satisfies both values. Solve $d+2Aa+3Ba^2=0$, selecting a positive stationary point with positive second derivative. If $B=0$, use the quadratic formula above; a negative discriminant or unusable minimum calls for fallback.

Do not accept a point merely because it minimizes an interpolant. Safeguard the next trial, for example within $[0.1a_{\mathrm{current}},0.5a_{\mathrm{current}}]$, evaluate the actual objective there, and test Armijo again. Safeguards avoid almost unchanged trials and extremely small jumps caused by a poor fit. The two distinct trial values are essential; equal nodes do not define this cubic fit.

A Goldstein/Wolfe search has different lower-size logic: a trial that is too short must be increased or bracketed, not contracted forever. The reference backtracking experiment in the handout with $-a+10a^2$ demonstrates this distinction.

Sources: Dennis and Schnabel (1996), §6.3.2, pp. 126--128; Biegler (2010), Algorithm 3.2, p. 50, and Exercise 4, p. 61; Nocedal and Wright (2006), §3.5, pp. 56--60.

Reference: solving the Levenberg--Marquardt secular equation¶

First suppose $\mathbf{B}\succ0$, $\mathbf{g}\ne\mathbf{0}$, and the Newton model minimum lies outside the radius. For $\delta\ge0$, solve

The norm $r(\delta)=\|\mathbf{p}(\delta)\|$ decreases strictly from its outside value to zero. Solve $r(\delta)=\Delta$, preferably via the reciprocal secular function

Differentiating the solve gives $\mathbf{p}'=-(\mathbf{B}+\delta\mathbf{I})^{-1}\mathbf{p}$. A second solve $(\mathbf{B}+\delta\mathbf{I})\mathbf{q}=\mathbf{p}$ yields

The same Cholesky factor can serve both solves. Establish a bracket with $h(\delta_{\mathrm{lo}})<0<h(\delta_{\mathrm{hi}})$, increasing the upper trial until it is large enough. A Newton proposal $\delta-h/h'$ must remain in the admissible bracket; otherwise use a bracketed fallback. Stop at the accuracy appropriate for the model-reduction/feasibility requirement, rather than forcing unnecessary multiplier digits.

The reciprocal form is often nearly linear in the large-shift regime because $r(\delta)\sim\|\mathbf{g}\|/\delta$. Biegler’s two-or-three-iteration observation concerns a useful approximate root; it is not an iteration bound for every model.

For an indefinite matrix, the positive-definite solve domain starts above $\max\{0,-\lambda_{\min}\}$. A root may fail to exist in that open domain: the hard case requires the singular endpoint and a null-space correction. Repeatedly increasing a shift cannot repair that missing component.

Sources: Biegler (2010), Eq. (3.51), p. 54; Nocedal and Wright (2006), §4.3 and Algorithm 4.3, pp. 85--87.

Reference: Cauchy reduction, stationarity, and collapsing radii¶

For symmetric $\mathbf{B}\ne0$, $\mathbf{g}\ne0$, use Euclidean/induced norms and let

This is a feasible ray trial. The quadratic-form norm bound gives

The Cauchy point minimizes over this ray, so its reduction is at least the trial reduction. Any step at least as good as Cauchy therefore supplies

If $\mathbf{B}=0$, the feasible boundary ray gives reduction $\Delta\|\mathbf{g}\|$ directly; do not divide by its zero norm. If $\mathbf{g}=0$, first-order stopping/classification is separate, and an indefinite model may still have a negative-curvature reduction.

Exact model minima satisfy the bound. Positive-definite dogleg steps do too, because the chosen point is at least as good as the feasible Cauchy point. A fixed positive fraction of this bound is enough in the general convergence framework.

With bounded model norms, an objective bounded below on the initial sublevel set and globally Lipschitz gradient, the standard trust-region iteration stated above with the ordered thresholds $0<\gamma<\min\{1/4,\kappa_1\}$ and $0<\kappa_1<\kappa_2<1$ and feasible steps satisfying a fixed positive fraction of the displayed Cauchy reduction bound gives $\|\nabla f(\mathbf{x}^k)\|\to0$. This is a first-order conclusion; positive-definite approximations do not classify the true limiting Hessian.

Under that Lipschitz hypothesis, for an exact gradient and $\|\mathbf{B}\|\le\beta$, the model mismatch obeys

If $\|\mathbf{g}\|\ge\varepsilon>0$ and the radius is small enough for the radius branch of the sufficient-reduction bound, then

Thus an accurate smooth model becomes relatively reliable at sufficiently small radii while the gradient stays large. Persistent collapse suggests inaccurate/noisy derivatives or values, a failed subproblem solve, or a numerically meaningless ratio when prediction is tiny. The ideal smooth proof does not apply unchanged to such errors. Stopping on a tiny radius or step should report the gradient norm, not label a minimum.

Near a nondegenerate minimum, fast local trust-region behavior requires stronger assumptions. Biegler Theorem 3.11 assumes Lipschitz Hessian, convergence to a point satisfying second-order sufficiency, model matrices converging to the limiting Hessian, and asymptotically exact subproblem solves with at least Cauchy reduction. Under that framework the radius bound eventually becomes inactive; it is not an unconditional noncollapse promise.

Sources: Nocedal and Wright (2006), Lemma 4.3, p. 78, and §4.2, pp. 77--84; Biegler (2010), Theorems 3.7--3.8, pp. 55--56, and Theorem 3.11, p. 58.

Reference: the hard case and a singular shifted system¶

Suppose $\mathbf B$ is symmetric, $\lambda_{\min}<0$, and let $\mathbf{B}=\mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^T$. In the positive-definite shifted domain,

If the gradient has a component in the most-negative eigenspace, the norm can grow without bound as the shift approaches its lower endpoint. If the gradient is orthogonal to that entire eigenspace, the limit can be finite. Orthogonality alone is not enough to say every radius is unreachable: compare the limiting norm with the required radius. The hard case arises when the boundary cannot be reached by a nonsingular shifted solve.

At $\delta=-\lambda_{\min}$, solve for the component perpendicular to the singular eigenspace and add a vector in that null space. For a simple most-negative eigenvalue, one may write

Here the dagger is the pseudoinverse, the base solution is perpendicular to the null space, and $\tau$ is chosen to reach the radius. There is no ordinary inverse at that singular endpoint. For repeated most-negative eigenvalues, use the corresponding null space, not an arbitrarily chosen unrelated eigenvector.

For $\mathbf{B}=\operatorname{diag}(-1,2)$, $\mathbf{g}=(0,1)^T$, $\Delta=1$, nonsingular shifts give $\mathbf{p}(\delta)=(0,-1/(2+\delta))^T$, whose limiting norm is $1/3$. At $\delta=1$, the base solution is $(0,-1/3)^T$. The two boundary solutions are

They satisfy feasibility, shifted stationarity, complementarity and positive semidefiniteness. The added negative-curvature direction improves the base model value from $-2/9$ to $-2/3$.

A pure positive-definite correction may suppress this useful curvature. For larger problems, truncated conjugate-gradient trust-region methods detect nonpositive curvature or a boundary crossing and truncate there, avoiding a full eigenvalue decomposition. This is a different mechanism from using an arbitrary indefinite Newton direction in a line search.

Sources: Nocedal and Wright (2006), §4.3, pp. 87--88, Eq. (4.45), and §7.1, pp. 169--175; Biegler (2010), Eqs. (3.54)--(3.55) and Algorithm 3.4, pp. 56--57.