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 — Examples

1 · Prerequisites

2 · Summary

An indefinite quadratic has a unique boundary trust-region minimizer computes an indefinite trust-region problem with a unique boundary minimizer and compares it with the Cauchy step. A singular shifted Hessian produces two hard-case minimizers exhibits two minimizers from a singular shifted Hessian. The final example Newton, Cauchy, and truncated-CG steps on one indefinite model compares the infeasible raw Newton direction, the feasible Cauchy point, and a truncated-CG boundary exit on the same quadratic, then checks the inexact-Newton descent test and strong Wolfe acceptance directly.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

An indefinite quadratic has a unique boundary trust-region minimizer

Example

Take $n = 2$ , $Δ = 1$ , $B = diag (- 1, 1)$ , and $g = (- 1, - 3) / \sqrt{2}$ . The model Hessian is indefinite. The exact global trust-region minimizer is a unique boundary point, while the Cauchy step is a different feasible boundary point with a strictly smaller predicted decrease.

Facts & Assumptions

Given: The trust-region model of Quadratic trust-region models and the actual-to-predicted reduction ratio, the optimality characterization of Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case, and the Cauchy procedure of The Cauchy step for a quadratic trust-region model.

[F1]

The model is $m (p) = f (x) + g^{T} p + \frac{1}{2} p^{T} B p$ and feasibility is $∥ p ∥_{2} \leq 1$ (Quadratic trust-region models and the actual-to-predicted reduction ratio).

[F2]

A feasible $p$ satisfying the shifted-Hessian equation, positive semidefiniteness, and multiplier complementarity is a global minimizer (Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case).

[F3]

For $g^{T} B g > 0$ , the Cauchy step is $p_{C} = - \min {∥ g ∥_{2}^{2} / (g^{T} B g), Δ / ∥ g ∥_{2}} g$ (The Cauchy step for a quadratic trust-region model).

Proof

1.1givenF1F2algebra

Set $p_{*} = (1, 1) / \sqrt{2}$ . Then $∥ p_{*} ∥_{2} = 1$ , $(B + 2 I) p_{*} = (1, 3) / \sqrt{2} = - g$ , and $B + 2 I = diag (1, 3)$ is positive definite. With $λ = 2$ , complementarity holds at the boundary, so [F2] gives a global minimizer. For any other feasible $z \neq p_{*}$ , expansion gives $m (z) - m (p_{*}) = \frac{1}{2} (z - p_{*})^{T} (B + 2 I) (z - p_{*}) + (1 - ∥ z ∥_{2}^{2}) > 0,$ because the first term is strictly positive and the second nonnegative; hence the minimizer is unique.

2.1givenF1F3algebra∎

The global minimizer has $g^{T} p_{*} = - 2$ and $p_{*}^{T} B p_{*} = 0$ , so its predicted reduction is $2$ . For the Cauchy step, $∥ g ∥_{2}^{2} = 5$ and $g^{T} B g = 4$ , hence [F3] gives $p_{C} = (1, 3) / \sqrt{10}$ and $∥ p_{C} ∥_{2} = 1$ . Its model value is $m (p_{C}) = f (x) - \sqrt{5} + 2 / 5$ , so its predicted reduction is $\sqrt{5} - 2 / 5 < 2$ ; the strict inequality follows from $\sqrt{5} < 12 / 5$ .

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

A singular shifted Hessian produces two hard-case minimizers

Example

Take $n = 2$ , $Δ = 1$ , $B = diag (- 2, 1)$ , and $g = (0, 1)$ . The gradient is orthogonal to the most negative eigenspace. The singular multiplier leaves a free component in that eigenspace, and the boundary condition produces two distinct global minimizers.

Facts & Assumptions

Given: The model definition Quadratic trust-region models and the actual-to-predicted reduction ratio and the necessary-and-sufficient global optimality result Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case.

[F1]

The model quadratic part is $q (p) = g^{T} p + \frac{1}{2} p^{T} B p$ and its feasible set is $∥ p ∥_{2} \leq 1$ (Quadratic trust-region models and the actual-to-predicted reduction ratio).

[F2]

Feasible points satisfying the shifted-Hessian conditions are global minimizers (Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case).

Proof

1.1givenF1algebra

The least eigenvalue is $μ = - 2$ with eigenspace $E_{μ} = span {(1, 0)}$ , and $g ⊥ E_{μ}$ . The equation $(B - μ I) p_{0} = - g$ with $p_{0} ⊥ E_{μ}$ gives $p_{0} = (0, - 1 / 3)$ , so $∥ p_{0} ∥_{2} = 1 / 3 < 1$ . The missing boundary component has squared norm $1 - 1 / 9 = 8 / 9$ .

2.1givenF1F2step 1.1algebra∎

Let $p_{\pm} = (\pm 2 \sqrt{2} / 3, - 1 / 3)$ . Each has norm $1$ , and $(B + 2 I) p_{\pm} = (0, - 1) = - g$ with $B + 2 I = diag (0, 3) ⪰ 0$ . Thus both satisfy [F2] with $λ = 2$ and are global minimizers. They are distinct, and each has $q (p_{\pm}) = - \frac{1}{3} + \frac{1}{2} (- 2 \cdot \frac{8}{9} + \frac{1}{9}) = - \frac{7}{6} .$ This verifies the singular hard case and its two boundary choices.

ExampleConstruction: AI-generatedVerification: AI-generatedOpen item page →

Newton, Cauchy, and truncated-CG steps on one indefinite model

Example

Let $f (z) = g^{T} z + \frac{1}{2} z^{T} B z$ on $R^{2}$ , where $B = diag (- 1, 1)$ , $g = (- 1, - 3) / \sqrt{2}$ , and the trust-region radius is $Δ = 1$ . The raw Newton direction is outside the ball but satisfies the exact inexact-Newton descent safeguard and a strong Wolfe line search accepts its full step. The Cauchy and first truncated-CG boundary steps coincide and have smaller predicted reduction. For the inexact-Newton call take $M \geq 2$ , $N \geq 1$ , $η_{k} = \overset{ˉ}{η} = 0$ , $σ = 1 / 2$ , $J = 0$ , $E, Z \geq 1$ , $γ = 2$ , and $λ_{0} = λ_{\max} = 1$ ; use the deterministic two-dimensional projected solver specified in step 1.1 with iteration count $m = 2$ , returning no-candidate if its two-dimensional basis or projected matrix is singular or if $M < 2$ .

Facts & Assumptions

Given: The quadratic trust-region model, the displayed $B, g, Δ$ , the Cauchy and truncated-CG procedures, and the supplied inexact-Newton and strong-Wolfe line-search algorithms.

[F1]

Quadratic trust-region models and the actual-to-predicted reduction ratio: $m (p) = f (0) + g^{T} p + \frac{1}{2} p^{T} B p$ and feasible steps satisfy $∥ p ∥_{2} \leq 1$ .

[F2]

Global trust-region minimizers satisfy the shifted-Hessian conditions, including the hard case: every feasible step satisfying $(B + λ I) p = - g$ , $B + λ I ⪰ 0$ , and $λ (1 - ∥ p ∥_{2}) = 0$ is a global trust-region minimizer.

[F3]

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

[F4]

Truncated conjugate gradients with boundary and negative-curvature exits: start with $z_{0} = 0$ , $r_{0} = g$ , $d_{0} = - g$ ; if $d_{0}^{T} B d_{0} > 0$ , set $α_{0} = ∥ r_{0} ∥_{2}^{2} / (d_{0}^{T} B d_{0})$ and, when $∥ z_{0} + α_{0} d_{0} ∥_{2} \geq Δ$ , return the positive boundary root on $z_{0} + t d_{0}$ as candidate before comparing with the Cauchy step. The unique positive root and feasibility of the selected output are established by Truncated-CG iterates are feasible and lie in generated Krylov subspaces.

[F5]

Finite-budget inexact Newton–Krylov with a descent safeguard: with zero shift, a candidate $p$ is accepted as a linear solve when $∥ B p + g ∥_{2} \leq η_{k} ∥ g ∥_{2}$ and $g^{T} p < - σ ∥ g ∥_{2} ∥ p ∥_{2}$ ; the descent fallback is $p = - g$ .

[F6]

Wolfe and strong Wolfe line-search conditions: a strong Wolfe step obeys $ϕ (t) \leq ϕ (0) + c_{1} t ϕ^{'} (0)$ and $∣ ϕ^{'} (t) ∣ \leq c_{2} ∣ ϕ^{'} (0) ∣$ , with $0 < c_{1} < c_{2} < 1 / 2$ .

[F7]

Finite-budget bracketing and zoom for a strong Wolfe step: from a descent direction, the first expansion trial is $t = 1$ and it returns that point when both strong Wolfe inequalities hold.

[F8]

The Krylov subspace $K_{m} (A, b) = span {b, A b, \dots, A^{m - 1} b}$ : $K_{2} (B, - g) = span {- g, B (- g)}$ .

Proof

Given: $B = diag (- 1, 1)$ , $g = (- 1, - 3) / \sqrt{2}$ , $Δ = 1$ , and $f (z) = g^{T} z + \frac{1}{2} z^{T} B z$ .

1.1givenF5F8algebra

The matrix $B$ is invertible and the raw Newton solution is $p_{N} = - B^{- 1} g = (- 1, 3) / \sqrt{2}$ . Direct calculation gives $B p_{N} + g = 0$ , $∥ p_{N} ∥_{2} = \sqrt{5}$ , $g^{T} p_{N} = - 4$ , $∥ g ∥_{2} ∥ p_{N} ∥_{2} = 5$ , and the unrestricted model decrease at $p_{N}$ is $- g^{T} p_{N} - \frac{1}{2} p_{N}^{T} B p_{N} = 2$ . Also $- g = (1, 3) / \sqrt{2}$ and $B (- g) = (- 1, 3) / \sqrt{2}$ are linearly independent, so [F8] gives $K_{2} (B, - g) = R^{2}$ . Put $V = [- g B (- g)]$ ; its determinant is $3$ , so the projected matrix $V^{T} B V$ is invertible because its determinant is $\det (V)^{2} \det (B) = - 9$ . Solving $V^{T} B V y = V^{T} (- g)$ gives $p = V y \in K_{2}$ with $B p + g$ orthogonal to $K_{2} = R^{2}$ , hence $B p + g = 0$ and $p = p_{N}$ . Thus a deterministic two-dimensional Galerkin Krylov solver may return $p_{N}$ . With $η_{0} = 0$ and descent parameter $σ = 1 / 2$ , [F5]'s residual and strict descent tests pass because $0 \leq 0$ and $- 4 < - 5 / 2$ .

1.2givenF1F3F4algebra

We have $∥ g ∥_{2}^{2} = 5$ and $g^{T} B g = 4$ . By [F3], $p_{C} = (1, 3) / \sqrt{10}$ and $∥ p_{C} ∥_{2} = 1$ . Its predicted reduction is $- g^{T} p_{C} - \frac{1}{2} p_{C}^{T} B p_{C} = \sqrt{5} - \frac{2}{5} .$ For truncated CG with residual tolerance zero and inner cap at least one, $d_{0} = - g$ , $d_{0}^{T} B d_{0} = 4$ , and $α_{0} = 5 / 4$ . The unconstrained point $\hat{z} = - (5 / 4) g$ has norm $5 \sqrt{5} / 4 > 1$ , so the boundary exit is $z_{0} + t_{0} d_{0}$ with $t_{0} = 1 / \sqrt{5}$ . It equals $p_{C}$ , and the final comparison in [F4] returns a step with the same predicted reduction $\sqrt{5} - 2 / 5$ .

2.1givenF6F7step 1.1algebra

For $ϕ (t) : = f (t p_{N})$ , direct substitution gives $ϕ (t) = - 4 t + 2 t^{2}$ and $ϕ^{'} (t) = - 4 + 4 t$ . Set $c_{1} = 1 / 10$ and $c_{2} = 1 / 4$ . At $t = 1$ , $ϕ (1) = - 2 \leq - 2 / 5 = c_{1} ϕ^{'} (0)$ and $∣ ϕ^{'} (1) ∣ = 0 \leq 1 = c_{2} ∣ ϕ^{'} (0) ∣$ . Thus the full step satisfies [F6]; with expansion budget at least one, [F7] returns $t = 1$ .

3.1givenF1F2step 2.1step 1.2algebra∎

The point $p_{*} = (1, 1) / \sqrt{2}$ has norm one and $(B + 2 I) p_{*} = (1, 3) / \sqrt{2} = - g$ , while $B + 2 I = diag (1, 3) ⪰ 0$ . By [F2], it is a global trust- region minimizer. Its predicted reduction is $- g^{T} p_{*} - \frac{1}{2} p_{*}^{T} B p_{*} = 2$ . The Cauchy decrease is strictly smaller because $\sqrt{5} < 12 / 5$ , which follows from $5 < 144 / 25$ . Thus the raw Newton line-search step is accepted at full length, whereas the feasible Cauchy and truncated-CG steps have the strictly smaller reduction $\sqrt{5} - 2 / 5 < 2$ .