拉格朗日算子和KKT条件(SVM系列)

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 参考链接

斯坦福大学凸优化对偶

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
心中带点小风骚的头像心中带点小风骚普通用户
上一篇 2022年4月15日 下午12:01
下一篇 2022年4月15日 下午12:21

相关推荐