《拉格朗日对偶》由会员分享，可在线阅读，更多相关《拉格朗日对偶（8页珍藏版）》请在金锄头文库上搜索。
1、2拉格朗日对偶(Lagrange duality)先抛开上面的二次规划问题，先来看看存在等式约束的极值问题求法，比如下面的最优 化问题：min /(w)s.t. hw = 0, i I,., Z.目标函数是f(w),下面是等式约束。通常解法是引入拉格朗日算子，这里使用上来表示 算子，得到拉格朗日公式为L是等式约束的个数。然后分别对w和E求偏导，使得偏导数等于0然后解出w和心。至于为什么引入拉格 朗日算子可以求出极值，原因是f(w)的dw变化方向受其他不等式的约束，dw的变化方向 与f(w)的梯度垂直时才能获得极值，而且在极值处，f(w)的梯度与其他等式梯度的线性组 合平行，因此他们之间存在线性
2、关系。(参考最优化与KKT条件)然后我们探讨有不等式约束的极值问题求法，问题如下：mirLujs.t. (w) 0, i 1,., fc= 0. % 1,., Z.我们定义一般化的拉格朗日公式kI= f(w) + 刀 + 工仔血(w).i= 1i=l这里的和:都是拉格朗日算子。如果按这个公式求解，会出现问题，因为我们求解的 是最小值，而这里的山已经不是0 了，我们可以将调整成很大的正值，来使最后的函 数结果是负无穷。因此我们需要排除这种情况，我们定义下面的函数：如(it = max C(u a, /3).这里的P代表primal。假设-;：:： -或者；二，那么我们总是可以调整心和氏来 使得有
3、最大值为正无穷。而只有g和h满足约束时，八畀皿为f(w)。这个函数的精妙 之处在于二色一，而且求极大值。因此我们可以写作/(w) if w satisfies )rimal constraints oc otherwise.这样我们原来要求的min f(w)可以转换成求：了。min= min max jC(u /?),我们使用来表示 =U。如果直接求解，首先面对的是两个参数，而；也是不等 式约束，然后再在W上求最小值。这个过程不容易做，那么怎么办呢？仔)=min (w. a,我们先考虑另外一个问题-1D的意思是对偶，门将问题转化为先求拉格朗日关于w的最小值，将 和 看伽(d, 0作是固定值。之
4、后在-求最大值的话：这个问题是原问题的对偶问题，相对于原问题只是更换了 min和max的顺序，而一般 更换顺序的结果是Max Min(X) = MinMax(X)。然而在这里两者相等。用来表示对偶 问题如下：d* max liiiii a./3) min maxcv. B) .下面解释在什么条件下两者会等价。假设f和g都是凸函数，h是仿射的(affine,11“-T111 1 1 . )。并且存在 w 使得对于所有的i.f 在这种假设下，一定存在/；使得沖是原问题的解，尸是对偶问题的解。还有另外满足库恩-塔克条件（Ka rush-Kuh n- Tucke r, KKT con diti on）
5、,该条件如下：03心10,心1=03g佔） 1, 4 = 1m我们将约束条件改写为：曲血）=汕）（心F巧-F 6） + 1 07 i L . . ., mm。胪、=o.i=l前面提到过对偶问题和原问题满足的几个条件，首先由于目标函数和线性约束都是凸函 数，而且这里不存在等式约束h。存在w使得对于所有的J因此，一定存在卞 使得卞是原问题的解，是对偶问题的解。在这里，求&就是求* 了。w 偽丿L如果求出了&，根据即可求出w (也是T，原问题的解)。然后max.y(0=_1- min.y(0=i w*Txt即可求出b。即离超平面最近的正的函数间隔要等于离超平面最近的负的函数间隔。 关于上面的对偶问题
6、如何求解，将留给下一篇中的SMO算法来阐明。这里考虑另外一个问题，由于前面求解中得到mW =工陽丁卞=1我们通篇考虑问题的出发点是根据求解得到的4,我们代入前式得到mx -bi=1也就是说，以前新来的要分类的样本首先根据w和b做一次线性运算，然后看求的结果 是大于0还是小于0,来判断正例还是负例。现在有了宀，我们不需要求出w,只需将新来 的样本和训练数据中的所有样本做内积和即可。那有人会说，与前面所有的样本都做运算是 不是太耗时了？其实不然，我们从KKT条件中得到，只有支持向量的二 其他情况 ；=1因此，我们只需求新来的样本和支持向量的内积，然后运算即可。这种写法为下面 要提到的核函数（kernel）做了很好的铺垫。这是上篇，先写这么多了。
