提到SVM，可能首先想到的是令人头大的公式推导，通过确定思想，公式等式转化，拉格朗日函数，求梯度，约束变换，KKT、SMO。。。最后终于得到我们的最优解。而在这其中，不免作为核心的就是拉格朗日函数以及KKT条件，就像建筑高楼大厦前需要打地基，如果说SVM这个模型方法是高楼大厦的话，拉格朗日函数和KKT这些最优化方法就是我们需要提前打好的地基。只有对这两个东西有了理解后，才能对SVM的公式推导能够有更深入的理解。
原始问题与拉格朗日函数
首先由原始问题：
均为实数域上的连续可微函数吗，这里要注意的是可能会有多个函数
。j也同理。
然后我们引进广义拉格朗日函数将损失函数和约束条件写到一起：
，这里新出现的变量
是拉格朗日乘子，而且
。
这时我们可以将
看做和
等效。为什么呢？由约束条件，第三项
为0，不用管了。第二项
小于等于0，所有
的最大值肯定就是第一项
了。
现在看看原始的问题
，现在组合上我们的拉格朗日函数就是
，而这个式子，就等价我们的原始问题了（损失函数加两个约束条件）。
变换后函数与对偶问题
刚刚已经得到问题转化后的新的表达式
。
这里引入拉格朗日对偶问题的定义：个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法
总而言之，原始问题经过变换后得到
，它与
（这里已经将αi>=0写到了max下面）为对偶关系。
这个对偶问题的最优值是小于等于原始问题的最优值的，而在某种特定情况下对偶问题的最优值就等于原始问题的最优值。这个特定情况，就是我们待会儿会说到的KKT条件，只有符合KKT条件时，我们才能放心大胆地去拿对偶问题算出来的答案当做最终答案。
为什么原始问题的最优值是小于等于对偶问题的最优值的？个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法
KKT条件
首先提一个问题，拉格朗日乘子法为啥长这样？
首先想象一下f(x)的最小值，比如可以想象成一个碗的最底部。
好，现在出现了等式约束条件h(x)。
刚刚碗的最底部已经不满足现在这个约束条件了。
f(x)与h(x)相切的地方，也许才是符合我们条件的最优值。
而在这个极值点
，这就是新的极值点条件。而实际上把右侧挪到左侧就变为了
，再求偏导为0，这就与之前的条件等价了。注意图中虽然是反向，但这里有可能是同向，有可能是反向，所以对
并没有做要求。这其实就是拉格朗日乘子法。
同理，如果是多个等式约束：
，也一样是刚刚的操作步骤，然后求梯度就行了。得到向量
。
如果是不等式约束呢？可行域由刚刚的一条线变成了一块区域。
如果是<=，则先取反成为>=。
对于不等式约束有两种情况，一种是极值点在可行域内部，一种是极值点仍然在与等值线相切的地方（而这种就和等式约束的情况是一致的）。
对于第一种情况，这个不等式约束等于没有，依然求解
为了后面方便比较，此时可以写成
.......................(1)
对于第二种情况，与前面阐述的等式约束的情况相同
........................(2)
而在这个极小值处，可以知道，
和
的方向刚好相反。因为
指向g(x)>0的一侧，而
就指向可行域的那一侧。而这就说明
一定是大于等于0的，
表示它们方向相反。
(2)于是就可以变为
.........................(3)
将（1）和（3）结合到一起可以写为：
| | 情况一： |
而将前面的等式约束写到一起，则为
| | 第一个公式解释：最优点的梯度为h(x)和g(x)的梯度的线性组合。这就是我们看到的拉格朗日函数。 最后一个公式，松弛互补条件（也叫对偶互补条件）解释：
|
当有多个约束条件时，变为
这个方程组就是所谓的KKT条件。它的含义是我们原始问题的极值点一定满足这个条件（不是极值点也可能满足），是取得极值的必要条件。
小结
对于无约束的优化问题，直接令梯度等于0求解。
对于含有等式约束的优化问题，拉格朗日乘子法，构造拉格朗日函数，令偏导为0求解。
对于含有不等式约束的优化问题，构造拉格朗日函数函数，利用KKT条件求解。
对于含有约束的优化问题，可以通过满足KKT条件转化为拉格朗日对偶来做。
SMO算法
为了解决带有不等式限制的凸优化问题（凸二次规划），一般采用内点法，但是内点法代价太大，需要存储一个nxn的矩阵，在内存有限的条件下不可行，且每次求全局导数花费时间很多。而SMO是解决二次优化的好东西，他每次选择两个拉格朗日乘子
来求条件最小值，然后更新
。由于在其他拉格朗日乘子固定的情况下，
有如下关系：
这样
就可以通过
表示出来，此时转化为一个变量的二次优化问题，这个就大大降低了计算量。所以SMO包括两个过程：一个过程是选择两个拉格朗日乘子，这是一个外部循环，一个过程来求解这两个变量的二次优化问题，这个是循环内过程。
SMO(sequential minimal optimization)算法，序列最小最优化算法。
说到SMO，不得不先提到坐标下降（上升）法。
坐标下降（上升）法
坐标下降法其实就是：先有一个初始点，每次通过在当前点沿一个坐标方向进行一维搜索，固定其他坐标方向，找到函数局部最小值。
一个周期循环所有方向（维度）的迭代过程，相当于梯度下降的一次迭代。
比如优化一个二元函数：
先固定x2，把f看成x1的一元函数求最优值，可以求导得到解析解：
再固定x1，把f看成x2的一元函数求最优值：
于是，当初始点为（2，2）时，我们的更新过程为：
（2,2）->（2,2/3）-> (2/3, 2/3) -> (2/3, 2/9)....
而梯度下降法使用目标函数的导数来确定搜索方向，该梯度方向可能不与任何坐标轴平行。两者都是迭代方法，且每一轮迭代，都需要O(mn)的计算量（m为样本数，n为系数向量的维度）。
SMO
它的思想类似于坐标上升法，我们需要优化一系列α的值，每次选择尽量少的优化，不断迭代直到函数收敛到最优值。Platt在1998年提出，针对软间隔最大化SVM对偶问题求解的一个算法：在每一步优化中，挑选出诸多参数（αk（k = 1,2,...,N))中的两个参数（αi，αj）作为“真正的参数”，其余参数都视为常数，从而问题就变成了类似二次方程求最大值的问题，从而我们就能求出解析解。
回顾我们的问题，一个这样的优化函数：
我们需要对
进行优化，但是这个凸二次优化问题的其他求解算法的复杂度很高。Platt提出SMO算法把原始问题求解N个参数二次规划问题，分解成多个二次规划问题求解，每个子问题只需要求解2个参数，节省了时间成本和内存需求。
第一步：乘子选择
如果不想看公式推导，可以直接看后面的小结。
与坐标上升法不同，在SMO中每次需要选择一对变量
，因为在SVM中，α并不是完全孤立，而是具有约束：
- 选出α1，α2，...，αN中“最不好的”两个参数αi，αj：违反KKT条件最严重的样本点
αi及其对应样本（xi,yi）的KKT条件为：
上述KKT可以直观地叙述为：
间隔超平面即为满足方程
的平面，有两个。
差异向量
，第k份对应三个KKT条件中的第k个，
且
将三份差异向量的平方相加来作为“损失”，从而直接选出使该损失最大的αi作为SMO的第一个参数即可：
当alpha1确定后，E1也可以确定（
），通过使
得到alpha2。
第一步小结：对于任意两个乘子，只要其中一个乘子违反了KKT条件，就将这个数据样例加入到候选集合。通过这样的判别条件，对所有乘子不为0或C的数据进行扫描，得到了一个待优化的候选集合。
第二步：两个乘子的优化
假设选取的是两个需要优化的参数
，剩下的则固定，作为常数处理。（把与
无关的项合并成常数项C，在该损失函数中可忽略）：
由
，两边同时乘以一个y1，可得到:
令
，将上述代入损失函数，就可消除α1：
对这个一元函数求极值，W对α的一阶导数为0得到：
由SVM对预测点的值为：
（ωx+b）
则v1和v2可以表示为：
将其代入，并整理得到：
将上式左边的α2视作新α，右方的α2视作旧α。同时将
代入：
记Ei为SVM预测值与真实值的误差：
右边变为：
于是得到了新α的表达式：
，利用线性关系
可得到α1。
令
得到
这里写的是未修剪的，这是未考虑约束条件下的最优解。
考虑约束条件：
由于y1,y2只能取1或者-1，这使α1和α2在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1。
下图左边为y1,y2不同时，斜率为1。此时线性限制条件写成
。
若k<0，则k的下界为：
k的上界为：
假设上轮迭代得到的解
，假设沿着约束方向α2未经剪辑的解为
，本轮迭代完成后的解为
。
必须满足上述的线段约束，假设L和H分别是
所在线段的下界和上界。
在左图中，很明显（y轴为x2的取值）：
解释：当k<0时就取-k即为后者，当k>0时取0.
同理，右图为：
于是将α2通过上下界进行修剪：
由于其余项始终保持不变，所以我们可通过
得知：
故
。
更新阈值b
在更新了一对α后，需要对b进行重新计算，因为b关系到误差
的计算。
解要满足的KKT条件的对偶互补条件为：
在软间隔最大化目标函数优化，已经分析过：
当
时，根据KKT条件可知相应的数据点为支持向量。满足
，两边同时乘上y1得到
，则b1为
由
可将上式前两项写成：
同理当
时，可得：
最终的
为
最后更新Ei
，S为所有支持向量xj的集合。
SMO算法流程
输入m个样本，其中x为n维特征向量。y为二元输出，值为1或者-1.
- 取
, k = 0个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 选取
、个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 求出
个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 利用线性关系求出
个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 求出
和Ei个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 通过KKT检查是否满足终止：
个人总结 ：SVM 与 拉格朗日函数、对偶问题 和 KKT条件 以及 SMO算法 - 若满足则停止，否则返回步骤2