Table of Contents

1 什么是KKT条件

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

$\begin{array}{ll} \min & f(\mathbf{x}) \\ \text { s.t. } & g(\mathbf{x}) \leq 0 \end{array}$

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

$\left\{\begin{array}{l} \nabla f+\sum_{i}^{n} \lambda_{i} \nabla g_{i}=0 \\ g_{i} \leq 0, j=1,2, \cdots, m \\ \mu_{i} \geq 0 \\ \mu_{i} g_{i}=0 \end{array}\right.$

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

2.KKT条件描述型理解

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

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

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

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

$\begin{aligned} \nabla_{\mathbf{x}} L &=\nabla f+\lambda \nabla g=0 \\ g(\mathbf{x}) & \leq 0 \\ \lambda & \geq 0 \\ \lambda g(\mathbf{x}) &=0 \end{aligned}$

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

3.数学推导

3.1

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

$\\min. f_{0}(x) \\ \text { s.t. } \\ f_{i}(x) \leq 0, i=1, \cdots, m \\ h_{i}(x)=0, i=1, \cdots, m$

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

构造一个新函数：

$L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)$

并要求λi >= 0，由于 $f_{i}(x) \leq 0, h_{i}(x)=0, i=1, \cdots, m$ ，故总有 $L(x, \lambda, \nu) \leq f_{0}(x)$ ，即L为目标函数的下界。L称为原优化问题的Lagrange函数，λ，v成为原问题的Lagrange乘子。

对不等式 $L(x, \lambda, \nu) \leq f_{0}(x)$ 两边同时对变量x最小化，可以得到p*的下界

$\min _{x} f_{0}(x)=p^{*} \geq \inf _{x} L(x, \lambda, \nu)=g(\lambda, \nu)$

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

$\\\max . g(\lambda, \nu) \\ \text { s.t. } \lambda_{i} \geq 0, i=1, \cdots, m$

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

3.2

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

$d^{*} \leq p^{*}$

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

对应弱对偶的是强对偶，即： $d^{*} = p^{*}$

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

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

$\begin{aligned} f_{0}\left(x^{*}\right) &=g\left(\lambda^{*}, \nu^{*}\right) \\ &=\inf _{x}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i}^{*} f_{i}(x)+\sum_{i=1}^{p} \nu_{i}^{*} h_{i}(x)\right) \\ & \leq f_{0}\left(x^{*}\right)+\sum_{i=1}^{m} \lambda_{i}^{*} f_{i}\left(x^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{*} h_{i}\left(x^{*}\right) \\ & \leq f_{0}\left(x^{*}\right) \end{aligned}$

所以：

$f_{0}\left(x^{*}\right)+\sum_{i=1}^{m} \lambda_{i}^{*} f_{i}\left(x^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{*} h_{i}\left(x^{*}\right)=f_{0}\left(x^{*}\right)$

$\sum_{i=1}^{m} \lambda_{i}^{*} f_{i}\left(x^{*}\right)=0$

因为：

$\lambda_{i} f_{i}(x) \leq 0, i=1, \cdots, m$

所以：

$\lambda_{i} f_{i}(x)=0, i=1, \cdots, m$

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

3.3总结

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

4 KKT条件总结

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

$\begin{aligned} &f_{i}\left(x^{*}\right) \leq 0, \quad i=1, \cdots, m\\ &h_{i}\left(x^{*}\right) =0, \quad i=1, \cdots, p \\ &\lambda_{i}^{*} \geq 0, \quad i=1, \cdots, m \\ &\lambda_{i}^{*} f_{i}\left(x^{*}\right) =0, \quad i=1, \cdots, m \\ &0 =\nabla f_{0}\left(x^{*}\right)+\sum_{i=1}^{m} \lambda_{i}^{*} \nabla f_{i}\left(x^{*}\right)+\sum_{i=1}^{p} \nu_{i}^{*} \nabla h_{i}\left(x^{*}\right) \end{aligned}$

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

5 参考链接

斯坦福大学凸优化对偶

文章出处登录后可见！

已经登录？立即刷新

拉格朗日算子和KKT条件（SVM系列）