A feasible working-set QP solve terminates under nondegenerate steps

Let $z$ be a feasible iterate, $W$ its working set, and $u\mathrm{\ne }0$ the exact direction minimizer. Its KKT equation is $Bu+(Bz+c)+A^T\nu +{\sum }_{i\in W}{\mu }_i{G}_i^T=0$, with $Au=0$ and $G_{i}u=0$ for $i\in W$. Multiplying by $u^T$ gives $(Bz+c{)}^{T}u=-u^{T}Bu$. Hence for every accepted $0<\alpha \le 1$, $q(z+\alpha u)-q(z)=-\alpha (1-\alpha \mathrm{/}2)u^{T}Bu<0.$ If $\alpha <1$, a blocking row cannot lie in the span of the current rows, since it has $G_{i}u>0$ while every row in that span annihilates $u$; adding it preserves independence.

Suppose instead $u=0$ and the multiplier of a working inequality $j$ is negative. After deleting $j$, let $v$ be the next exact direction. If $v=0$, the new stationarity equation, extended with a zero multiplier on row $j$, and the old one give two multiplier representations for the same gradient on independent old working rows; uniqueness would force ${\mu }_j=0$, a contradiction. Hence $v\mathrm{\ne }0$. The new direction stationarity, dotted with $v$, gives $(Bz+c{)}^{T}v=-v^{T}Bv$. The old face stationarity, also dotted with $v$, gives $(Bz+c{)}^{T}v+{\mu }_j{G}_{j}v=0$, because all retained working rows annihilate $v$. Therefore ${\mu }_j{G}_{j}v=v^{T}Bv>0$, so $v\mathrm{\ne }0$ and $G_{j}v<0$. The dropped inequality is feasible to first order, and by the positive-step hypothesis the next iterate moves strictly along this descent direction.

For a fixed working set $W$, positive definiteness makes the face objective have at most one minimizer. Once the algorithm reaches that face minimizer, either all working inequality multipliers are nonnegative and it terminates, or step 1.2 gives a strict objective decrease after a negative multiplier is dropped. Every later iterate is then below the minimum value on that face, so the same working set cannot be face-minimized again. There are at most $2^m$ working sets.

Between successive face minimizers, each nonterminal partial step adds an independent blocker, so there can be at most $n-r$ such additions before the feasible direction space is zero. A full step with no blocker reaches a face minimizer immediately. Thus each of the at most $2^m$ face-minimization episodes uses at most $n-r+2\le n+2$ iterations. The cap $N\ge (n+2)2^m$ cannot be reached before a terminal KKT point.

At termination, feasibility is maintained and every working inequality multiplier is nonnegative; assign zero multipliers to inequalities outside the working set. This is a KKT tuple at a point $z$. For every feasible $y$, stationarity and complementarity give $(Bz+c{)}^T(y-z)=-{\sum }_i{\lambda }_i{G}_i(y-z)\ge 0$. Consequently $q(y)-q(z)=(Bz+c{)}^T(y-z)+\frac{1}{2}(y-z{)}^{T}B(y-z)\ge 0$, strictly if $y\mathrm{\ne }z$ by [A1]. Thus $z$ is the unique global minimizer. If a degeneracy or cap status occurs instead, the algorithm reports no KKT certificate, as stated.