拉格朗日乘数法之KKT条件:不等式约束求解

在之前的拉格朗日乘数法中介绍了拉格朗日乘数法求极值的基本思想，而当时的约束条件都是等式，所以如果约束条件变成了不等式，那么如何利用拉格朗日乘数法求极值呢？这就是本篇文章中涉及到的拉格朗日乘数法的KTT条件推广。

不等式约束

对于不等式约束g(x)<=0g(x)<=0g(x)<=0，和等式约束h(x)=0h(x)=0h(x)=0不一样，h(x)=0h(x)=0h(x)=0可以在平面上画出一条等高线，而g(x)<=0g(x)<=0g(x)<=0是一个区域，很多个等高线堆叠而成的一块区域，我们把这块区域称为可行域。

不等式约束分两种情况来讨论，第一种是极小值点落在可行域内（不包含边界），第二种是极小值点落在可行域外（包含边界）。

下面举两个例子来解释这两种情况，然后总结两种情况给出转换求解。

极小值点落在可行域内（不包含边界）

考虑目标函数f(x)=x12+x22f(x) = x_1^2 + x_2^2f(x)=x12​+x22​,不等式约束g(x)=x12+x22−1≤0g(x) = x_1^2 + x_2^2 -1 \le 0g(x)=x12​+x22​−1≤0，显然f(x)f(x)f(x)的极小值为原点(0,0)，落在可行域内。可行域以原点为圆心，半径为1。

可以看出这种情况下约束不起作用，问题退化成了无约束求最极值问题，所以在拉格朗日函数中直接令拉格朗日乘子λ=0\lambda=0λ=0，此时拉格朗日函数可不就简化为L(x,λ)=f(x)L(x, λ)=f(x)L(x,λ)=f(x)了。对于这种无约束求极小值点x∗x^*x∗就是求函数f(x)f(x)f(x)的极小值点，对应极小值点有f(x∗)f(x^*)f(x∗)的梯度等于0。

极小值点落在可行域外（包含边界）

考虑目标函数f(x)=(x1−2)2+(x2+2)2f(x) = (x_1 - 2)^2 + (x_2 + 2)^2f(x)=(x1​−2)2+(x2​+2)2,不等式约束g(x)=x12+x22−1≤0g(x) = x_1^2 + x_2^2 - 1 \le 0g(x)=x12​+x22​−1≤0，显然f(x)f(x)f(x)的极小值为点(2, -2)，落在可行域外。可行域是以原点为圆心，半径为1的区域。

这种情况约束起作用，要考虑求解f(x)f(x)f(x)在可行域内的极小值点。

根据梯度的知识对于f(x)f(x)f(x)而言要沿着f(x)f(x)f(x)的负梯度方向走，才能走到极小值点，如下图的蓝色箭头。
这个时候g(x)g(x)g(x)的梯度往区域外发散，如下图红色箭头。

显然，走到极小值点的时候，g(x)g(x)g(x)的梯度和f(x)f(x)f(x)的负梯度同向。因为极小值点在边界上，这个时候g(x)等于0,那么约束条件变为了等式约束，也就是我们之前提到的利用拉格朗日乘数法求解的问题。

这里注意一下要求λ>0\lambda>0λ>0，因为我们的KKT条件中标准形式是最小化且不等式约束条件都是<=0的，而g(x)的梯度是指向大于 0 的一侧，所以有目标函数和约束条件梯度反向。只有当λ>0\lambda>0λ>0是才有能保证目标函数和约束条件梯度反向。

至此可以将两种情况做一个总结：
极小值点落在可行域内（不包含边界）：这个时候可行域的限制不起作用，相当于没有约束,直接f(x)的梯度等于0求解，这个时候g(x极小值点)<0（因为落在可行域内）。

即：g(X∗)<0，λ=0g(X^*)<0，\lambda=0g(X∗)<0，λ=0
∇xf(X∗)=0\nabla_x f(X^*)=0∇x​f(X∗)=0

极小值点落在可行域外（包含边界）：可行域的限制起作用，极小值点应该落在可行域边界上即g(x)=0，类似于等值约束，此时有g(x)的梯度和f(x)的负梯度同向。
即：g(X∗)=0g(X^*)=0g(X∗)=0
−∇xf(X∗)=λg(X∗)，λ>0-\nabla_x f(X^*)=\lambda g(X^*)，\lambda>0−∇x​f(X∗)=λg(X∗)，λ>0

将两种情况结合起来，并且数学家们为了更简洁的表示，两种情况下λ⋅g=0\lambda \cdot g=0λ⋅g=0都成立，这样就可以得到拉格朗日乘数法的KKT条件：

要在约束g(x)⩽0g(\boldsymbol{x}) \leqslant 0g(x)⩽0下最小化f(x)f(\boldsymbol{x})f(x)，可转化为在如下约束下最小化式的拉格朗日函数：

{g(x)⩽0;λ⩾0;λjgj(x)=0. \begin{cases} g(\boldsymbol{x}) \leqslant 0; \\ \lambda \geqslant 0; \\ \lambda_j g_j(\boldsymbol{x}) = 0 . \end{cases}⎩⎨⎧​g(x)⩽0;λ⩾0;λj​gj​(x)=0.​

对应最小值的解满足如下约束：

1. ∇xL(x∗,λ∗)=0\nabla_x \mathcal{L}(x^*,\lambda^*) = 0∇x​L(x∗,λ∗)=0(拉格朗日求解条件)
2. λ∗≥0\lambda^* \ge 0λ∗≥0（拉格朗日乘子必须为非负，称为对偶可行性条件）
3. λ∗g(x∗)=0\lambda^* g(x^*) = 0λ∗g(x∗)=0（转换为拉格朗日函数两种分类情况的约束，称为互补松弛条件）
4. g(x∗)⩽0g({x^*}) \leqslant 0g(x∗)⩽0(原始问题中的约束条件，称为可行性条件)

这些条件称为 Karush-Kuhn-Tucker (简称KKT)条件。

上述做法可推广到多个约束。考虑具有mmm个等式约束和nnn个不等式约束，且可行域D⊂Rd\mathbb{D} \subset \mathbb{R}^dD⊂Rd非空的优化问题

min⁡xf(x)s.t.hi(x)=0(i=1,…,m),gj(x)⩽0(j=1,…,n). \begin{align} \min_{\boldsymbol{x}} \quad & f(\boldsymbol{x}) \\ \text{s.t.} \quad & h_i(\boldsymbol{x}) = 0 \quad (i=1,\dots,m), \\ & g_j(\boldsymbol{x}) \leqslant 0 \quad (j=1,\dots,n). \end{align}xmin​s.t.​f(x)hi​(x)=0(i=1,…,m),gj​(x)⩽0(j=1,…,n).​​

引入拉格朗日乘子λ=(λ1,λ2,…,λm)T\boldsymbol{\lambda} = (\lambda_1,\lambda_2,\dots,\lambda_m)^\mathrm{T}λ=(λ1​,λ2​,…,λm​)T和μ=(μ1,μ2,…,μn)T\boldsymbol{\mu} = (\mu_1,\mu_2,\dots,\mu_n)^\mathrm{T}μ=(μ1​,μ2​,…,μn​)T，相应的拉格朗日函数为

L(x,λ,μ)=f(x)+∑i=1mλihi(x)+∑j=1nμjgj(x) L(\boldsymbol{x}, \boldsymbol{\lambda}, \boldsymbol{\mu}) = f(\boldsymbol{x}) + \sum_{i=1}^{m} \lambda_i h_i(\boldsymbol{x}) + \sum_{j=1}^{n} \mu_j g_j(\boldsymbol{x})L(x,λ,μ)=f(x)+i=1∑m​λi​hi​(x)+j=1∑n​μj​gj​(x)

由不等式约束引入的 KKT 条件(j=1,2,…,n)(j = 1,2,\dots,n)(j=1,2,…,n)为

{gj(x)⩽0;μj⩾0;μjgj(x)=0. \begin{cases} g_j(\boldsymbol{x}) \leqslant 0; \\ \mu_j \geqslant 0; \\ \mu_j g_j(\boldsymbol{x}) = 0 . \end{cases}⎩⎨⎧​gj​(x)⩽0;μj​⩾0;μj​gj​(x)=0.​

特别注意：优化问题是凸优化的话，KKT条件就是极小值点（而且是全局极小）存在的充要条件。