机器学习数学基础 120 章

KKT 条件与互补松弛

层级：B｜按需

1. KKT 是约束最优的统一检查表

Karush–Kuhn–Tucker（KKT）条件把等式 Lagrange 法推广到不等式约束。SVM 支持向量为何只有部分样本的乘子非零、L1 为何出现阈值结构、对偶解如何恢复原始解，都依赖 KKT。

2. 原问题与 Lagrangian

采用标准形式：

min⁡xf(x)s.t.gi(x)≤0,i=1,…,m,hj(x)=0,j=1,…,q.\begin{aligned} \min_x\quad&f(x)\\ \text{s.t.}\quad&g_i(x)\le0, i=1,\ldots,m,\\ &h_j(x)=0, j=1,\ldots,q. \end{aligned}

Lagrangian：

L(x,α,λ)=f(x)+∑iαigi(x)+∑jλjhj(x),\mathcal L(x,\alpha,\lambda) =f(x)+\sum_i\alpha_i g_i(x) +\sum_j\lambda_jh_j(x),

其中不等式乘子要求 αi≥0\alpha_i\ge0，等式乘子 λj\lambda_j 可任意实数。

3. 四组 KKT 条件

1）原始可行性

gi(x∗)≤0,hj(x∗)=0.g_i(x^*)\le0, \qquad h_j(x^*)=0.

候选解必须满足原约束。

2）对偶可行性

αi∗≥0.\alpha_i^*\ge0.

3）驻点条件

∇f(x∗)+∑iαi∗∇gi(x∗)+∑jλj∗∇hj(x∗)=0.\nabla f(x^*) +\sum_i\alpha_i^*\nabla g_i(x^*) +\sum_j\lambda_j^*\nabla h_j(x^*)=0.

4）互补松弛

αi∗gi(x∗)=0∀i.\alpha_i^*g_i(x^*)=0 \quad\forall i.

每个不等式约束的“松弛量”与乘子不能同时非零。

4. 互补松弛的含义

对约束 gi(x)≤0g_i(x)\le0：

  • 若严格不活跃 gi(x∗)<0g_i(x^*)<0，则必须 αi∗=0\alpha_i^*=0；
  • 若 αi∗>0\alpha_i^*>0，则必须 gi(x∗)=0g_i(x^*)=0，约束活跃；
  • 活跃约束也可能乘子为 0（退化情形）。

只有真正限制最优解的约束才能产生非零“法向力”。

5. 一维例子

min⁡x(x−3)2s.t. x≤1.\min_x(x-3)^2 \quad\text{s.t. }x\le1.

令 g(x)=x−1≤0g(x)=x-1\le0：

L=(x−3)2+α(x−1).\mathcal L=(x-3)^2+\alpha(x-1).

KKT：

2(x−3)+α=0,2(x-3)+\alpha=0, x−1≤0,quadα≥0,quadα(x−1)=0.x-1\le0,quad\alpha\ge0,quad\alpha(x-1)=0.

若约束不活跃则 α=0\alpha=0、x=3x=3，但不可行；所以约束活跃 x=1x=1，进而 α=4\alpha=4。

6. 为什么乘子必须非负

对可行点 gi(x)≤0g_i(x)\le0，若 αi≥0\alpha_i\ge0：

L(x,α,λ)lef(x)\mathcal L(x,\alpha,\lambda)le f(x)

（等式项为零）。这保证 Lagrange 对偶函数为原问题最优值的下界。若标准形式写成 gi≥0g_i\ge0，乘子符号会相应反转。

7. 必要与充分条件

一般非凸问题中，满足约束资格条件的局部最优点满足 KKT，但 KKT 点不一定全局最优。

若：

  • f,gif,g_i 凸；
  • hjh_j 仿射；
  • 存在严格满足不等式的点（Slater 条件，适当形式）；

则 KKT 对原—对偶最优通常既必要又充分，并有强对偶。

8. SVM 中的互补松弛

硬间隔约束：

1−yi(wTxi+b)≤0.1-y_i(w^Tx_i+b)\le0.

乘子 αi≥0\alpha_i\ge0，互补松弛：

αi[1−yi(wTxi+b)]=0.\alpha_i[1-y_i(w^Tx_i+b)]=0.

若样本严格在间隔外，括号 <0<0，故 αi=0\alpha_i=0；只有落在间隔边界上的样本可能 αi>0\alpha_i>0，它们是支持向量，并决定分类超平面。

软间隔还有松弛变量与上界 0≤αi≤C0\le\alpha_i\le C，不同区间对应正确在间隔外、在间隔上、间隔内或误分类。

9. 活跃集方法

若知道最优点哪些约束活跃，可把它们当等式约束求解，再检查乘子和其他约束。活跃集算法在“猜测—求解—更新”间迭代。互补松弛正是选择活跃约束的代数条件。

10. KKT 残差用于数值检查

数值解不精确满足方程，可报告：

  • 原始不可行度；
  • 对偶不可行度；
  • 驻点残差范数；
  • 互补残差；
  • 原—对偶间隙。

只看目标值停止可能得到违反约束的解。

易错点

  1. 乘子符号依赖约束写成 g≤0g\le0 还是 g≥0g\ge0。
  2. 互补松弛不是说 α\alpha 和 gg 都为零，只要求乘积为零。
  3. 活跃约束可能乘子为零。
  4. 非凸问题的 KKT 点不保证全局最优。
  5. 必须检查约束资格条件和原始可行性。

常见问答

Q1：支持向量为何“支持”了边界？

只有它们对偶乘子非零，w=∑iαiyixiw=\sum_i\alpha_iy_ix_i 中只有这些样本有贡献；移动非支持向量的小量通常不改变最优边界。

Q2：KKT 与梯度为零是什么关系？

无约束时约束项消失，驻点条件退化为 ∇f=0\nabla f=0；有约束时梯度由活跃约束法向的线性组合抵消。

Q3：Slater 条件是什么直觉？

存在一个对所有凸不等式严格可行、同时满足仿射等式的点，说明可行域有足够“内部”，避免某些边界退化，常保证强对偶。

练习

  1. 为 min⁡x2\min x^2 s.t. x≥1x\ge1 写标准 g≤0g\le0 与 KKT。
  2. 求最优 xx 与乘子。
  3. 若某约束严格满足，乘子必须是什么？
  4. 互补松弛如何解释硬间隔 SVM 的非支持向量？
  5. 非凸问题满足 KKT 后还能直接宣布全局最优吗？

答案与提示

  1. g(x)=1−x≤0g(x)=1-x\le0；2x−α=0,1−x≤0,α≥0,α(1−x)=02x-\alpha=0,1-x\le0,\alpha\ge0,\alpha(1-x)=0。
  2. x=1,α=2x=1,\alpha=2。
  3. 0。
  4. 间隔约束严格时乘子为 0，不进入 ww 的对偶展开。
  5. 不能。