AI 与工程数学 / 系统课时

检查互补松弛与活跃约束

检查互补松弛与活跃约束

求出一个带不等式约束的候选解后,还要判断究竟哪些约束真正卡住了最优点。本节用 KKT 条件中的互补松弛,把“约束是否取等号”和“拉格朗日乘子是否为零”联系起来,并据此识别决定最终解的活跃集。

学习目标

  • 根据约束函数值判断活跃约束与非活跃约束
  • 使用互补松弛检查拉格朗日乘子是否合理
  • 理解活跃约束、正乘子与最终最优解之间的关系

从约束是否取等号开始

考虑带不等式约束的问题

min⁡xf(x),gi(x)≤0.\min_x f(x),\quad g_i(x)\le 0.

在候选最优点 x∗x^* 上,如果 gi(x∗)=0g_i(x^*)=0,该约束称为活跃约束;如果 gi(x∗)<0g_i(x^*)<0,说明当前点与边界仍有余量,它就是非活跃约束。

例如变量满足 0≤x≤10\le x\le 1,写成标准形式可取 g1(x)=x−1≤0g_1(x)=x-1\le0 与 g2(x)=−x≤0g_2(x)=-x\le0。当 x∗=1x^*=1 时,上界约束取等号,因此 g1g_1 活跃;下界仍有一个单位的余量,所以 g2g_2 非活跃。

活跃约束与互补松弛关系

活跃集通常记为

A(x∗)={i∣gi(x∗)=0}.A(x^*)=\{i\mid g_i(x^*)=0\}.

一旦知道活跃集,就能把注意力集中在真正贴住边界的约束上,而不是把所有不等式都当作同等重要。

互补松弛如何筛掉非活跃约束

KKT 条件要求每个不等式约束都有乘子 λi≥0\lambda_i\ge0,并满足互补松弛

λigi(x∗)=0.\lambda_i g_i(x^*)=0.

这个乘积等于零带来两个关键结论。若 gi(x∗)<0g_i(x^*)<0,约束还有严格余量,那么为了使乘积为零,只能有 λi=0\lambda_i=0。因此非活跃约束不会在驻点条件中贡献任何力。

反过来,如果 λi>0\lambda_i>0,就必然有 gi(x∗)=0g_i(x^*)=0,说明该约束一定活跃。不过要注意,活跃约束并不保证乘子一定严格大于零;退化问题中完全可能同时出现 gi(x∗)=0g_i(x^*)=0 和 λi=0\lambda_i=0。

用一个候选解完整检查

考虑

min⁡x(x−2)2,0≤x≤1.\min_x (x-2)^2,\quad 0\le x\le1.

把约束写为 g1(x)=x−1≤0g_1(x)=x-1\le0、g2(x)=−x≤0g_2(x)=-x\le0。无约束最优点是 x=2x=2,落在可行区间之外,因此直觉上最优解会被上界挡在 x∗=1x^*=1。

下面直接检查约束值、互补松弛以及驻点条件。代码是完整可运行示例。

python
x = 1.0
lambda1 = 2.0
lambda2 = 0.0

g1 = x - 1.0
g2 = -x
grad_f = 2.0 * (x - 2.0)

# g1 的梯度为 1,g2 的梯度为 -1。
stationarity = grad_f + lambda1 - lambda2
active = [
    name
    for name, value in [("g1", g1), ("g2", g2)]
    if abs(value) < 1e-9
]

print(f"g1={g1:.1f}, g2={g2:.1f}")
print(f"lambda1*g1={lambda1 * g1:.1f}, lambda2*g2={lambda2 * g2:.1f}")
print(f"stationarity={stationarity:.1f}")
print(f"active constraints: {active}")

预期输出

text
g1=0.0, g2=-1.0
lambda1*g1=0.0, lambda2*g2=-0.0
stationarity=0.0
active constraints: ['g1']

这里 g1=0g_1=0,所以上界活跃;g2=−1<0g_2=-1<0,所以下界非活跃并对应 λ2=0\lambda_2=0。同时 λ1=2\lambda_1=2 抵消了目标函数在边界处继续向右下降的趋势,这正是上界真正限制最优解的含义。

从活跃集判断哪些约束决定解

实际检查一个候选解时,可以按固定顺序处理:先计算所有 gi(x∗)g_i(x^*) 并确认原始可行性,再找出接近零的约束,然后检查乘子非负性和 λigi(x∗)\lambda_i g_i(x^*),最后将乘子代入驻点条件。

数值算法不会总得到精确的零,因此工程实现中通常采用容差。例如把 ∣gi(x∗)∣≤10−6|g_i(x^*)|\le10^{-6} 暂时视为活跃,而不是直接使用浮点数的精确相等比较。容差过大会把接近边界但尚未活跃的约束误判进去,过小则可能漏掉受数值误差影响的真实活跃约束。

对于满足适当约束资格条件的凸优化问题,如果候选点同时满足原始可行性、对偶可行性、互补松弛和驻点条件,KKT 条件就能给出非常强的最优性判断。活跃集告诉你“哪些边界贴住了解”,乘子则进一步说明这些边界在一阶最优条件中承担了多大的约束作用。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

检查互补松弛与活跃约束

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通