KKT条件

对于不等式约束优化问题

$$\begin{gathered} \min f(x) \\ s.t.g(x)\le 0 \end{gathered}$$

拉格朗日函数为 $L(x,\lambda )=f(x)+\lambda g(x)$ 。

KKT条件包括

• 拉格朗日函数的定常方程式: ${\nabla }_{x}L=\nabla f+\lambda \nabla g=0$
• 原始可行性: $g(x)\le 0$
• 对偶可行性: $\lambda \ge 0$
• 互补松弛性: $\lambda g(x)=0$

假设 $x^{\ast }$ 为满足约束条件的最佳解

• $g(x^{\ast })<0$：最佳解在可行域的内部，称为内部解，此时约束条件无效， $x^{\ast }$ 满足 $\nabla f=0,\lambda =0$
• $g(x^{\ast })=0$：最佳解在可行域的边界，称为边界解，此时约束条件有效，约束不等式变成约束等式 $g(x)=0$ 。并且，此时 $\nabla f$ 一定指向可行域内部，而 $\nabla g$ 一定指向可行域外部，而 $\nabla f+\lambda \nabla g=0$ ，得到 $\lambda \ge 0$

因此，不论是内部解还是边界解，$$\lambda g(x)=0$$ 恒成立，也就是互补松弛条件

原始问题和对偶问题

$$\begin{gathered} \underset{x}{\min }f(x) \\ s.t.\begin{array}{rl}& c_i(x)\le 0,i=1,2,\cdots ,K\\ & h_j(x)=0,j=1,2,\cdots ,L\end{array} \end{gathered}$$

拉格朗日函数

$$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^K{\alpha }_i{c}_i(x)+\sum _{j=1}^L{\beta }_j{h}_j(x)$$

原始问题

是先取关于拉格朗日乘子 $\alpha ,\beta$ 的 $\max$ ，再取关于参数的 $\min$

因为 $\alpha \ge 0$ ，因此在可行域外（$c_i(x)\le 0$），如果取 $\alpha$ 接近于正无穷，那么 $L(x,\alpha ,\beta )$ 也会趋近于正无穷，只有在可行域内，才存在max，也就是 $f(x)$ 。

对偶问题

先取关于参数的 $\min$ ，再取关于拉格朗日乘子 $\alpha ,\beta$ 的 $\max$

显然，对偶问题的最小值一定小于等于原始问题的最小值。

参考

Karush-Kuhn-Tucker (KKT)条件
统计学习方法 李航