序列最小优化算法（Sequential minimal optimization, SMO）是一种用于解决支持向量机训练过程中所产生优化问题的算法。SMO由微软研究院的约翰·普莱特于1998年发明，被广泛使用于SVM的训练过程中，并在通行的SVM库LIBSVM中得到实现。1998年，SMO算法发表在SVM研究领域内引起了轰动，因为先前可用的SVM训练方法必须使用复杂的方法，并需要昂贵的第三方二次规划工具。而SMO算法较好地避免了这一问题。

SMO算法主要用于解决支持向量机目标函数的最优化问题。考虑数据集 的二分类问题，其中 是输入向量， 是向量的类别标签，只允许取两个值。一个软边缘支持向量机的目标函数最优化等价于求解以下二次规划问题的最大值：

满足：

其中， 是SVM的参数，称为惩罚因子，用于定义对误分类的惩罚，而 是核函数。这两个参数都需要使用者制定。

C的推导式：

记L为损失函数，C乘以L为损失的惩罚因子，SVM中有如下目标函 数：

显然，这些损失是常数且>=0，因此引入松弛变量的概念替换原来的损失函数计算结果，重写简化：

进行拉格朗日变换，变为：

对偶转换，转为对极大值函数的极小问题，也就是先函数对w、b求导取极小值，然后代入：

最终得到如下对偶问题：

SMO是一种解决此类支持向量机优化问题的迭代算法。由于目标函数为凸函数，一般的优化算法都通过梯度方法一次优化一个变量求解二次规划问题的最大值，但是，对于以上问题，由于限制条件 存在，当某个 ，从 更新到 时，上述限制条件即被打破。为了克服以上的困难，SMO采用一次更新两个变量的方法。

假设算法在某次更新时更新的变量为 和 ，则其余变量都可以视为常量。为了描述方便，规定

因而，二次规划目标值可以写成

由于限制条件 存在，将 看作常数，则有 成立（ C为常数）。由于 ，从而 ( 为变量 ， ）。取 为优化变量，则上式又可写成

对 求偏导以求得最大值，有

因此，可以得到

规定误差项 ，取 ，并规定 ，上述结果可以化简为

再考虑限制条件 的取值只能为直线 落在 矩形中的部分。因此，具体的SMO算法需要检查 的值以确认这个值落在约束区间之内。

对于区域外的，需要进行剪辑：

因为 只能是1或-1，因此的关系被限制在盒子里的一条线段上（只能是a1-a2/a1+a2两种情况，既要么相一致要么不一致），又因为两变量的优化问题实际上仅仅是一个变量的优化问题（一个能由另一个得出），我们假设是对的优化问题,所以只存在2幅图的情况：

1）y1!=y2（二者不一致），则根据上面的约束 ，这里的k是上面的C，有 ，L，H为约束下的最小，最大值。有以下关系：

2）y1=y2时

原来未剪辑后的公式为：

剪辑后则为：

求另外一个变量

在求得 后， 则可以直接依据 得出，因为：

因此 有：

求偏置b

更新完后还需要更新b，因为此时参数变了，当

时：

于是新的b可更新：

因为： 所以可以把b写成有E的式子：

同样的，如果

有：

虽然理论上以上的偏置b都可以用来更新，但是SMO里面b采用更加鲁棒的更新策略，为：

SMO算法是一个迭代优化算法。在每一个迭代步骤中，算法首先选取两个待更新的向量，此后分别计算它们的误差项，并根据上述结果计算出 和 。最后再根据SVM的定义计算出偏移量 。对于误差项而言，可以根据 、 和b的增量进行调整，而无需每次重新计算。具体的算法如下：

1、随机数初始化向量权重 ，并计算偏移量

2、初始化误差项

3、 选取两个向量作为需要调整的点

4、令

5、如果

6、令

7、如果

8、令

9、令

10、 利用更新的 和 修改 和 的值

11、如果达到终止条件，则停止算法，否则转3

其中，U和V为 的下界和上界。特别地，有

这一约束的意义在于使得 和 均位于矩形域 中。

可以采用启发式的方法选择每次迭代中需要优化的向量。第一个向量可以选取不满足支持向量机KKT条件的向量，亦即不满足

的向量。而第二个向量可以选择使得 最大的向量。

SMO算法的终止条件可以为KKT条件对所有向量均满足，或者目标函数 增长率小于某个阈值，即