二次规划的活跃集法

形式陈述

取正整数 $n\ge1$ ，变量 $x\in\mathbb R^n$ ，考虑严格凸二次规划

\min_x f(x)=\tfrac12x^THx+c^Tx,\qquad Ax\le b, \qquad H=H^T\succ0.

二次型的正定性保证非空可行集上存在唯一最优点。给定可行初值，令 $\mathcal A(x)=\{i:a_i^Tx=b_i\}$ 为所有活跃约束；算法另保存一个工作集 $W\subseteq\mathcal A(x)$ ，其约束行线性独立。活跃集描述点的位置，工作集是本轮暂时当作等式处理的约束，它们不必相同。

在当前点记 $g=Hx+c$ ，求等式约束子问题

\min_p\ g^Tp+\tfrac12p^THp,\qquad A_Wp=0.

通过线性方程组计算唯一方向与工作乘子：

\begin{pmatrix}H&A_W^T\\A_W&0\end{pmatrix} \begin{pmatrix}p\\\nu\end{pmatrix} =\begin{pmatrix}-g\\0\end{pmatrix}.

迭代分成两支。

若 $p\ne0$ ，取 $\alpha=\min\left\{1, \min_{i\notin W,\ a_i^Tp>0} \frac{b_i-a_i^Tx}{a_i^Tp}\right\}.$ 内层集合为空时只取一。令 $x\leftarrow x+\alpha p$ ；若某条约束达到最小比值且 $\alpha\le1$ ，将一个阻挡约束加入工作集。
若 $p=0$ ，检查 $\nu$ 。若所有分量非负，令工作集外乘子为零，得到完整KKT 证书并终止；否则删除一条负乘子约束，保留同一个 $x$ ，重解方向。

主算法假设工作集一直线性独立，并且每次阻挡移动具有正步长；并列可用固定索引顺序选择。实现遇到零步长、相关工作行或重复状态时，应进入明确的退化处理，而不能靠放宽可行性冒充正常进展。

直觉

先假定几面墙暂时不能离开，在这些墙的交面内寻找二次目标的最低点。若路上撞到另一面墙，就停在它前面，把它加入工作集。若已经在当前面的最低点，乘子告诉我们哪些墙是真正阻力，哪些只是错误地把自己锁住。

对于 $a_i^Tx\le b_i$ 的写法，合法乘子应非负。负乘子意味着该约束在当前等式模型里需要向错误方向“拉住”最优点；解除它，通常就有新的可行下降方向。这个符号来自统一的 Lagrangian $f+\lambda^T(Ax-b)$ ，改变不等式方向后必须同步改变符号约定。

三角形可行域中的工作集轨迹：从原点释放下界，到达右顶点，再沿斜边进入边的内部最优点 — 工作约束的释放与加入

例子与边界

两次释放和一次阻挡

求

\min_{x,y}\tfrac12[(x-2)^2+(y-1)^2],\qquad -x\le0,\ -y\le0,\ x+y\le2.

把三条约束依次编号为 $1,2,3$ 。从 $(0,0)$ 开始， $W=\{1,2\}$ 。

两条下界都固定。 方向只能为零。梯度为 $(-2,-1)$ ，由 $g+A_W^T\nu=0$ 得 $\nu=(-2,-1)$ 。删除乘子更负的约束一。
只固定 $y=0$ 。 子问题给 $p=(2,0)$ 。斜边的阻挡比值为 $2/2=1$ ，所以走完整步到 $(2,0)$ ，并将约束三加入。此时 $W=\{2,3\}$ 。
右顶点的工作方向为零。 梯度为 $(0,-1)$ 。驻点方程给 $\nu_3=0,\nu_2=-1$ ，因此释放约束二，留下 $W=\{3\}$ 。
沿斜边优化。 方向满足 $p_x+p_y=0$ 。解方程得 $p=(-1/2,1/2)$ 、 $\nu_3=1/2$ 。没有新约束提前阻挡，走到 $(3/2,1/2)$ 。
终止核验。 重解后 $p=0$ ，乘子为 $(0,0,1/2)$ ，三条约束可行，互补关系成立，梯度 $(-1/2,-1/2)$ 被斜边法向力抵消。

目标从 $5/2$ 降到 $1/2$ ，再降到 $1/4$ ；释放约束的两轮不移动几何点。最优点位于斜边内部，并非多面体顶点，所以不能把这条轨迹说成单纯形法的顶点换基。

紧约束可以不在工作集里

第一条下界刚被释放时，点仍为原点，所以 $x=0$ 依然紧；它只是不再作为等式限制方向。若每轮把所有紧约束无条件放回工作集，刚才的删除立刻被撤销，算法会卡在起点。

约束冗余也需要处理。若额外加入 $2x+2y\le4$ ，它与约束三在同一条边上同时紧，两个法向量相关，不能直接把二者都放入要求满行秩的块系统。几何可行域没变，线性代数却可能奇异；应保留独立工作行，并在最终证书中允许冗余约束的乘子为零。

推论与应用

两个不变量与终止证书

工作方程 $A_Wp=0$ 保证旧工作约束保持紧。对其他约束，只有 $a_i^Tp>0$ 才会消耗剩余裕量，最小比值检验恰好保证没有约束被穿过。因此每个接受点保持原始可行。

把方向方程左乘 $p^T$ ，利用 $A_Wp=0$ ，得到

g^Tp=-p^THp<0\quad(p\ne0).

故对 $0<\alpha\le1$ ，

f(x+\alpha p)-f(x) =-\alpha(1-\alpha/2)p^THp<0.

这解释为什么可以沿面内方向走到第一面阻挡墙，而不需要另加普通线搜索。 $p=0$ 且工作乘子非负时，扩展成完整乘子即可满足全部 KKT 条件；严格凸性使证书认证唯一全局解。

删去负乘子约束后，为什么会获得自由？在独立工作行下，可以选方向 $d$ 使保留的工作行对它为零，被删除行满足 $a_j^Td<0$ 。由原驻点式 $g=-A_W^T\nu$ ，有 $g^Td=-\nu_j a_j^Td<0$ 。若其余活跃约束不阻挡这一方向，就能作小的可行下降步；若立即被另一条紧约束以零步长阻挡，就进入退化情形。

退化与计算成本

每次删除约束之前，零方向意味着当前点是该工作面上唯一的最小点。删除负乘子后，非退化假设保证随后有正步长下降，因而不可能再以相同工作集回到同一个面最小点。两次删除之间，阻挡步骤每次增加一条独立工作行，至多增加 $n$ 次；没有新阻挡的完整步则直接到达当前面最小点。工作集只有有限多种，所以非退化版本有限终止。但这些数量可以随约束数呈组合增长，不能从“每次解一个线性系统”推断总复杂度为多项式。含零步长时，任意并列规则可能反复增删约束；可采用经过证明的字典序扰动或专门的防循环工作集规则，实际程序至少应检测重复状态并报告退化。

若本轮有 $w$ 条工作约束，直接稠密求解 $(n+w)$ 阶块系统成本为 $O((n+w)^3)$ ；扫描阻挡约束为 $O(mn)$ 。相邻工作集只改一行时可以更新分解，暖启动也能复用上次接近正确的工作集，这使该方法适合重复的小中型 QP。寻找可行初值是另一个阶段；从不可行点直接使用上述比值检验，会失去其可行性不变量。

在序列二次规划中，本页可以作为局部 QP 的内层求解器。非线性原约束的可行性仍需外层检查，因为 QP 只满足线性化约束。

参考资料

Robert M. Freund, Solution Methods for Quadratic Optimization, MIT, 2004，§2，工作集、负乘子释放与非退化方向。
Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., 2006，§16.5，active-set methods for convex QP；作者目录。
Dimitri P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, 1982，§1.5，简单约束、可行方向与活跃约束策略。
Philip E. Gill, Walter Murray and Margaret H. Wright, Practical Optimization, 1981，Ch. 5，线性约束与工作集方法。

形式陈述 ​

两次释放和一次阻挡 ​

紧约束可以不在工作集里 ​

两个不变量与终止证书 ​

退化与计算成本 ​

反向链接

形式陈述

两次释放和一次阻挡

紧约束可以不在工作集里

两个不变量与终止证书

退化与计算成本