项目地址：https://github.com/Daya-Jin/ML_for_learner/blob/master/svm/SMO.ipynb
原博客：https://daya-jin.github.io/2019/03/24/SequentialMinimalOptimization/
算法概述
在之前讲解SVM博客中，分析了SVM模型的理论基础与优化目标，并且讨论了SVM在达到最优解时的一些性质。但是前文中并没有提及SVM目标函数的优化方法，本文的目的就是讨论二次优化算法SMO用于SVM的学习。因为SMO算法涉及到的很多数学知识已超出本文范畴，某些地方只给出直接结论。
首先回顾SVM的优化目标为：
为了将核函数加入进来，将目标函数中两训练样本的内积替换成核函数的形式：
SMO算法的核心思想是：每次只选取一对参数进行优化。假设在上述目标中，我们只令与
为参数，其他
为常数，那么优化问题可以写成：
去除无关常量，简化后的优化目标可以写成：
在前文中提过SVM在优化后的一些性质，如对于分类正确的样本，其对应的是等于
的，同样的，那么对于软间隔SVM，不难推出优化后的几个性质：
| 样本分类情况 | 对应的 |
|---|---|
优化策略
SMO每次只选取一对视为参数，假设先选定
，那么
的优化公式为：
然后再看优化问题中的约束条件，由于只有
与
是参数，那么该优化条件还可以写成：
。而
与
的可能取值为
，由几何方法可以得到优化参数
的一个上下界：
- 若
，
，
- 若
，
，
所以，在优化之后，还需要检验是否还符合约束条件，若不满足，则需要做截断处理：
而的优化公式为：
其中。
针对任一一个，若
在边界范围
内，可以推出对应的
：
那么将其写成一个条件函数，可得到的迭代优化公式：
