简易解说拉格朗日对偶(Lagrange duality)

引言:尝试用最简单易懂的描述解释清楚机器学习中会用到的拉格朗日对偶性知识,非科班出身,如有数学专业博友,望多提意见!



1.原始问题

假设

是定义在

上的连续可微函数(为什么要求连续可微呢,后面再说,这里不用多想),考虑约束最优化问题:

称为约束最优化问题的原始问题。

现在如果不考虑约束条件,原始问题就是:

因为假设其连续可微,利用高中的知识,对

求导数,然后令导数为0,就可解出最优解,很easy. 那么,问题来了(呵呵。。。),偏偏有约束条件,好烦啊,要是能想办法把约束条件去掉就好了,bingo! 拉格朗日函数就是干这个的。


引进广义拉格朗日函数(generalized Lagrange function):

不要怕这个式子,也不要被拉格朗日这个高大上的名字给唬住了,让我们慢慢剖析!这里

是拉格朗日乘子(名字高大上,其实就是上面函数中的参数而已),特别要求

.


现在,如果把

看作是关于

的函数,要求其最大值,即

再次注意

是一个关于

的函数,经过我们优化(不要管什么方法),就是确定

的值使得

取得最大值(此过程中把

看做常量),确定了

的值,就可以得到

的最大值,因为

已经确定,显然最大值

就是只和

有关的函数,定义这个函数为:

其中


下面通过

是否满足约束条件两方面来分析这个函数:

  • 考虑某个

    违反了原始的约束,即

    或者

    ,那么:

  注意中间的最大化式子就是确定

的之后的结果,若

,则令

,如果

,很容易取值

使得

  • 考虑

    满足原始的约束,则:

    ,注意中间的最大化是确定

    的过程,

    就是个常量,常量的最大值显然是本身.


通过上面两条分析可以得出:

那么在满足约束条件下:

与原始优化问题等价,所以常用

代表原始问题,下标 P 表示原始问题,定义原始问题的最优值:


原始问题讨论就到这里,做一个总结:通过拉格朗日这位大神的办法重新定义一个无约束问题(大家都喜欢无拘无束),这个无约束问题等价于原来的约束优化问题,从而将约束问题无约束化!



2.对偶问题

定义关于

的函数:

注意等式右边是关于

的函数的最小化,

确定以后,最小值就只与

有关,所以是一个关于

的函数.


考虑极大化

,即

  

这就是原始问题的对偶问题,再把原始问题写出来:

形式上可以看出很对称,只不过原始问题是先固定

中的

,优化出参数

,再优化最优

,而对偶问题是先固定

,优化出最优

,然后再确定参数

.

定义对偶问题的最优值:



3. 原始问题与对偶问题的关系

定理:若原始问题与对偶问题都有最优值,则

证明:对任意的

,有

由于原始问题与对偶问题都有最优值,所以

也就是说原始问题的最优值不小于对偶问题的最优值,但是我们要通过对偶问题来求解原始问题,就必须使得原始问题的最优值与对偶问题的最优值相等,于是可以得出下面的推论:

推论:设

分别是原始问题和对偶问题的可行解,如果

,那么

分别是原始问题和对偶问题的最优解。

所以,当原始问题和对偶问题的最优值相等:

时,可以用求解对偶问题来求解原始问题(当然是对偶问题求解比直接求解原始问题简单的情况下),但是到底满足什么样的条件才能使的

呢,这就是下面要阐述的 KKT 条件



4. KKT 条件

定理:对于原始问题和对偶问题,假设函数

是凸函数,

是仿射函数(即由一阶多项式构成的函数,f(x)=Ax + b, A是矩阵,x,b是向量);并且假设不等式约束

是严格可行的,即存在

,对所有

,则存在

,使得

是原始问题的最优解,

是对偶问题的最优解,并且

定理:对于原始问题和对偶问题,假设函数

是凸函数,

是仿射函数(即由一阶多项式构成的函数,f(x)=Ax + b, A是矩阵,x,b是向量);并且假设不等式约束

是严格可行的,即存在

,对所有

,则

分别是原始问题和对偶问题的最优解的充分必要条件是

满足下面的Karush-Kuhn-Tucker(KKT)条件:

关于KKT 条件的理解:前面三个条件是由解析函数的知识,对于各个变量的偏导数为0(这就解释了一开始为什么假设三个函数连续可微,如果不连续可微的话,这里的偏导数存不存在就不能保证),后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。

特别注意当

时,由KKT对偶互补条件可知:

,这个知识点会在 SVM 的推导中用到.



5. 总结

一句话,某些条件下,把原始的约束问题通过拉格朗日函数转化为无约束问题,如果原始问题求解棘手,在满足KKT的条件下用求解对偶问题来代替求解原始问题,使得问题求解更加容易。

本文转载自  http://www.cnblogs.com/90zeng/ 作者:博客园-90Zeng

可参考博文:http://blog.csdn.net/robin_xu_shuai/article/details/52803645

(0)

相关推荐

  • 拉格朗日对偶

    对偶是最优化方法里的一种方法,它将一个最优化问题转换成另外一个问题,二者是等价的.拉格朗日对偶是其中的典型例子.对于如下带等式约束和不等式约束的优化问题: 与拉格朗日乘数法类似,构造广义拉格朗日函数: ...

  • 【原创】支持向量机原理(五)线性支持回归

    【原创】支持向量机原理(五)线性支持回归

  • 风水知识 | 办公室风水大全,简易的办公布局禁忌

    一.办公桌的摆放风水讲究 第一,桌台上,左手边尽可能的高,右边尽可以的整齐,右边不能高过左边. 第二,桌台上,左边放一盆水培植物,右边不能放固定电话. 第三,每个座位,都会有左边和右边,请保持固定从座 ...

  • 雅马哈天剑变速杆定位销断裂的应急处理办法(图示解说)

    作者:摩托中国 海风 一辆雅马哈天剑,由于在骑行时错误操作,致使变速杆定位销断裂. 关于如何解决这个问题,我一共思考了三个方案: 1.换大箱体,维修费用高,还得变更行车证上的发动机号. 2.打透,攻丝 ...

  • 夏天学画写意荷花,送你简易画法!

    荷花是一种水生花,有单瓣.复瓣.重瓣等不同种类.荷花又别称"莲花,芙蕖.水芝,水芸等.用写意方法画荷花,是对真实荷花的提炼.夸张和概括. 画荷花,必须把荷花"出淤泥而不染,濯清涟而 ...

  • 真品图和仿品图新老对比解说天珠的真假辨别

    从天珠的表面看,它是点而不是线的形状.它的颜色有些是棕色,有些是暗红色.(如果仔细观察,朱砂不仅在表面,而且在内层.我知道,所有的老珠不一定都有朱砂点.许多老天柱没有朱砂点.不仅朱砂圆点可以用来鉴别西 ...

  • 摩托车油箱变形的简易修复办法

    摩托车是两轮的,天生具有不稳定性,摔车这种事情估计每个老司机都遇到过,那么,当有时点背的时候,把油箱碰个凹坑也就难以避免了.变形的油箱放在车上难看,换一个吧又挺贵,有什么办法能简易修复一下呢?我提供两 ...

  • 摩托车缸压是否正常如何判断?看我简易方法

    玩车有一定年头的车友,总喜欢自己动手维修,但有时需要知道缸压是否合适的时候,却没有称手的工具,今天我向大家介绍一种适合于修理时粗略检查汽缸压缩性的简单方法. 找一根内孔为 Φ6mm ,长为 1500m ...

  • 想做电影解说,用合成音可以过原创吗?要注意什么?

    电影解说用合成音是可以过原创的!但个人建议还是要有具备特色的嗓音,才能让观众更加有感触,更容易记得你!这样才会吸引路人成为你的粉丝! 电影解说其实有很多种方式!有深度解说,魔性解说电影等等.但是要做好 ...

  • 一生必背650句古今对偶佳句,读完唇齿留香(建议收藏)

    一生必背650句春对夏,秋对冬,暮鼓对晨钟:云对雨,雪对风,晚照对晴空...... 对偶是中国诗词和对联创作的常用手法,讲究文句两两相对.字数相等.句法相似.平仄相对.意义相关. 今天就从@泽光书院 ...