LemmaStatement: Literature-sourcedProof: AI-adaptedPipeline-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.

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.

Depends on

Used by

Cited to discharge well-definedness by Finite-budget adaptive regularization using cubic models.

Dependency tree · two levels

63 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint, Adaptive cubic overestimation methods for unconstrained optimization. Part I: motivation, convergence and numerical results (author preprint) (standard reference, not scraped)
Coralia Cartis, Nicholas I. M. Gould, and Philippe L. Toint, Adaptive cubic overestimation methods for unconstrained optimization. Part II: worst-case iteration complexity (author preprint) (standard reference, not scraped)