引言

在上一小节中，我们介绍，用二次规划的方法来求解支持向量机的问题。如果用非线性的特征转化的方式，可以在一个更复杂的Z空间里做二次规划。这种思想是希望通过最大间隔的方式来控制模型的复杂度，通过特征转换来实现复杂的边界。
但是这引入了新的问题：在进行特征转换之后，在新的高维空间中，求解二次规划问题就会变得很困难。甚至在无限大的维度上求解最佳化的问题就变得不可能了。
所以，这一小节，我们要解答的是，通过非常复杂的特征转换，甚至无限维的特征转换，该如何移除在Z空间上对高维度的依赖。

对偶问题

对于原始的SVM问题，进行特征转换之后，问题有d+1个变量(d为Z空间的维度)，N个限制条件。我们要转化为一个对等的问题，在这种情况下，问题只有N个变量，N+1个限制条件。
所以，不管是变量的数量也好，条件的数量也好，都只有和数据量有关系，和转换到什么维度的空间中没有关系。变量的数量不会随着特征转换有所变化。

第一步：引入拉格朗日函数

SVM和正则化的思想有些类似，是求解一个有条件的最佳化问题。

由上面这个图可以知道，左侧是原始的有条件的最佳化问题，右侧是使用拉格朗日乘数αn >= 0将条件加入到表达式中去。
于是，我们得到了下面这个SVM表达式：

这个式子的意思是，当b和w向量固定的时候，调整α使得拉格朗日函数的值最大，然后再求一个最小值的问题。
下面再解释一下这里的max的过程：
当b和w是违反约束条件的，那么造成αn与一个正数相乘，对其求解一个最大值问题，只能得到一个无限大的值，这样再求解一个最小化的问题，就可以将这些违反条件的b和w排除掉；
当b和w是符合约束条件的，那么造成αn与一个非正数相乘，就能得到一个有边界的最大值。

这一步，我们就可以将一个有条件的最佳化问题，通过拉格朗日乘数转换成一个表达式，从而方便后面的求解。

第二步：拉格朗日对偶问题的转化

对于一个给定的α，对拉格朗日函数的最大化的值总是大于任意一个拉格朗日函数的值，如下：

任何一个给定的α都会有上图的结果，于是我们对右边的式子去一个最大值的动作，就得到了下面的不等式：

这样看上去是将原来的式子的最大化和最小化作了一个交换，这被称为拉格朗日对偶问题。这样就得到了原来问题解法的下限。

强对偶关系需要满足条件

凸函数（convex primal）
原来的问题是有解的，在Z空间中可分（feasible primal）
线性条件（linear constraints）

如果满足上述强对偶关系的话，那么不等式的左右就是等价相等的了。于是，我们就可以来求解右边的问题。
右边的式子有个好处，本来，我们将约束条件通过拉格朗日乘数加入到求解问题中，但这样我们没有办法求解，现在对于max{min[L(b,w,α)]}来说，求解里面的最小化问题时α是固定的（可以看做一个常数），那么这就是一个凸二次规划问题，于是我们就可以用二次规划的方法来求解了。