• 为了保证你在浏览本网站时有着更好的体验,建议使用类似Chrome、Firefox之类的浏览器~~
    • 如果你喜欢本站的内容何不Ctrl+D收藏一下呢,与大家一起分享各种编程知识~
    • 本网站研究机器学习、计算机视觉、模式识别~当然不局限于此,生命在于折腾,何不年轻时多折腾一下

机器学习导论(附录)–拉格朗日对偶与KKT条件

ml admin 3年前 (2016-11-23) 1822次浏览 0个评论 扫描二维码

首先是拉格朗日原问题(强调强调强调,一会我们还会回来看这里的,这里我们将原问题记为p):

minf0(x)

 

s.t.fi(x)0,i=1,,m

 

hi(x)=0,i=1,,p

注意:这里我们要求fihi的定义域都是非空的,此时的定义域记为 D,但是这里我们并不要求原问题是凸的

拉格朗日对偶的中心思想是在目标函数中考虑上约束条件,也就是引入拉格朗日算子,得到增广目标函数,也就是拉格朗日函数

L(x,λ,μ)=f0(x)+i=0mλifi(x)+i=1pμihi(x)

也就是说,我们现在优化的对象除了 x,还加上了 m 个λi,p 个μi,这时候定义域变成了D×Rm×Rp

我们定义拉格朗日函数的对偶函数为

g(λ,μ)=infxDL(x,λ,μ)=infxDf0(x)+i=0mλifi(x)+i=1pμihi(x)

也就是说,我们定义对偶函数为拉格朗日函数的下界,那么问题来了,如果拉格朗日函数没有下界呢?没关系,这时候我们就让对偶函数为即可。

由于对偶函数g(λ,μ)是关于(λ,μ)仿射函数的逐点下确界,所以
不管原问题是不是凸的,其对偶函数一定凹的
(参考前面的讨论,注意前面讨论的是凸性,但是凸性与凹性换几个地方就行了)

引入对偶,使得原问题的求解变成了讨论“求原问题的下界”。为什么呢?因为对于λ0,都有g(λ,μ)p,简单验证一下:
如果一个x^是可行的解,那么fi(x^)0,hi(x^)=0,由于λ0,从而

i=0mλifi(x)+i=1pμihi(x)

第一项为负数,第二项为 0,所以

L(x^,λ,μ)=f0(x^)+i=0mλifi(x^)+i=1pμihi(x^)f0(x^)

因而

g(λ,μ)=infxDL(x,λ,μ)L(x^,λ,μ)f0(x^)

即每个可行点,都有g(λ,μ)f0(x^)

上面的公式好枯燥,给大家看一张图就明白了

无标题.png

在图中,实线代表的是目标函数f0,而虚线代表的是约束条件f1,彩色的点线代表λ取不同值的时候对应的拉格朗日函数L(x,λ)=f0(x)+λf1(x)(本来有十条的,但是最近撸太多手抖实在画不动了………画 5 条大家也能看的懂吧….),我们可以看到,在约束条件可行(f1(x)0)的区间内,拉格朗日函数都是小于目标函数的。我们可以看到,在可行区间内,目标函数的最值将在 x = -0.46 处取得p=1.54

下面我们来看一看对偶函数的图像:

QQ 图片 20150324160718.png

其中实线代表的是对偶函数,而虚线代表的是目标函数f0的最优值p=1.54,从图像中,我们可以发现,对偶函数确实是原问题的一个下界,此外,我们也可以发现:在原问题中,目标函数f0,约束条件f1都不是凸的,但对偶函数是凹的

为了更好地理解,我们再举一个例子,一个优化问题:

minxTx

 

s.t.Ax=b

这个问题是等式约束,很简单,我们用高数上面的知识就可以解决了,我们取拉格朗日函数

L(x,μ)=xTx+μT(Axb)

然后求导,令其为 0

ΔxL(x,μ)=2x+ATμ=0

求得

x=12ATμ

这时候目标函数最小,好,现在我们来看看如果讨论对偶会怎么样
首先对偶函数为

g(μ)=infxL(x,μ)

代入最优解x=12ATμ

g(μ)=infxL(12ATμ,μ)=14μTAATμbTμ

我们会发现,对偶函数是二次凹函数,并且有

14μTAATμbTμinf{xTx|Ax=b}

拉格朗日对偶,通过引入参数λ,μ,可以让原问题得到一个与λ,μ相关的下界(这时候跟 x 没什么关系了)。但现在的问题就是,究竟哪个下界才是最好的?因为下界有很多个,所以应该选取哪个下界?
答案是:最大的下界是最好的,这个解我们记为d

从上面的图,大家也可以看到,对偶函数的最大值最接近原问题的最优解,由于对偶问题总存在这么一个等式dp(即使原问题不是凸的这个不等式也成立),所以,pd也被称为最优对偶间隙

举一个对偶的例子,比如线性规划,其标准式为

minCTx

 

s.t.Ax=b

 

x0

我们取拉格朗日函数

L(x,λ,μ)=CTxi=1nλixi+μT(Axb)=bTμ+(C+ATμλ)Tx

则对偶函数为

g(λ,μ)=infxL(x,λ,μ)=bTμ+infx(C+ATμλ)Tx

由于线性函数只有为常数的时候才有下界,所以g(λ,μ)又可以写为

g(λ,μ)=bTμ,        如果ATμλ+c=0

 

g(λ,μ)=,        其他

强烈抗议:没法进行公式堆叠啊!!!!!!!!!

上面是对偶函数,我们说过,对偶函数刻画的是一个下界,哪个下界是最好的呢?最大的是最好的,所以,对偶问题可以表述为maxg(λ,μ)
也就是

maxbTμ

 

s.t.ATμλ+c=0

 

λ0

上面这个问题还可以进一步缩写为

maxbTμ

 

s.t.ATμ+c0

这就是线性规划标准形式的对偶问题,这种表述也称之为不等式形式线性规划

好,我们我们从不等式形式线性规划出发,也就是现在我们的原问题是:

maxCTx

 

s.t.ATxb

(注:跟上边的不等式形式符号变了,但表达没变)

我们取拉格朗日函数

L(x,λ)=CTx+λT(Axb)=bTλ+(ATλ+C)Tx

那么对偶函数就是

g(λ)=infxL(x,λ)=bTλ+infx(ATλ+C)Tx

同样,由于线性函数只有恒为常数的时候才有下界,因此对偶函数可以写为

g(λ)=bTλ,        如果ATλ+c=0

 

g(λ)=,        其他

强烈抗议:没法进行公式堆叠啊!!!!!!!!!
还是那句话,哪个下界是最好的呢?最大的是最好的,所以maxg(λ)可以表述为

maxbTλ

 

s.t.ATλ+c=0

 

λ0

你看,这又回到标准型的线性规划了。

在拉格朗日对偶之后,dp总是成立的,这个我们也叫做弱对偶性,如果说我们能够使得d=p,那么这时候我们求解对偶问题就相当于求解原问题了,大家看前面的图,对偶问题显然不等价于原问题的。那么什么时候对偶问题等价于原问题呢(这种情况叫做强对偶)?一般情况下,如果原问题是凸的,那么这个问题具有强对偶,也就是对偶问题的最优解等于原问题的最优解(不绝对,也有例外的)。

如何判定一个问题是否具有强对偶性呢?一个判据是 Slater 条件,这里不讲,另一个就是大家所知到的 KKT 条件了。如果说一个问题,它满足 KKT 条件,那么这个问题就具有强对偶性,求取对偶问题就相当于求取原问题。但如果不满足 KKT 条件呢?那就不能这么做了。

而恰好,SVM 问题里面都是满足 KKT 条件的,所以 SVM 里面求取对偶解就相当于求取原问题的解。那么我们为什么要求它的对偶呢?因为 kernel,通过对偶之后得到一个向量内积的形式,也就是xTx这种形式,而这种形式是 kernel 所擅长处理的。如果没有对偶,就没有后面的 kernel 映射,SVM 也实现不了非线性分割。


Deeplearn, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明机器学习导论(附录)–拉格朗日对偶与 KKT 条件
喜欢 (1)
admin
关于作者:
互联网行业码农一枚/业余铲屎官/数码影音爱好者/二次元

您必须 登录 才能发表评论!