1.问题定义

$\left \{ \begin{aligned}w^Tx+b &= 1\\w^Tx+b &= -1\end{aligned}\right.$
我们最大化两条直线的距离：
$\begin{aligned}\rm{max}\ \frac{2}{||w||_2}<=>min\ ||w||_2 \\ s.t.\ y_i(w^Tx_i+b)-1\ge0\end{aligned}$

2.求解

原问题转化为：
$\begin{aligned}&{\rm min}\ ||w||_2 \\ s.t.\ g_i(w,b) = 1-y_i(&w^Tx_i+b)\le0, {\rm where}\ i=1,2,...,n\end{aligned}$
构造拉格朗日函数：
$\begin{aligned}L(w,b,\lambda)=||w||_2+&\sum_i^n\lambda_i*(1-y_i(w^Tx_i+b))\\&s.t.\ \lambda_i\ge0 \end{aligned}$
强对偶条件：
$\begin{aligned}\underset{w,b}{\rm min}\ \underset{\lambda}{\rm max}\ &L(w,b,\lambda)\\<=>\underset{\lambda}{\rm max}\ \underset{w,b}{\rm min}\ &L(w,b,\lambda)\end{aligned}$
现对参数 w 和 b 求偏导数：
$\begin{aligned}\frac{\partial L}{\partial w} &=w-\sum_{i=1}^{n}\lambda_iy_ix_i=0\\\frac{\partial L}{\partial b} &= -\lambda_iy_i=0 \end{aligned}$
得到
$\begin{aligned}&w=\sum_{i=1}^{n}\lambda_iy_ix_i\\&\sum_{i=1}^{n}\lambda_iy_i=0 \end{aligned}$
代入 $L$
$\begin{aligned}L(\lambda) &= \sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)+\sum_i^n\lambda_i*(1-y_i(\sum_{j=1}^n\lambda_jy_j(x_i\cdot x_j)+b))\\&=\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)+\sum_i^n\lambda_i-\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^n\lambda_iy_ib\\&=\sum_i^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)\\&s.t.\ \lambda_i\ge0\end{aligned}$

$\begin{aligned}\underset{\lambda}{\rm max}\ L(\lambda) &= \sum_i^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_i\cdot x_j)\\ &s.t.\ \lambda_i\ge0, \sum_{i=1}^{n}\lambda_iy_i=0\end{aligned}$
我们可以看出来这是一个二次规划问题，问题规模正比于训练样本数，我们常用 SMO(Sequential Minimal Optimization) 算法求解。

SMO(Sequential Minimal Optimization)，序列最小优化算法，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值。我们来看一下 SMO 算法在 SVM 中的应用。

我们刚说了 SMO 算法每次只优化一个参数，但我们的优化目标有约束条件： $\sum_{i=1}^{n}\lambda_iy_i=0$ ，没法一次只变动一个参数。所以我们选择了一次选择两个参数。具体步骤为：
1.选择两个需要更新的参数 $\lambda_i,\lambda_j$ ，固定其他参数。于是我们有以下约束：
$\lambda_iy_i+\lambda_jy_j = c= -\sum_{k\neq i,j}^n\lambda_ky_k, \lambda_i\ge0,\lambda_j\ge0$
由此可以得出 $\lambda_j=\frac{c-\lambda_iy_i}{y_j}$ ，也就是说我们可以用 $\lambda_i$ 的表达式代替 $\lambda_j$ 。这样就相当于把目标问题转化成了仅有一个约束条件的最优化问题，仅有的约束是 $\lambda_j\ge0$ 。
2.对于仅有一个约束条件的最优化问题，我们完全可以在 $\lambda_i$ 上对优化目标求偏导，令导数为零，从而求出变量值 $\lambda_{i\_new}$ ，然后根据 $\lambda_{i\_new}$ 求出 $\lambda_{j\_new}$ 。
3.多次迭代直至收敛。
通过 SMO 求得最优解 $\lambda^*$ 。