SVM中拉格朗日乘子法、KKT条件、对偶问题详解

创作目的1.SVM回顾2.拉格朗日乘子法3.KKT条件4.对偶问题强对偶性证明总结

创作目的

我是机器学习初学者，目前正在上机器学习课，老师的SVM部分讲解的非常细致，我收获颇丰于是想自己记录一下SVM的详细内容以及推导过程方便自己以后复习。这一节主要针对拉格朗日乘子法以及其KKT条件还有强对偶、弱对偶问题进行总结和推导，希望在这一块有疑问的同学可以一起交流学习。萌新第一次写博客，很多地方表述不足希望大家指出。

1.SVM回顾

支持向量机（SVM）是目前最好的有监督分类方法之一，SVM分类器的基本型的推导很多书以及网上都有这里就不再介绍了，如果有时间以后可以补上。知乎上我找到一位作者总结的很到位感兴趣的读者可以去看看：支持向量机基本概念

SVM基本型基于两类最大化间隔的思想等价于下面这个优化问题：

（1） 式本身就是一个凸二次规划问题，凸函数以及凸二次规划的定义可以见链接：

/promisejia/article/details/81241201

凸二次规划问题可以直接用现成的优化计算包求解但这样计算较复杂，所以我们引入朗格朗日乘子法对其"对偶问题"进行更高效的求解。（1）的对偶问题为：

上式必须要满足KKT条件：

将KKT条件最后两项代入约束目标，这样原问题（1）就转换成了只有α的二次规划问题，一般采用SMO算法可以很快求解出近似解，SMO算法我将在下一次详细总结。

身边很多同学刚开始学SVM到这的时候就开始“黑人问号.jpg”了。什么是拉格朗日乘子？什么是对偶问题？为什么求min就转变成求max min了？KKT条件又是什么鬼？下面我一一进行解答。

2.拉格朗日乘子法

拉格朗日乘子法最开始是只针对等式约束优化问题提出的。对于一个等式约束优化问题：

引入一个自变量α，α可以取任意值，则（2）严格等价于：

现在来证明一下，我们把（3）式分满足（2）的约束条件和不满足两种情况讨论，即h(x)=0和h(x)≠0：

（4）与（3）等价，同时对于（4）由于α可以取任意值，当h(x)≠0时，αh(x)可以无限大，那么取最小值时永远不可能取到h(x)≠0的情况。那么（3）就严格等价于h(x)=0的情况，也就是（2）了，证毕。

但是SVM算法基本型是一个不等式约束优化，同样对于一个不等式约束：

它等价于（6），这里α加上了约束，不再可以取任意数而是取大于等于0的数：

证明同上，讨论（6）满足(5)的约束和不满足约束两种情况，即：

对于（7）式第一排αh(x)小于等于0，对第一排求最大值时αh(x)=0，消掉后只留下f(x)。对于（7）第二排，αh(x)可以取到无限大所以取最小时不可能取到第二排，于是（6）就等价于（7）的第一排消掉αh(x)，也就是等价于（5），证毕。

同时我们看到（7）也等价于（5），我们把（7）表示成：

通过（8）我们可以发现min max出现了 ，SVM基本型代入上式可以发现与SVM中的对偶问题只是在max min的顺序上不同了。这里强调一点，（8）式并不是（5）式的对偶问题，它们是严格等价的，是同一个问题，关于对偶问题我将在第四节细讲。下面来看满足（8）式的约束条件，也就是KKT条件。

3.KKT条件

刚才我们知道了（5）等价于（8），对于（8）最优解 x* 还应该满足以下的约束条件，统称为KKT条件：

a.首先，x* 要满足已有的两个基本约束，h(x*)<=0，以及α>=0；

b.同时（8）等价于（5）必须满足αh(x*)=0这个条件；

c.最后，我们在高中就学过对于一个无约束的凸函数求极小值问题的最优解x*一定满足∇xf(x∗)=0\nabla_xf(x*)=0∇x​f(x∗)=0这个条件，而当有约束条件时如（5）我们通过拉格朗日乘子法把（5）转化为（8）。（8）式先对max进行求极大值，再求min时，此时α的值已经固定，我们不妨将（8）约束目标min后边看成一个关于x的函数g(x)这时α不再构成约束,则（8）等价于对于无约束凸函数g(x)求极小值问题，所以一定满足条件：∇xf(x∗)+α∇xh(x∗)=0\nabla_xf(x*)+α∇xh(x*)=0∇x​f(x∗)+α∇xh(x∗)=0。

于是关于满足（8）的KKT条件就是：

注意：KKT条件只是对于原问题的约束条件，最优解一定得满足KKT条件，KKT条件是原问题的充分必要条件。KKT条件与对偶问题无关只与原问题有关。

4.对偶问题

由前面分析我们知道了（5）等价于（8）。对于（8）式这样的不等式约束问题，我们可以定义其对偶问题。

我们定义（8）的对偶问题为：

可以看到这里的对偶问题仅仅知识交换了目标函数的max和min的求解顺序，约束条件都相同，所以原问题的约束条件KKT条件仍然是对偶问题的约束条件。对偶问题先确定里面x关于函数极小值有时候会比原问题先求α关于函数最大值更容易求解，比如SVM就是对偶问题比较好求解。但是对偶问题和原问题不是等价的，原问题和对偶问题有如下的关系：

记f(x)+αh(x)为f(x,α)，上式推导过程：

可以发现原问题目标函数始终是大于等于对偶问题的，所以我们定义当原问题目标函数的最优值等于对偶问题的值时称原问题满足强对偶性，大于时则为弱对偶的。只有当原问题有强对偶性我们才可以用对偶问题去等价原问题，那么什么时候原问题才满足强对偶性呢？答案是当原问题（5）是一个凸优化问题且满足salter条件时，它是强对偶的，下面来简单推导一下。

强对偶性证明

在B站上看见一位up讲解的特别好，这里再进行总结一下，附上链接：

/video/BV1aE411o7qd?t=427&p=33

对于一个约束优化问题，如（5）：

他的原问题和对偶问题可以表示为：

上一节提到原问题和对偶问题一定满足关系：p*>=d*，当"="成立时满足强对偶性。下面给出证明：

设D为f(x),h(x)的定义域的交集，为了方便表示出p和d的关系，我们将f(x)和h(x)表示为横纵坐标，建立一个平面直角坐标系，在定义域D下可以在该坐标系下定义原问题以及对偶问题的可行域G：

为了便于理解，我们记h(x)轴为x轴，f(x)为y轴，（不失一般性）我们假设问题的可行域为一个非凸的区域,则该坐标系可以表示为：

原问题最优解p*=min f(x)满足h(x)<=0，可行域即为上图阴影区域，要找此区域f(x)的极小值，即找到可行域中纵坐标最小的点即可，如上图蓝点位置就是该可行域的p*。

此外我们还需要找到d* 的值才能找到p* 和d* 的关系。我们把d*=max min f(x,α)拆成两部分，即:

第一部分：d*=max f(x*,α) (α是自变量，x* 是一个确定的数)；

第二部分：f(x*,α)=min f(x,α) ，(x是自变量，α是一个确定但未知的数)；

再由f(x,α)=f(x)+αh(x) 等价于 f(x)=-αh(x) + f(x,α),我们把d* 转化成了坐标系中的一次函数y=kx+b的形式。

首先，我们先看d* 的第二部分，它在坐标系中等价于f(x)=-αh(x) +b这条直线，由于α>0,所以h(x)的系数-α一定小于0，所以直线是经过二、四象限的，此外p* 一定在定义域G中所以直线与G必须要有交点才满足条件。第二部分的目标函数min f(x,α)即直线的常数项b，如下图，我们可以通过平移直线找到直线与可行域G相交时得到b的值，我们先固定一个α再将直线向上平移刚好与可行域相切时得到的常数项b最小。

现在我们来看d* 的第一部分，也就是一次项系数-α的影响下常数项b求最大值，由于-α<0直线必须经过一、二、四象限，所以我们可以通过旋转直线求此时b的极大值。注意当直线与可行域相切时才满足第二部分的条件，如下图当直线旋转到非凸可行域两端点处相切时，既满足第一部分极小时的条件，又使得此时b最大，即此时对应的b就是d*。

通过上图我们可以明显看到当可行域是非凸情形时d是小于p的，这也是弱对偶问题的另一种解释。那么当可行域是凸区域的情形会如何呢？我们看看下图：

可以看到当可行域G为凸区域时，p* 和d* 刚好相等。目前已经证明：当原问题是一个凸优化问题，且满足slater条件时，可行域G就是一个凸区域，即原问题是强对偶问题。而SVM原问题是一个凸优化问题，同时是一个二次规划问题先天满足slater条件，所以SVM是一个强对偶性优化问题可以将原问题转换为对偶问题进行求解。

总结

本文主要对SVM问题中出现的拉格朗日乘子法以及其KKT条件还有强对偶、弱对偶问题进行总结和推导，用于个人期末复习以及加深印象。可能还有许多错误和不足，欢迎大家指正。下一节将对求解SVM对偶问题的主要算法SMO算法进行总结。