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.

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 B 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 E and inequality support J of its KKT certificate.

Facts & Assumptions

Given: The exact-arithmetic algorithm and a subproblem with positive- definite B.

[A1]

The equality rows retained by the algorithm are independent and their right-hand sides define the same consistent equality set as the original rows.

[F1]

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.

[F2]

The SQP KKT matrix is nonsingular under positive reduced curvature: if the active/equality rows are independent and B is positive definite on their null space, the KKT matrix is nonsingular.

[F3]

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 E and J.

Proof

1.1A1F3algebra

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.

1.2givenF2F3algebra

For any enumerated subset whose rows are independent, the KKT matrix is nonsingular by [F2], because B 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 pˉ. For every feasible y, stationarity and complementarity give (Bpˉ+c)T(y−pˉ)=−∑iλiGi(y−pˉ)≥0, since only active inequalities have positive multipliers. Thus q(y)−q(pˉ)=(Bpˉ+c)T(y−pˉ)+12(y−pˉ)TB(y−pˉ)≥0, with equality only for y=pˉ. Hence the accepted candidate is the unique global minimizer.

2.1A1F1F2F3

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.

3.1F1F3step 1.1step 1.2step 2.1∎

There are exactly 2m 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

Used by

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