Radius mechanisms

RadiusRule

Abstract supertype for trust-region radius update mechanisms.

A concrete MyRule <: RadiusRule must implement

initial_radius(rule, Δ0, g_norm) -> Float64
update_radius!(rule, Δ, ρ, accepted, η1, η2,
               s_norm, g_norm_old, g_norm_new) -> Float64

and, if it carries mutable state,

reset_rule!(rule) -> nothing

Arguments of update_radius!

• Δ: the current radius Δ_k.
• ρ: the ratio that drives the scaling. This is ρk for ordinary rules and the retrospective ratio ρ̃k for those declaring needs_retrospective. On a rejected step ρ̃ is undefined and the solver passes ρ_k, so a retrospective rule must branch on accepted before it compares ρ to its own thresholds.
• accepted: whether the step was taken, i.e. ρ_k ≥ η. Decided by the solver with the acceptance threshold η, which the rule never sees.
• η1, η2: scaling thresholds, η ≤ η1 ≤ η2 < 1.
• s_norm: ‖s_k‖, the realised trial step length.
• g_norm_old: the criticality measure at the current iterate, before the accept/reject decision. Used by RDFO. Under a SecondOrder wrapper this is τk, not ‖gk‖.
• g_norm_new: the criticality measure after it. Used by rules of the form Δ = μ·crit (RGrad and relatives). Equal to g_norm_old on a rejected step.

Every rule must contract when the iteration is unsuccessful — Δ_{k+1} ≤ γ2Δ_k whenever ρ_k < η — or it forfeits weak admissibility, and, since a rejected step leaves both the model and the iterate unchanged, a rule that returns Δ_{k+1} = Δ_k there will re-solve an identical subproblem for ever. Because η ≤ η1, branching on ρ < η1 is enough to guarantee it, which is why most rules can ignore accepted.

The test suite asserts this for every concrete rule; see test/test_rules.jl.

RDelta(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, Δmin = 0.0, Δmax = Inf)

Classical three-case multiplicative update (Conn, Gould & Toint §6.1):

ρ < η1       →  Δ ← γ1 Δ
η1 ≤ ρ < η2  →  Δ ← γ2 Δ
ρ ≥ η2       →  Δ ← γ3 Δ

The branches are read off ρ alone, never off acceptance, so with η < η1 this rule contracts on iterations whose step was nonetheless taken — which is the whole content of decoupling the two thresholds.

Criticality-blind: the radius depends on its own history and on ρ, never on ‖g‖. Consequently liminf Δ_k > 0, the trust-region constraint eventually stops binding with no side condition, and the radius carries no asymptotic information about criticality.

RStep(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, Δmin = 1e-14, Δmax = Inf,
        contract_on_step = true)

Radius proportional to the realised step:

ρ < η1       →  Δ ← γ1 ‖s_k‖     (or γ1 Δ_k, see `contract_on_step`)
η1 ≤ ρ < η2  →  Δ ← γ2 ‖s_k‖
ρ ≥ η2       →  Δ ← γ3 ‖s_k‖

contract_on_step = true is the rule as stated in Part I, in which all three branches are anchored to ‖s_k‖. false gives the variant that contracts on the previous radius instead, which is milder whenever the subsolver returned an interior step: γ1‖s_k‖ ≤ γ1Δ_k. Both satisfy the contraction condition; they differ in how fast the radius falls after a rejection, so which one is in force should be reported rather than left implicit.

Requires η1 > 0: at η1 = 0 the aggressive branch is unreachable for every ρ ≥ 0 and the lower-bound constant of Part I degenerates.

RDFO(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, ζ = 1.0, Δmin = 0.0, Δmax = Inf)

DFO-like update comparing the radius to the criticality measure:

ρ < η1                 →  Δ ← γ1 Δ
ρ ≥ η1 and Δ > ζ·crit  →  Δ ← γ2 Δ     (radius large relative to criticality)
ρ ≥ η1 and Δ ≤ ζ·crit  →  Δ ← γ3 Δ     (room to expand)

Uses the criticality measure before the accept/reject decision — ‖gk‖ for the bare rule, τk under a SecondOrder wrapper.

Drives Δ_k → 0, so eventual inactivity of the trust region requires ζ > κ̄ = 8/λ*_min(∇²f(x*)). That constant is a property of the solution and cannot be checked in advance; below the threshold the constraint can bind at every iteration, the method converges only linearly, and no first-order diagnostic shows anything wrong. Choose ζ generously: on a heterogeneous test set an over-large ζ costs nothing, while an over-small one costs solved problems.

RGrad(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, μ = 1.0, half_test = true,
        Δmin = 0.0, Δmax = Inf)

Gradient-scaled radius Δ_k = μ_k ‖g_k‖ with an unbounded multiplier:

ρ < η1                     →  μ ← γ1 μ
η1 ≤ ρ < η2                →  μ ← γ2 μ
ρ ≥ η2 and ‖s_k‖ > ½Δ_k    →  μ ← γ3 μ
otherwise                  →  μ unchanged

Here μ_k is the radius-to-criticality ratio Δ_k/‖g_k‖, so the rule performs a search for the inactivity threshold κ̄ without knowing it: μ climbs on very successful iterations that use the region, contracts otherwise, and stops climbing once the region stops binding. Because μ is uncapped it crosses any threshold eventually, which makes eventual inactivity unconditional — the only rule in the survey for which this holds without a hypothesis on an unknowable constant.

The middle branch is not decoration: it is what keeps μ from ratcheting upward on mediocre iterations, and the four-branch form is the one the boundedness argument for μ is stated about.

The guard ‖s_k‖ > ½Δ_k is not cosmetic either. It is what converts "μ grows" into "‖sk‖ is comparable to μk‖gk‖", which is the step that makes the boundedness argument work. Any constant in (0,1) serves; `halftest = false` disables the guard, which breaks that argument.

See RGradCapped for the bounded variant required by the global asymptotic theory (Δ_k → 0 needs μ_k ≤ μ̄).

RGradCapped(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, μ = 1.0, μ_max = 1.0,
              half_test = true, Δmin = 0.0, Δmax = Inf)

RGrad with an explicit cap μ_k ≤ μ_max.

The cap is what the asymptotic results requiring Δ_k → 0 assume, and it is not free. Eventual inactivity now needs μ_max > κ̄ = 8/λ*_min; below that the trust region binds at every iteration and the method degrades to linear convergence while ρ stays healthy and ‖g‖ keeps falling.

With a truncated-CG subsolver a small μ_max is worse than slow. The first CG iterate lies along -g, so if the region is small enough that CG truncates there, the returned step is exactly the Cauchy point and the model Hessian stops influencing the search direction: the method has silently become gradient descent, and its limit can be a degenerate critical point that is not a minimiser. cg_step_info reports it.

RAdaptiveStep(; γ1, γ2, γ3, λ1, λ2, Δmin = 1e-14, Δmax = Inf)

Hei (2003) step-anchored rule with a smooth factor:

Δ_{k+1} = R_{η1}(ρ_k) · ‖s_k‖

The switch point of R is the scaling threshold η1 supplied by the solver, not a constant of the rule, so the family stays comparable with the three-case rules under the same (η, η1, η2).

Step-anchored like RStep, so the same Δmin guard applies and for the same reason, and η1 > 0 is required for the same reason.

RAdaptiveGrad(; μ = 1.0, γ1, γ2, γ3, λ1, λ2, Δmin = 0.0, Δmax = Inf)

Hei factor driving a Fan-Yuan multiplier, accumulated:

μ_{k+1} = μ_k · R_{η1}(ρ_k),    Δ_{k+1} = μ_{k+1} · crit_{k+1}

Combines the smooth factor of the Hei family with the ratio-tracking of RGrad: μ is again the radius-to-criticality ratio, but it is scaled continuously in ρ rather than by one of three constants. Because the scaling is multiplicative and R ≤ γ2 < 1 below η1, contraction on unsuccessful iterations holds without a guard.

Since μ accumulates, it is unbounded above and the rule inherits RGrad's unconditional eventual inactivity.

RAdaptiveGradCapped(; μ = 1.0, μ_max = 1.0, γ1, γ2, γ3, M, λ1, λ2,
                      Δmin = 0.0, Δmax = Inf)

RAdaptiveGrad with the cap μ_k ≤ μ_max, i.e. RAdaptiveGrad(ω, μ̄) of the appendix:

ρ_k ≥ η2 and ‖s_k‖ ≤ ½Δ_k  →  μ unchanged
otherwise                   →  μ ← min(R_{η1}(ρ_k) μ_k, μ_max)

The cap is what the asymptotic results needing Δ_k → 0 assume, and it carries the same cost as it does for RGradCapped: eventual inactivity now requires μ_max > κ̄, and below that the region binds at every iteration while ρ stays healthy and ‖g‖ keeps falling.

μ0 is clamped to μ_max when the caller asks for more, so a sweep over the cap at fixed μ0 stays constructible below μ0.

RDeltaStep(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, Δmin = 0.0, Δmax = Inf)

R-delta-step of Part I: the classical rule with an aggressive decrease taken from the step rather than from the radius.

ρ_k < η1        →  Δ ← γ1 ‖s_k‖
η1 ≤ ρ_k < η2   →  Δ ← γ2 Δ_k
ρ_k ≥ η2        →  Δ ← γ3 Δ_k

It is the mirror image of RStep, which rebuilds the radius from the step on every branch. Here only the unsuccessful branch does, so the radius keeps its own history while a rejected step is punished by how short it was. That matters when the model is poor but the region is not: ‖s_k‖ can be far below Δ_k, and contracting from Δ_k would leave the region far larger than anything the model has been trusted to do.

Unlike every other rule in the package this one admits γ2 = 1, which the appendix states explicitly: the middle branch then holds the radius rather than shrinking it, and admissibility still follows from the first branch because γ1 < 1 and η ≤ η1.

RRTR(; γ1 = 0.0625, γ2 = 0.25, γ3 = 2.5, η̃₁ = 0.05, η̃₂ = 0.9,
       Δmin = 1e-14, Δmax = Inf)

Retrospective update of Bastin, Malmedy, Mouffe, Toint & Tomanos (2010).

The radius for iteration k+1 is chosen from how well the new model m_{k+1} retrospectively predicts f at the previous iterate, rather than from how well m_k predicted f at the new one. Acceptance is still decided by ρ and η; only the scaling uses ρ̃.

On a rejected step (accepted = false), ρ̃ is undefined — it judges a step that was not taken — and the solver passes ρ instead, so the rule branches on the flag first and uses only the sign of the ratio, as the source rule does:

rejected, ρ ≥ 0     →  Δ ← γ2 ‖s_k‖
rejected, ρ < 0     →  Δ ← min(γ2‖s_k‖, γ1Δ_k)

and on an accepted step

ρ̃ ≥ η̃₂             →  Δ ← max(γ3‖s_k‖, Δ_k)
η̃₁ ≤ ρ̃ < η̃₂        →  Δ ← Δ_k
0 ≤ ρ̃ < η̃₁         →  Δ ← γ2‖s_k‖
ρ̃ < 0              →  Δ ← min(γ2‖s_k‖, γ1Δ_k)

The safeguard factor θ_{k-1} of Part I is taken as 0, so max[γ1, θ] = γ1.

Branching on accepted is mandatory, not defensive. Comparing a classical ρ against the retrospective thresholds would leave the radius untouched for ρ ∈ [η̃₁, η) — an unsuccessful iteration with no contraction, which forfeits weak admissibility and, since a rejected step changes neither the model nor the iterate, reproduces the same subproblem for ever.

The first accepted branch is the interesting one: max(γ3‖s_k‖, Δ_k) is simultaneously step-driven and non-decreasing, which is what lets this rule secure eventual inactivity from a consequence of the standing assumptions (ρ̃ → 1) rather than from a condition on a user parameter, as RDFO needs. The price is structural: ρ̃ → 1 requires either the secant condition on the model, or asymptotic second-order coherence plus a quadratic model decrease.

RRTRGrad(; γ1 = 0.25, γ2 = 0.5, γ3 = 2.0, μ = 1.0, μ_max = Inf,
           η̃₁ = 0.05, η̃₂ = 0.9, half_test = true, Δmin = 0.0, Δmax = Inf)

Retrospective gradient-scaled rule of Fan, Pan & Song (2016):

μ_{k+1} = γ1 μ_k               if the step was rejected, or ρ̃ < η̃₁
          γ2 μ_k               if η̃₁ ≤ ρ̃ < η̃₂
          min{γ3 μ_k, μ_max}   if ρ̃ ≥ η̃₂ and ‖s_k‖ > ½Δ_k
          μ_k                  otherwise
Δ_{k+1} = μ_{k+1} · crit_{k+1}

Structurally RGrad with ρ replaced by ρ̃, intermediate contraction by γ2 included, and with the cap μ_max of RGradCapped: the default μ_max = Inf leaves μ uncapped, and the initial μ is clamped to μ_max. half_test = false drops the ½Δ test. The argument that μ cannot diverge is ratio-agnostic — it uses only the monotone decrease of f, the local quadratic bounds, and the ½Δ test — so it transfers unchanged from RGrad to this rule. All the ratio has to supply is convergence to 1.

The explicit rejected branch matters for the same reason as in RRTR: on a rejected step crit_{k+1} = crit_k, so leaving μ untouched returns exactly Δ_k and the solver cannot make progress.

initial_radius(rule, Δ0, g_norm) -> Float64

Radius at iteration 0. Most rules return Δ0; those of the form Δ = μ·crit return μ0 · g_norm and so ignore Δ0 entirely.

update_radius!(rule, Δ, ρ, accepted, η1, η2, s_norm, g_norm_old, g_norm_new)

Radius for the next iteration. May mutate rule (e.g. the multiplier μ). See RadiusRule for the meaning of each argument.

reset_rule!(rule) -> nothing

Restore mutable state to its construction value. The fallback clears the recorded branch, which every rule carries; rules with a multiplier extend it. Called at the start of every solve and by SolverCore.reset!.

needs_retrospective(rule) -> Bool

true if the rule expects the retrospective ratio ρ̃ in the ρ slot of update_radius!. The solver computes ρ̃ only when this returns true, since it costs one extra model evaluation at the previous iterate, and only on accepted steps, since ρ̃ compares the new model against a step that was taken.

is_criticality_anchored(rule) -> Bool

true if the radius is tied to a criticality measure, so that Δ_k → 0 along a convergent run. For these rules eventual inactivity of the trust region requires a parameter above the problem-dependent threshold κ̄ = 8/λ*_min.

The complement is not a single regime: RDelta keeps liminf Δ_k > 0, while the step-anchored rules drive Δ_k → 0 in the local regime with the stronger summability Σ_k Δ_k < ∞, inherited from Powell's theorem on the step series. Use asymptotic_regime when the three-way distinction matters.

asymptotic_regime(rule) -> Symbol

Which of the three asymptotic regimes the rule belongs to:

• :vanishing — Δ_k → 0 with Σ_k Δ_k²/M_k < ∞ (criticality-anchored);
• :step_summable — Σ_k Δ_k < ∞ in the local regime (step-anchored);
• :bounded_below — liminf_k Δ_k > 0 (criticality-blind, radius-anchored).

retrospective_ratio(actual, s, g_new, Hnew_s) -> Float64

Retrospective ratio ρ̃, from

• actual: f(x_k) − f(x_{k+1}), the achieved reduction (same numerator as ρ);
• s: the step s_k;
• g_new: g_{k+1}, the gradient at the new iterate;
• Hnew_s: H_{k+1} · s_k, the new model Hessian applied to the step.

Returns -Inf when the retrospective predicted reduction is non-positive, which sends the rule to its most conservative branch — the same convention the solver uses for ρ.

The denominator is −g_{k+1}ᵀs_k + ½ s_kᵀH_{k+1}s_k. Note the sign of the first term: it is a reduction measured backwards along the step. Near convergence g_{k+1}ᵀs_k → 0 — the new gradient is asymptotically orthogonal to the step that produced it — so it is the curvature term ½s_kᵀH_{k+1}s_k that carries the denominator, and positivity of ρ̃ in the limit is a statement about the model Hessian along s_k, not about the gradient. That is why ρ̃ → 1 requires either the secant condition or asymptotic second-order coherence, and is not implied by first-order coherence alone.

last_branch(rule) -> Symbol

Which branch the rule took at the most recent update_radius!.

The vocabulary is uniform across mechanisms, so branch counts are comparable:

For the Hei family the factor is continuous and the branch is read off its position relative to 1.

This is what makes Properties P1 and P2 of Part~II observable rather than inferred: P1 asks that the radius not contract while the region binds, which is the statement that no :contract, :shrink or :expand_capped occurs on an active iteration, and the count of :expand is the climb the multiplier makes towards κ̄.