1 什么是KKT条件

不等式约束的原始问题描述为：

含有不等式约束的KKT条件为如下式①所示：

注意，KKT条件是非线性规划最优解的必要条件

2.KKT条件描述型理解

(1)当最优解 x* 满足g(x*) <0时，最优解位于可行域内部，此时不等式约束无效，λ=0。

(2)当最优解 x*满足g(x*) = 0时，最优解位于可行域的边界，此时不等式约束变为等式约束，g(x)=0。

(3)同时根据几何意义，λ必<0（根据梯度可得）。

根据上面的讨论，既然我们需要的是必要条件，那么可以通过对上述情况进行并集运算得到最优解的必要条件，即公式②：

(4)当有多个不等式约束时，可推广至式①形式。

3.数学推导

3.1

以如下优化问题为例进行推导：

假设该问题的最优值为p*。现在考虑求p*的下界。

构造一个新函数：

并要求λi >= 0，由于，故总有，即L为目标函数的下界。L称为原优化问题的Lagrange函数，λ，v成为原问题的Lagrange乘子。

对不等式两边同时对变量x最小化，可以得到p*的下界

上式为对任意λ，v的p*的下界，我们需要最接近p*的下界，即最大下界（称为最好的下界）。求最好下界的过程表述如下最优化问题：

此问题称为原优化问题的Lagrange对偶问题。

3.2

设Lagrange对偶问题的最优值为d*，故有如下不等式：

这是最一般的性质，不需要原始优化问题满足任何条件，称为弱对偶。

对应弱对偶的是强对偶，即：

强对偶性需要原问题的目标函数为凸函数，且满足Slater规则。

强对偶性成立时，假设x*为原问题的最优解，（λ*，v*）为对偶问题的最优解，有

所以：

因为：

所以：

上述这条性质称为互补松弛性，直观理解为若原问题中的约束为紧约束（），则对应的对偶问题中的对偶变量为松的（λi>0），反之若约束为松，则对偶变量为紧。

3.3总结

上述描述的为原问题最优解x*，对偶问题最优解（λ*，v*）所满足的条件，即必要条件。如果原问题时凸问题时，则为充要条件，也就是能够求得全局最优解的方法。

4 KKT条件总结

kkt条件要求强对偶，形式如下：

前两条为x*满足的原问题的约束。第三条表示对偶变量满足的约束，第四条为互补松弛条件，第五条表示Lagrange函数在x*处取得极小值（即x*是最优解，满足Lagrange函数极小的条件）。

5 参考链接

斯坦福大学凸优化对偶