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 exhaustive active-set QP solve terminates with the unique minimizer exactly when feasible
Statement
For the SQP subproblem of The linearized quadratic subproblem in sequential quadratic programming with
symmetric positive definite, the exact algorithm of
Exact exhaustive active-set solve for the SQP quadratic subproblem terminates after finitely many
subset tests. It returns QP-infeasible exactly when the subproblem's
polyhedron is empty; otherwise it returns the unique global minimizer, full
equality and inequality multiplier vectors, and the retained equality basis
and inequality support of its KKT certificate.
Facts & Assumptions
Given: The exact-arithmetic algorithm and a subproblem with positive- definite .
The equality rows retained by the algorithm are independent and their right-hand sides define the same consistent equality set as the original rows.
A feasible strictly convex linear-constrained QP has a unique KKT minimizer with independent active support: feasibility gives a unique minimizer with a KKT certificate supported on a set of active rows independent together with the equality rows.
The SQP KKT matrix is nonsingular under positive reduced curvature: if the active/equality rows are independent and is positive definite on their null space, the KKT matrix is nonsingular.
Exact exhaustive active-set solve for the SQP quadratic subproblem tests every inequality subset in a finite order and accepts only feasible candidates with nonnegative selected inequality multipliers; it returns their multipliers expanded to the original equality and inequality indices, together with and .
Proof
The equality reduction is finite: there are finitely many row subsets to check, and exact rank and consistency tests decide each one. Under [A1] it preserves the equality feasible set; if it reports inconsistency, that set is empty and the full QP is infeasible.
For any enumerated subset whose rows are independent, the KKT matrix is nonsingular by [F2], because is positive definite on every subspace. Thus its equality-constrained candidate is uniquely defined. If that candidate passes the inequality feasibility and multiplier-sign filters, its zero-extended multipliers give a feasible KKT tuple for the original QP, with primal point . For every feasible , stationarity and complementarity give , since only active inequalities have positive multipliers. Thus , with equality only for . Hence the accepted candidate is the unique global minimizer.
If the QP is feasible, [F1] supplies an active KKT support whose rows are independent together with the reduced equality rows. [F3] therefore tests that support. The solve in step 1.2 returns its KKT point, and its feasibility and nonnegative multipliers make it pass both filters. Hence the algorithm cannot report QP-infeasible on a feasible subproblem.
There are exactly inequality subsets. Every subset requires only finitely many exact rank, solve, and feasibility operations, so [F3] terminates. If no candidate was found, step 2.1 shows the QP is infeasible; if a candidate was found, step 1.2 shows it is the unique minimizer with the returned full KKT multipliers and support data.
Depends on
- A feasible strictly convex linear-constrained QP has a unique KKT minimizer with independent active support
- Exact exhaustive active-set solve for the SQP quadratic subproblem
- The SQP KKT matrix is nonsingular under positive reduced curvature
- The linearized quadratic subproblem in sequential quadratic programming
Used by
- Two-component design with an active demand constraint Example
- Finite merit-globalization budgets return a defined status Theorem
Cited to discharge well-definedness by Exact exhaustive active-set solve for the SQP quadratic subproblem.
Dependency tree · two levels
11 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)