本文原作者:汪毅雄,经授权后发布。
导语:本文先介绍了凸优化的满足条件,然后用一个通用模型详细地推导出原始问题,再解释了为什么要引入对偶问题,以及原始问题和对偶问题的关系,之后推导了两者等价的条件,最后以SVM最大间隔问题的求解来说明其可行性。
凸优化理论广泛用于机器学习中,也是数学规划领域很重要的一个分支,当然也是很复杂的。本文总结一下我获取的资料和个人在一些难点上的理解。
当我们要求一个函数 min f(x) 的时候,如果 f(x) 可导,我们通过是通过求 f(x) 的导数来得。
但是如果函数 f(x) 带约束条件,那么问题就开始变复杂了。凸优化的目标就是解决带约束条件函数的极值问题。
凸优化解决的通用模型是:
很显然,所有的极值问题都可以转化成如上的模型。面对这个问题,凸优化理论怎么处理的呢?
不是所有的极值问题都可以适用的凸优化理论的,它必须满足以下条件:
1、目标函数 f(x) 为凸函数
2、不等式约束函数 g(x) 为凸函数
3、等式约束函数 h(x) 为仿射函数
只有同时满足以上3个条件,才属于凸优化的范畴。
1.1 凸函数是什么?
可以这样理解:
1、定义域为凸集,凸集几何意义表示为:如果集合中任意2个元素连线上的点也在集合C中,则C为凸集,下图左图为凸集,右图为非凸集。
2、二阶可导,且二阶导数大于0
1.2仿射函数是什么?
一句话就是最高阶数为1的函数,如:Ax+b,
可以这么理解条件3,等式约束条件 h(x)=0 可以这么写
也就是说 h(x) 和 -h(x) 都必须同时是凸函数,那么其二阶导数就必须为0,也就是说阶数不能超过1。
对于凸优化的通用模型,由于其带有约束条件,很难处理,因此我们会考虑怎么用一个式子来表述那个通用模型呢?
其拉格朗日函数的max就在求min的时候就可以作为等价模型,这句话很拗口,这块也是一个难以琢磨的点,很多资料都是直接给出结果,我这边试着一步一步剖析。
我们写出模型的拉格朗日表达式
如果这么定义拉格朗日表达式,那么
就上述模型就等价于 f(x),为什么呢?
我么可以看到这个函数是以α,β的函数,其中α必须大于等于0. 那么 g(x)、f(x)、h(x)都可以看作常量。而我们的约束条件是:
A、设想一下不满足约束条件的话:
1)假设 g(x)>0 h(x)=0,那么拉格朗日函数可表示为
这是一个线性函数,因为 g(x)>0,所以函数的最大值点肯定是在α为+∞的时候,因此这种情况
的值为+∞。
2)假设 g(x)<=0 h(x)!=0,那么拉格朗日函数可表示为
同理,如果h(x)>0,则函数的最大值点肯定是在β为+∞的时候取到。如果h(x)<0,则函数的最大值点肯定是在β为-∞的时候取到。也就是无论如何,
的值依然为+∞。
也就是说,如果不满足约束条件,
的值永远为+∞。
B、如果满足约束条件的话,那么拉格朗日函数可表示为
由于α>=0, g(x)<=0,所以
必然为0或负数,也就是说,这时候
值就为 f(x)。
而在求min f(x)的情况下,如果不满足约束条件
的值为+∞,只有满足才为f(x)。因此当且仅当,在求min f(x)的前提下:
所以min-max就是我们转化的原始问题!
1) 方便求解
2) 规划理论中,对于不知道有没有解的情况,可以通过对偶问题来缩小范围。
引用一个经典的由不是很恰当的例子说:
所以可以通过它的对偶问题来说:
这样问题就变得有可行解了。
先写出拉格朗日表达式:
把原始问题转成其对偶问题,也就是先求max转成先求min:
为什么这种转化是可行的呢?因为两者始终存在这么一个关系
且在满足kkt条件的前提下,两者是相等的!
用图来说就是
3.2.1 为什么min-max >= max-min?
1、先简单理解一下这个,对于任意的存在最小值的 f(x), 总有任意的x*,都有:
其中等式成立的条件是
也就是在x*处的导数为0.
2、min是以x为参数的函数,假设它的最优解为x*,那么原始问题的结果为:
max是以α、β为参数的函数,假设它的最优解为α*、β*,那么对偶问题的结果为:
3、那么我们都有以下推断
由于由以下关系,所以第一个大于等于号成立
由step1中所讲述的,第二个大于等于号也成立。
因此min-max >= max-min是成立的。
3.2.2 KKT条件
在本节最开始说了,我们需要的:
不是原问题 > 对偶问题,而是原问题 = 对偶问题。
因此在3.2.1推导的公式中,两个大于等于号必须取等号,这就能推导出我们的KKT条件。
在第一个大于等号中,强制其为等号,推导出的条件为:
,也就是
在第二个大于等号中,强制其为等号,推导出的条件为:
拉格朗日不等式约束条件:
初始条件:
如果同时满足以上5个条件,那么原问题就可以等价于对偶问题!
回到SVM的初始模型
可以看到,
是二次函数,典型的凸函数!
而约束条件最高阶只有一阶,确实是仿射函数。
也就是说,SVM可以套用凸优化理论。
可以很简单的写出,其拉格朗日形式为:
其对偶问题是先求以w、b为参数的min,再求以α为参数的max,这部分具体推导已经在文章
《 机器学习之SVM - 理论知识 》中做了,有兴趣可以了解。
最终得到的结果是:
如果两个问题等价,那么其KKT条件,我们也套用模型中内容,可以推导出:
令
那么有:
1、初始条件:
2、拉格朗日条件:
3、互补松弛条件:
4、参数导数为0条件:
更多优质技术文章请关注官方微信公众号:
更多优质技术文章请关注官方知乎机构号:
https://www.zhihu.com/org/teng-xun-zhi-neng-tai-ji-qi-xue-xi-ping-tai/activities
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。