问题描述
假设要解决的优化问题为:
约束条件为
问题的简单改写
我们现在需要用一个函数来写出上面问题的等价问题。也就是要把约束条件跟目标函数写进一个函数中,把这个函数记作,那么可以写作:
这里的是个无穷阶跃函数,其表达式为:
如果 大于0, 由于阶跃函数取值为正无穷, 那么函数不可能在这时取到极小值. 如果小于等于0, 那么 值为0,求最小值就是求的最小值.注意到此时的小于等于0,因此完全和原问题等价.
至此已经把求原问题最小值成功写成求该函数最小值了.
改写成连续可导形式
不难发现, 这个函数不是连续可导的函数, 因此不好进行极值的求解 (连续可导函数可通过让导数值为0来求极值).我们需要进一步把函数转化成一个连续函数的等价形式.
不连续的原因是函数造成的,如何去改写呢?
一个最简单的方法把给松弛成, .假设如下图所示:
显然, 是的一个下界,这个结论对于任意都是成立的.
现在可以把中的替换为,新的函数由于引入的新的参数,因此不能用一个字母来表示,于是记作:
那么这个函数该如何跟之前的等价呢?
我们注意到如果时取值为,时取值为, 那么的效果将跟完全相同. 要实现这一步,只需要把写成即可.也就是把(6)式中的看作变量,看作常量求(6)式的最大值. 如果那么取值为时最大,如果, 那么的值, 当且仅当时取到,才能使最大.因此, 的等价函数为. 原问题等价为也就是. 其中表示把看作变量求函数的最小值.
对偶问题
注意到求与求原问题等价, 都不好进行求解. 但是,如果我们考虑调换求极值的顺序, 也就是先把看作变量求函数的最小值, 再把看作变量求函数的最大值. 那么问题就变成:
这个问题跟原问题是不等价的,它被称为原问题的对偶问题. 虽然不等价, 但是对偶问题的最优值是原问题最优值的一个下界,证明如下:
第一项是因为, 第二项就是把看作变量同时取极小值, 是原问题的最优值. 第三项是因为由第二项可知的所有值都小于等于,因此, 的最大值, 也就是对偶问题的最优值是小于等于的.所以对偶问题的最优值是原问题最优值的一个下界.
根据凸优化的相关理论是一个凹函数, 因此容易求解.具体证明可参考:https://github.com/ShiqinHuo/Numerical-Optimization-Books/blob/master/Convex%20Optimization%20Boyd.pdf.
当问题具有强对偶性时, . 若则问题具有弱对偶性.一般来说,几乎所有的凸优化问题都满足强对偶性.比如SVM中, 它的损失函数就是凸函数, 我们几乎就能断定它是一个强对偶的问题.
KKT条件
对于一个没有约束的凸优化问题, 只需要对函数的梯度求导并令其为0即可. 对于由约束的凸优化问题而言, 它的最优解一定满足KKT条件. 第一个条件如下所示:
这个条件可以解释为目标函数和约束函数的梯度必须平行且相反, 如下图所示:
假设目标函数为 ,不等值约束为,如图所示, 最小值点取在梯度的反方向和约束条件梯度的方向上. 值得注意的是,如果最小值落在可行域内,约束将不起作用,取值为,上面的等式依然成立,求极小值的方法就是直接令梯度为.
根据(8)式我们有:
最右边的不等式成立的原因为.(10)式成立的条件只有取等号, 因此我们得到了第二个KKT条件:
综上, 在不等式约束下凸优化问题的所有KKT条件包括:
参考资料
[1] David Knowles,Lagrangian Duality for Dummies,November 13, 2010
[2] 瑞典皇家理工学院(KTH)“统计学习基础”课程的KKT课件:http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf