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.

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.

Depends on

Used by

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

Cited to discharge well-definedness by Truncated conjugate gradients with boundary and negative-curvature exits.

Dependency tree · two levels

9 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

Jorge Nocedal and Stephen J. Wright, Numerical Optimization, second edition (standard reference, not scraped)