KKT条件介绍

KKT是非线性规划领域的重要成果，它是判断某点是极值点的必要条件。对于凸规划，KKT条件就是充要条件了，只要满足就是一定是极值点，且一定得到是全局最优解。

问题模型

“等式约束+不等式约束” 优化问题。

设目标函数f(x)，不等式约束为g(x)和h(x)，此时的约束优化问题描述如下：

$min\:\:\:\:f(x)$

$s.t.\:\:\:\:\:h_{j}(x)=0\:\:\:\:\:\:j=1,2,\dots,p$

$g_{k}(x)\leq 0\:\:\:\:\:\:j=1,2,\dots,q$

我们定义不等式约束下的拉格朗日函数L, 则L表达式为:

$L(x,\lambda,\mu)=f(x)+\sum_{j=1}^{p}\lambda_{j} h_{j}(X)+\sum_{k=1}^{q}\mu_{k}g_{k}(x)$

其中f(x)是目标函数，$h_{j}(x)$是第j个等式约束条件，$\lambda_{j}$ 是对应的约束系数，$g_{k}(x)$ 是不等式约束，$\mu_{k}$是对应的约束系数(松弛变量)。

一点铺垫

实质上，KKT条件描述的是：这个点已经是可行域的边界了，再走一点就不满足约束条件了。显然，最优解一定在可行域的边界上的。如下图例子所示:

这张图的紫色区域就是四个不等式约束限定的可行域，如果求z=x+2y的最大值，结果当然是红星店取得最大值，总之极值点应该在可行域的边界，这在自变量多的高维可行域空间同样适用。

KKT到底是什么

KKT条件就是说：如果一个点x是满足所有约束的极值点，那么该点x就要满足一下所有条件，即KKT条件:

$\nabla f(x)+\sum_{j=1}^{p}\lambda_{j}\nabla h_{j}(X)+\sum_{k=1}^{q}\mu_{k}\nabla g_{k}(x)=0$

$\mu_{k}\geq 0$

$\mu_{k}g_{k}(x)=0$

$h_{j}(x)=0$

$g_{k}(x)\leq 0$

举例

带有不等式约束的最优化问题通常可以表述为如下形式:

$min\: f(x)$

$s.t.\:\:\:\:\:g_{k}(x)\leq 0,k=1,2,\dots,q$

给出一个具体的例子：

$min\:f(d_{1},d_{2})=d_{1}^{2}+d_{2}^{}-2 d_{2}+2$

$s.t.\:\:\:\:\: d_{1}^{2}+d_{2}^{2}<4$

写出拉格朗日函数

$g(d_{1},d_{2},\lambda)=f(d_{1},d_{2})+\lambda (d_{1}^{2}+d_{2}^{2}-4)$

λ是拉格朗日乘子(KKT乘子)，它的目的是能够将不等式约束变为等式约束，主要 λ>=0。等式约束的拉格朗日乘子是不等于0即可的。

求偏导

$g(d_{1},d_{2},\lambda)= f(d_{1},d_{2})=d_{1}^{2}+d_{2}^{}-2 d_{2}+2+\lambda (d_{1}^{2}+d_{2}^{2}-4)$

然后对该式子三个未知量分别求偏导,且令导数函数为0：

$2d_{1}+2\lambda d_{1}=0$

$2d_{2}-2+2\lambda d_{2}=0$

$d_{1}^{2}+d_{2}^{2}-4=0$

$\lambda \geq 0$

计算

根据上面式子可以得出存在两种可能的情况：

第一种情况：
当lamda不等于0的时候，根据上面的式子可以得出 $d_{1}=0$，根据其他的式子可以得到 $d_{2}=+/-2$ ，然后无论 d2 = +2/-2，λ都不满足大于等于0的条件。因此不存在的。

第二种情况：
当λ等0的时候，根据上面的式子可以得出 $d_{1}=1,d_{2}=\sqrt{3}$。因此该式子是正确的。

各种情况下的KKT条件

等式约束下的KKT条件

题目描述：

$minimize\:\:\:\:\:x^{T}x$

$s.t.\:\:\:\:\: Ax=b$

拉格朗日函数:

L(x,v)=x^{T}x+λ(Ax-b)

KKT条件:

$\frac{\partial L(x,\lambda)}{\partial (x)}=0$

$\lambda = 0$ 拉格朗日乘子在等式约束下等于0

$Ax=b$ 等式约束条件

不等式约束下的KKT条件

题目描述：

$maximize\:\:\:\:\:f(x)=(x-3)^{3}$

$s.t.\:\:\:\:\: 1\leq x \leq 5$

等价于：要保证是min f(x)以及不等式约束要小于等于0

$minmize f(x)=-(x-3)^{3}$

$g_{1}(x)=1-x\leq 0$

$g_{2}(x)=x-5\leq 0$

拉格朗日函数:

$L(x,\lambda_{1},\lambda_{2})=f(x)+\lambda_{1}g_{1}(x)+\lambda_{2}g_{2}(x)=-(x-3)^{3}+\lambda_{1}(1-x)+\lambda_{2}(x-5)$

KKT条件:

$\frac{\partial L(x,\lambda_{1},\lambda_{2})}{\partial (x)}=-2(x-3)-\lambda_{1}+\lambda_{2}=0$

$\lambda_{1}g_{1}(x)=\lambda_{1}(1-x)=0$ 不等式约束条件

$\lambda_{2}g_{2}(x)=\lambda_{2}(x-5)=0$ 不等式约束条件

$g_{1}(x)\leq 0$ 不等式约束条件

$g_{2}(x)\leq 0$ 不等式约束条件

$\lambda_{1} \geq 0$ 拉格朗日乘子在不等式约束下大于等于0

$\lambda_{2} \geq 0$ 拉格朗日乘子在等式约束下大于等于0

等式约束和不等式约束结合的KKT条件

题目描述：

$min\:\:\:\:f(x)$

$s.t.\:\:\:\:\:h_{j}(x)=0\:\:\:\:\:\:j=1,2,\dots,p$

$g_{k}(x)\leq 0\:\:\:\:\:\:j=1,2,\dots,q$

拉格朗日函数：

$L(x,\lambda,\mu)=f(x)+\sum_{j=1}^{p}\lambda_{j} h_{j}(X)+\sum_{k=1}^{q}\mu_{k}g_{k}(x)$

KKT条件：

$\nabla f(x)+\sum_{j=1}^{p}\lambda_{j}\nabla h_{j}(X)+\sum_{k=1}^{q}\mu_{k}\nabla g_{k}(x)=0$ 对x求导等于0

$\mu_{k}\geq 0$

$\mu_{k}g_{k}(x)=0$

$h_{j}(x)=0$

$g_{k}(x)\leq 0$