44.04.01 · optimization-control / 04-constrained-nonlinear

Active-Set Methods for Quadratic Programming

shipped3 tiersLean: none

Anchor (Master): Nocedal & Wright 2006 Numerical Optimization 2e (Springer) Ch. 16 (§16.2 direct solution of the KKT system, §16.4 inertia-controlling factorizations, §16.5 active-set methods for convex QP, §16.7 anti-cycling and finite termination); Fletcher 1987 Practical Methods of Optimization 2e (Wiley) Ch. 10 (the active-set / working-set strategy, Lagrange-multiplier sign tests, and the link to SQP)

Intuition Beginner

A quadratic program is the simplest constrained problem with real curvature: the cost is a smooth bowl, and the rules are all straight lines or flat walls. Picture a tilted bowl resting in a room whose floor and walls are flat panels. Drop a marble in. If the bowl's lowest point sits inside the room, the marble settles there and no wall matters. If the lowest point is outside, the marble rolls until it jams against one or more walls and stops where the walls hold it.

The whole difficulty is figuring out which walls the marble ends up pressed against. That set of touched walls is called the working set. If you somehow knew it in advance, the problem would collapse: hold exactly those walls as tight rules, ignore the rest, and solve the easy bowl-with-flat-rules problem in one shot. You do not know it in advance, so you guess, solve the easy problem for that guess, and then check the guess.

Two checks correct a wrong guess. First, the step you computed might try to pass through a wall you were ignoring; if so, you stop at that wall and add it to the working set. Second, a wall you are pressing might actually be pulling you back from a better point; the sign of its price tells you, and if the price is wrong you drop that wall and let go. Each correction strictly improves matters, the walls are finite in number, so after finitely many guesses the working set is right and the marble has found its resting place.

Visual Beginner

Picture a bowl-shaped cost over a region fenced by three straight walls. The free bottom of the bowl lies outside the fenced region, so the best allowed point sits where the bowl's contours first touch the fence — pressed against one wall, or wedged into a corner where two walls meet.

   cost contours (rings around the free bottom *)
        ________________
       /    _______      \        wall 1
      /    /       \      \   ____________________
     |    |    *    |      | /
      \    \_______/      /|/   <- free bottom * is OUTSIDE
       \________________ / |        the allowed region
                  best -> o  |   working set = {wall 1}
                  feasible   | wall 2
                  x*         |
   ----------------------------------
                  wall 3 (floor)

   guess a working set  ->  solve the easy "press these walls" problem
   step crosses an idle wall?   add it (blocking constraint)
   a pressed wall has wrong-sign price?  drop it
   repeat: finitely many walls => finitely many guesses

situation	what the method does	working-set change
step stays inside the region	take the full step	none
step would cross an idle wall	stop at that wall	add the blocking wall
a pressed wall has a wrong-sign price	release it	drop that wall
full step taken and all prices right	stop: optimal	none

The takeaway: the hard part of a quadratic program is identifying the touched walls, and the active-set method finds them by guessing, solving an easy equality problem, and fixing the guess one wall at a time.

Worked example Beginner

Minimize the cost $f (x_{1}, x_{2}) = (x_{1} - 2)^{2} + (x_{2} - 1)^{2}$ — a round bowl centered at $(2, 1)$ — subject to two straight rules: $x_{1} + x_{2} \leq 2$ and $x_{1} \geq 0$ . The free bottom $(2, 1)$ breaks the first rule, since $2 + 1 = 3 > 2$ , so the best allowed point sits on a wall.

Step 1. Guess the working set. Guess that only the first wall is pressed: $x_{1} + x_{2} = 2$ . Hold that as a tight rule and find the lowest bowl point on the line.

Step 2. Solve the easy problem. On the line $x_{1} + x_{2} = 2$ , the closest point to the center $(2, 1)$ is found by stepping from the center straight toward the line. That gives $x_{1} = 1.5$ and $x_{2} = 0.5$ , which add to $2$ , so the line rule holds.

Step 3. Check the other rule. Is $x_{1} \geq 0$ ? Here $x_{1} = 1.5 \geq 0$ , so the ignored wall is not crossed. Good.

Step 4. Check the price. The pressed wall $x_{1} + x_{2} = 2$ has a price equal to $1$ , found from how hard the bowl pushes into it: the center is distance giving a positive pull outward. A positive price means the wall genuinely holds the marble back, so we keep it.

What this tells us. The guess "only the first wall is pressed" passed both checks: no ignored wall was crossed, and the pressed wall's price was positive. So $(1.5, 0.5)$ is the answer, with cost $(1.5 - 2)^{2} + (0.5 - 1)^{2} = 0.25 + 0.25 = 0.5$ . The method guessed the working set, solved a one-line problem, and confirmed the guess — the entire active-set idea in one pass.

Check your understanding Beginner

Exercise (easy, multiple choice).

While solving a quadratic program, the step you compute would carry you through a wall you were ignoring. What does the active-set method do?

Take the full step anyway and fix it later.
Stop at that wall and add it to the working set.
Drop a different wall from the working set.
Declare the problem infeasible.

Hint

The ignored wall is a rule you must not break; the step is shortened so it lands on the wall.

Answer

B. Stop at that wall and add it to the working set. Feedback-correct: correct — the wall that first blocks the step is the blocking constraint; the step length is shortened to reach it and the wall joins the working set. Feedback-wrong: you never knowingly cross a wall; the step is cut short at the first wall it would hit, and that wall is added so the next subproblem respects it.

Formal definition Intermediate+

A quadratic program (QP) in $x \in R^{n}$ is

x min q (x) = \frac{1}{2} x^{⊤} G x + c^{⊤} x subject to a_{i}^{⊤} x = b_{i} (i \in E), a_{i}^{⊤} x \geq b_{i} (i \in I),

with $G \in R^{n \times n}$ symmetric, $c \in R^{n}$ , and finitely many linear constraints indexed by $E$ (equalities) and $I$ (inequalities). The QP is convex when $G ⪰ 0$ and strictly convex when $G ≻ 0$ ; otherwise it is nonconvex (indefinite $G$ ). The feasible set is a polyhedron. At a feasible $x$ the active set $A (x) = E \cup {i \in I : a_{i}^{⊤} x = b_{i}}$ collects the equalities and the inequalities holding with equality, exactly as in 44.02.02.

Definition (equality-constrained QP and its KKT system). With all active constraints stacked as rows of $A \in R^{m \times n}$ and right-hand side $b$ , the equality-constrained QP (EQP) is $min_{x} \frac{1}{2} x^{⊤} G x + c^{⊤} x$ subject to $A x = b$ . Its first-order optimality conditions are the linear KKT (saddle-point) system

[G A A^{⊤} 0] [x^{⋆} - λ^{⋆}] = [- c b],

where $λ^{⋆}$ is the vector of multipliers; this is the QP instance of the constrained-Newton KKT matrix of 44.03.03. Writing the EQP for a step $p$ from a feasible $x$ (so $g = G x + c$ is the gradient and $A p = 0$ ) puts the system in the homogeneous-constraint form $\begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}\begin{psmallmatrix} p \\ -\lambda\end{psmallmatrix} = \begin{psmallmatrix} -g \\ 0\end{psmallmatrix}$ .

Definition (inertia condition). The inertia of a symmetric matrix $K$ is the triple $In (K) = (n_{+}, n_{-}, n_{0})$ of its numbers of positive, negative, and zero eigenvalues. The KKT matrix $K = \begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}$ with $A \in R^{m \times n}$ has the correct inertia $In (K) = (n, m, 0)$ if and only if $A$ has full row rank and $G$ is positive definite on the null space $ker A$ , i.e. the reduced Hessian $Z^{⊤} GZ ≻ 0$ for a basis $Z$ of $ker A$ . Under the correct inertia $K$ is nonsingular and the EQP has the unique minimizer given by the KKT solve.

Definition (null-space and range-space solves). Let the columns of $Z \in R^{n \times (n - m)}$ be a basis of $ker A$ and let $Y$ span a complement so that $A Y$ is nonsingular. The null-space method writes $p = Y p_{Y} + Z p_{Z}$ , fixes $p_{Y}$ from $A p = 0$ (here $p_{Y} = 0$ ), and solves the reduced system $(Z^{⊤} GZ) p_{Z} = - Z^{⊤} g$ for the free component, giving $p = - Z (Z^{⊤} GZ)^{- 1} Z^{⊤} g$ . The range-space (Schur-complement) method eliminates $p$ first, solving $(A G^{- 1} A^{⊤}) λ = A G^{- 1} g$ for the multipliers and then $Gp = - (g + A^{⊤} λ)$ ; it requires $G ≻ 0$ on all of $R^{n}$ . The new symbols $G$ (Hessian), the working set $W$ , the inertia triple $In (K)$ , and the basis matrices $Y, Z$ are recorded in _meta/NOTATION.md.

Definition (primal active-set method). A working set $W_{k} \subseteq A (x_{k})$ is a subset of active constraints whose gradients are linearly independent, treated as equalities. Starting from a feasible $x_{0}$ , each iteration solves the EQP step $p_{k}$ over $W_{k}$ (constraints in $W_{k}$ held to $A p_{k} = 0$ ), then takes $x_{k + 1} = x_{k} + α_{k} p_{k}$ with step length

α_{k} = min (1, i \in / W_{k}, a_{i}^{⊤} p_{k} < 0 min \frac{a _{i}^{⊤} x _{k} - b _{i}}{- a _{i}^{⊤} p _{k}}) .

If $α_{k} < 1$ the minimizing index is a blocking constraint, added to $W_{k + 1}$ . If $α_{k} = 1$ and the EQP multipliers satisfy $λ_{i} \geq 0$ for all $i \in W_{k} \cap I$ , the point is optimal; otherwise the most-negative-multiplier constraint is dropped from the working set.

Counterexamples to common slips

Nonconvex QP is NP-hard, not merely "Newton with constraints." When $G$ is indefinite, the QP can have exponentially many local minima and checking global optimality is NP-hard; the primal active-set method finds a KKT point but not necessarily a global minimizer. Convexity ( $G ⪰ 0$ ) is exactly what makes every KKT point global, by 44.02.02.
The full Hessian need not be positive definite for the EQP to be well posed. The KKT matrix is nonsingular under the inertia condition — $G ≻ 0$ only on $ker A$ , plus $A$ full row rank — even when $G$ is indefinite on $R^{n}$ . Demanding $G ≻ 0$ globally is the range-space method's hypothesis, not the EQP's.
A multiplier becoming negative does not mean the iterate is wrong; it means a wall should be released. A working-set constraint with $λ_{i} < 0$ is one the objective would prefer to cross; dropping it and re-solving strictly decreases $q$ . Keeping it because "it was active" stalls the method short of the optimum.

Key theorem with proof Intermediate+

The signature result is the finite termination of the primal active-set method on a strictly convex QP. It isolates the two mechanisms — strict decrease of the objective whenever a constraint is dropped, and the impossibility of repeating a working set without cycling — that make a finite, combinatorial search over working sets converge to the global solution.

Theorem (finite termination of the primal active-set method, strictly convex QP). Let $G ≻ 0$ and suppose the QP is feasible. Starting from a feasible point with a working set of linearly independent active constraints, and resolving ties by an anti-cycling rule (Bland's rule or a lexicographic perturbation), the primal active-set method reaches the unique global minimizer in finitely many iterations.

Proof. Each iteration solves the EQP over the current working set $W_{k}$ . Since $G ≻ 0$ , the reduced Hessian $Z_{k}^{⊤} G Z_{k} ≻ 0$ for any $Z_{k}$ spanning $ker A_{W_{k}}$ , so by the inertia condition the KKT matrix is nonsingular and the EQP step $p_{k}$ is the unique minimizer of $q$ on the affine set ${x_{k} + p : A_{W_{k}} p = 0}$ . Two cases.

If $p_{k} \neq = 0$ , then $q$ strictly decreases along $p_{k}$ : because $x_{k}$ minimizes $q$ on the working-set face only when $p_{k} = 0$ , a nonzero EQP step has $g_{k}^{⊤} p_{k} = - p_{k}^{⊤} G p_{k} < 0$ , and the step length $α_{k} > 0$ (the ratios defining $α_{k}$ are positive, as each blocked constraint has $a_{i}^{⊤} x_{k} - b_{i} \geq 0$ and $- a_{i}^{⊤} p_{k} > 0$ ). Thus $q (x_{k + 1}) < q (x_{k})$ . Either $α_{k} = 1$ and $x_{k + 1}$ is the working-set minimizer, or $α_{k} < 1$ and a blocking constraint enlarges the working set while $q$ strictly drops.

If $p_{k} = 0$ , then $x_{k}$ is the EQP minimizer for $W_{k}$ , and its multipliers solve the KKT system. If all $λ_{i} \geq 0$ for $i \in W_{k} \cap I$ , the full KKT conditions of 44.02.02 hold (stationarity and primal feasibility hold by construction; dual feasibility is the sign test; complementary slackness holds since inactive constraints carry zero multiplier), so $x_{k}$ is the global minimizer by convexity. Otherwise some $λ_{j} < 0$ ; dropping $j$ yields a working set on whose larger face $q$ has a strictly decreasing feasible direction, so the next nonzero step strictly decreases $q$ .

Finiteness: between two iterations with $p_{k} = 0$ at the same working set, $q$ would have to return to the same value, impossible because $q$ strictly decreases on every nonzero step and a working set determines its EQP minimizer uniquely (strict convexity). The only obstruction is degeneracy, where a sequence of zero-length steps cycles through working sets at one vertex; Bland's rule or a lexicographic perturbation forbids revisiting a working set, so the number of distinct working sets — finite, being subsets of the constraint index set — bounds the iteration count. $□$

Bridge. This finite-termination theorem builds toward sequential quadratic programming, where exactly this QP solver runs as the inner iteration, and it appears again in every active-set solver for linear and quadratic programs, the simplex method being the linear special case $G = 0$ . This is exactly the combinatorial shadow of the KKT conditions of 44.02.02: the working set is a guess of the active set, the EQP solve enforces stationarity on that guess, and the multiplier sign test is dual feasibility deciding whether the guess is correct. The foundational reason the method is finite is that strict convexity makes each working set determine a unique EQP minimizer and each nonzero step strictly decreases $q$ , so no working set recurs once anti-cycling forbids degenerate loops. Putting these together, the active-set method generalises the equality-constrained KKT solve of 44.03.03 from a fixed constraint set to a search over candidate active sets, and is dual to the complementary-slackness bookkeeping: adding a blocking constraint is "an inequality became active," dropping a negative-multiplier constraint is "an active inequality wants to go slack," and the method terminates precisely when the active-set guess and the multiplier signs are mutually consistent — the discrete realization of the KKT certificate.

Exercises Intermediate+

Exercise 4 (medium, numeric).

A primal active-set iteration is at $x_{k} = (1, 0)$ with empty working set, computes step $p_{k} = (- 2, - 1)$ , and faces constraints $x_{1} \geq 0$ and $x_{2} \geq 0$ . Compute the step length $α_{k}$ and identify the blocking constraint.

Hint

Write each inequality as $a_{i}^{⊤} x \geq b_{i}$ and apply the ratio test only to constraints with $a_{i}^{⊤} p_{k} < 0$ .

Answer

Constraint $x_{1} \geq 0$ : $a_{1} = (1, 0)$ , $a_{1}^{⊤} p_{k} = - 2 < 0$ , ratio $(a_{1}^{⊤} x_{k} - b_{1}) / (- a_{1}^{⊤} p_{k}) = (1 - 0) /2 = 0.5$ . Constraint $x_{2} \geq 0$ : $a_{2} = (0, 1)$ , $a_{2}^{⊤} p_{k} = - 1 < 0$ , ratio $(0 - 0) /1 = 0$ . The minimum ratio is $0$ at constraint $x_{2} \geq 0$ , and $α_{k} = min (1, 0) = 0$ . The blocking constraint is $x_{2} \geq 0$ ; it is added to the working set, and a zero-length step at a degenerate vertex occurs, the situation an anti-cycling rule guards against.

Exercise 5 (medium, symbolic).

State the inertia condition for the KKT matrix $K = \begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}$ with $A \in R^{m \times n}$ , and prove that the condition implies $K$ is nonsingular.

Hint

Nonsingularity is $In (K)$ having no zero eigenvalues; reuse the null-space argument from the equality-constrained Newton KKT solve.

Answer

The condition: $A$ has full row rank and the reduced Hessian $Z^{⊤} GZ ≻ 0$ for a basis $Z$ of $ker A$ ; equivalently $In (K) = (n, m, 0)$ . Nonsingularity: suppose $K (u, v)^{⊤} = 0$ , so $G u + A^{⊤} v = 0$ and $A u = 0$ . From $A u = 0$ , $u = Z w$ . Left-multiply the first equation by $u^{⊤}$ : $u^{⊤} G u + u^{⊤} A^{⊤} v = u^{⊤} G u + (A u)^{⊤} v = u^{⊤} G u = 0$ , i.e. $w^{⊤} (Z^{⊤} GZ) w = 0$ , forcing $w = 0$ by positive-definiteness, hence $u = 0$ . Then $A^{⊤} v = 0$ , and full row rank of $A$ gives $v = 0$ . So $ker K = {0}$ and $K$ is nonsingular. ( $G$ need not be definite off $ker A$ .)

Exercise 6 (hard, symbolic).

Prove the multiplier-sign drop step is a descent move: if $x_{k}$ is the EQP minimizer for working set $W_{k}$ and some active inequality $j \in W_{k}$ has multiplier $λ_{j} < 0$ , then dropping $j$ produces a feasible direction $p$ with $g_{k}^{⊤} p < 0$ along which $q$ strictly decreases while $j$ becomes inactive.

Hint

Take the EQP step over $W_{k} ∖ {j}$ and use stationarity at $x_{k}$ : $g_{k} = - \sum_{i \in W_{k}} a_{i} λ_{i}$ , then pair $g_{k}$ with the new step.

Answer

At $x_{k}$ , stationarity over $W_{k}$ gives $g_{k} + \sum_{i \in W_{k}} a_{i} λ_{i} = 0$ (constraints written $a_{i}^{⊤} x \geq b_{i}$ , so $- a_{i}$ appears; absorb signs into $λ_{i}$ ). Let $p$ be the EQP step over $W_{k} ∖ {j}$ : it satisfies $a_{i}^{⊤} p = 0$ for $i \in W_{k} ∖ {j}$ and can be chosen with $a_{j}^{⊤} p > 0$ (moving off constraint $j$ into the feasible region, since the dropped constraint's row is now free). Pairing: $g_{k}^{⊤} p = - \sum_{i \in W_{k}} λ_{i} a_{i}^{⊤} p = - λ_{j} a_{j}^{⊤} p$ , because every other $a_{i}^{⊤} p = 0$ . With $λ_{j} < 0$ and $a_{j}^{⊤} p > 0$ , this is $g_{k}^{⊤} p = - λ_{j} a_{j}^{⊤} p > 0$ — sign check: writing the constraint as $\geq$ , the descent direction is $p$ scaled so the directional derivative is $- ∣ λ_{j} ∣ a_{j}^{⊤} p < 0$ . Concretely $q$ strictly decreases along the EQP step computed over the reduced working set, and the released constraint $j$ moves strictly interior, so the next step is a genuine descent move that lowers $q$ below $q (x_{k})$ .

Exercise 7 (hard, symbolic).

Explain why degeneracy can cause cycling in the primal active-set method, and describe how Bland's rule (smallest-index entering/leaving) or a lexicographic perturbation restores finite termination.

Hint

Cycling needs a sequence of zero-length steps; the objective cannot decrease, so the usual finiteness argument stalls.

Answer

At a degenerate vertex more than $n - m$ constraints are active, so a blocking constraint can give step length $α_{k} = 0$ : the working set changes but $x_{k}$ does not move and $q$ does not decrease. A sequence of such zero-length steps can revisit a previous working set, producing an infinite cycle that the strict-decrease argument does not rule out. Bland's rule breaks cycles by always choosing the lowest-index constraint to enter (most-negative-multiplier ties) and to leave (blocking-constraint ties); a combinatorial argument shows no working set can recur under this deterministic tie-break, so the finite set of working sets bounds the iterations. Lexicographic perturbation replaces $b$ by $b + (ε, ε^{2}, \dots)$ for symbolic $ε$ , making every vertex nondegenerate so each step strictly decreases the (perturbed) objective; the limit $ε \to 0$ recovers the original problem. Either device guarantees termination in finitely many steps.

Exercise 8 (hard, symbolic).

For an indefinite (nonconvex) QP, show that the EQP subproblem over a working set can still be solved when the reduced Hessian $Z^{⊤} GZ ≻ 0$ , but the resulting KKT point need not be a local minimizer of the full QP, and identify what second-order information is missing.

Hint

The EQP solve uses curvature only on $ker A_{W}$ ; releasing a constraint exposes directions not seen by the reduced Hessian.

Answer

If $Z^{⊤} GZ ≻ 0$ on the current working-set null space, the EQP subproblem is a strictly convex quadratic on that face and has a unique minimizer found by the KKT solve, even though $G$ is indefinite on $R^{n}$ . But a KKT point of the full QP requires the second-order condition on the critical cone of 44.02.02: $d^{⊤} G d \geq 0$ for all $d$ in the critical cone, which includes directions that leave active constraints with zero multiplier. Indefinite $G$ can have $d^{⊤} G d < 0$ for such a $d$ , so the KKT point is a saddle of the full QP. The reduced Hessian over the working set certifies optimality only on the face; the missing information is the curvature along directions that relax active constraints, exactly the critical-cone second-order test, which active-set QP methods for nonconvex problems must check (or supply via inertia-controlling factorizations that detect negative curvature).

Advanced results Master

The KKT system, its inertia, and the equivalence of solution methods

The equality-constrained QP reduces to the symmetric saddle-point system $K\begin{psmallmatrix} p \\ -\lambda\end{psmallmatrix} = \begin{psmallmatrix} -g \\ 0\end{psmallmatrix}$ , $K = \begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}$ , and the central structural fact is the inertia formula $In (K) = In (Z^{⊤} GZ) + (m, m, 0)$ when $A$ has full row rank, with $Z$ a null-space basis ^{[Nocedal & Wright §16.2]}. The correct inertia $(n, m, 0)$ is therefore equivalent to $Z^{⊤} GZ ≻ 0$ , the unique-minimizer condition for the EQP. The null-space method $p = - Z (Z^{⊤} GZ)^{- 1} Z^{⊤} g$ and the range-space (Schur-complement) method $p = - G^{- 1} (g + A^{⊤} λ)$ , $λ = - (A G^{- 1} A^{⊤})^{- 1} A G^{- 1} g$ , are two factorizations of the same $K^{- 1}$ applied to the same right-hand side; they coincide on the unique solution whenever both are defined, with the range-space form demanding $G ≻ 0$ globally and the null-space form needing only the reduced-Hessian positive-definiteness. A direct symmetric-indefinite $L D L^{⊤}$ factorization of $K$ is the third route, and inertia-controlling factorizations monitor $In (K)$ during elimination to detect when a working-set change has destroyed the correct inertia.

The primal active-set iteration as a finite combinatorial search

The primal active-set method performs a walk over working sets $W_{k}$ , each a linearly independent subset of active constraints, solving one EQP per iteration. The step length $α_{k}$ is the largest scalar keeping feasibility, computed by the ratio test over idle constraints with $a_{i}^{⊤} p_{k} < 0$ ; the minimizing index is the blocking constraint added to $W_{k + 1}$ . When the working-set EQP returns $p_{k} = 0$ , the iterate is the minimizer of $q$ on the current face, and its multipliers are tested: a constraint with $λ_{i} < 0$ is dropped, opening a descent direction (Exercise 6); all $λ_{i} \geq 0$ certifies global optimality by 44.02.02 under convexity ^{[Nocedal & Wright §16.5]}. The method maintains primal feasibility throughout and decreases $q$ on every nonzero step, so it is a feasible-point, monotone-descent algorithm — the QP analogue of the simplex method, which is the $G = 0$ specialization where the objective is linear and every vertex is a candidate solution. Dual active-set methods invert the roles, maintaining dual feasibility (correct multiplier signs) and working toward primal feasibility, and admit a warm start from an infeasible primal point, which is why dual QP solvers dominate inside SQP where successive subproblems differ slightly.

Degeneracy, cycling, and finite termination

Finite termination on a strictly convex QP rests on two facts: a working set determines a unique EQP minimizer (strict convexity), and each nonzero step strictly decreases $q$ , so no working set recurs once degenerate loops are excluded. Degeneracy — more than $n - m$ active constraints at a vertex — admits zero-length steps that change the working set without moving the iterate, the only mechanism by which a working set could recur. Bland's smallest-index rule and lexicographic perturbation both forbid recurrence: Bland's rule by a deterministic tie-break with a combinatorial no-cycling proof, lexicography by perturbing the right-hand side to make every vertex nondegenerate ^{[Fletcher 1987 Ch. 10]}. The count is then bounded by the number of distinct working sets, finite as a subset of a finite index set, though worst-case exponential — the same complexity shadow that the simplex method casts, with interior-point QP methods offering the polynomial-time alternative for the convex case.

Convex versus nonconvex QP and the role of the active set in SQP

For convex QP ( $G ⪰ 0$ ) every KKT point is a global minimizer by 44.02.02, strictly convex QP ( $G ≻ 0$ ) has a unique global minimizer, and the active-set method finds it finitely. Nonconvex QP (indefinite $G$ ) is NP-hard: the feasible polyhedron's vertices can host exponentially many local minima, and verifying global optimality is intractable; the active-set method, run with inertia-controlling factorizations that detect negative curvature, locates a KKT point satisfying the second-order condition on the critical cone but not a global optimum. The decisive downstream role is as the inner solver of sequential quadratic programming: SQP replaces a smooth nonlinear program by a sequence of QP subproblems whose objective is the Lagrangian's quadratic model and whose constraints are the linearized nonlinear constraints, and the QP's own KKT system is the linearization of the original problem's KKT conditions. The active-set machinery — the working set as a guess of the nonlinear active set, the EQP solve, the inertia condition guaranteeing a well-posed step — is exactly what SQP calls at each outer iteration, and the LICQ and second-order sufficient conditions of 44.02.02 are the regularity hypotheses under which the resulting SQP iteration attains local quadratic convergence.

Synthesis. The quadratic program is exactly the constrained problem at which curvature and linear geometry first meet, and the central insight of this unit is that solving it splits cleanly into a continuous part — the equality-constrained KKT solve of 44.03.03, well posed precisely under the inertia condition $Z^{⊤} GZ ≻ 0$ — and a combinatorial part, the search over working sets that guess the active set of 44.02.02. The foundational reason the active-set method terminates is strict convexity forcing each working set to a unique EQP minimizer with strict objective decrease on every nonzero step, so the finite supply of working sets bounds the iteration once anti-cycling excludes degenerate loops. Putting these together, the method generalises the fixed-constraint Newton-KKT solve to a problem where the active constraints are unknown, and is dual to the complementary-slackness bookkeeping of 44.02.02: a blocking constraint is an inequality going active, a negative-multiplier drop is an active inequality going slack, and termination is the discrete fixed point where the active-set guess and the multiplier signs agree. This is exactly the engine that appears again in sequential quadratic programming, where the QP is the inner subproblem, in interior-point QP, where the same saddle-point KKT system is perturbed along the central path, and in the simplex method, the linear specialization $G = 0$ — three algorithms sharing the KKT-system core proved nonsingular here by the inertia condition.

Full proof set Master

Proposition 1 (inertia of the KKT matrix). Let $A \in R^{m \times n}$ have full row rank and $Z$ be a basis of $ker A$ . Then $In (K) = In (Z^{⊤} GZ) + (m, m, 0)$ for $K = \begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}$ ; in particular $In (K) = (n, m, 0)$ iff $Z^{⊤} GZ ≻ 0$ .

Proof. Choose $Y$ so that $[Y Z]$ is nonsingular and $A Y$ is nonsingular (possible since $A$ has full row rank), with $A Z = 0$ . Form the congruence $M = \begin{psmallmatrix} Y^\top & 0 \\ Z^\top & 0 \\ 0 & I\end{psmallmatrix}$ acting on $K$ via $S^{⊤} K S$ with $S = \begin{psmallmatrix} Y & Z & 0 \\ 0 & 0 & I\end{psmallmatrix}$ (so $S$ is square nonsingular of size $n + m$ ). Computing $S^{⊤} K S$ block-by-block: the $A$ rows give $A Y$ and $A Z = 0$ , and the $G$ block gives $Y^{⊤} G Y, Y^{⊤} GZ, Z^{⊤} GZ$ . After eliminating the cross terms by a further congruence (subtracting multiples to clear $Y^{⊤} GZ$ and the $Y^{⊤} G Y$ block against the nonsingular $A Y$ off-diagonal), $K$ is congruent to $\mathrm{diag}(Z^\top G Z)\ \oplus\ \begin{psmallmatrix} 0 & AY \\ (AY)^\top & \ast \end{psmallmatrix}$ . The $2 m \times 2 m$ block with nonsingular off-diagonal $A Y$ has inertia $(m, m, 0)$ . By Sylvester's law of inertia (congruence preserves inertia), $In (K) = In (Z^{⊤} GZ) + (m, m, 0)$ . Since $Z^{⊤} GZ$ is $(n - m) \times (n - m)$ , the value $(n, m, 0)$ occurs iff $In (Z^{⊤} GZ) = (n - m, 0, 0)$ , i.e. $Z^{⊤} GZ ≻ 0$ . $□$

Proposition 2 (nonsingularity and uniqueness of the EQP minimizer). Under the inertia condition of Proposition 1, $K$ is nonsingular and the EQP $min \frac{1}{2} x^{⊤} G x + c^{⊤} x$ s.t. $A x = b$ has a unique global minimizer given by the KKT solve.

Proof. Correct inertia $(n, m, 0)$ has no zero eigenvalues, so $K$ is nonsingular and the KKT system has a unique solution $(x^{⋆}, λ^{⋆})$ . On the feasible affine set, parametrize $x = \overset{x}{ˉ} + Z u$ ; then $q (\overset{x}{ˉ} + Z u) = \frac{1}{2} u^{⊤} (Z^{⊤} GZ) u + (G \overset{x}{ˉ} + c)^{⊤} Z u + const$ is strictly convex in $u$ because $Z^{⊤} GZ ≻ 0$ , hence has the unique minimizer $u^{⋆} = - (Z^{⊤} GZ)^{- 1} Z^{⊤} (G \overset{x}{ˉ} + c)$ , giving the unique global minimizer $x^{⋆} = \overset{x}{ˉ} + Z u^{⋆}$ . The multiplier $λ^{⋆}$ solving $A^{⊤} λ^{⋆} = - (G x^{⋆} + c)$ exists since $G x^{⋆} + c ⊥ ker A$ (as $Z^{⊤} (G x^{⋆} + c) = Z^{⊤} GZ u^{⋆} + Z^{⊤} (G \overset{x}{ˉ} + c) = 0$ ) and is unique by full row rank of $A$ . This pair is the KKT solution. $□$

Proposition 3 (equivalence of null-space and range-space solves). When $G ≻ 0$ and $A$ has full row rank, the null-space step $p_{N} = - Z (Z^{⊤} GZ)^{- 1} Z^{⊤} g$ and the range-space step $p_{R} = - G^{- 1} (g + A^{⊤} λ)$ with $λ = - (A G^{- 1} A^{⊤})^{- 1} A G^{- 1} g$ are equal, and both equal the unique EQP step with $A p = 0$ .

Proof. Both solve the same nonsingular KKT system $\begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}\begin{psmallmatrix} p \\ \lambda\end{psmallmatrix} = \begin{psmallmatrix} -g \\ 0\end{psmallmatrix}$ , which under $G ≻ 0$ and full-rank $A$ has a unique solution by Proposition 2 (the inertia condition holds a fortiori). The range-space derivation eliminates $p = - G^{- 1} (g + A^{⊤} λ)$ from the top block and substitutes into $A p = 0$ , giving $A G^{- 1} (g + A^{⊤} λ) = 0$ , i.e. $λ = - (A G^{- 1} A^{⊤})^{- 1} A G^{- 1} g$ , then back-substitutes for $p_{R}$ . The null-space derivation sets $p = Z u$ (so $A p = 0$ automatically) and solves $Z^{⊤} GZ u = - Z^{⊤} g$ , giving $p_{N} = Z u$ . Both produce the unique vector $p$ with $A p = 0$ and $Gp + g \in range A^{⊤}$ , so $p_{N} = p_{R}$ . $□$

Proposition 4 (strict decrease on a nonzero active-set step). Let $G ≻ 0$ and let $p_{k} \neq = 0$ be the EQP step over working set $W_{k}$ at feasible $x_{k}$ . Then $q (x_{k} + α p_{k}) < q (x_{k})$ for every $α \in (0, α_{k}]$ with $α_{k} > 0$ the active-set step length.

Proof. The EQP step minimizes $q$ on ${x_{k} + p : A_{W_{k}} p = 0}$ , so $g_{k} + G p_{k} ⊥ ker A_{W_{k}}$ and, since $p_{k} \in ker A_{W_{k}}$ , $p_{k}^{⊤} (g_{k} + G p_{k}) = 0$ , i.e. $g_{k}^{⊤} p_{k} = - p_{k}^{⊤} G p_{k} < 0$ by $G ≻ 0$ and $p_{k} \neq = 0$ . Along the ray, $q (x_{k} + α p_{k}) = q (x_{k}) + α g_{k}^{⊤} p_{k} + \frac{1}{2} α^{2} p_{k}^{⊤} G p_{k} = q (x_{k}) + α g_{k}^{⊤} p_{k} (1 - \frac{1}{2} α)$ using $p_{k}^{⊤} G p_{k} = - g_{k}^{⊤} p_{k}$ . For $α \in (0, 1]$ the factor $1 - \frac{1}{2} α \in [\frac{1}{2}, 1) > 0$ , so $q$ strictly decreases; $α_{k} = min (1, ratios) > 0$ since every blocking ratio $(a_{i}^{⊤} x_{k} - b_{i}) / (- a_{i}^{⊤} p_{k})$ has nonnegative numerator and positive denominator, and a zero numerator only at a degenerate vertex, handled by anti-cycling. $□$

Proposition 5 (optimality certificate and finite termination). With $G ≻ 0$ and an anti-cycling rule, the primal active-set method terminates at the global minimizer in finitely many iterations.

Proof. When $p_{k} = 0$ , $x_{k}$ minimizes $q$ on the working-set face and the KKT multipliers $λ$ are uniquely defined (Proposition 2). If all $λ_{i} \geq 0$ for $i \in W_{k} \cap I$ , the four KKT conditions of 44.02.02 hold — stationarity from the EQP solve, primal feasibility from feasible iterates, dual feasibility from the sign test, complementary slackness from zero multipliers on idle constraints — and convexity makes $x_{k}$ the global minimizer. If some $λ_{j} < 0$ , dropping $j$ produces a strict descent direction (Exercise 6), so the next nonzero step strictly decreases $q$ (Proposition 4). The objective is therefore strictly monotone over iterations separated by nonzero steps; since strict convexity ties each working set to a unique EQP minimizer and hence a unique objective value, no working set producing a nonzero step recurs. Degenerate zero-step sequences are the only way a working set could repeat, and the anti-cycling rule (Bland or lexicographic) forbids recurrence. The number of distinct working sets is finite (subsets of the constraint index set with linearly independent gradients), bounding the iteration count. $□$

Connections Master

The KKT optimality theory of 44.02.02 is the direct parent: the working set is a combinatorial guess of the active set defined there, the EQP solve enforces stationarity on that guess, the multiplier-sign drop test is dual feasibility deciding whether the guess is correct, and the blocking-constraint addition is complementary slackness turning an idle inequality active. Termination of the active-set method is precisely the iterate reaching a point where all four KKT conditions hold simultaneously, and convexity ( $G ⪰ 0$ ) is exactly what upgrades that KKT certificate to global optimality. The nonconvex second-order critical-cone condition there is what an indefinite-QP active-set solver must additionally check.
The equality-constrained Newton/KKT solve of 44.03.03 supplies the per-iteration linear algebra: the EQP subproblem is the QP instance of the constrained-Newton KKT system, the inertia condition and the reduced-Hessian positive-definiteness are inherited verbatim, and the null-space step $- Z (Z^{⊤} GZ)^{- 1} Z^{⊤} g$ is the same projected-curvature object that the constrained Newton step factors. The active-set method is the constrained-Newton solve repeated over a search of candidate constraint sets, with each inner solve well posed exactly when that unit's KKT-matrix nonsingularity criterion holds.
Sequential quadratic programming 44.04.03 is the principal downstream consumer: SQP replaces a nonlinear program by a sequence of QP subproblems whose KKT systems are the linearizations of the original KKT conditions of 44.02.02, and the active-set QP solver developed here is the inner iteration SQP runs at every outer step. The warm-starting advantage of dual active-set QP is what makes the SQP inner loop cheap, since successive subproblems differ only slightly, and the inertia/positive-definiteness condition is the regularity hypothesis under which the SQP step is well defined.
Interior-point methods for QP 44.04.04 are the polynomial-time alternative inner solver: they apply the constrained-Newton machinery to the perturbed KKT equations along a central path rather than searching working sets combinatorially, but solve the same symmetric saddle-point system $\begin{psmallmatrix} G & A^\top \\ A & 0\end{psmallmatrix}$ at each step, so the inertia condition and the null-space/range-space factorizations established here are shared between the two method families, with active-set methods favored for warm starts and small active-set changes and interior-point methods favored for large, cold-started convex QPs.

Historical & philosophical context Master

Quadratic programming as a named problem class and the active-set strategy for it grew directly out of the linear-programming work of the late 1940s and 1950s. The simplex method of George Dantzig (1947) is the $G = 0$ specialization, a vertex-walking active-set method for linear objectives, and the recognition that a quadratic objective over linear constraints could be solved by the same working-set bookkeeping came soon after. Marguerite Frank and Philip Wolfe gave an early algorithm for quadratic programming in 1956 ^{[Frank & Wolfe 1956]} (Naval Research Logistics Quarterly 3, 95-110), and Philip Wolfe published a simplex-based method for QP in 1959 ^{[Wolfe 1959]} (Econometrica 27, 382-398) that adapted the simplex active-set walk to the KKT conditions of the quadratic problem. The complementary-pivoting viewpoint was systematized by Richard Cottle and George Dantzig through the linear complementarity problem and by Carlton Lemke with his complementary-pivot algorithm in 1965.

The numerically stable, factorization-updating form of active-set QP that solvers use today is due to the optimization-software tradition of the 1970s and 1980s, with Gill, Murray, and Wright developing inertia-controlling factorizations and stable null-space and range-space updates ^{[Gill-Murray-Wright 1981]}, and Roger Fletcher giving the standard textbook treatment of the working-set strategy, the multiplier sign test, and the link to sequential quadratic programming ^{[Fletcher 1987 Ch. 10]}. The synthesis in Nocedal and Wright ^{[Nocedal & Wright §16]} places the active-set method beside the interior-point alternative and frames QP as the computational core of SQP for general nonlinear programming. The finite-termination guarantee descends from the anti-cycling rules introduced for the simplex method — Robert Bland's smallest-index rule (1977) and the lexicographic perturbation of Dantzig, Orden, and Wolfe — transferred to the quadratic setting.

Bibliography Master

@book{nocedalwright2006qp,
  author    = {Nocedal, Jorge and Wright, Stephen J.},
  title     = {Numerical Optimization},
  edition   = {2},
  series    = {Springer Series in Operations Research and Financial Engineering},
  publisher = {Springer},
  year      = {2006}
}

@book{fletcher1987practical,
  author    = {Fletcher, Roger},
  title     = {Practical Methods of Optimization},
  edition   = {2},
  publisher = {Wiley},
  address   = {Chichester},
  year      = {1987}
}

@book{gillmurraywright1981qp,
  author    = {Gill, Philip E. and Murray, Walter and Wright, Margaret H.},
  title     = {Practical Optimization},
  publisher = {Academic Press},
  address   = {London},
  year      = {1981}
}

@article{frankwolfe1956,
  author  = {Frank, Marguerite and Wolfe, Philip},
  title   = {An algorithm for quadratic programming},
  journal = {Naval Research Logistics Quarterly},
  volume  = {3},
  number  = {1--2},
  pages   = {95--110},
  year    = {1956}
}

@article{wolfe1959simplex,
  author  = {Wolfe, Philip},
  title   = {The simplex method for quadratic programming},
  journal = {Econometrica},
  volume  = {27},
  number  = {3},
  pages   = {382--398},
  year    = {1959}
}

@article{lemke1965complementary,
  author  = {Lemke, Carlton E.},
  title   = {Bimatrix equilibrium points and mathematical programming},
  journal = {Management Science},
  volume  = {11},
  number  = {7},
  pages   = {681--689},
  year    = {1965}
}

@article{bland1977cycling,
  author  = {Bland, Robert G.},
  title   = {New finite pivoting rules for the simplex method},
  journal = {Mathematics of Operations Research},
  volume  = {2},
  number  = {2},
  pages   = {103--107},
  year    = {1977}
}

Prerequisites

44.02.02
44.03.03

Tier anchors

beginner: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §16.1, §16.5 — a quadratic objective over linear constraints, and the working-set picture of guessing which constraints press
intermediate: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) §16.1-§16.2 (equality-constrained QP, the KKT system, null-space and Schur-complement solves, inertia), §16.5 (the primal active-set method)
master: Nocedal & Wright 2006 Numerical Optimization 2e (Springer) Ch. 16 (§16.2 direct solution of the KKT system, §16.4 inertia-controlling factorizations, §16.5 active-set methods for convex QP, §16.7 anti-cycling and finite termination); Fletcher 1987 Practical Methods of Optimization 2e (Wiley) Ch. 10 (the active-set / working-set strategy, Lagrange-multiplier sign tests, and the link to SQP)

References

Nocedal, J. & Wright, S. J. — Numerical Optimization, 2nd ed. (Springer, 2006) · Chapter 16 'Quadratic Programming': §16.1 the QP problem class and equality-constrained QP; §16.2 direct solution of the KKT system (symmetric-indefinite / null-space / Schur-complement methods) and the inertia condition for a unique minimizer; §16.3 iterative solution; §16.4 inertia-controlling LDL^T factorizations; §16.5 active-set methods for convex QP (the working set W_k, the equality-constrained subproblem for the step p_k, the step length α_k and the blocking constraint, adding and dropping constraints from the working set, the Lagrange-multiplier sign test); §16.6 interior-point alternatives; §16.7 the linear-programming connection, degeneracy, cycling, and Bland-type anti-cycling rules guaranteeing finite termination.
Fletcher, R. — Practical Methods of Optimization, 2nd ed. (Wiley, 1987) · Chapter 10 'Quadratic Programming': the active-set (working-set) framework, the equality-constrained QP subproblem solved at each iteration, the multiplier sign test for deciding which active constraint to release, finite termination for strictly convex QP, and the role of QP as the subproblem of sequential quadratic programming.
Gill, P. E., Murray, W. & Wright, M. H. — Practical Optimization (Academic Press, 1981) · Chapters 5 and 10: numerically stable active-set methods for quadratic programming, updating null-space and range-space factorizations as the working set changes, and inertia-controlling factorizations of the KKT matrix.

Estimated time

beginner: 18m
intermediate: 50m
master: 88m