KKT条件

KKT 条件把有约束最优化的“可行”“驻点”与“哪些约束真正起作用”合在一起。对可微问题 $min{f}_0(x)$，约束 $f_i(x)\le 0$、$h_j(x)=0$，若 $x^{\ast }$ 与乘子 ${\lambda }_i\ge 0,{\nu }_j$ 满足 $$\begin{array}{cc}{f}_i(x^{\ast })& \le 0,h_j(x^{\ast })=0,\\ {\lambda }_i& \ge 0,{\lambda }_i{f}_i(x^{\ast })=0,\\ \mathrm{\nabla }{f}_0(x^{\ast })+\sum _i{\lambda }_i\mathrm{\nabla }{f}_i(x^{\ast })+\sum _j{\nu }_j\mathrm{\nabla }{h}_j(x^{\ast })& =0,\end{array}$$ 便满足原始可行性、对偶可行性、互补松弛与驻点四组条件。

约束何时施力

继续看 $min{x}^2$ 且 $x\ge 1$。写 $f_1(x)=1-x\le 0$，最优 $x^{\ast }=1$ 处约束正好取等号。驻点式 $2x^{\ast }-\lambda =0$ 给 $\lambda =2$，其余条件也满足。若某约束严格有余量 $f_i(x^{\ast })<0$，互补松弛迫使对应 ${\lambda }_i=0$；这就是“未卡住解的约束没有乘子压力”的精确含义。

充分与必要分开说

若 $f_0,f_i$ 凸、等式约束 $h_j$ 仿射，并且找到满足 KKT 的点，则该点是全局最优：对任意可行 $y$，凸函数的一阶下界与驻点式合用即可推出 $f_0(y)\ge f_0(x^{\ast })$。反过来，要保证最优点一定有 KKT 乘子，还需约束资格条件；例如 Slater 条件在适当凸问题中提供这一点。非凸问题即使满足 KKT，也未必全局最优。

具体地，凸性给 $f_0(y)\ge f_0(x^{\ast })+\mathrm{\nabla }{f}_0(x^{\ast }{)}^{𝖳}(y-x^{\ast })$。把驻点式代入右边，并对每个 $f_i$ 用 $f_i(y)\ge f_i(x^{\ast })+\mathrm{\nabla }{f}_i(x^{\ast }{)}^{𝖳}(y-x^{\ast })$，得到 $$f_0(y)\ge f_0(x^{\ast })+\sum _i{\lambda }_i(f_i(x^{\ast })-f_i(y)).$$ 仿射等式的差为零；互补松弛使 ${\lambda }_i{f}_i(x^{\ast })=0$，而 $y$ 可行使 $-{\lambda }_i{f}_i(y)\ge 0$。故右边不小于 $f_0(x^{\ast })$，全局最优性由此成立。

参考资料

• Boyd 与 Vandenberghe，Convex Optimization，KKT Conditions。
• MIT 6.079，凸优化讲义。
• 继续阅读：拉格朗日对偶、凸函数、拉格朗日乘数法。