“在上述凸问题中,KKT 的驻点先保证 Lagrange 函数达到全局下确界,再由原始可行、对偶可行与互补松弛使两侧目标相等,形成可核验的原始—对偶证书。在线性与二次规划中,活跃集法通过阻挡步…”
形式陈述
取正整数
二次型的正定性保证非空可行集上存在唯一最优点。给定可行初值,令
在当前点记
通过线性方程组计算唯一方向与工作乘子:
迭代分成两支。
- 若
,取 内层集合为空时只取一。令 ;若某条约束达到最小比值且 ,将一个阻挡约束加入工作集。 - 若
,检查 。若所有分量非负,令工作集外乘子为零,得到完整KKT 证书并终止;否则删除一条负乘子约束,保留同一个 ,重解方向。
主算法假设工作集一直线性独立,并且每次阻挡移动具有正步长;并列可用固定索引顺序选择。实现遇到零步长、相关工作行或重复状态时,应进入明确的退化处理,而不能靠放宽可行性冒充正常进展。
直觉
先假定几面墙暂时不能离开,在这些墙的交面内寻找二次目标的最低点。若路上撞到另一面墙,就停在它前面,把它加入工作集。若已经在当前面的最低点,乘子告诉我们哪些墙是真正阻力,哪些只是错误地把自己锁住。
对于
例子与边界
两次释放和一次阻挡
求
把三条约束依次编号为
- 两条下界都固定。 方向只能为零。梯度为
,由 得 。删除乘子更负的约束一。 - 只固定
。 子问题给 。斜边的阻挡比值为 ,所以走完整步到 ,并将约束三加入。此时 。 - 右顶点的工作方向为零。 梯度为
。驻点方程给 ,因此释放约束二,留下 。 - 沿斜边优化。 方向满足
。解方程得 、 。没有新约束提前阻挡,走到 。 - 终止核验。 重解后
,乘子为 ,三条约束可行,互补关系成立,梯度 被斜边法向力抵消。
目标从
紧约束可以不在工作集里
第一条下界刚被释放时,点仍为原点,所以
约束冗余也需要处理。若额外加入
推论与应用
两个不变量与终止证书
工作方程
把方向方程左乘
故对
这解释为什么可以沿面内方向走到第一面阻挡墙,而不需要另加普通线搜索。
删去负乘子约束后,为什么会获得自由?在独立工作行下,可以选方向
退化与计算成本
每次删除约束之前,零方向意味着当前点是该工作面上唯一的最小点。删除负乘子后,非退化假设保证随后有正步长下降,因而不可能再以相同工作集回到同一个面最小点。两次删除之间,阻挡步骤每次增加一条独立工作行,至多增加
若本轮有
在序列二次规划中,本页可以作为局部 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,线性约束与工作集方法。