Alphabeta Math
TheoremStatement: AI-adaptedProof: AI-adaptedPipeline-generatedprecheck pass
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.

Finite SQP status is sound and the exact local branch inherits OPT6 conditions

Statement

Every active-kkt-residual-certified return of Finite-budget active-set SQP with a certified KKT-system residual status with reported bound η satisfies the exact active linear solve residual bound ∥Ks+FA(z)∥2≤η≤τ. For a quadratic FE reduced objective with affine equality constraints and affine active inequalities, in particular a program constrained only by a box, this also bounds the exact active KKT residual of the returned next point. On a nonlinear reduced problem, if the true active set is identified and the OPT6 hypotheses hold, exact-arithmetic full steps started sufficiently close converge quadratically to the active KKT pair. The finite-precision residual bound alone does not imply forward error, box optimality, or an SQP accuracy rate.

Facts & Assumptions

Given: A returned finite-budget status and its active set, computed residual upper bound, and, for the separate local convergence statement, a nonlinear program satisfying the stated OPT6 conditions.

[F1]

The finite algorithm returns the finite-precision QR vector as its step and reports active-kkt-residual-certified only after checking η≤τ; it does not label box feasibility or global optimality (Finite-budget active-set SQP with a certified KKT-system residual status).

[F2]

The OPT6 QR certificate bounds the exact residual of its active KKT linear system; the corresponding solution error additionally depends on ∥K−1∥ (The computed KKT residual certificate bounds the exact linear-system residual).

[F3]

The exact Hessian/local branch has quadratic convergence under identified active set, LICQ, strict complementarity, positive reduced curvature, locally Lipschitz Jacobian, and a sufficiently close start (Exact-Hessian SQP converges quadratically on the identified active KKT system).

[A1]

The QR residual certificate’s floating-point assumptions and no-overflow checks hold on any returned certified branch.

Proof

1.1A1F1F2givenalgebra

By [F1], a certified return contains a computed linear solve residual bound η≤τ. Applying [F2] gives the exact inequality ∥Ks+FA(z)∥2≤η≤τ. The theorem supplies no smaller bound unless the reported η is smaller.

2.1F1step 1.1givenalgebra

Write the quadratic objective as ϕ(x)=12xTQx+cTx+c0 with symmetric Q, and stack all equalities and active inequalities as cA(x)=Gx−d. With their stacked multiplier μ, the algorithm's convention gives FA(x,μ)=(Qx+c+GTμ,Gx−d) and K=[QGTG0]. Thus FA is affine in the combined primal-dual variable and FA(z+s)=FA(z)+Ks. Step 1.1 therefore bounds the returned point's active KKT residual. Affine box inequalities alone do not give this identity when an equality constraint is nonlinear.

3.1F3givenalgebra∎

In the separate exact local branch, the hypotheses listed in [F3] imply the active KKT Jacobian is nonsingular and locally Lipschitz. The cited OPT6 Newton theorem then applies to the exact full-step active-system iteration started sufficiently near its root and gives quadratic convergence. This conclusion is conditional on those hypotheses and is independent of finite-budget status.

Remarks

The exact local convergence conclusion remains conditional on the OPT6 hypotheses and is independent of this finite-budget residual status. No exact-solve status implies a small forward error without a bound on the inverse active KKT matrix.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 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