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 . 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.
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).
The OPT6 QR certificate bounds the exact residual of its active KKT linear system; the corresponding solution error additionally depends on (The computed KKT residual certificate bounds the exact linear-system residual).
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).
The QR residual certificate’s floating-point assumptions and no-overflow checks hold on any returned certified branch.
Proof
By [F1], a certified return contains a computed linear solve residual bound . Applying [F2] gives the exact inequality . The theorem supplies no smaller bound unless the reported is smaller.
Write the quadratic objective as with symmetric , and stack all equalities and active inequalities as . With their stacked multiplier , the algorithm's convention gives and . Thus is affine in the combined primal-dual variable and . 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.
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
- Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed. (standard reference, not scraped)