关于KKT条件下的最优化问题
其中g是不等式约束，h是等式约束，那么KKT条件就是函数的最优值，它必定满足下面条件：
?难点：第三个式子不好理解，第三个条件为互补松弛条件。
以最简单的最优化问题形式为例：
?假设
?那么对于该例子，使用拉格朗日乘数法进行转化并设g函数
转化为对偶问题
?
同时设p*的解为x*，d*的解为λ*和n*
那么，可将假设的解带入d*中进行如下推导：?
?
又由于约束条件
因此可得
?为0，可删去，
又因为一开始条件就有
可得：?
?又因为经过拉格朗日函数的转换，svm问题转化为对偶问题，具有强对偶性，因此根据对偶问题的定义
那么
?
图中的小于等于号只能取等于
因此可得结论
?
该条件就是互补松弛条件。
?smo算法
?在经过拉格朗日转化以及优化后最终得到的式子为：
?
为了求解上面含有这两个变量的目标优化问题，我们首先分析约束条件，所有的α1,α2α1,α2都要满足约束条件，然后在约束条件下求最小。
根据上面的约束条件α1y1+α2y2=?，0≤αi≤Ci=1，2α1y1+α2y2=?，0≤αi≤C，i=1,2，又由于y1,y2y1,y2均只能取值1或者-1, 这样α1,α2α1,α2在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说α1,α2α1,α2的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：
?
?????????由于α1,α2的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题
????????假设最终是α2的优化问题。由于我们采用的是启发式的迭代法，假设我们上一轮迭代得到的解是,
假设沿着约束方向α2未经剪辑的解是
,本轮迭代完成后的解为
,
未经剪辑是因为在进行求导后的a2应满足条件，若超出最高或低于最低应选择临界线处作为a2的值。
由于必须满足上图中的线段约束。假设L和H分别是上图中
，
所在的线段的边界。那么很显然有：??
L≤≤H
对于L和H，我们也有限制条件如果是上面左图中的情况，则
如果是上面右图中的情况，我们有：
假如我们通过求导得到的则最终的
应该为：
?之后只需要将目标函数对α2求偏导数求得
?具体求解步骤如下：
?最后得到的表达式：
再经过剪辑得到
再利用和
的线性关系，我们也可以得到新的
。?
由于对a1，a2进行了优化，因此需要重新计算阈值b，当0<<C时，有：
于是新的为：?
计算出E1为：
可以看到上面两个式子都有相同的
?
因此可以将用E1表示为：?
?最终的为
??
得到了后我们需要更新Ei
最终迭代将各个参数求得。?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?