ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

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$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

23 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.