第二部分：转化为对偶问题进一步简化
这一部分涉及的数学原理特别多。如果有逻辑错误希望可以指出来。
上一部分得到了最大间隔分类器的基本形式：
直接求的话一看就很复杂，我们还需要进一步简化。
这里就需要介绍拉格朗日乘子法。介绍它还是从最最简单的形式说起：
优化问题这里面有很多东西，我先给出参考过的资料有，可以先看看这些资料自己总结一下，因为我觉得这部分内容很多人总结的都很好了：
①《支持向量机导论》的第五章最优化理论
⑤一些博客，下面会给具体链接
优化问题最简单的应该就是无约束的优化问题了吧。
一般的做法就是，先求导，然后导函数为0，就可以得到极小值点对应的x的值，代入后就得到对应的y的极小值，而这里极小值就是最小值。
然后高中其实我们就知道，即使无约束（即定义域为R），在很多情况下，极小值点也不一定是最小值点。因为可能会有很多个导函数为0的点（比如说正弦函数），所以此时我们的做法应该就是求出所有极小值点对应的y值，然后选择最小的。
这就是最简单的无约束优化问题，其实就是求导，让导数等于0。
现在把问题变得复杂一点，我们考虑带等式约束的优化问题，下面举的例子和图片来自
我觉得这里已经解释的很不错了。
举个例子，现在的优化问题是：
既然必须在这条直线上运行，那么我们可以先在直观上看在这条直线上运行如何影响原来目标函数的值。如果我们沿着这条直线从左上一直到右下，根据等高线我们可以知道目标函数值是先增大，然后减少。
很明显，当他的速度正好和他所在位置的等高线相切时。此时不会有法线方向的速度了。
那他什么时候速度能和等高线相切呢？注意到这个人的“速度”方向其实一直被限制为这个直线的方向，所以相切发生在这个直线和等高线相切时。
（可能有些不太准确，但是为了直观上理解只能这样了）
此时我们就可以得到那个可以使目标函数值最大的点，就是找那个相切的点。
注意到，当约束函数的方向和等高线相切时，它们的梯度方向是共线的，即在那个点满足：
上面就是当遇到等式约束的优化问题时，从直观上该如何解决，主要就是找到那个“相切点”。
那么我们如何用数学的方法求出满足这个条件的这个点呢？这就需要用到拉格朗日乘子法了。
(这里简单说一下只有一个等式约束时的情况)
对于优化问题：
我们引入拉格朗日乘子λ，写出这个问题的拉格朗日函数：
而我们的优化问题其实可以转化为：
这个拉格朗日函数和我们之前说的
有什么关系呢？你可以试着让拉格朗日函数对每个变量都求偏导，并让偏导为0，就可以发现：
也就是说对拉格朗日函数求偏导，导数为0得到的结果其实就是我们之前需要的那两个条件：①梯度成正比②满足约束条件
拉格朗日乘子法其实就是把原来的有约束的优化问题转化为了无约束的优化问题，并且成功的把约束条件包含在了这个无约束的优化问题中。这就是我对于拉格朗日乘子法的理解。
到这里我们知道可以用拉格朗日乘子法来解决等式约束的优化问题。
但是你可能注意到在SVM的优化问题里，约束并不是个等式，而是一组不等式
而我们之前介绍的是等式约束的优化问题，所以我们还必须要介绍带有不等式约束更一般的优化问题。
在这里我只能说一说自己的理解了。
如果对于优化问题
有三个不等式约束。对于这样的约束问题，它的最优解x*是一定需要满足KKT条件的。我先写出这些条件（下面这些条件再加上原始的约束条件其实就是整个KKT条件了，下面在更一般的情况下说），并在直观上说明为什么要这样。具体的证明在《AnIntroductiontoOptimization》上有。
现在我们一个一个在直观上解释
条件（1）是说所有的KKT乘子需要大于等于0。关于这个问题我查了很多资料，但是没有一个让我觉得说清楚的解释。我个人把这个理解为一种规范？这个问题还需要思考，希望有人可以解释一下。
条件（2）表示目标函数在最优点的梯度可以用g1(x)，g2(x)和g3(x)线性表示出来。这里看到是三个的线性组合之后的反方向，这是因为之前规定这个问题是最小化问题，根据Wiki上KKT条件的资料表明，如果是最大化问题，那么会是：
（图片来自于《AnIntroductiontoOptimization》）
（这个要注意，不是说gi(x)=0了，它对应的KKT乘子就不能是0了，具体参考《AnIntroductiontoOptimization》
）
但是现在我只能通过给定的条件解释为什么要这样，却不能解释这些条件都是怎么推导出来的...
KKT条件是最优解的一个必要条件，在求解最优解时，通过解这些式子来求最优点。
4.更一般的优化问题，既有等式约束，又有不等式约束
而对于更一般形式的最优化问题，即既有等式约束，也有不等式约束：
而且对于这个更一般的优化问题，在《支持向量机导论》的第五章（其他书上都还没找到）还可以找到它所对应的广义拉格朗日函数：
我现在可以写出这个优化问题对应的KKT条件（参考Wiki百科KKT条件的分类方式）：
（1）Stationarity（平稳性..但是不知道为什么这么叫）
这里是最小化，所以对应的梯度条件是：
（注意这里的x可能有很多维，这时就是对每一维的偏导需要满足这个条件）
（2）Primalfeasibility（优化问题自带的约束条件）
就是原来的已经存在的那两类约束，包括等式和不等式
（3）Dualfeasibility（具体含义还不太明白）
就是KKT乘子必须满足的
（4）Complementaryslackness（互补松弛条件）
这么看一共有三个等式两个不等式，具体可以分为：①梯度要求②原始约束条件③KKT乘子需要满足大于等于0④互补松弛条件。
（这里可以把①和②分为一类，因为①和②都是对应的拉格朗日函数对变量求偏导为0）
但是作为学完KKT条件的练习，我们可以尝试自己求一求之前的SVM问题的KKT条件！
上一部分最后的优化问题：
如果我们需要用KKT条件来解决这个问题的话，我们现在就可以写出它需要满足的KKT条件了，在此之前，先把约束不等式写成标准形式，并且注意到这里没有等式约束：
那么可以先写出对应的拉格朗日函数：
然后我们就可以先写出它需要满足的KKT条件为：
（1）梯度条件（对ω和b求偏导并等于0）
（2）自带的约束条件
（3）KKT乘子需要满足的
（4）最后就是松弛互补条件：
OK，可以自己推导一下KKT条件，是不是发现介绍SVM的书上的那些原来莫名其妙就给出来的KKT条件自己也能写出来呢。
很多书讲的太笼统了，还是有很多细节逻辑需要考虑的。
关于对偶问题的资料，我推荐：
①《支持向量机导论》第五章
②《统计学习方法》后面的附录
大家可以先自己看一看，关于对偶问题的内容在《统计学习方法》附录那里讲的是最清楚的个人认为。
在求解最优化问题时，经常把原问题转化为对偶问题求解。
现在我们需要求解的优化问题为：
它对应的拉格朗日函数为：
那么我现在可以定义一个问题：
需要证明这个问题与原始的约束问题
等价。
证明这两个最优化问题等价，其实就是证明它们的优化目标和它们的约束条件是等价的。
这个也很容易证明：
所以我们就把原始的约束问题表示为广义拉格朗日函数的极小极大问题。
然后需要介绍其对偶问题，其实它的对偶问题很简单，就是把极小和极大的顺序颠倒一下即可。
我们先定义：
得到拉格朗日函数的极大极小问题，也就是原问题的对偶问题
那么原问题的最优值和对偶问题的最优值有什么关系呢？
证明：对任意的x,λ,μ：
（第一个等号是定义，第二个小于等于号是因为min的定义，第三个小于等于号是因为max的定义）
那么什么时候对偶问题的解和原问题的最优解可以相等呢？
3.对偶问题和原问题的最优解相等的充要条件
在《统计学习方法》里给出了定理：
具体证明我没查，这个定理我觉得知道就好。
所以你可以看到KKT条件很重要。
接下来还是回到SVM的主线，我们需要来求一下SVM中遇到的问题的对偶形式是什么。
首先还是把原问题再列一下：
拉格朗日函数：
KKT条件为：
所以原问题写成极小极大问题的形式就是：
然后我们就可以求出它对应的极大极小问题形式，即对偶问题形式：
就是极大和极小换了下位置。
但是这样一换位置的好处就是，我们就可以先求解内部的
通过求偏导（之前已经求过了，在KKT条件里）并代入我们可以得到进一步只和有关的优化问题了，这一步的消去代入过程如下：
（最好还是自己推导一遍）
所以我们现在得到进一步的优化问题：
然后还需要满足之前说的KKT条件（可以翻看之前求出来的KKT条件），所以除了上面这两个约束外，还需要:
最后整理一下从SVM基本形式到它的对偶形式的逻辑过程：
②从它的拉格朗日函数形式转化为对偶形式，这里需要知道条件下对偶形式的最优解和原问题的最优解相等，也就需要理解KKT条件每一个的意义，并知道对于一般的约束问题如何写出它的KKT条件