TheoremStatement: AI-adaptedProof: 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.

The computed KKT residual certificate bounds the exact linear-system residual

Statement

Suppose Finite-precision reduced-QR KKT solve with certified residual status successfully returns $\hat{z}$ and a certified $η$ for a nonsingular square matrix $K$ and vector $b$ . Then $∥ K \hat{z} - b ∥_{2} \leq η .$ If $z_{*} = K^{- 1} b$ , then also $∥ \hat{z} - z_{*} ∥_{2} \leq ∥ K^{- 1} ∥_{2} η .$ The certificate may be large; the theorem makes no accuracy claim without an additional bound on $∥ K^{- 1} ∥_{2}$ and a small certified $η$ .

Facts & Assumptions

Given: The operationwise arithmetic hypotheses, successful reduced QR and residual computation, and the returned certificate $η$ .

[F1]

Finite-precision reduced-QR KKT solve with certified residual status returns the minimum of the rounded-residual and QR backward-error bounds.

[F2]

Rounded matrix products give certified linear and normal-equation residual allowances bounds the difference between the exact residual and the computed rounded residual.

[F3]

Computed reduced QR least squares is backward stable for full column rank supplies the QR backward representation and its perturbation bounds.

[F4]

Operationwise real and complex floating point arithmetic with rounded square roots and fused multiply-add specifies the arithmetic assumptions required by [F2] and [F3].

[F5]

The SQP KKT matrix is nonsingular under positive reduced curvature provides nonsingularity for a full-row-rank active KKT matrix with positive reduced curvature.

[A1]

The KKT matrix has full-row-rank constraints and positive curvature on their null space; all successful-operation hypotheses hold, and the stated certificate is computed without overflow.

Proof

1.1A1F1F2F3F4F5algebra

By [F1], a successful return includes successful exact-storage admission, so its stored $K, b$ equal the intended data. By [F5], $K$ is nonsingular. Put $r = K \hat{z} - b$ for those same intended data. By [F2], $∥ r ∥_{2} \leq ∥ \hat{r} ∥_{2} + W$ . By [F3], $r = δ b - Δ K \hat{z}$ , so $∥ r ∥_{2} \leq β_{b} ∥ b ∥_{2} + β_{K} ∥ K ∥_{F} ∥ \hat{z} ∥_{2}$ . These are precisely the two bounds in [F1].

2.1F1step 1.1algebra∎

Since [F1] returns their minimum, $∥ K \hat{z} - b ∥_{2} \leq η$ . The exact solution satisfies $K z_{*} = b$ , hence $K (\hat{z} - z_{*}) = r$ ; multiplying by $K^{- 1}$ gives $∥ \hat{z} - z_{*} ∥_{2} \leq ∥ K^{- 1} ∥_{2} ∥ r ∥_{2} \leq ∥ K^{- 1} ∥_{2} η$ .

Depends on

Used by

Dependency tree · two levels

15 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, 2nd ed. (standard reference, not scraped)