有效集法介绍（ActiveSetMethod）
单纯性法（Simplex Method）是“线性规划之⽗”George Dantzig 最著名的成果，也是求解线性规划最有⼒的算法之⼀。⽽这⼀算法在求解⼆次规划（Quadratic Programming, QP）时的升级版就是有效集法（Active Set Method, ASM）。这两种算法的特点都是迭代点会循着约束边界前进，直到达到问题的最优点。本⽂对⽤于求解 QP 命题的 Primal ASM 算法作以介绍，主要内容的来源是 Nocedal 等⼈2006 年的著作 Numerical Optimization 第⼆版。
有效集（Active Set）
要说有效集法，⾸先要说说什么是有效集。有效集是指那些在最优点有效（active）的不等式约束所组成的集合。例如，考虑⼆次函数=x2+y2+2x+y≥0≥−1
函数的等⾼线及两个约束的图像如下：
这⾥写图⽚描述
办理港澳通行证需要什么材料通过计算或者从图上可以看出，当没有约束时，⽬标函数的最⼩值在 (−1,−0.5) 处取得。当考虑上述的两条约束时，⽬标函数的最⼩值在(0,−0.5) 处取得。这个时候在最优点处，约束 x≥0 中的等号被激活，这条约束就被称为有效约束（active constraint）。如果我们记两条约束的编号为 1 和 2，那么在最优点
处的有效集就可以记为
A∗={1}
⽽如果原命题中 y≥−1
这条约束改为 y≥−0.5
，即要求解的优化命题变为
=x2+y2+2x+y≥0≥−0.5
函数的等⾼线及两个约束的图像如下：
这⾥写图⽚描述
此时优化命题的解仍然是 (0,−0.5) ，但在最优点处两条约束均被激活，即此时的有效集可以记为
桥式电路A∗={1,2}
有效集法
从上⾯可以看出，如果我们能提前知道在最优点处有效的约束，那我们就可以把那些未有效的不等式约束剔除掉并把原命题转化成更易求解的等式约束命题。然⽽，在求解之前我们往往对最优点处的有效约束知之甚少。因此如何找到最优点处的有效约束也就是有效集法的主要⼯作。另外在这⾥要提⼀点，其实在⼀些应⽤中，我们需要求解⼀系列类似的 QP 命题，这个时候我们往往对最优点处的有效约束有⼀个初始猜测，因此通过这种⽅式可以实现算法的热启动（Warm Start），从⽽加速算法的收敛。下⾯我们正式开始介绍 ASM 的理论。我们考虑的是带有不等式约束的凸⼆次规划命题：
minxq(x)subject toaTix=12xTGx+xTc≥bi,i∈I
在 ASM 中，我们会构造⼀个⼯作集（Working Set），与有效集类似，⼯作集也是有效约束的集合，但只是我们认为在某次迭代中有效约束的集合，它可能与最优点处的有效集相同，也有可能不同。如果相同，我们可以通过计算对偶变量 λ
了解到此时已经是最优点从⽽退出迭代。如果不同，我们会对⼯作集进⾏更新，从现有⼯作集中删除⼀条约束或者增加⼀条新的约束到⼯作集中。因为⼯作集是随着迭代⽽改变的，因此记⼯作集为 Wk
。
在第 k
次迭代开始时，我们⾸先检查当前的迭代点 xk 是否是当前⼯作集 Wk 下的最优点。如果不是，我们就通过求解⼀个等式约束的 QP 命题来得到⼀个前进⽅向 p ，在计算 p 的时候，我只关注 Wk
我来比划你来猜词语库中的等式约束⽽忽略原命题的其他约束。为了便于计算，我们定义
p=x−xk,gk=Gxk+c
把上⾯的定义代⼊原命题有：
q(x)=q(xk+p)=12pTGp+gTkp+ρk
其中 ρk=12xTkGxk+xTkc
在这⾥可以看作是常数因此可以从上⾯的优化命题中去掉。因此我们可以写出如下所⽰的在第 k
次迭代需要求解的 QP ⼦命题：
痛苦ss天赋minqsubject to12pTGp+gTkpaTip=0,i∈Wk
草色青青我们记上⾯的命题求解得到的最优解为 pk
，
⾸先假定求解得到的 pk 不为0∗。即我们有了⼀个⽅向使得沿着这个⽅向⽬标函数会下降，然后我们需要确定⼀个步长 αk 来决定⾛多远。如果 xk+pk 对于所有原命题的约束都是可⾏的，那么此时的 αk=1，否则 αk 则是⼀个⼩于1的正数。定义步长 αk
之后我们就可以得到迭代点更新的式⼦：
xk+1=xk+αkpk
关于步长 αk
的计算，我们有如下的分析。其实，步长的计算主要就是要保证新的迭代点不要违反原命题的约束，那么在⼯作集 Wk 内的约束就不⽤担⼼了，因为在求解 pk 的过程中就已经保证了⼯作集内的约束必须得到满⾜。那么对于⾮⼯作集中的约束 i∉Wk，我们⾸先判断 aTipk 的符号，如果 aTipk≥0 ，那么通过分析可知只要步长 αk ⼤于0，则该约束⼀定可以满⾜，因此我们需要关注的主要就是 aTipk<0 的那些约束。为了保证原命题中的约束 aTi(xk+αkpk)≥bi 能够满⾜，我们需要使得 αk
满⾜
αk≤bi−aTixkaTipk
因此，我们可以把计算 αk
的⽅法显式地写出来：
αk=min(1,mini∉Wk,aTipk<0bi−aTixkaTipk)
要注意的是，虽然我们这⾥的确把 αk
显式地表⽰出来，但仔细看就会发现求解 αk 其实还是⼀个逐条约束去检查的过程。⽐如对于我们从 αk=1 开始，逐条约束开始判断，⾸先判断如果 aTipk≥0 则直接跳到⼀条约束，否则可以判断 αk 与 bi−aTixkaTipk 的⼤⼩，如果前者⼩于后者，那么没问题可以去检查下⼀条约束，否则直接令 αk 取值为后者。以我⾃⼰的经验，当原命题的约束个数较多时，计算步长 αk
往往是⼀个⽐较耗时的环节。如果能有什么好办法可以削减这部分的计算量，那么对于 QP 的加速求解将会是很有益的⼯作。
当我们在计算 αk
的时候，每条约束都会对应⼀个不违反其约束的最⼩的 αk 的值，⽽且在最⼩的 αk 就是这次迭代的步长值 αk ，⽽这条约束就被称为blocking constraint（如果 αk=1 且没有新的约束在下⼀步迭代点处激活，那么此次迭代没有 blocking constraint）。注意，也有可能出现 αk=0 的情况，这是因为在当前迭代点处有其他的有效约束没有被添加到⼯作集中。如果 αk<1， 也就是说下降⽅向 pk 被某条不在⼯作
集 Wk 内的约束阻拦住了。因此我们可以通过将这条约束添加到⼯作集的⽅法来构造新的⼯作集 Wk+1
。
通过上⾯的⽅法我们可以持续地向⼯作集内添加有效约束，直到在某次迭代中我们发现当前的迭代点已经是当期⼯作集下的最优点。这种情况很容易判断，因为此时计算出来的 pk=0
。接下来我们就要验证当前的迭代点是不是原命题的最优点，验证的⽅法就是判断⼯作集内的约束对应的对偶变量 λ 是否都⼤于等于 0，如果满⾜这⼀点，那么所有的 KKT 条件都成⽴，可以退出迭代并给出原命题的最优解（关于这部分的推导，详细内容请见原书的 16.5节）。λ
的计算由下式给出
∑i∈W^aiλi^=g=Gx^+c
陆水湖如果通过上式计算出来的有⼀个或者多个 λ^i
的值⼩于 0。那么就表明通过去掉⼯作集的某⼀条或⼏条约束，⽬标函数值可以进⼀步下降。因此我们会从对应的 λ^i 值⼩于 0 的约束中选择⼀条，将其从⼯作集 Wk 中剔除从⽽构造出新的⼯作集 Wk+
1 。如果有多于⼀条的可选约束，那么不同的剔除⽅法会遵循不同原则，我们在这⾥不加更多说明地遵循去除对应 λ^i
值最⼩（绝对值最⼤）的那条约束。
基于上⾯的讨论，我们可以得到⼀个 Primal 的 ASM 的算法，具体的算法可见原书 Algorithm 16.3，这⾥我们给出⼀个算法的流程图。
这⾥写图⽚描述
这⾥要注意，Primal ASM 算法的迭代点都是在可⾏域内或者可⾏域的边界上移动，这样的好处是即使你提前终⽌迭代，那么算法得到的也是⼀个可⾏解（Dual 的算法往往不能保证这⼀点）。⽽这样的缺点则是在算法启动是需要我们给定⼀个可⾏的初始点，⽽求解这样⼀个可⾏的初始点往往也不是⼀件简单的事情。现在的⼀种⽅法是通过⼀个 Pha I 的过程来得到这样⼀个可⾏的初始点，也就是求解⼀个只有约束的线性规划命题。⽽初始的⼯作集往往可以取为空集。
举例
我们⽤下⾯这个⼆维的例⼦来说明 ASM 算法的过程。
minxq(x)=(x1−1)2+(x2−2.5)2ssubject tox1−2x2+2−x1−2x2+6−x1+2x2+2x1x2≥0,≥0,≥0,≥0,≥0.
⽰意图如下：
这⾥写图⽚描述
假设此时迭代初始点为 x0=(2,0)T
，
初始的⼯作集为 W0={3,5} 。注意此时初始⼯作可以只有约束 3 或 5，也可以是空集，这⾥我们只是举⼀个 W0={3,5} 的例⼦。当这两条约束点都激活时，迭代点 x0=(2,0) 显然是当前⼯作集下的最优点，即 p0=0。因此我们有 x1=(2,0)T。当 p0=0 时，我们需要检查对偶变量 λ 的符号。计算可以得到 (λ^3,λ^5)=(−2,−1)
。因为不是所有的对偶变量都是正值，说明当前迭代点不是最优点，因此我们需要从⼯作集中删除⼀条约束，这⾥我们选择删除对应的对偶变量的绝对值最⼤的值所对应的约束，即第 3 条约束。
婴儿趴着睡即此时⼯作集内只有第 5 条约束， W1={5}
。在当前的⼯作集下计算得到的 p1=(−1,0)T 。因为在前进的路上没有 blocking constraint 的阻碍，因此计算得到的步长 α1=1。同时我们可以得到新的迭代点 x2=(1,0)T
。
因为步长 α1=1
，因此我们在⼯作集不变的情况下，即 W2={5}，再求解⼀次等式约束命题，此时我们会得到前进⽅向 p2=0，因此更新后的迭代点为
x3=(1,0)T。因此我们去检查各个对偶变量的正负号，通过计算可得 λ^5=−5
，说明当前点不是最优点，同时我们将约束 5 从⼯作集中删除。
此时⼯作集为空集，即 W3=∅
。此时求解下降⽅向就相当于在求解⼀个⽆约束命题，从图中可以看出，下降⽅向为 p3=(0,2.5)。然⽽此时，在下降的⽅向上有 blocking constraint 的存在，因此计算得到的步长为 α3=0.6，同时我们得到新的迭代点为 x4=(1,1.5)T，同时我们将 blocking constraint 添加到⼯作集中得到更新后的⼯作集为 W4={1}
。
此时进⼊下⼀次迭代，求解得到的下降⽅向为 p4=(0.4,0.2)
。并且在前进的⽅向上没有 blocking constraint，因此求得的步长为 1 。得到的新的迭代点为 x5=(1.4,1.7)T。因为步长为 1，因此我们在不改变⼯作集的情况下再计算⼀次下降⽅向，得到 p5=0，此时我们检查对偶变量的值，发现 λ^1=0.8 是正值，说明当前的迭代点已经是最优点。因此我们退出迭代，并得到问题的最优解 x∗=(1.4,1.7)T
。
通过上⾯这张图，我们可以较为清楚地了解 ASM 算法的计算流程。
后记
数铣最后要提⼀点，关于算法的收敛性，原书中的定理 16.6 证明了，只要每次迭代的前进⽅向 pk
