我们知道，支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以致无法使用。所以，如何高效地实现支持向量机学习就成为一个重要的问题。目前人们已提出许多快速实现算法。本节讲述其中的序列最小最优化（sequential minimaloptimization，SMO）算法，这种算法1998年由Platt提出。
SMO算法就是求解凸二次规划的对偶问题
\[\underset{\alpha}{min}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i\\
s.t. \quad \sum_{i=1}^{N}\alpha_iy_i=0\\
\quad \quad \quad C\geq \alpha_i\geq 0,i=1,2,\cdots,N\]
$\alpha_i$是拉格朗日乘子，每个$\alpha_i$对应一个样本点$(x_i,x_j)$。
SMO算法是启发式算法，，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。
注意，子问题的两个变量中只有一个是自由变量。假设$\alpha_1$,$\alpha_2$为两个变量，其他乘子固定，那么由等式约束$\sum_{i=1}^{N}\alpha_iy_i=0$可知
\[\alpha_1=-y_1\sum_{i=2}^{N}\alpha_iy_i\]
所以子问题中同时更新两个变量。整个SMO算法包括两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。
两个变量二次规划的求解方法不失一般性，假设选择的两个变量是$\alpha_1$,$\alpha_2$其他变量$\alpha_i$是固定的。于是SMO的最优化问题的子问题可以写成：
\[\underset{\alpha_1,\alpha_2}{min}\quad W(\alpha_1,\alpha_2)=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^{N}\alpha_i\\
=\frac{1}{2}[K]_{11}\alpha_1^2+\frac{1}{2}[K]_{22}\alpha_2^2+y_1y_2[K]_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^{N}\alpha_iy_iK(x_i,x_1)+y_2\alpha_2\sum_{i=3}^{N}\alpha_iy_iK(x_i,x_2)\\
s.t.\quad y_1\alpha_1+y_2\alpha_2=-\sum_{i=1}^{N}\alpha_iy_i=k\\
\quad\quad\quad C\geq \alpha_i\geq 0,i=1,2,\cdots,N\]
k是个常数。$W(\alpha_1,\alpha_2)$省掉很多不含$\alpha_1,\alpha_2$的常数项。
由于只有两个变量$\alpha_1,\alpha_2$，所以约束可以表示为平面区域
约束$y_1\alpha_1+y_2\alpha_2=-\sum_{i=1}^N\alpha_iy_1=k$限制了目标函数在平行对角线的直线上寻优，所以实质是单变量优化问题，那么
当$y_1\neq y_2$时，$\alpha_1-\alpha_2=k$，所以给定一组旧的可行解$\alpha_1^{old}$，$\alpha_2^{old}$和新的可行解都满足
\[\alpha_1^{old}-\alpha_2^{old}=k\\
\alpha_1^{new}-\alpha_2^{new}=k=\alpha_1^{old}-\alpha_2^{old}\]
那么
\[0\leq \alpha_1^{new}\leq C\\
0\leq \alpha_2^{new}\leq C\]
得出
\[0\leq \alpha_2^{new}+\alpha_1^{old}-\alpha_2^{old}\leq C\]
\[0\leq \alpha_2^{new}\leq C\]
也是
\[\alpha_2^{old}-\alpha_1^{old}\leq \alpha_2^{new}\leq C+\alpha_2^{old}-\alpha_1^{old}\]
\[-k\leq \alpha_2^{new}\leq C-k\]
\[0\leq \alpha_2^{new}\leq C\]
因此$\alpha_2^{new}$所在对角线端点的界为
\[L=max(0,\alpha_2^{old}-\alpha_1^{old})H=min(C,C+\alpha_2^{old}-\alpha_1^{old})\]
同理，当$y_1=y_2$时，$\alpha_1+\alpha_2=k$，所以给定一组旧的可行解$\alpha_1^{old}$,$\alpha_2^{old}$，和新的可行解$\alpha_1^{new}$,$\alpha_2^{new}$，所在对角线端点的界为
\[L=max(0,\alpha_2^{old}+\alpha_1^{old}-C)H=min(C,\alpha_2^{old}+\alpha_1^{old})\]
定理：记
\[g(x)=\sum_{i=1}^{N}\alpha_iy_iK(x_i,x)+b\]
令
\[E_i=g(x_i)-y_i=(\sum_{j=1}^{N}\alpha_jy_jK(x_i,x_j)+b)-y_i\]
表示输入$x_i$的预测值和标签$y_i$的差。
利用$y_1=\mp1$
\[y_1\alpha_1+y_2\alpha_2=k\\
\alpha_1=y_1(k-y_2\alpha_2)\]
代入$\underset{\alpha_1,\alpha_2}{min}W(\alpha_1,\alpha_2)$，则只是成了$\alpha_2$的二次函数优化问题了，那么利用
\[\frac{\partial{W}}{\partial{\alpha_2}}=0\]
得到
\[\alpha_2^{new,un}=\alpha_2^{old}+\frac{y_2(E_1-E_2)}{[K]_{11}+[K]_{22}-2[K]_{12}}\]
又注意到边界，所以
\[\alpha_2^{new}=\left\{\begin{matrix}
H,\alpha_2^{new.un}>H\\
\alpha_2^{new.un},L\leq \alpha_2^{new.un}\leq H\\
L,\alpha_2^{new.un}<L
\end{matrix}\right.\]
SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
1．第1个变量的选择