支持向量机SVM(二)

作者:u013472838

【转载请注明出处】http://www.cnblogs.com/jerrylead
6 拉格朗日对偶(Lagrange duality)

     先抛开上面的二次规划问题,先来看看存在等式约束的极值问题求法,比如下面的最优化问题:

    clip_image001[9]    

    目标函数是f(w),下面是等式约束。通常解法是引入拉格朗日算子,这里使用clip_image003[14]来表示算子,得到拉格朗日公式为

    clip_image004[6]    

    L是等式约束的个数。

    然后分别对w和clip_image003[15]求偏导,使得偏导数等于0,然后解出w和clip_image006[6]。至于为什么引入拉格朗日算子可以求出极值,原因是f(w)的dw变化方向受其他不等式的约束,dw的变化方向与f(w)的梯度垂直时才能获得极值,而且在极值处,f(w)的梯度与其他等式梯度的线性组合平行,因此他们之间存在线性关系。(参考《最优化与KKT条件》)

然后我们探讨有不等式约束的极值问题求法,问题如下:

    clip_image007[6]    

    我们定义一般化的拉格朗日公式

clip_image008[6]

    这里的clip_image010[50]clip_image012[14]都是拉格朗日算子。如果按这个公式求解,会出现问题,因为我们求解的是最小值,而这里的clip_image014[6]已经不是0了,我们可以将clip_image010[51]调整成很大的正值,来使最后的函数结果是负无穷。因此我们需要排除这种情况,我们定义下面的函数:

    clip_image015[6]

    这里的P代表primal。假设clip_image017[6]或者clip_image019[6],那么我们总是可以调整clip_image010[52]clip_image012[15]来使得clip_image021[10]有最大值为正无穷。而只有g和h满足约束时,clip_image021[11]为f(w)。这个函数的精妙之处在于clip_image023[6],而且求极大值。

    因此我们可以写作

    clip_image024[6]

    这样我们原来要求的min f(w)可以转换成求clip_image026[10]了。    

    clip_image027[6]

    我们使用clip_image029[6]来表示