Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Trust region and cubic regularization methods

1 · Prerequisites

2 · Summary

Quadratic trust-region models and the actual-to-predicted reduction ratio fixes the Euclidean model, feasible ball, reductions, and ratio. The global subproblem characterization Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case includes singular shifted Hessians and the boundary hard case. The Cauchy decrease bound supports both the SPD dogleg and finite truncated-CG step procedures.

A finite-budget trust-region method with ratio-based radius updates accepts only feasible steps with a stated fraction of Cauchy decrease and falls back to the Cauchy step when needed. Its small-radius branch selects a boundary Cauchy step. Under the additional radius threshold in The actual-to-predicted ratio approaches one at small radii away from stationarity, the ratio is at least $η_{2}$ and the radius expands up to its cap. Under bounded model Hessians, a Lipschitz gradient, and a lower-bounded objective, the proved conclusion is gradient liminf zero; no gradient-limit claim is made without stronger uniform assumptions. The separate Trust-region first-order complexity counts both successful and unsuccessful trials bounds accepted steps and telescopes the multiplicative radius updates to count every rejected trial. The elementary estimate The natural logarithm is bounded above by its positive argument minus one closes the logarithmic radius term in the stated $O (ε^{- 2})$ total-trial bound.

The ARC branch defines a separate cubic model and preserves exact global model minimizers as a solver special case. Its finite-budget algorithm also accepts inexact candidates only after checking the two cubic solution conditions, the residual termination condition, and sufficient Cauchy-model decrease; solver failure, inconsistent candidates, domain exit, and exhausted regularization are explicit statuses. Under a Lipschitz Hessian and a lower-bounded objective, with $σ_{m a x} \geq 3 L$ and the parameter and solver conditions of Adaptive cubic regularization reaches first-order accuracy in O(ε⁻³ᐟ²) evaluations, exact global steps give the $O (ε^{- 3 / 2})$ outer evaluation bound, including unsuccessful trials. Admissible inexact steps give the same order when the gradient is uniformly Lipschitz on trial segments, with the stated model-solution and regularization conditions; the proof counts outer trials, not inner solver work.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Quadratic trust-region models and the actual-to-predicted reduction ratio

Definition

Let $n \geq 1$ , let $f : R^{n} \to R$ be differentiable at $x \in R^{n}$ , and put $g : = \nabla f (x)$ using the gradient convention of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case. Let $B \in R^{n \times n}$ be a symmetric matrix and let $Δ > 0$ . A quadratic model at $x$ is

$m (p) : = f (x) + ⟨ g, p ⟩ + \frac{1}{2} p^{T} B p, p \in R^{n},$

with the Euclidean inner product and norm of The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ and matrix products as in Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes. The trust-region ball is $B_{Δ} : = {p : ∥ p ∥_{2} \leq Δ}$ . The predicted reduction of a feasible step $p \in B_{Δ}$ is $pred (p) : = m (0) - m (p)$ . Its actual reduction is $ared (p) : = f (x) - f (x + p)$ . When $pred (p) > 0$ , the actual-to-predicted reduction ratio is

$ρ (p) : = \frac{ared (p)}{pred (p)} .$

The quantity $∥ B ∥_{2}$ means the matrix norm induced by the Euclidean vector norm, namely the $p = 2$ case of The matrix norm induced by a published vector p-norm. It is not required that $B = \nabla^{2} f (x)$ in this definition; exact Hessians and symmetric model approximations are both admitted. The ratio is undefined when predicted reduction is nonpositive, so an algorithm must use a separately justified fallback or return a failure status in that case.

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

The cubic-regularized quadratic model

Definition

Let $f : R^{n} \to R$ be twice differentiable at $x$ , let $g : = \nabla f (x)$ , let $B \in R^{n \times n}$ be symmetric, and let $σ > 0$ . The cubic-regularized quadratic model is

$m_{σ} (s) : = f (x) + ⟨ g, s ⟩ + \frac{1}{2} s^{T} B s + \frac{σ}{3} ∥ s ∥_{2}^{3}, s \in R^{n},$

using the Euclidean conventions of The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ , the gradient and Hessian conventions of The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case and The Hessian matrix and critical points of a scalar field, and the induced matrix norm of The matrix norm induced by a published vector p-norm. Its predicted reduction is $m_{σ} (0) - m_{σ} (s)$ . Define the actual reduction by $ared (s) : = f (x) - f (x + s)$ and, when the predicted reduction is positive, define the ratio $ρ_{σ} (s) : = \frac{ared (s)}{m_{σ} (0) - m_{σ} (s)} .$ When $B = \nabla^{2} f (x)$ , this is the exact-Hessian ARC model; approximation error in a different $B$ requires separate bounds. The definition alone gives no convergence or evaluation-complexity guarantee.

LemmaStatement: AI-adaptedProof: AI-adaptedOpen item page →

The natural logarithm is bounded above by its positive argument minus one

Statement

For every real $x \geq 1$ , the natural logarithm of The natural logarithm as the inverse of the exponential function satisfies $0 \leq \log x \leq x - 1 \leq x .$

Facts & Assumptions

Given: $x \geq 1$ and the natural logarithm.

[F1]

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the exponential function on $(0, \infty)$ .

[F2]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is continuous and strictly increasing, and $\log 1 = 0$ .

[F3]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\log^{'} (t) = 1 / t$ for every $t > 0$ .

[F4]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a function continuous on a closed interval and differentiable in its interior has a point where its derivative equals its endpoint difference divided by the interval length.

[A1]

$x \geq 1$ .

Proof

Given: The hypotheses in the Statement.

1.1givenA1F1F2F3F4caseschoose

By [F1], $\log$ is defined on $[1, x]$ . If $x = 1$ , [F2] gives $\log x = 0$ . If $x > 1$ , [F2] gives continuity of $\log$ on $[1, x]$ , and [F3] gives differentiability on $(1, x)$ . By [F4], there is $c \in (1, x)$ such that $\log x - \log 1 = \frac{x - 1}{c},$ so $\log x = (x - 1) / c$ .

2.1givenA1F2step 1.1algebracases∎

In the $x = 1$ case the claimed inequalities are equalities except $x - 1 \leq x$ . In the $x > 1$ case, $c > 1$ and $x - 1 > 0$ , so $0 < (x - 1) / c < x - 1 < x$ . Combining with step 1.1 proves all three inequalities.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case

Statement

Let $n \geq 1$ , let $B \in R^{n \times n}$ be symmetric, let $g \in R^{n}$ , and let $Δ > 0$ . Every global minimizer $p_{*}$ of $q (p) : = ⟨ g, p ⟩ + \frac{1}{2} p^{T} B p over ∥ p ∥_{2} \leq Δ$ has a multiplier $λ \geq 0$ such that $(B + λ I) p_{*} = - g, B + λ I ⪰ 0, λ (Δ - ∥ p_{*} ∥_{2}) = 0.$ Conversely, every feasible $p_{*}$ satisfying these conditions is a global minimizer. A global minimizer always exists.

The singular hard case is included as follows. Let $μ$ be the least eigenvalue of $B$ and $E_{μ}$ its eigenspace. If $μ < 0$ , $g ⊥ E_{μ}$ , and the solution $p_{0}$ of $(B - μ I) p_{0} = - g$ , $p_{0} ⊥ E_{μ}$ , has $∥ p_{0} ∥_{2} \leq Δ$ , then $p_{*} = p_{0} + z, z \in E_{μ}, ∥ z ∥_{2}^{2} = Δ^{2} - ∥ p_{0} ∥_{2}^{2}$ is a global minimizer with the singular multiplier $λ = - μ$ . If $∥ p_{0} ∥_{2} < Δ$ , both signs of any chosen nonzero $z$ of the required length give distinct minimizers.

Facts & Assumptions

Given: $n \geq 1$ , a real symmetric matrix $B \in R^{n \times n}$ , a vector $g \in R^{n}$ , a radius $Δ > 0$ , and the trust-region quadratic model and Euclidean conventions of Quadratic trust-region models and the actual-to-predicted reduction ratio.

[F1]

Quadratic trust-region models and the actual-to-predicted reduction ratio: the feasible set is the closed Euclidean ball ${p : ∥ p ∥_{2} \leq Δ}$ and the model differs from $q$ only by the constant $f (x)$ .

[F2]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F3]

Positive definite, negative definite, semidefinite, and indefinite quadratic forms: a symmetric matrix $C$ is positive semidefinite exactly when $v^{T} C v \geq 0$ for every $v$ .

[F4]

Intermediate value theorem, by bisection with a canonical left-half rule: a continuous function on $[a, b]$ takes every value between $f (a)$ and $f (b)$ : a continuous real-valued function on a closed interval takes every value between its endpoint values.

[F5]

Sums, scalar multiples, products, absolute values, maxima, minima and quotients with nonvanishing denominator of continuous functions are continuous, as are constants, the identity and every polynomial function: finite sums, products, and quotients with nonzero denominators of continuous real functions are continuous on their domains.

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2algebra

By [F2], choose an orthogonal matrix $U$ such that $D : = U^{T} B U = diag (μ_{1}, \dots, μ_{n})$ with $μ_{1} \leq \dots \leq μ_{n}$ . Put $c : = U^{T} g$ and write $p = U y$ . Then $q (U y) = \sum_{i} (c_{i} y_{i} + \frac{1}{2} μ_{i} y_{i}^{2})$ and $∥ U y ∥_{2} = ∥ y ∥_{2}$ , so it suffices to construct a minimizer in these coordinates.

2.1step 1.1F4F5algebrachoose

Set $λ_{0} : = \max (0, - μ_{1})$ and, for $λ > λ_{0}$ , define $φ (λ) : = \sum_{i} c_{i}^{2} / (μ_{i} + λ)^{2}$ and $y_{i} (λ) : = - c_{i} / (μ_{i} + λ)$ . Every denominator is positive, so [F5] gives continuity of $φ$ . Let $Z : = {i : μ_{i} + λ_{0} = 0}$ . If some $i \in Z$ has $c_{i} \neq 0$ , choose $λ_{a} > λ_{0}$ with $λ_{a} - λ_{0} < ∣ c_{i} ∣ / Δ$ ; its single term gives $φ (λ_{a}) > Δ^{2}$ . Otherwise $c_{i} = 0$ for $i \in Z$ . Then $φ_{0} : = \sum_{i \notin Z} \frac{c_{i}^{2}}{(μ_{i} + λ_{0})^{2}}$ is finite. If $φ_{0} > Δ^{2}$ , each term with $i \notin Z$ is continuous at $λ_{0}$ by [F5], while each term with $i \in Z$ is zero for $λ > λ_{0}$ and extends as the constant zero. Thus the extension with value $φ_{0}$ is continuous at $λ_{0}$ , so choose $λ_{a} > λ_{0}$ close enough that $φ (λ_{a}) > Δ^{2}$ . In either case with $φ (λ_{a}) > Δ^{2}$ , put $S : = \sum_{i} ∣ μ_{i} ∣$ and choose $R > \max {λ_{a}, S + 2 ∥ c ∥_{2} / Δ}$ . Then $μ_{i} + R > 2 ∥ c ∥_{2} / Δ$ for every $i$ , giving $φ (R) < Δ^{2} / 4 < Δ^{2}$ . By [F4] on $[λ_{a}, R]$ , choose $λ > λ_{0}$ with $φ (λ) = Δ^{2}$ . The vector $y_{i} = - c_{i} / (μ_{i} + λ)$ then has norm $Δ$ , $(D + λ I) y = - c$ , and $D + λ I$ is positive definite.

3.1step 1.1step 2.1F3algebraconstruct

In the remaining case every $i \in Z$ has $c_{i} = 0$ and the finite sum $φ_{0}$ in step 2.1 satisfies $φ_{0} \leq Δ^{2}$ . Set $y_{i}^{0} = - c_{i} / (μ_{i} + λ_{0})$ for $i \notin Z$ and $y_{i}^{0} = 0$ for $i \in Z$ . If $λ_{0} = 0$ , take $y = y^{0}$ ; then $D$ is positive semidefinite, $D y = - c$ , and $∥ y ∥_{2} \leq Δ$ . If $λ_{0} > 0$ , the zero-denominator coordinates form the least-eigenvalue eigenspace. Add a vector $z$ supported on those coordinates with $∥ z ∥_{2}^{2} = Δ^{2} - ∥ y^{0} ∥_{2}^{2}$ and take $y = y^{0} + z$ . Such a vector exists by scaling a unit eigenvector; it is orthogonal to $y^{0}$ . Then $(D + λ_{0} I) y = - c$ , $D + λ_{0} I ⪰ 0$ , and $∥ y ∥_{2} = Δ$ . This is the hard-case construction.

4.1step 2.1step 3.1F3givenalgebra

In either construction, returning to $p = U y$ gives a feasible vector and a $λ \geq 0$ with $(B + λ I) p = - g$ , $B + λ I ⪰ 0$ , and $λ (Δ - ∥ p ∥_{2}) = 0$ . For every feasible $v$ , direct expansion gives $q (v) - q (p) = \frac{1}{2} (v - p)^{T} (B + λ I) (v - p) + \frac{λ}{2} (∥ p ∥_{2}^{2} - ∥ v ∥_{2}^{2}) \geq 0,$ because the first term is nonnegative by [F3] and the second is zero if $λ = 0$ and nonnegative otherwise. Thus the constructed vector is a global minimizer.

5.1step 4.1F2F3givenalgebrachoose

Conversely, let $p_{*}$ be any global minimizer. Then $q (p_{*}) = q (p)$ , where $p$ is the constructed minimizer, and $p_{*}$ is feasible. Applying the identity in step 4.1 with $v = p_{*}$ expresses zero as the sum of two nonnegative terms. In particular, for $H : = B + λ I$ , $(p_{*} - p)^{T} H (p_{*} - p) = 0$ . By [F2], diagonalize the symmetric positive semidefinite matrix $H$ from step 4.1. In these coordinates the last quadratic form is $\sum_{i} ν_{i} w_{i}^{2} = 0$ with every $ν_{i} \geq 0$ , so $ν_{i} w_{i} = 0$ for every $i$ and $H (p_{*} - p) = 0$ . Since $H p = - g$ , this gives $H p_{*} = - g$ . If $λ > 0$ , the other nonnegative term in the identity vanishes only when $∥ p_{*} ∥_{2} = Δ$ ; if $λ = 0$ , complementarity is automatic. Thus $p_{*}$ satisfies all three conditions.

6.1step 3.1step 4.1∎

The constructed case $λ_{0} > 0$ has $g ⊥ E_{μ}$ and adds exactly the missing boundary component in $E_{μ}$ ; when its length is positive, opposite choices of $z$ are distinct and the same inequality in step 4.1 proves both globally minimizing. This verifies the stated hard-case clause.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

The Cauchy step for a quadratic trust-region model

Definition

Input a model of Quadratic trust-region models and the actual-to-predicted reduction ratio with gradient $g$ , symmetric model matrix $B$ , and radius $Δ > 0$ . If $g = 0$ , return $p_{C} = 0$ with status stationary. If $g \neq 0$ , set $c : = g^{T} B g$ and define $τ : = {\begin{cases} Δ / ∥ g ∥_{2}, & c \leq 0, \\ \min {∥ g ∥_{2}^{2} / c, Δ / ∥ g ∥_{2}}, & c > 0. \end{cases}$ Return $p_{C} : = - τ g$ with status step.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Positive-definite Newton and dogleg steps are well-defined

Statement

Let $B$ be the real symmetric positive-definite model matrix of Quadratic trust-region models and the actual-to-predicted reduction ratio, with $n \geq 1$ , $g \in R^{n}$ , and radius $Δ > 0$ . There is a unique $p_{N} \in R^{n}$ satisfying $B p_{N} = - g$ . The Dogleg steps for positive-definite trust-region models procedure is well-defined on this input and returns a feasible vector. If its boundary-intersection branch is taken, the displayed scalar formula is the unique root $t \in (0, 1)$ of $∥ p_{C} + t (p_{N} - p_{C}) ∥_{2}^{2} = Δ^{2}$ . On a nonstationary input the procedure performs one linear solve and, only on its boundary branch, one scalar-root computation; it has no iteration loop.

Facts & Assumptions

Given: A positive-definite symmetric matrix $B$ , vector $g$ , radius $Δ > 0$ , and the definitions of the Newton and dogleg procedures.

[F1]

Positive definite, negative definite, semidefinite, and indefinite quadratic forms: positive definiteness means $v^{T} B v > 0$ for every nonzero $v$ .

[F2]

Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis: a real symmetric matrix has an orthonormal eigenbasis.

[F3]

Invertible Euclidean linear maps: an invertible Euclidean linear map has a two-sided linear inverse.

[F4]

Dogleg steps for positive-definite trust-region models: after the stationary check, the procedure computes the Cauchy step, solves $B p_{N} = - g$ , returns $p_{N}$ if it is feasible, returns $p_{C}$ if it is on the boundary, and otherwise uses the displayed quadratic-root formula before comparing the two model values.

[F5]

The Cauchy step for a quadratic trust-region model: for $g \neq 0$ , the Cauchy parameter is nonnegative and at most $Δ / ∥ g ∥_{2}$ , so $∥ p_{C} ∥_{2} \leq Δ$ .

[F6]

[F7]

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2F3algebra

By [F2], write $B = U diag (μ_{1}, \dots, μ_{n}) U^{T}$ with $U$ orthogonal. Positive definiteness [F1] gives $μ_{i} > 0$ for every unit eigenvector. Thus $C = U diag (1 / μ_{1}, \dots, 1 / μ_{n}) U^{T}$ satisfies $C B = B C = I$ and is a linear inverse by [F3]. Hence $p_{N} = - C g$ solves $B p_{N} = - g$ . If $p$ is another solution, then $B (p - p_{N}) = 0$ , and applying $C$ gives $p = p_{N}$ .

2.1givenF4F5step 1.1cases

If $g = 0$ , [F4] returns $p = 0$ , which is feasible. Suppose $g \neq 0$ . The Cauchy step exists by its explicit formula and is feasible by [F5], and step 1.1 gives the unique Newton step. If $∥ p_{N} ∥_{2} \leq Δ$ , the algorithm returns the feasible $p_{N}$ . If $∥ p_{N} ∥_{2} > Δ$ but $∥ p_{C} ∥_{2} = Δ$ , it returns the feasible $p_{C}$ .

3.1givenF4F6F7step 2.1algebra

In the remaining branch, $∥ p_{N} ∥_{2} > Δ$ and $∥ p_{C} ∥_{2} < Δ$ . Put $d = p_{N} - p_{C}$ and $q (t) = ∥ p_{C} + t d ∥_{2}^{2} - Δ^{2}$ . Then $q$ is a real quadratic polynomial, $q (0) < 0$ , and $q (1) > 0$ . By [F6] it is continuous, and [F7] gives a root $t \in (0, 1)$ . Its coefficients are $a = ∥ d ∥_{2}^{2} > 0$ , $b = 2 ⟨ p_{C}, d ⟩$ , and $c = ∥ p_{C} ∥_{2}^{2} - Δ^{2} < 0$ . Thus its discriminant $b^{2} - 4 a c > b^{2}$ , and the two roots have product $c / a < 0$ . Exactly one root is positive, and the quadratic formula identifies it as $(- b + \sqrt{b^{2} - 4 a c}) / (2 a)$ . The root in $(0, 1)$ is therefore exactly the algorithm's scalar $t$ . The vector $p_{D} = p_{C} + t d$ has norm $Δ$ ; the final comparison returns either $p_{D}$ or $p_{C}$ , both feasible.

4.1step 1.1step 2.1step 3.1F4cases∎

Step 1.1 proves unique Newton-step existence, and steps 2.1 and 3.1 cover every dogleg branch and establish its feasibility and root formula. The Definition calls the Newton solve once on every nonstationary input, calls the scalar-root formula only in branch 3, and has no iteration branch.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease

Statement

For the cubic model $m_{σ}$ of The cubic-regularized quadratic model, with $σ > 0$ and symmetric $B$ , a global minimizer exists. If $g \neq 0$ and $s_{*}$ is any global minimizer, then $s_{*} \neq 0$ and $g + B s_{*} + σ ∥ s_{*} ∥_{2} s_{*} = 0,$ $m_{σ} (0) - m_{σ} (s_{*}) \geq \frac{σ}{6} ∥ s_{*} ∥_{2}^{3} .$

More generally, every $s$ satisfying $g^{T} s + s^{T} B s + σ ∥ s ∥_{2}^{3} = 0, s^{T} B s + σ ∥ s ∥_{2}^{3} \geq 0$ has $m_{σ} (0) - m_{σ} (s) \geq \frac{σ}{6} ∥ s ∥_{2}^{3}$ . For $g \neq 0$ , put $a = ∥ g ∥_{2}$ and $q = g^{T} B g$ . The unique minimizer of the cubic model on the negative-gradient ray ${- t g : t \geq 0}$ is $s_{C} = - t_{C} g, t_{C} = \frac{- q + \sqrt{q^{2} + 4 σ a^{5}}}{2 σ a^{3}} > 0.$

Facts & Assumptions

Given: $n \geq 1$ , $σ > 0$ , $g \in R^{n}$ , symmetric $B \in R^{n \times n}$ , and the model $m_{σ}$ .

[F1]

The cubic-regularized quadratic model: $m_{σ} (s) = f (x) + ⟨ g, s ⟩ + \frac{1}{2} s^{T} B s + \frac{σ}{3} ∥ s ∥_{2}^{3}$ .

[F2]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ ⟨ u, v ⟩ ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ and the Euclidean norm satisfies the triangle inequality.

[F3]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: $∥ B s ∥_{2} \leq ∥ B ∥_{2} ∥ s ∥_{2}$ .

[F4]

For $n \geq 1$ , every Euclidean closed ball and every Euclidean sphere of positive radius is compact: every Euclidean closed ball in $R^{n}$ is compact.

[F5]

A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value: a continuous real-valued function on a nonempty compact metric space attains its minimum.

[F6]

Continuity and derivatives of positive-base real powers: for $u > 0$ , $(u^{3 / 2})^{'} = \frac{3}{2} u^{1 / 2}$ .

[F7]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a function continuous on a closed interval and differentiable in its interior has an interior point where its derivative equals its endpoint slope.

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2F3algebrachoose

Put $a : = ∥ g ∥_{2}$ and $M : = ∥ B ∥_{2}$ . For $r : = ∥ s ∥_{2}$ , [F2] and [F3] give $m_{σ} (s) \geq f (x) - a r - \frac{1}{2} M r^{2} + \frac{σ}{3} r^{3} .$ Choose $R > 0$ so that $R^{2} \geq 6 a / σ$ and $R \geq 3 M / σ$ . For every $r \geq R$ , the first negative term is at most $σ r^{3} / 6$ and the second is at most $σ r^{3} / 6$ ; hence $m_{σ} (s) \geq f (x) = m_{σ} (0)$ outside the closed ball of radius $R$ .

1.2givenF1F6algebra

Now suppose $g \neq 0$ and let $s_{*}$ be a global minimizer. For small $t > 0$ , $m_{σ} (- t g) - m_{σ} (0) = - t ∥ g ∥_{2}^{2} + \frac{1}{2} t^{2} g^{T} B g + \frac{σ}{3} t^{3} ∥ g ∥_{2}^{3} < 0,$ because the negative linear term dominates the quadratic and cubic terms as $t ↓ 0$ . Hence $s_{*} \neq 0$ . For any direction $h$ , put $r : = ∥ s_{*} ∥_{2} > 0$ and $ψ (t) : = m_{σ} (s_{*} + t h) - m_{σ} (s_{*}) = t ⟨ g + B s_{*}, h ⟩ + \frac{1}{2} t^{2} h^{T} B h + \frac{σ}{3} (r^{2} + 2 t ⟨ s_{*}, h ⟩ + t^{2} ∥ h ∥_{2}^{2})^{3 / 2} - \frac{σ}{3} r^{3} .$ By [F6], $ψ^{'} (0) = ⟨ g + B s_{*} + σ r s_{*}, h ⟩$ . Since $t = 0$ minimizes $ψ$ , its positive difference quotients are nonnegative and its negative difference quotients are nonpositive, so this derivative is zero. Taking $h = g + B s_{*} + σ r s_{*}$ gives $g + B s_{*} + σ ∥ s_{*} ∥_{2} s_{*} = 0.$

1.3givenalgebra

Let $s$ satisfy the two inexact-step conditions in the Statement and write $r = ∥ s ∥_{2}$ . Substituting $- g^{T} s = s^{T} B s + σ r^{3}$ into the model decrease gives $m_{σ} (0) - m_{σ} (s) = \frac{1}{2} s^{T} B s + \frac{2 σ}{3} r^{3} .$ The second condition implies $s^{T} B s \geq - σ r^{3}$ , and therefore the right side is at least $σ r^{3} / 6$ .

1.4givenF7algebrachoose

Suppose $g \neq 0$ , put $a = ∥ g ∥_{2} > 0$ and $q = g^{T} B g$ , and define $ψ (t) = m_{σ} (- t g) - m_{σ} (0)$ for $t \geq 0$ . Then $ψ (t) = - a^{2} t + \frac{1}{2} q t^{2} + \frac{σ}{3} a^{3} t^{3}, ψ^{'} (t) = - a^{2} + q t + σ a^{3} t^{2} .$ The two roots of $ψ^{'}$ are $t_{\pm} = \frac{- q \pm \sqrt{q^{2} + 4 σ a^{5}}}{2 σ a^{3}};$ their product is $- 1 / (σ a) < 0$ , so $t_{-} < 0 < t_{+}$ . The derivative factors as $σ a^{3} (t - t_{-}) (t - t_{+})$ , hence it is negative on $[0, t_{+})$ and positive on $(t_{+}, \infty)$ . Applying [F7] on any subinterval of either range shows that $ψ$ strictly decreases before $t_{+}$ and strictly increases after it. Thus $t_{C} = t_{+}$ is the unique global minimizer on $[0, \infty)$ , proving the stated Cauchy-ray formula.

2.1step 1.1F1F2F3F4F5

The model is continuous: for $u, v \in R^{n}$ , the triangle inequality gives $∣ ∥ u ∥_{2} - ∥ v ∥_{2} ∣ \leq ∥ u - v ∥_{2}$ . If $∥ u - v ∥_{2} < 1$ , then $∥ u ∥_{2} \leq ∥ v ∥_{2} + 1$ , and $∣ ∥ u ∥_{2}^{3} - ∥ v ∥_{2}^{3} ∣ = ∣ ∥ u ∥_{2} - ∥ v ∥_{2} ∣ (∥ u ∥_{2}^{2} + ∥ u ∥_{2} ∥ v ∥_{2} + ∥ v ∥_{2}^{2})$ tends to zero with $∥ u - v ∥_{2}$ ; this also holds at $v = 0$ , where $∥ u ∥_{2}^{3} \leq ∥ u ∥_{2}$ for $∥ u - v ∥_{2} < 1$ . The linear term is continuous by [F2], and $∣ u^{T} B u - v^{T} B v ∣ \leq ∥ u - v ∥_{2} ∥ B ∥_{2} (∥ u ∥_{2} + ∥ v ∥_{2})$ by [F2] and [F3], so the quadratic term is continuous as well. The closed ball from step 1.1 is nonempty and compact by [F4]. Thus [F5] gives a minimizer on that ball. Since $0$ is in the ball and every point outside has model value at least $m_{σ} (0)$ , this minimizer is global on $R^{n}$ .

2.2step 1.2givenalgebra

Global minimality also gives $m_{σ} (s_{*}) \leq m_{σ} (- s_{*})$ . The quadratic and cubic terms are even, so this inequality reduces to $⟨ g, s_{*} ⟩ \leq 0$ . Taking the inner product of the stationary equation in step 1.2 with $s_{*}$ gives $s_{*}^{T} B s_{*} + σ ∥ s_{*} ∥_{2}^{3} = - ⟨ g, s_{*} ⟩ \geq 0$ . Substitution back into the model decrease yields $m_{σ} (0) - m_{σ} (s_{*}) = \frac{1}{2} s_{*}^{T} B s_{*} + \frac{2 σ}{3} ∥ s_{*} ∥_{2}^{3} \geq \frac{σ}{6} ∥ s_{*} ∥_{2}^{3},$ as claimed.

3.1step 2.1step 1.2step 2.2step 1.3step 1.4∎

Steps 1.1, 2.1, 1.2, and 2.2 prove the exact global-minimizer claims, step 1.3 proves the inexact-step decrease, and step 1.4 proves the Cauchy-ray assertion.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

The Cauchy step gives a quantitative model decrease

Statement

In the quadratic model of Quadratic trust-region models and the actual-to-predicted reduction ratio, let $g \neq 0$ , let $B$ be symmetric, and let $Δ > 0$ . Write $M : = ∥ B ∥_{2}$ for the induced Euclidean matrix norm, with the convention $\min {Δ, ∥ g ∥_{2} / M} = Δ$ when $M = 0$ . The Cauchy step $p_{C}$ of The Cauchy step for a quadratic trust-region model minimizes the model on the negative-gradient segment ${- t g : 0 \leq t \leq Δ / ∥ g ∥_{2}}$ and satisfies $m (0) - m (p_{C}) \geq \frac{1}{2} ∥ g ∥_{2} \min {Δ, ∥ g ∥_{2} / M} .$

Facts & Assumptions

Given: A trust-region quadratic model with $g \neq 0$ , symmetric $B$ , radius $Δ > 0$ , and its Cauchy step.

[F1]

The Cauchy step for a quadratic trust-region model: if $c : = g^{T} B g \leq 0$ , then $p_{C} = - (Δ / ∥ g ∥_{2}) g$ ; if $c > 0$ , then $p_{C} = - τ g$ with $τ = \min {∥ g ∥_{2}^{2} / c, Δ / ∥ g ∥_{2}}$ .

[F2]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: $∥ B g ∥_{2} \leq ∥ B ∥_{2} ∥ g ∥_{2}$ .

[F3]

[F4]

Quadratic trust-region models and the actual-to-predicted reduction ratio: $m (p) = f (x) + ⟨ g, p ⟩ + \frac{1}{2} p^{T} B p$ .

Proof

Given: The hypotheses in the Statement.

1.1givenF1F4algebra

Put $a : = ∥ g ∥_{2} > 0$ , $c : = g^{T} B g$ , and $ψ (t) : = m (- t g) - m (0) = - t a^{2} + \frac{1}{2} t^{2} c$ on $0 \leq t \leq Δ / a$ . If $c \leq 0$ , then for $t_{2} > t_{1} \geq 0$ , $ψ (t_{2}) - ψ (t_{1}) = - (t_{2} - t_{1}) a^{2} + \frac{1}{2} c (t_{2}^{2} - t_{1}^{2}) < 0$ ; hence its minimum is at $t = Δ / a$ , which is the first branch in [F1]. The predicted reduction is $P \geq a Δ \geq \frac{1}{2} a \min {Δ, a / M}$ . This case also covers $M = 0$ , since then $c = 0$ .

1.2givenF1F2F3F4algebra

Suppose $c > 0$ . Completing the square in $ψ$ shows its unconstrained minimizer is $t = a^{2} / c$ , so its minimizer on the segment is $τ = \min {a^{2} / c, Δ / a}$ , the second branch in [F1]. Put $s : = τ a$ ; then $s = \min {a^{3} / c, Δ}$ and $s \leq a^{3} / c$ . Thus $P = a s - \frac{1}{2} (c / a^{2}) s^{2} \geq \frac{1}{2} a s$ . By [F2] and [F3], $c = ⟨ g, B g ⟩ \leq a ∥ B g ∥_{2} \leq M a^{2}$ , whence $a^{3} / c \geq a / M$ and $s \geq \min {Δ, a / M}$ . Therefore $P \geq \frac{1}{2} a \min {Δ, a / M}$ .

2.1step 1.1step 1.2∎

The cases $c \leq 0$ and $c > 0$ exhaust all real $c$ . Both establish that the algorithm returns the segment minimizer and prove the stated decrease bound.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Dogleg steps for positive-definite trust-region models

Definition

Input a quadratic trust-region model of Quadratic trust-region models and the actual-to-predicted reduction ratio with positive-definite $B$ (Positive definite, negative definite, semidefinite, and indefinite quadratic forms) and radius $Δ > 0$ . If $g = 0$ , return $p = 0$ with status stationary. Otherwise compute the Cauchy step $p_{C}$ by The Cauchy step for a quadratic trust-region model and the Newton-model step $p_{N}$ by solving $B p_{N} = - g$ .

If $∥ p_{N} ∥_{2} \leq Δ$ , return $p_{N}$ .
If $∥ p_{C} ∥_{2} = Δ$ , return $p_{C}$ .
Otherwise put $d : = p_{N} - p_{C}$ , $a : = ∥ d ∥_{2}^{2}$ , $b : = 2 ⟨ p_{C}, d ⟩$ , and $c : = ∥ p_{C} ∥_{2}^{2} - Δ^{2} < 0$ . Compute $t : = \frac{- b + \sqrt{b^{2} - 4 a c}}{2 a} .$ Set $p_{D} : = p_{C} + t d$ , the boundary intersection on the segment from the Cauchy step to the Newton-model step.
Compare the two model values. Return $p_{D}$ if $m (p_{D}) \leq m (p_{C})$ and return $p_{C}$ otherwise.

The status is step in the nonstationary branches.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Truncated conjugate gradients with boundary and negative-curvature exits

Definition

Input a model of Quadratic trust-region models and the actual-to-predicted reduction ratio, a finite inner cap $J \in N_{0}$ , and a residual tolerance $τ_{t o l} \geq 0$ . If $g = 0$ , return $0$ with status stationary. Otherwise initialize $z_{0} = 0$ , $r_{0} = g$ , $d_{0} = - r_{0}$ , and $j = 0$ . For at most $J$ inner iterations:

If $∥ r_{j} ∥_{2} \leq τ_{t o l}$ , take $z_{j}$ as the candidate and stop.
If $d_{j} = 0$ , take $z_{j}$ as the candidate and stop; the final comparison below then returns $p_{C}$ whenever $z_{j}$ does not give at least its model decrease.
Put $c_{j} : = d_{j}^{T} B d_{j}$ . If $c_{j} \leq 0$ , set $t_{j} : = \frac{- ⟨ z_{j}, d_{j} ⟩ + \sqrt{⟨ z_{j}, d_{j} ⟩^{2} + ∥ d_{j} ∥_{2}^{2} (Δ^{2} - ∥ z_{j} ∥_{2}^{2})}}{∥ d_{j} ∥_{2}^{2}},$ take $z_{j} + t_{j} d_{j}$ as the candidate, and stop. This is the nonpositive curvature boundary exit.
Otherwise put $α_{j} : = ∥ r_{j} ∥_{2}^{2} / c_{j}$ and $\hat{z} : = z_{j} + α_{j} d_{j}$ . If $∥ \hat{z} ∥_{2} \geq Δ$ , use the same positive-root formula in step 3, take $z_{j} + t_{j} d_{j}$ as the candidate, and stop at the trust boundary.
Set $r_{j + 1} : = r_{j} + α_{j} B d_{j}$ and $z_{j + 1} : = \hat{z}$ . If $∥ r_{j + 1} ∥_{2} \leq τ_{t o l}$ , take $z_{j + 1}$ as the candidate and stop. Otherwise set $β_{j + 1} : = \frac{∥ r_{j + 1} ∥_{2}^{2}}{∥ r_{j} ∥_{2}^{2}}, d_{j + 1} : = - r_{j + 1} + β_{j + 1} d_{j},$ and increase $j$ by one.

If the cap is reached, take the current $z_{j}$ as the candidate. In all nonstationary cases compute the Cauchy step $p_{C}$ and compare model values: return the candidate if its model value is no greater than $m (p_{C})$ , and otherwise return $p_{C}$ . Thus a capped or unhelpful inner recurrence still returns the selected candidate or Cauchy step.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

Finite-budget adaptive regularization using cubic models

Definition

Input an open set $U \subseteq R^{n}$ , a twice continuously differentiable $f : U \to R$ , an initial point $x_{0} \in U$ , target $ε \geq 0$ , outer trial cap $N \in N_{0}$ , and an exact-Hessian cubic-model solver $S$ . Other inputs are $0 < η_{1} < η_{2} < 1$ , $γ_{u p} > 1$ , $0 < γ_{d o w n} < 1$ , $0 < κ < 1$ , $0 < σ_{m i n} \leq σ_{0} \leq σ_{m a x}$ , $0 < κ_{θ} < 1$ , and the finite inner cap $J \in N_{0}$ . On input of the model, $J$ , and $κ_{θ}$ , the solver $S$ returns no-candidate or proposes a vector. A proposed vector is admissible when it passes the model-solution checks below. The solver may return no-candidate if it cannot certify such a vector within its cap. Exact global minimizers are an admissible special case; the local criterion also permits inexact steps satisfying the stated conditions of Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease ↗.

The output is the last accepted iterate and one of stationary, target-achieved, outer-budget-exhausted, model-solver-failure, inconsistent-model-solver, domain-exit, or regularization-cap-exhausted.

For $k = 0, 1, \dots, N$ , in order:

Compute $g_{k} : = \nabla f (x_{k})$ . If $g_{k} = 0$ , return $(x_{k}, stationary)$ . If $∥ g_{k} ∥_{2} \leq ε$ , return $(x_{k}, target-achieved)$ . If $k = N$ , return $(x_{k}, outer-budget-exhausted)$ .
Set $B_{k} : = \nabla^{2} f (x_{k})$ and form the model $m_{k} (s) = f (x_{k}) + ⟨ g_{k}, s ⟩ + \frac{1}{2} s^{T} B_{k} s + \frac{σ_{k}}{3} ∥ s ∥_{2}^{3}$ of The cubic-regularized quadratic model. By The Hessian of a $C^{2}$ scalar field is symmetric, $B_{k}$ is symmetric. Put $a_{k} : = ∥ g_{k} ∥_{2}$ , $q_{k} : = g_{k}^{T} B_{k} g_{k}$ , and compute the cubic Cauchy step $s_{C, k} : = - t_{C, k} g_{k}, t_{C, k} : = \frac{- q_{k} + \sqrt{q_{k}^{2} + 4 σ_{k} a_{k}^{5}}}{2 σ_{k} a_{k}^{3}} .$ Call $S (m_{k}, J, κ_{θ})$ . If it returns no-candidate, return $(x_{k}, model-solver-failure)$ . For a proposed $s_{k}$ , recompute ${pred}_{k} : = m_{k} (0) - m_{k} (s_{k})$ and $\nabla m_{k} (s_{k}) : = g_{k} + B_{k} s_{k} + σ_{k} ∥ s_{k} ∥_{2} s_{k}$ . Check $g_{k}^{T} s_{k} + s_{k}^{T} B_{k} s_{k} + σ_{k} ∥ s_{k} ∥_{2}^{3} = 0, s_{k}^{T} B_{k} s_{k} + σ_{k} ∥ s_{k} ∥_{2}^{3} \geq 0,$ $∥ \nabla m_{k} (s_{k}) ∥_{2} \leq κ_{θ} \min {1, ∥ s_{k} ∥_{2}} ∥ g_{k} ∥_{2}, m_{k} (s_{k}) \leq m_{k} (s_{C, k}) .$ If any check fails, or if $s_{k} = 0$ or ${pred}_{k} \leq 0$ , return $(x_{k}, inconsistent-model-solver)$ .
If $x_{k} + s_{k} \notin U$ , return $(x_{k}, domain-exit)$ without evaluating $f$ there. Otherwise evaluate $f (x_{k} + s_{k})$ and set $ρ_{k} : = [f (x_{k}) - f (x_{k} + s_{k})] / {pred}_{k}$ . If $ρ_{k} < η_{1}$ , reject the step and keep $x_{k + 1} : = x_{k}$ . If $σ_{k} = σ_{m a x}$ , return $(x_{k}, regularization-cap-exhausted)$ ; otherwise set $σ_{k + 1} : = \min {γ_{u p} σ_{k}, σ_{m a x}}$ and continue.
If $ρ_{k} \geq η_{1}$ , accept and set $x_{k + 1} : = x_{k} + s_{k}$ . If $ρ_{k} > η_{2}$ and $∥ s_{k} ∥_{2} \geq κ ∥ g_{k} ∥_{2} / σ_{k}$ , set $σ_{k + 1} : = \max {σ_{m i n}, γ_{d o w n} σ_{k}}$ ; otherwise set $σ_{k + 1} : = σ_{k}$ .

The finite cap, solver failure, inconsistent-solver, domain-exit, and regularization-cap branches are explicit. The model-solution checks include the two cubic conditions (4.1)–(4.2), residual condition TC.s, and the Cauchy-model decrease condition of Cartis–Gould–Toint, Part II, §4. The procedure alone makes no unconditional convergence or evaluation-complexity claim.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Truncated-CG iterates are feasible and lie in generated Krylov subspaces

Statement

For the interior recurrence of Truncated conjugate gradients with boundary and negative-curvature exits, before it exits at the boundary, nonpositive curvature, residual tolerance, or inner cap, its vectors satisfy $z_{j} \in K_{j} (B, - g), r_{j}, d_{j} \in K_{j + 1} (B, - g),$ where $K_{j}$ is the Krylov subspace of The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ . Every boundary exit uses the unique positive root of the displayed formula, and the algorithm returns a feasible vector.

Facts & Assumptions

Given: A quadratic trust-region model with radius $Δ > 0$ , nonzero $g$ , and the truncated-CG procedure.

[F1]

Truncated conjugate gradients with boundary and negative-curvature exits: $z_{0} = 0$ , $r_{0} = g$ , $d_{0} = - r_{0}$ ; an interior update is $z_{j + 1} = z_{j} + α_{j} d_{j}$ , $r_{j + 1} = r_{j} + α_{j} B d_{j}$ , and $d_{j + 1} = - r_{j + 1} + β_{j + 1} d_{j}$ . A boundary formula is used only after the zero-direction guard has passed, and an interior update is made only when $∥ \hat{z} ∥_{2} < Δ$ .

[F2]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{m} (B, - g) = span {- g, B (- g), \dots, B^{m - 1} (- g)}$ , $K_{0} = {0}$ , and multiplication by $B$ sends $K_{m}$ into $K_{m + 1}$ .

[F3]

The Cauchy step for a quadratic trust-region model: for $g \neq 0$ , its formula gives $0 \leq τ \leq Δ / ∥ g ∥_{2}$ and $p_{C} = - τ g$ .

[F4]

Quadratic trust-region models and the actual-to-predicted reduction ratio: feasible vectors satisfy $∥ p ∥_{2} \leq Δ$ , where $Δ > 0$ .

Proof

Given: The hypotheses in the Statement.

1.1givenF1F2F4

Initially, $z_{0} = 0 \in K_{0} (B, - g)$ , while $r_{0} = g \in K_{1} (B, - g)$ and $d_{0} = - g \in K_{1} (B, - g)$ . Also $∥ z_{0} ∥_{2} = 0 < Δ$ .

2.1step 1.1F1F2F4inductionalgebra

Suppose the algorithm makes an interior update at index $j$ . By [F2], $B d_{j} \in K_{j + 2}$ , while $z_{j} \in K_{j} \subseteq K_{j + 1}$ and $r_{j}, d_{j} \in K_{j + 1}$ . The first two recurrences in [F1] therefore give $z_{j + 1} \in K_{j + 1}$ and $r_{j + 1} \in K_{j + 2}$ . The last recurrence gives $d_{j + 1} \in K_{j + 2}$ . The update is made only when $∥ \hat{z} ∥_{2} < Δ$ , so $z_{j + 1}$ remains strictly inside the ball.

3.1givenF1F4step 1.1step 2.1algebra

At a boundary exit, put $z = z_{j}$ , $d = d_{j}$ , $a = ∥ d ∥_{2}^{2}$ , $b = ⟨ z, d ⟩$ , and $c = ∥ z ∥_{2}^{2} - Δ^{2}$ . Steps 1.1 and 2.1 show $∥ z ∥_{2} < Δ$ , and the zero-direction guard in [F1] gives $d \neq 0$ , so $a > 0$ and $c < 0$ . The boundary equation is $a t^{2} + 2 b t + c = 0.$ Its discriminant is $4 (b^{2} - a c) > 4 b^{2}$ , and the product of its roots is $c / a < 0$ . Thus it has exactly one positive root, namely $t = \frac{- b + \sqrt{b^{2} + a (Δ^{2} - ∥ z ∥_{2}^{2})}}{a},$ which is the algorithm's formula. In the positive-curvature exit, the unconstrained point $\hat{z} = z + α_{j} d$ satisfies $∥ \hat{z} ∥_{2} \geq Δ$ , so the quadratic is nonnegative at $α_{j}$ . It is negative on $[0, t_{+})$ , where $t_{+}$ is its unique positive root; hence $t_{+} \leq α_{j}$ . In either boundary branch, $∥ z + t_{+} d ∥_{2} = Δ$ .

4.1step 1.1step 2.1step 3.1F1F3F4cases

Before a non-boundary stop, the current recurrence vector is strictly inside the ball by steps 1.1 and 2.1. Thus residual-tolerance and zero-direction stops, and the inner-cap stop, use a feasible current vector. A boundary stop uses a vector of norm $Δ$ by step 3.1. The stationary branch returns zero, and the final comparison returns either its feasible candidate or the Cauchy step, which is feasible because [F3] gives $∥ p_{C} ∥_{2} = τ ∥ g ∥_{2} \leq Δ$ . Hence every returned vector is feasible.

5.1step 1.1step 2.1induction∎

Induction on the interior updates proves the claimed Krylov memberships. The base case is step 1.1, and the induction step is step 2.1.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicablejudge pass (gpt-6-luna)Open item page →

A finite-budget trust-region method with ratio-based radius updates

Definition

Input $f : R^{n} \to R$ of class $C^{1}$ , an initial point $x_{0}$ , an initial radius $0 < Δ_{0} \leq Δ_{m a x}$ , a trial cap $N \in N_{0}$ , a target $ε \geq 0$ , constants $0 < η_{1} < η_{2} < 1$ , $0 < γ_{d e c} < 1 < γ_{i n c}$ , $0 < θ_{C} \leq 1$ , and a declared model-Hessian bound $M_{B} \geq 0$ . At each trial $k$ , the supplied symmetric model matrix $B_{k}$ must satisfy $∥ B_{k} ∥_{2} \leq M_{B}$ . A finite-budget subproblem routine $S$ returns either a vector or failure; its output is treated only as a candidate and is not assumed to minimize the trust-region model. The output is the last accepted point and one of stationary, target-achieved, outer-budget-exhausted, or model-evaluation-failure.

For $k = 0, 1, \dots, N$ , in order:

Set $g_{k} : = \nabla f (x_{k})$ . If $g_{k} = 0$ , return $(x_{k}, stationary)$ . If $∥ g_{k} ∥_{2} \leq ε$ , return $(x_{k}, target-achieved)$ . If $k = N$ , return $(x_{k}, outer-budget-exhausted)$ .
Form $m_{k}$ from Quadratic trust-region models and the actual-to-predicted reduction ratio, compute the Cauchy step $p_{C}$ from The Cauchy step for a quadratic trust-region model, and set $P_{C} : = m_{k} (0) - m_{k} (p_{C})$ . Query $S$ with this model and radius. Use its candidate $q$ only if it is feasible and $m_{k} (0) - m_{k} (q) \geq θ_{C} P_{C}$ ; otherwise set $p : = p_{C}$ . If it qualifies, set $p : = q$ . If $M_{B} = 0$ , interpret $∥ g_{k} ∥_{2} / (2 M_{B}) = + \infty$ . Whenever $Δ_{k} \leq ∥ g_{k} ∥_{2} / (2 M_{B})$ , replace the candidate by $p : = p_{C}$ .
Recompute $P_{k} : = m_{k} (0) - m_{k} (p)$ . Evaluate $ρ_{k} : = [f (x_{k}) - f (x_{k} + p)] / P_{k}$ . If this evaluation is unavailable, return $(x_{k}, model-evaluation-failure)$ .
If $ρ_{k} < η_{1}$ , reject: set $x_{k + 1} : = x_{k}$ and $Δ_{k + 1} : = γ_{d e c} Δ_{k}$ . Otherwise accept and set $x_{k + 1} : = x_{k} + p$ . If $ρ_{k} \geq η_{2}$ and $∥ p ∥_{2} = Δ_{k}$ , set $Δ_{k + 1} : = \min {γ_{i n c} Δ_{k}, Δ_{m a x}}$ ; in every other accepted case set $Δ_{k + 1} : = Δ_{k}$ .

The finite subproblem budget alone does not imply convergence or a complexity bound.

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

The actual-to-predicted ratio approaches one at small radii away from stationarity

Statement

Let $m$ be the model of Quadratic trust-region models and the actual-to-predicted reduction ratio, with $g \neq 0$ , symmetric $B$ , and radius $Δ > 0$ . Suppose $∥ B ∥_{2} \leq M_{B}$ for a declared $M_{B} \geq 0$ , and $f$ is $C^{1}$ on an open set containing the segment from $x$ to $x + p$ . Suppose the gradient of $f$ is $L$ -Lipschitz on that segment, meaning $∥ \nabla f (u) - \nabla f (v) ∥_{2} \leq L ∥ u - v ∥_{2}$ there. Let $0 < θ \leq 1$ , let $p$ be feasible, and suppose $m (0) - m (p) \geq θ [m (0) - m (p_{C})]$ for the Cauchy step $p_{C}$ of The Cauchy step for a quadratic trust-region model. Interpret $∥ g ∥_{2} / (2 M_{B}) = + \infty$ if $M_{B} = 0$ , and assume $Δ \leq ∥ g ∥_{2} / (2 M_{B})$ . Then the predicted reduction is positive and $∣ ρ (p) - 1 ∣ \leq \frac{2 (L + M_{B}) Δ}{θ ∥ g ∥_{2}} .$ Consequently, for $0 < η_{2} < 1$ , if $L + M_{B} > 0$ and $Δ \leq \frac{θ (1 - η_{2}) ∥ g ∥_{2}}{2 (L + M_{B})},$ then $ρ (p) \geq η_{2}$ . If $L + M_{B} = 0$ , then $ρ (p) = 1$ .

Facts & Assumptions

Given: The model, the smoothness and Hessian-bound assumptions in the Statement, and a feasible step satisfying the stated fraction of Cauchy decrease.

[F1]

The Cauchy step for a quadratic trust-region model: if $c : = g^{T} B g \leq 0$ , then $p_{C} = - (Δ / ∥ g ∥_{2}) g$ ; if $c > 0$ , then $p_{C} = - \min {∥ g ∥_{2}^{2} / c, Δ / ∥ g ∥_{2}} g$ .

[F2]

The Cauchy step gives a quantitative model decrease: $m (0) - m (p_{C}) \geq \frac{1}{2} ∥ g ∥_{2} \min {Δ, ∥ g ∥_{2} / M_{B}},$ with the zero-matrix convention from that lemma.

[F3]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: $∥ B v ∥_{2} \leq ∥ B ∥_{2} ∥ v ∥_{2}$ .

[F4]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: $∣ u^{T} v ∣ \leq ∥ u ∥_{2} ∥ v ∥_{2}$ .

[F5]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : if a scalar function is continuous on a closed interval and differentiable in its interior, its endpoint difference equals its derivative at an interior point times the interval length.

[A1]

$∥ B ∥_{2} \leq M_{B}$ .

[A2]

The gradient Lipschitz inequality in the Statement holds along the segment $x + t p$ , $0 \leq t \leq 1$ .

[A3]

$m (0) - m (p) \geq θ [m (0) - m (p_{C})]$ with $0 < θ \leq 1$ .

Proof

Given: The hypotheses in the Statement.

1.1givenA1A3F1F2F3F4algebra

Put $a : = ∥ g ∥_{2} > 0$ and $c : = g^{T} B g$ . By [F3] and [F4], $c \leq ∣ c ∣ \leq a ∥ B g ∥_{2} \leq M_{B} a^{2}$ . If $c \leq 0$ , [F1] gives $∥ p_{C} ∥_{2} = Δ$ . If $c > 0$ , then $M_{B} > 0$ and $a^{2} / c \geq 1 / M_{B}$ ; since $Δ / a \leq 1 / (2 M_{B})$ , [F1] again gives $∥ p_{C} ∥_{2} = Δ$ . Put $M : = ∥ B ∥_{2}$ . If $M > 0$ , [A1] gives $a / M \geq a / M_{B}$ ; if $M = 0$ , use the zero-matrix convention in [F2]. Hence [F2] and [A3] imply $m (0) - m (p) \geq θ [m (0) - m (p_{C})] \geq \frac{1}{2} θ a Δ > 0.$

2.1givenA1A2F4F5step 1.1algebra∎

Define $ϕ (t) : = f (x + t p)$ and $h (t) : = ϕ (t) - ϕ (0) - t ϕ^{'} (0)$ . For $0 < t \leq 1$ , the gradient Lipschitz bound and [F4] give $∣ h^{'} (t) ∣ = ∣ ⟨ \nabla f (x + t p) - \nabla f (x), p ⟩ ∣ \leq L t ∥ p ∥_{2}^{2} .$ By [F5] on $h$ over $[0, 1]$ , $∣ h (1) ∣ \leq L ∥ p ∥_{2}^{2}$ . From the model formula and [A1], $∣ ared (p) - pred (p) ∣ \leq ∣ h (1) ∣ + \frac{1}{2} ∣ p^{T} B p ∣ \leq (L + M_{B}) ∥ p ∥_{2}^{2} .$ Since $∥ p ∥_{2} \leq Δ$ , step 1.1 yields $∣ ρ (p) - 1 ∣ \leq \frac{(L + M_{B}) Δ^{2}}{\frac{1}{2} θ a Δ} = \frac{2 (L + M_{B}) Δ}{θ a} .$ If $L + M_{B} = 0$ , the numerator vanishes and $ρ (p) = 1$ ; otherwise the stated threshold gives $∣ ρ (p) - 1 ∣ \leq 1 - η_{2}$ , hence $ρ (p) \geq η_{2}$ .

LemmaStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Cubic regularization bounds consecutive unsuccessful trials

Statement

Suppose $f$ is $C^{2}$ and its Hessian is $L$ -Lipschitz on each trial segment, meaning $∥ \nabla^{2} f (u) - \nabla^{2} f (v) ∥_{2} \leq L ∥ u - v ∥_{2} .$ Run Finite-budget adaptive regularization using cubic models with exact Hessians, and assume each trial on which a ratio is evaluated uses either an exact global cubic-model minimizer or a candidate passing the algorithm's cubic solution, residual, and Cauchy-decrease checks, together with $0 < σ_{m i n} \leq σ_{k} \leq σ_{m a x}$ and $σ_{m a x} \geq 3 L$ . Then no ratio-based rejection occurs when $σ_{k} \geq 3 L$ . If $γ_{u p} > 1$ , let $R \in N_{0}$ satisfy $γ_{u p}^{R} σ_{m i n} \geq 3 L$ ; such an $R$ exists. Every block of consecutive ratio-based rejected trials has length at most $R$ .

Facts & Assumptions

Given: The smoothness and weight bounds in the Statement, and the update rules of the ARC procedure.

[F1]

Finite-budget adaptive regularization using cubic models: every ratio trial passes the model-solution checks; a rejection leaves $x$ fixed and sets $σ^{+} = \min {γ_{u p} σ, σ_{m a x}}$ ; an accepted step keeps $σ$ or decreases it, with floor $σ_{m i n}$ .

[F2]

The cubic-regularized quadratic model: $m_{σ} (s) = f (x) + ⟨ g, s ⟩ + \frac{1}{2} s^{T} B s + \frac{σ}{3} ∥ s ∥_{2}^{3}$ .

[F3]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: $∥ A v ∥_{2} \leq ∥ A ∥_{2} ∥ v ∥_{2}$ .

[F4]

[F5]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : for a scalar differentiable function on a closed interval, its endpoint difference equals its derivative at some interior point times the interval length.

[F6]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : powers of any real number greater than $1$ diverge to $+ \infty$ .

[F7]

The Hessian of a $C^{2}$ scalar field is symmetric: for $C^{2}$ $f$ , $\nabla^{2} f (x)$ is symmetric.

[A1]

The Hessian is $L$ -Lipschitz on each trial segment.

[A2]

Every trial on which a ratio is evaluated uses the exact Hessian and a candidate passing the two cubic decrease conditions in the algorithm; ratio-based rejection uses its stated update.

[A3]

The weights satisfy $0 < σ_{m i n} \leq σ_{k} \leq σ_{m a x}$ , $σ_{m a x} \geq 3 L$ , and $γ_{u p} > 1$ .

[A4]

The ARC acceptance threshold satisfies $0 < η_{1} < 1$ .

Proof

Given: The hypotheses in the Statement.

1.1givenA1A2A4F1F2F3F4F5F7algebra

Fix a trial point $x$ and a solver-success candidate $s$ that reaches the ratio computation. By [F7], $B = \nabla^{2} f (x)$ is symmetric, so the cubic model is defined. Put $ϕ (t) : = f (x + t s)$ for $0 \leq t \leq 1$ . The Hessian Lipschitz assumption gives $∣ ϕ^{''} (u) - ϕ^{''} (v) ∣ = ∣ s^{T} (\nabla^{2} f (x + u s) - \nabla^{2} f (x + v s)) s ∣ \leq L ∣ u - v ∣ ∥ s ∥_{2}^{3},$ where the bound follows from [A1], [F3], and [F4]. Define $h (t) : = ϕ (t) - ϕ (0) - t ϕ^{'} (0) - \frac{1}{2} t^{2} ϕ^{''} (0)$ . For $t > 0$ , [F5] applied to $ϕ^{'}$ on $[0, t]$ gives $ϕ^{'} (t) - ϕ^{'} (0) = t ϕ^{''} (u_{t})$ for some $u_{t} \in (0, t)$ . Hence $∣ h^{'} (t) ∣ = t ∣ ϕ^{''} (u_{t}) - ϕ^{''} (0) ∣ \leq L t^{2} ∥ s ∥_{2}^{3}$ . Applying [F5] to $h$ on $[0, 1]$ yields $∣ f (x + s) - f (x) - ⟨ \nabla f (x), s ⟩ - \frac{1}{2} s^{T} \nabla^{2} f (x) s ∣ \leq L ∥ s ∥_{2}^{3} .$ By [F2], when $σ \geq 3 L$ the cubic term dominates this remainder, so $f (x + s) \leq m_{σ} (s)$ . Since the trial reaches the ratio computation, $g \neq 0$ and the algorithm's first two model checks hold; the extended Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease then gives $m_{σ} (0) - m_{σ} (s) \geq σ ∥ s ∥_{2}^{3} / 6 > 0$ . Hence $ρ \geq 1 > η_{1}$ ; that trial cannot be rejected.

2.1givenA3F1F6step 1.1algebra∎

If $3 L \leq σ_{m i n}$ , all weights are at least $3 L$ and there are no rejections, so take $R = 0$ . Otherwise, by [F6] choose a finite $R$ with $γ_{u p}^{R} σ_{m i n} \geq 3 L$ . At the start of any rejection block, $σ \geq σ_{m i n}$ . After at most $R$ consecutive rejections, repeated use of [F1] gives $σ \geq \min {γ_{u p}^{R} σ_{m i n}, σ_{m a x}} \geq 3 L$ . By step 1.1 the next trial cannot be rejected. Thus the block contains at most $R$ rejections.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Cauchy-decrease trust-region iterations have liminf gradient norm zero

Statement

Let $f : R^{n} \to R$ be $C^{1}$ , bounded below, and have an $L$ -Lipschitz gradient on every trial segment. At every iteration let $B_{k}$ be symmetric with $∥ B_{k} ∥_{2} \leq M_{B}$ for a fixed $M_{B} \geq 0$ . Fix $0 < η_{1} < η_{2} < 1$ , $0 < γ_{d e c} < 1 < γ_{i n c}$ , $0 < θ_{C} \leq 1$ , and $0 < Δ_{0} \leq Δ_{m a x}$ . Start from any $x_{0} \in R^{n}$ and consider an infinite-horizon trajectory that at each nonstationary iteration follows the model-formation, step-selection, ratio, and radius-update rules of A finite-budget trust-region method with ratio-based radius updates, with target $0$ and its finite outer-cap return omitted. If this trajectory is infinite, then ${lim inf}_{k \to \infty} ∥ \nabla f (x_{k}) ∥_{2} = 0.$

Facts & Assumptions

Given: The smoothness, boundedness, and update assumptions of the Statement and the algorithm's Cauchy-decrease safeguard.

[F1]

A finite-budget trust-region method with ratio-based radius updates: every selected step has predicted reduction at least $θ_{C}$ times the Cauchy decrease; when $Δ_{k} \leq ∥ g_{k} ∥_{2} / (2 M_{B})$ , the algorithm uses the Cauchy step. A rejected trial multiplies the radius by $γ_{d e c}$ ; an accepted trial either keeps it or increases it, capped by $Δ_{m a x}$ .

[F2]

The Cauchy step gives a quantitative model decrease: for $g_{k} \neq 0$ , $m_{k} (0) - m_{k} (p_{C}) \geq \frac{1}{2} ∥ g_{k} ∥_{2} \min {Δ_{k}, ∥ g_{k} ∥_{2} / ∥ B_{k} ∥_{2}},$ with the zero-matrix convention stated there.

[F3]

The actual-to-predicted ratio approaches one at small radii away from stationarity: if $∥ g_{k} ∥_{2} \geq ε > 0$ and $Δ_{k} \leq \min {\frac{ε}{2 M_{B}}, \frac{θ_{C} (1 - η_{2}) ε}{2 (L + M_{B})}},$ then $ρ_{k} \geq η_{2}$ for a step with the stated Cauchy-decrease fraction. Zero denominators mean $+ \infty$ .

[F4]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $0 < q < 1$ , then $q^{j} \to 0$ as $j \to \infty$ .

[F5]

Limit superior and limit inferior of a real sequence as $\inf_{n} \sup_{k \geq n} x_{k}$ and $\sup_{n} \inf_{k \geq n} x_{k}$ in $\overline{R}$ : ${lim inf}_{k} a_{k} = \sup_{n} i_{n}$ , where $i_{n} : = \inf {a_{k} : k \geq n}$ .

[F6]

Every subset of $\overline{R}$ has a least upper bound and a greatest lower bound in $\overline{R}$ , agreeing with the real supremum and infimum on nonempty sets bounded in $R$ : every tail has a greatest lower bound in $\overline{R}$ ; it lies below every tail element and above every other lower bound.

[F7]

Upper bound, least upper bound, and strict upper bound: if every element of a set is at most $b$ , then $b$ is an upper bound and its supremum is at most $b$ .

[A1]

$f$ has a finite lower bound on $R^{n}$ .

[A2]

Every $B_{k}$ is symmetric and obeys $∥ B_{k} ∥_{2} \leq M_{B}$ .

[A3]

$\nabla f$ is $L$ -Lipschitz on each generated trial segment.

Proof

Given: The hypotheses in the Statement.

1.1givenA2A3F1F3inductionalgebra

Fix any $ε > 0$ and suppose that $∥ g_{k} ∥_{2} \geq ε$ for every $k \geq K$ . Put $d_{ε} : = \min {\frac{ε}{2 M_{B}}, \frac{θ_{C} (1 - η_{2}) ε}{2 (L + M_{B})}}, {\overset{ˉ}{d}}_{ε} : = \min {d_{ε}, Δ_{m a x}},$ where zero denominators are interpreted as $+ \infty$ . Define $r_{ε} : = \min {Δ_{K}, γ_{d e c} {\overset{ˉ}{d}}_{ε}} > 0$ . Every radius from index $K$ onward is at least $r_{ε}$ : this holds at index $K$ ; an accepted update does not shrink the radius; and a rejected update can occur only when $Δ_{k} > {\overset{ˉ}{d}}_{ε}$ , so its new radius is greater than $γ_{d e c} {\overset{ˉ}{d}}_{ε} \geq r_{ε}$ . The rejection restriction follows from [F1], [F3], and $∥ g_{k} ∥_{2} \geq ε$ ; if ${\overset{ˉ}{d}}_{ε} = Δ_{m a x}$ then rejection is impossible.

2.1givenA1A2F1F2F4step 1.1assume-contraalgebradischarge-contradiction

Suppose, for contradiction, that $∥ g_{k} ∥_{2} \geq ε$ for every $k$ after some index. An infinite block of rejections would give radii $γ_{d e c}^{j} Δ$ tending to zero by [F4], contradicting step 1.1. Thus there are infinitely many accepted steps. At every such sufficiently late step, [F2] and [F1] give $m_{k} (0) - m_{k} (p_{k}) \geq \frac{1}{2} θ_{C} ε \min {r_{ε}, ε / M_{B}} > 0,$ using the zero-matrix convention if $M_{B} = 0$ . Since acceptance means $ρ_{k} \geq η_{1}$ , each accepted step decreases $f$ by at least $η_{1}$ times this fixed positive quantity. Infinitely many such decreases contradict the lower bound [A1]. Therefore the gradients cannot eventually stay above any $ε > 0$ .

3.1step 2.1F5F6F7chooseassume-contradischarge-contradiction∎

Put $a_{k} : = ∥ g_{k} ∥_{2}$ . Since every $a_{k} \geq 0$ , zero is a lower bound of each tail; [F6] therefore gives $0 \leq i_{n} \leq a_{k}$ for every $k \geq n$ , and [F5] gives ${lim inf}_{k} a_{k} \geq 0$ . Suppose instead that ${lim inf}_{k} a_{k} > 0$ . Choose $ε > 0$ strictly below this extended-real value (take $ε = 1$ if it is $+ \infty$ ). If $i_{n} \leq ε$ for every $n$ , then [F7] makes $ε$ an upper bound for all $i_{n}$ and therefore ${lim inf}_{k} a_{k} = \sup_{n} i_{n} \leq ε$ , a contradiction. Thus some $i_{N} > ε$ , and [F6] implies $a_{k} \geq i_{N} > ε$ for all $k \geq N$ . This contradicts step 2.1. Hence the liminf is zero.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Trust-region first-order complexity counts both successful and unsuccessful trials

Statement

For every nonstationary trial of A finite-budget trust-region method with ratio-based radius updates, the selected predicted reduction is positive, and every accepted trial strictly decreases the objective.

Assume the hypotheses and parameter ranges of Cauchy-decrease trust-region iterations have liminf gradient norm zero, and let $f_{i n f}$ be a lower bound for $f$ . For each target $0 < ε \leq 1$ , consider the infinite-horizon trajectory that follows the nonterminal transition rules of A finite-budget trust-region method with ratio-based radius updates with target $ε$ , omitting its finite outer-cap return, until its first iterate with $∥ \nabla f (x_{k}) ∥_{2} \leq ε$ . Define $c_{δ} : = \min {\frac{1}{2 M_{B}}, \frac{θ_{C} (1 - η_{2})}{2 (L + M_{B})}}, c_{R} : = \min {Δ_{0}, γ_{d e c} \min {c_{δ}, Δ_{m a x}}},$ where a zero denominator means $+ \infty$ , and put $c_{P} : = \min {c_{R}, 1 / M_{B}}, c_{S} : = \frac{1}{2} η_{1} θ_{C} c_{P} > 0.$ Then the number $N_{s}$ of accepted steps before reaching the target and the number $N_{u}$ of rejected trials obey $N_{s} \leq \frac{f (x_{0}) - f_{i n f}}{c_{S} ε^{2}},$ $N_{u} \leq \frac{\log (Δ_{0} / r_{ε}) + N_{s} \log γ_{i n c}}{∣ \log γ_{d e c} ∣}, r_{ε} : = \min {Δ_{0}, γ_{d e c} \min {c_{δ} ε, Δ_{m a x}}} .$ Here $\log$ denotes the natural logarithm of a positive real. Consequently, accepted steps and total trials $N_{s} + N_{u}$ are $O (ε^{- 2})$ as $ε ↓ 0$ . An outer cap at least the resulting total-trial bound suffices for the finite-budget algorithm to return target-achieved or stationary, with gradient norm at most $ε$ .

Facts & Assumptions

Given: The model-Hessian bound, gradient Lipschitz bound, bounded-below objective, parameter ranges, and step safeguard of the trust-region method.

[F1]

A finite-budget trust-region method with ratio-based radius updates: each step has predicted reduction at least $θ_{C}$ times the Cauchy decrease; a rejection multiplies $Δ$ by $γ_{d e c}$ ; an accepted update multiplies it by a factor in $[1, γ_{i n c}]$ , respecting $Δ_{m a x}$ .

[F2]

The Cauchy step gives a quantitative model decrease: if $a : = ∥ g_{k} ∥_{2} > 0$ , then $m_{k} (0) - m_{k} (p_{C}) \geq \frac{1}{2} a \min {Δ_{k}, a / ∥ B_{k} ∥_{2}},$ with the zero-matrix convention stated there.

[F3]

The actual-to-predicted ratio approaches one at small radii away from stationarity: when $a \geq ε$ and $Δ_{k} \leq c_{δ} ε$ , the algorithm's small-radius branch gives $ρ_{k} \geq η_{2}$ and uses the boundary Cauchy step, so rejection is impossible.

[F4]

The natural logarithm as the inverse of the exponential function: $\log x$ is defined for $x > 0$ as the inverse of the real exponential.

[F5]

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: $\log$ is strictly increasing, $\log 1 = 0$ , and the product and quotient laws hold for positive arguments.

[F6]

The natural logarithm is bounded above by its positive argument minus one: $0 \leq \log y \leq y - 1 \leq y$ for $y \geq 1$ .

[F7]

Every complete ordered field is Archimedean: for every real $R$ there is an integer $m \in N$ with $m > R$ .

[F8]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $0 < q < 1$ , then $q^{j} \to 0$ as $j \to \infty$ .

[A1]

The target satisfies $0 < ε \leq 1$ .

[A2]

Every model matrix is symmetric with norm at most $M_{B}$ , and the gradient is $L$ -Lipschitz on every trial segment.

[A3]

The objective satisfies $f (x) \geq f_{i n f}$ at all iterates.

Proof

Given: The hypotheses in the Statement.

1.1givenA1A2F1F3inductionalgebra

Let ${\overset{ˉ}{δ}}_{ε} : = \min {c_{δ} ε, Δ_{m a x}}$ . Every radius during a pre-target trial is at least $r_{ε} = \min {Δ_{0}, γ_{d e c} {\overset{ˉ}{δ}}_{ε}} > 0.$ Indeed, this holds initially. If a trial is rejected, [F3] implies its radius exceeded ${\overset{ˉ}{δ}}_{ε}$ , since at or below that threshold the ratio is at least $η_{2}$ ; after multiplication by $γ_{d e c}$ the new radius is greater than $γ_{d e c} {\overset{ˉ}{δ}}_{ε}$ . An accepted update does not decrease the radius. Induction proves the bound.

1.2F1F2givencasesalgebra

For any nonstationary trial, $∥ g_{k} ∥_{2} > 0$ and $Δ_{k} > 0$ . By [F2], the Cauchy step has $P_{C} > 0$ . The selection rule either chooses a candidate with predicted decrease at least $θ_{C} P_{C}$ , or uses $p_{C}$ ; the small-radius override also uses $p_{C}$ . Since $0 < θ_{C} \leq 1$ , every branch therefore gives $P_{k} \geq θ_{C} P_{C} > 0$ , so the ratio in the algorithm is defined.

2.1givenA1A2A3F1F2F3F7F8step 1.1chooseassume-contradischarge-contradictionalgebra

If the target were never reached, every rejection block would be finite: an infinite block would multiply a fixed radius by $γ_{d e c}^{j} \to 0$ by [F8], eventually making $Δ \leq {\overset{ˉ}{δ}}_{ε}$ , where [F3] forbids rejection. Thus an infinite pre-target run would contain infinitely many accepted trials. For any accepted trial its starting gradient norm $a$ exceeds $ε$ . From step 1.1, $Δ_{k} \geq r_{ε} \geq c_{R} ε$ , because $ε \leq 1$ and $\min {c_{δ} ε, Δ_{m a x}} \geq ε \min {c_{δ}, Δ_{m a x}} .$ Since $Δ_{0} \geq ε Δ_{0}$ , taking the minimum with $Δ_{0}$ in the definition of $r_{ε}$ gives $r_{ε} \geq c_{R} ε$ . Also $a / ∥ B_{k} ∥_{2} \geq ε / M_{B}$ , with the stated infinity convention if $M_{B} = 0$ . Hence $\min {Δ_{k}, a / ∥ B_{k} ∥_{2}} \geq c_{P} ε .$ By [F1] and [F2], the predicted reduction is at least $\frac{1}{2} θ_{C} c_{P} ε^{2}$ . Acceptance gives actual decrease at least $η_{1}$ times this amount, namely $c_{S} ε^{2}$ . If the target were never reached, after $m$ accepted trials the objective would be at most $f (x_{0}) - m c_{S} ε^{2}$ . By [F7] choose an integer $m > (f (x_{0}) - f_{i n f}) / (c_{S} ε^{2})$ ; this contradicts [A3]. Therefore the target is reached after finitely many accepted trials. Summing their decreases gives $N_{s} c_{S} ε^{2} \leq f (x_{0}) - f_{i n f}$ , the claimed successful-step bound.

2.2givenF1F4F5step 1.1algebra

Let $Δ_{T}$ be the radius after the accepted trial that first reaches the target. Each rejected trial multiplies the radius by $γ_{d e c}$ ; each accepted update multiplies it by some $r_{j} \in [1, γ_{i n c}]$ . Therefore $Δ_{T} = Δ_{0} γ_{d e c}^{N_{u}} \prod_{j = 1}^{N_{s}} r_{j} .$ Step 1.1 gives $Δ_{T} \geq r_{ε}$ . By [F5], $\log γ_{d e c} < 0$ , and logarithms of positive products give $\log Δ_{T} = \log Δ_{0} + N_{u} \log γ_{d e c} + \sum_{j = 1}^{N_{s}} \log r_{j} .$ Rearranging and using $\log r_{j} \leq \log γ_{i n c}$ yields $N_{u} ∣ \log γ_{d e c} ∣ = \log (Δ_{0} / Δ_{T}) + \sum_{j = 1}^{N_{s}} \log r_{j} \leq \log (Δ_{0} / r_{ε}) + N_{s} \log γ_{i n c},$ which proves the rejection bound, including every rejected trial.

3.1givenF5F6step 2.1step 2.2algebra

Since $r_{ε} \geq c_{R} ε$ for $0 < ε \leq 1$ , [F5] gives $\log (Δ_{0} / r_{ε}) \leq \log (Δ_{0} / (c_{R} ε)) = \log (Δ_{0} / c_{R}) + \log (1 / ε) .$ By [F6], $\log (1 / ε) \leq 1 / ε$ ; since $0 < ε \leq 1$ , $1 / ε \leq 1 / ε^{2}$ . Thus the radius term is $O (ε^{- 2})$ , as is $N_{s}$ by step 2.1, so $N_{s} + N_{u} = O (ε^{- 2})$ . If the finite outer cap allows at least that many trials, the process reaches the target before the cap.

4.1F1step 1.2algebra∎

On an accepted trial, $ρ_{k} \geq η_{1} > 0$ and $P_{k} > 0$ by step 1.2. Thus $f (x_{k + 1}) = f (x_{k}) - ρ_{k} P_{k} < f (x_{k})$ , proving strict decrease at every accepted trial.

TheoremStatement: Literature-sourcedProof: AI-adaptedOpen item page →

Adaptive cubic regularization reaches first-order accuracy in O(ε⁻³ᐟ²) evaluations

Statement

Let $n \geq 1$ , and let $f : R^{n} \to R$ be $C^{2}$ and bounded below by $f_{i n f}$ . Run Finite-budget adaptive regularization using cubic models with exact Hessians and parameters $0 < η_{1} < η_{2} < 1$ , $γ_{u p} > 1$ , $0 < γ_{d o w n} < 1$ , $0 < κ < 1$ , $0 < κ_{θ} < 1$ , and $0 < σ_{m i n} \leq σ_{k} \leq σ_{m a x}$ with $σ_{m a x} \geq 3 L$ . Suppose the Hessian is $L$ -Lipschitz on every trial segment, and let $0 < ε \leq 1$ . Let $R \in N_{0}$ satisfy $γ_{u p}^{R} σ_{m i n} \geq 3 L$ (take $R = 0$ if $σ_{m i n} \geq 3 L$ ).

For the counts below, use the trajectory that follows the trial, acceptance/rejection, and regularization-update rules of Finite-budget adaptive regularization using cubic models with its finite outer-cap return omitted. The finite-cap conclusion then reinstates that return.

The algorithm has two complexity guarantees.

Exact model minimizers. If every solver call returns an exact global minimizer, define $C_{g} : = σ_{m a x} + \sqrt{n} L, c_{g} : = \frac{η_{1} σ_{m i n}}{6 C_{g}^{3 / 2}} .$ Through the first iterate with gradient norm at most $ε$ , the numbers $N_{s}$ of accepted steps and $N_{u}$ of rejected trials satisfy $N_{s} \leq [f (x_{0}) - f_{i n f}] c_{g}^{- 1} ε^{- 3 / 2} + 1, N_{u} \leq R N_{s} .$
Admissible inexact model steps. Suppose each solver-success candidate passes the cubic solution, residual, and Cauchy-decrease checks in Finite-budget adaptive regularization using cubic models, and $\nabla f$ is $K$ -Lipschitz on every trial segment. If the solver succeeds at every nonterminal trial, define $D_{g} : = \frac{σ_{m a x} + \sqrt{n} L + κ_{θ} K}{1 - κ_{θ}}, c_{a} : = \frac{η_{1} σ_{m i n}}{6 D_{g}^{3 / 2}} .$ Then the same counts satisfy $N_{s} \leq [f (x_{0}) - f_{i n f}] c_{a}^{- 1} ε^{- 3 / 2} + 1, N_{u} \leq R N_{s} .$

In either case the uncapped process reaches a stationary or target-achieved iterate with gradient norm at most $ε$ . For the finite-cap algorithm, an outer cap at least $(R + 1) (\frac{f (x_{0}) - f_{i n f}}{c ε^{3 / 2}} + 1)$ suffices, where $c = c_{g}$ in case 1 and $c = c_{a}$ in case 2. The resulting number of outer trials, and their function, gradient, and Hessian evaluation counts, are $O (ε^{- 3 / 2})$ . These counts do not bound the internal work of the model solver.

Facts & Assumptions

Given: The smoothness, lower-bound, solver, and weight assumptions of the Statement and the ARC update rules.

[F1]

Finite-budget adaptive regularization using cubic models: a trial is accepted exactly when $ρ_{k} \geq η_{1}$ ; rejected trials leave $x_{k}$ unchanged and increase $σ_{k}$ by the capped factor $γ_{u p}$ . A solver-success candidate passes the two cubic solution conditions and residual bound in its Definition.

[F2]

Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease: every global model minimizer has zero cubic-model gradient and model decrease at least $σ_{k} ∥ s_{k} ∥_{2}^{3} / 6$ when $g_{k} \neq 0$ ; every candidate satisfying the two cubic solution conditions has the same decrease bound.

[F3]

Cubic regularization bounds consecutive unsuccessful trials: with an $L$ -Lipschitz Hessian, exact Hessians, solver candidates satisfying the cubic decrease conditions, $σ_{m a x} \geq 3 L$ , and the stated regularization updates, every block of rejected trials has length at most $R$ .

[F4]

The Hessian of a $C^{2}$ scalar field is symmetric: the Hessian of a $C^{2}$ scalar field is symmetric.

[F5]

The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ : a scalar function continuous on a closed interval and differentiable in its interior has an interior point where its derivative equals its endpoint slope.

[F6]

Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1: $∥ A v ∥_{2} \leq ∥ A ∥_{2} ∥ v ∥_{2}$ .

[F7]

[F8]

The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ : each standard coordinate vector has Euclidean norm $1$ , and the Euclidean norm is induced by the standard inner product.

[A1]

The Hessian is $L$ -Lipschitz on every trial segment.

[A2]

The objective satisfies $f (x) \geq f_{i n f}$ for all $x$ .

[A3]

The weights remain in $[σ_{m i n}, σ_{m a x}]$ and $σ_{m a x} \geq 3 L$ .

Proof

Given: The hypotheses in the Statement.

1.1givenA1F4F5F6F7algebra

On any trial segment, put $s = s_{k}$ and, for each coordinate $i$ , let $e_{i}$ be its standard basis vector and $r_{i} (t) : = e_{i}^{T} (\nabla f (x_{k} + t s) - g_{k} - t B_{k} s), 0 \leq t \leq 1.$ Since $B_{k} = \nabla^{2} f (x_{k})$ by the algorithm and [F4] confirms its symmetry, $r_{i} (0) = 0$ and $r_{i}^{'} (t) = e_{i}^{T} (\nabla^{2} f (x_{k} + t s) - B_{k}) s .$ By [A1], [F6], [F7], and [F8], $∣ r_{i}^{'} (t) ∣ \leq L t ∥ s ∥_{2}^{2}$ . Applying [F5] to $r_{i}$ on $[0, 1]$ gives $∣ r_{i} (1) ∣ \leq L ∥ s ∥_{2}^{2}$ . Consequently, $∥ \nabla f (x_{k} + s) - g_{k} - B_{k} s ∥_{2} \leq \sqrt{n} L ∥ s ∥_{2}^{2} .$

2.1givenA1A2F1F2F5step 1.1algebra

In case 1, at a nonstationary accepted trial, the exact model-minimizer condition in [F2] and step 1.1 yield $∥ \nabla f (x_{k + 1}) ∥_{2} \leq (σ_{k} + \sqrt{n} L) ∥ s_{k} ∥_{2}^{2} \leq C_{g} ∥ s_{k} ∥_{2}^{2} .$ If the accepted trial is nonterminal, then $∥ \nabla f (x_{k + 1}) ∥_{2} > ε$ , so $∥ s_{k} ∥_{2} > (ε / C_{g})^{1 / 2}$ . By [F2], its predicted reduction is greater than $σ_{m i n} (ε / C_{g})^{3 / 2} / 6$ . Acceptance therefore decreases $f$ by more than $c_{g} ε^{3 / 2}$ . Summing over nonterminal accepted trials and using [A2] bounds their number by $[f (x_{0}) - f_{i n f}] / (c_{g} ε^{3 / 2})$ . At most one further accepted trial reaches the first iterate with gradient norm at most $ε$ .

2.2givenA1F1F5F6F7step 1.1algebra

In case 2, let $s = s_{k}$ , $r = ∥ s ∥_{2}$ , $g = g_{k}$ , and $g^{+} = \nabla f (x_{k} + s)$ . The candidate residual check in [F1] gives $∥ g + B_{k} s + σ_{k} r s ∥_{2} \leq κ_{θ} \min {1, r} ∥ g ∥_{2} .$ Step 1.1 and the triangle inequality therefore imply $∥ g^{+} ∥_{2} \leq (σ_{m a x} + \sqrt{n} L) r^{2} + κ_{θ} \min {1, r} ∥ g ∥_{2} .$ By the $K$ -Lipschitz gradient assumption, $∥ g ∥_{2} \leq ∥ g^{+} ∥_{2} + K r$ . Substitution and $r \min {1, r} \leq r^{2}$ give $(1 - κ_{θ} \min {1, r}) ∥ g^{+} ∥_{2} \leq (σ_{m a x} + \sqrt{n} L + κ_{θ} K) r^{2} .$ Since $1 - κ_{θ} \min {1, r} \geq 1 - κ_{θ} > 0$ , $∥ g^{+} ∥_{2} \leq D_{g} r^{2}$ .

3.1givenF1F3step 2.1algebra

In case 1 an infinite nonterminal run would have infinitely many accepted trials: solver calls succeed and [F3] bounds every rejection block by $R$ . Each such accepted trial decreases $f$ by more than the fixed positive $c_{g} ε^{3 / 2}$ by step 2.1, contradicting [A2]. Thus a target iterate exists. By [F3], every block of rejected trials has length at most $R$ . There is no rejected block after the first stationary or target-achieved iterate, so $N_{u} \leq R N_{s}$ . In case 1 this gives $N_{s} + N_{u} \leq (R + 1) (\frac{f (x_{0}) - f_{i n f}}{c_{g} ε^{3 / 2}} + 1) .$

3.2givenA1A2F1F2step 2.2algebra

If an accepted trial in case 2 is nonterminal, then $∥ g^{+} ∥_{2} > ε$ , so $r > (ε / D_{g})^{1 / 2}$ . The second decrease conclusion of [F2] gives predicted reduction greater than $σ_{m i n} (ε / D_{g})^{3 / 2} / 6$ . Acceptance thus decreases $f$ by more than $c_{a} ε^{3 / 2}$ . Summing over nonterminal accepted trials and using [A2] bounds their number by $[f (x_{0}) - f_{i n f}] / (c_{a} ε^{3 / 2})$ ; at most one further accepted trial reaches the first iterate with gradient norm at most $ε$ .

4.1givenF1F3step 3.2algebra∎

In case 2, solver success and [F3] likewise force infinitely many accepted trials in an infinite nonterminal run, contradicting the positive decrease in step 3.2 and [A2]. Thus a target iterate exists. The rejection count [F3] applies in case 2 as well, so $N_{u} \leq R N_{s}$ and $N_{s} + N_{u} \leq (R + 1) (\frac{f (x_{0}) - f_{i n f}}{c_{a} ε^{3 / 2}} + 1) .$ Both trial bounds are $O (ε^{- 3 / 2})$ for fixed constants. Each outer trial evaluates at most one objective, gradient, and Hessian; an additional terminal gradient check changes the count by at most one. Taking the cap $N$ at least the corresponding bound prevents budget exhaustion before a stationary or target-achieved iterate.

5 · Examples, counterexamples and false statements

None yet.

Trust region and cubic regularization methods

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Quadratic trust-region models and the actual-to-predicted reduction ratio

Definition

The cubic-regularized quadratic model

Definition

The natural logarithm is bounded above by its positive argument minus one

Statement

Facts & Assumptions

Proof

Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case

Statement

Facts & Assumptions

Proof

The Cauchy step for a quadratic trust-region model

Definition

Positive-definite Newton and dogleg steps are well-defined

Statement

Facts & Assumptions

Proof

Global cubic minimizers, admissible inexact steps, and cubic Cauchy decrease

Statement

Facts & Assumptions

Proof

The Cauchy step gives a quantitative model decrease

Statement

Facts & Assumptions

Proof

Dogleg steps for positive-definite trust-region models

Definition

Truncated conjugate gradients with boundary and negative-curvature exits

Definition

Finite-budget adaptive regularization using cubic models

Definition

Truncated-CG iterates are feasible and lie in generated Krylov subspaces

Statement

Facts & Assumptions

Proof

A finite-budget trust-region method with ratio-based radius updates

Definition

The actual-to-predicted ratio approaches one at small radii away from stationarity

Statement

Facts & Assumptions

Proof

Cubic regularization bounds consecutive unsuccessful trials

Statement

Facts & Assumptions

Proof

Cauchy-decrease trust-region iterations have liminf gradient norm zero

Statement

Facts & Assumptions

Proof

Trust-region first-order complexity counts both successful and unsuccessful trials

Statement

Facts & Assumptions

Proof

Adaptive cubic regularization reaches first-order accuracy in O(ε⁻³ᐟ²) evaluations

Statement

Facts & Assumptions

Proof

5 · Examples, counterexamples and false statements

Sources