KKT条件介绍

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

问题模型

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

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

m i n      f ( x ) min\:\:\:\:f(x) minf(x)

s . t .       h j ( x ) = 0        j = 1 , 2 , … , p s.t.\:\:\:\:\:h_{j}(x)=0\:\:\:\:\:\:j=1,2,\dots,p s.t.hj​(x)=0j=1,2,…,p

g k ( x ) ≤ 0        j = 1 , 2 , … , q g_{k}(x)\leq 0\:\:\:\:\:\:j=1,2,\dots,q gk​(x)≤0j=1,2,…,q

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

L ( x , λ , μ ) = f ( x ) + ∑ j = 1 p λ j h j ( X ) + ∑ k = 1 q μ k g k ( x ) L(x,\lambda,\mu)=f(x)+\sum_{j=1}^{p}\lambda_{j} h_{j}(X)+\sum_{k=1}^{q}\mu_{k}g_{k}(x) L(x,λ,μ)=f(x)+j=1∑p​λj​hj​(X)+k=1∑q​μk​gk​(x)

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

一点铺垫

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

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

KKT到底是什么

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

∇ f ( x ) + ∑ j = 1 p λ j ∇ h j ( X ) + ∑ k = 1 q μ k ∇ g k ( x ) = 0 \nabla f(x)+\sum_{j=1}^{p}\lambda_{j}\nabla h_{j}(X)+\sum_{k=1}^{q}\mu_{k}\nabla g_{k}(x)=0 ∇f(x)+j=1∑p​λj​∇hj​(X)+k=1∑q​μk​∇gk​(x)=0

μ k ≥ 0 \mu_{k}\geq 0 μk​≥0

μ k g k ( x ) = 0 \mu_{k}g_{k}(x)=0 μk​gk​(x)=0

h j ( x ) = 0 h_{j}(x)=0 hj​(x)=0

g k ( x ) ≤ 0 g_{k}(x)\leq 0 gk​(x)≤0

举例

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

m i n   f ( x ) min\: f(x) minf(x)

s . t .       g k ( x ) ≤ 0 , k = 1 , 2 , … , q s.t.\:\:\:\:\:g_{k}(x)\leq 0,k=1,2,\dots,q s.t.gk​(x)≤0,k=1,2,…,q

给出一个具体的例子：

m i n   f ( d 1 , d 2 ) = d 1 2 + d 2 − 2 d 2 + 2 min\:f(d_{1},d_{2})=d_{1}^{2}+d_{2}^{}-2 d_{2}+2 minf(d1​,d2​)=d12​+d2​−2d2​+2

s . t .       d 1 2 + d 2 2 < 4 s.t.\:\:\:\:\: d_{1}^{2}+d_{2}^{2}<4 s.t.d12​+d22​<4

写出拉格朗日函数

g ( d 1 , d 2 , λ ) = f ( d 1 , d 2 ) + λ ( 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) g(d1​,d2​,λ)=f(d1​,d2​)+λ(d12​+d22​−4)

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

求偏导

g ( d 1 , d 2 , λ ) = f ( d 1 , d 2 ) = d 1 2 + d 2 − 2 d 2 + 2 + λ ( d 1 2 + d 2 2 − 4 ) 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) g(d1​,d2​,λ)=f(d1​,d2​)=d12​+d2​−2d2​+2+λ(d12​+d22​−4)

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

2 d 1 + 2 λ d 1 = 0 2d_{1}+2\lambda d_{1}=0 2d1​+2λd1​=0

2 d 2 − 2 + 2 λ d 2 = 0 2d_{2}-2+2\lambda d_{2}=0 2d2​−2+2λd2​=0

d 1 2 + d 2 2 − 4 = 0 d_{1}^{2}+d_{2}^{2}-4=0 d12​+d22​−4=0

λ ≥ 0 \lambda \geq 0 λ≥0

计算

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

第一种情况：

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

第二种情况：

当λ等0的时候，根据上面的式子可以得出 d 1 = 1 , d 2 = 3 d_{1}=1,d_{2}=\sqrt{3} d1​=1,d2​=3

​。因此该式子是正确的。

各种情况下的KKT条件

等式约束下的KKT条件

题目描述：

m i n i m i z e       x T x minimize\:\:\:\:\:x^{T}x minimizexTx

s . t .       A x = b s.t.\:\:\:\:\: Ax=b s.t.Ax=b

拉格朗日函数:

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

KKT条件:

∂ L ( x , λ ) ∂ ( x ) = 0 \frac{\partial L(x,\lambda)}{\partial (x)}=0 ∂(x)∂L(x,λ)​=0

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

A x = b Ax=b Ax=b 等式约束条件

不等式约束下的KKT条件

题目描述：

m a x i m i z e       f ( x ) = ( x − 3 ) 3 maximize\:\:\:\:\:f(x)=(x-3)^{3} maximizef(x)=(x−3)3

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

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

m i n m i z e f ( x ) = − ( x − 3 ) 3 minmize f(x)=-(x-3)^{3} minmizef(x)=−(x−3)3

g 1 ( x ) = 1 − x ≤ 0 g_{1}(x)=1-x\leq 0 g1​(x)=1−x≤0

g 2 ( x ) = x − 5 ≤ 0 g_{2}(x)=x-5\leq 0 g2​(x)=x−5≤0

拉格朗日函数:

L ( x , λ 1 , λ 2 ) = f ( x ) + λ 1 g 1 ( x ) + λ 2 g 2 ( x ) = − ( x − 3 ) 3 + λ 1 ( 1 − x ) + λ 2 ( x − 5 ) 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) L(x,λ1​,λ2​)=f(x)+λ1​g1​(x)+λ2​g2​(x)=−(x−3)3+λ1​(1−x)+λ2​(x−5)

KKT条件:

∂ L ( x , λ 1 , λ 2 ) ∂ ( x ) = − 2 ( x − 3 ) − λ 1 + λ 2 = 0 \frac{\partial L(x,\lambda_{1},\lambda_{2})}{\partial (x)}=-2(x-3)-\lambda_{1}+\lambda_{2}=0 ∂(x)∂L(x,λ1​,λ2​)​=−2(x−3)−λ1​+λ2​=0

λ 1 g 1 ( x ) = λ 1 ( 1 − x ) = 0 \lambda_{1}g_{1}(x)=\lambda_{1}(1-x)=0 λ1​g1​(x)=λ1​(1−x)=0 不等式约束条件

λ 2 g 2 ( x ) = λ 2 ( x − 5 ) = 0 \lambda_{2}g_{2}(x)=\lambda_{2}(x-5)=0 λ2​g2​(x)=λ2​(x−5)=0 不等式约束条件

g 1 ( x ) ≤ 0 g_{1}(x)\leq 0 g1​(x)≤0 不等式约束条件

g 2 ( x ) ≤ 0 g_{2}(x)\leq 0 g2​(x)≤0 不等式约束条件

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

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

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

题目描述：

m i n      f ( x ) min\:\:\:\:f(x) minf(x)

s . t .       h j ( x ) = 0        j = 1 , 2 , … , p s.t.\:\:\:\:\:h_{j}(x)=0\:\:\:\:\:\:j=1,2,\dots,p s.t.hj​(x)=0j=1,2,…,p

g k ( x ) ≤ 0        j = 1 , 2 , … , q g_{k}(x)\leq 0\:\:\:\:\:\:j=1,2,\dots,q gk​(x)≤0j=1,2,…,q

拉格朗日函数：

L ( x , λ , μ ) = f ( x ) + ∑ j = 1 p λ j h j ( X ) + ∑ k = 1 q μ k g k ( x ) L(x,\lambda,\mu)=f(x)+\sum_{j=1}^{p}\lambda_{j} h_{j}(X)+\sum_{k=1}^{q}\mu_{k}g_{k}(x) L(x,λ,μ)=f(x)+j=1∑p​λj​hj​(X)+k=1∑q​μk​gk​(x)

KKT条件：

∇ f ( x ) + ∑ j = 1 p λ j ∇ h j ( X ) + ∑ k = 1 q μ k ∇ g k ( x ) = 0 \nabla f(x)+\sum_{j=1}^{p}\lambda_{j}\nabla h_{j}(X)+\sum_{k=1}^{q}\mu_{k}\nabla g_{k}(x)=0 ∇f(x)+j=1∑p​λj​∇hj​(X)+k=1∑q​μk​∇gk​(x)=0 对x求导等于0

μ k ≥ 0 \mu_{k}\geq 0 μk​≥0

μ k g k ( x ) = 0 \mu_{k}g_{k}(x)=0 μk​gk​(x)=0

h j ( x ) = 0 h_{j}(x)=0 hj​(x)=0

g k ( x ) ≤ 0 g_{k}(x)\leq 0 gk​(x)≤0