KKT 条件

形式陈述 ​

考虑可微问题

$$\underset{x}{min}{f}_0(x),f_i(x)\le 0(i=1,\dots ,m),h_j(x)=0(j=1,\dots ,p),$$

并定义 $L(x,\lambda ,\nu )=f_0(x)+\sum _i{\lambda }_i{f}_i(x)+\sum _j{\nu }_j{h}_j(x)$。点 $(x^{\ast },{\lambda }^{\ast },{\nu }^{\ast })$ 满足 KKT 条件，指以下四项同时成立：

1. 原始可行：$f_i(x^{\ast })\le 0$ 且 $h_j(x^{\ast })=0$；
2. 对偶可行：${\lambda }_i^{\ast }\ge 0$；
3. 互补松弛：${\lambda }_i^{\ast }{f}_i(x^{\ast })=0$；
4. 驻点：$\mathrm{\nabla }{f}_0(x^{\ast })+\sum _i{\lambda }_i^{\ast }\mathrm{\nabla }{f}_i(x^{\ast })+\sum _j{\nu }_j^{\ast }\mathrm{\nabla }{h}_j(x^{\ast })=0$。

三种结论必须分开。一般光滑问题的局部最优点只有在适当约束资格（如 LICQ 或 MFCQ）下才必有 KKT 乘子。若 $f_0,f_i$ 凸且 $h_j$ 仿射，则任何满足 KKT 的点都是全局最优解，这是充分性。若该凸问题还满足 Slater 条件并且最优解存在，则最优点存在乘子并满足 KKT，因而 KKT 成为充要证书。

直觉 ​

在最优点处，目标梯度不能指向任何可行的一阶下降方向。活跃约束 $f_i(x^{\ast })=0$ 的梯度是边界法向量，乘子把这些法向量与等式约束法向量组合起来，恰好抵消目标梯度；不活跃约束还有余量，不应贡献阻力，所以互补松弛迫使对应乘子为零。约束资格保证这些一阶法向量确实足以描述局部可行几何。

例子与边界 ​

考虑 $\underset{x}{min}(x-a{)}^2$，约束 $x\ge 0$，写作 $f_1(x)=-x\le 0$。KKT 驻点为 $2(x-a)-\lambda =0$，另有 $x\ge 0$、$\lambda \ge 0$、$\lambda x=0$。若 $a>0$，最优点 $x^{\ast }=a$，约束不活跃且 ${\lambda }^{\ast }=0$；若 $a<0$，最优点 $x^{\ast }=0$，约束活跃且 ${\lambda }^{\ast }=-2a>0$。同一问题清楚展示了乘子何时消失、何时承担边界法向力。

约束资格不能删。对 $\underset{x}{min}x$，约束 $x^2\le 0$，唯一可行点 $x^{\ast }=0$ 当然是最优点；但驻点方程要求 $1+\lambda \cdot 2x^{\ast }=0$，即 $1=0$，不存在任何 KKT 乘子。失败原因是活跃约束在原点的梯度为零，无法表达真实可行集。由此不能笼统宣称“KKT 当且仅当最优”。

推论与应用 ​

KKT 条件把Lagrange 对偶公理库拉格朗日对偶Lagrange duality通过拉格朗日函数构造原问题下界的对偶问题，并研究弱对偶、强对偶与最优性条件。的零对偶间隙变成可核验的原始—对偶证书：原始可行、对偶可行与互补松弛共同使两侧目标相等。在线性与二次规划中，它给出活跃集方法和原始—对偶内点法的方程骨架；在支持向量机中，互补松弛区分支持向量与非支持样本。对不可微凸问题，驻点方程需改用次梯度；若定义域边界没有显式列为约束，还应加入相应法锥。

参考资料

• Stephen Boyd and Lieven Vandenberghe, Convex Optimization, Cambridge University Press, 2004, §5.5, KKT optimality conditions.
• Stanford EE364a, Duality lecture notes, KKT conditions, Slater's condition, and optimality certificates.
• Jorge Nocedal and Stephen J. Wright, Numerical Optimization, 2nd ed., Springer, 2006, Ch. 12, constraint qualifications and first-order conditions.