如题所述
目标函数: , 引入Lagrange算子:
目标函数:
约束条件:
根据约束条件和目标函数的类型分为3类:
KKT条件指在满足某些规则条件下, 非线性规划 问题能有最优解的 充要条件 , 是广义拉格朗日乘数的重要成果
一般优化问题(含等式和不等式约束约束):
引入Lagrange算子 :
KKT条件指上述问题的最优点 必须满足:
(1) 约束条件满足:
(2)
即,
最优点 处, 必须是 和 的 线性组合
引入拉格朗日算子可以求出极值的原因 :
(3) 且
不等式约束一直是优化问题中的难题，求解对偶问题可以将支持向量机原问题约束中的不等式约束转化为等式约束；
支持向量机中用到了高维映射，但是映射函数的具体形式几乎完全不可确定，而求解对偶问题之后，可以使用核函数来解决这个问题。
并不一定要用拉格朗日对偶。要注意用拉格朗日对偶并没有改变最优解，而是改变了算法复杂度：
在原问题下，求解算法的复杂度与样本维度（等于权值w的维度）有关；
而在对偶问题下，求解算法的复杂度与样本数量（等于拉格朗日算子a的数量）有关。
因此，
支持向量机实现非线性的方法的数学本质是升维，升维升到无穷维则无法表达w, 所以还是使用拉格朗日对偶方法更好一点。准确的说，可以用一些优化算法直接求最小间距，但是，升维的时候核要是正定的，且升维可数，而且不是很大的时候可以用。
任意一个带约束的优化均可写成:
将上述带约束的优化问题转化为无约束优化问题, 定义拉格朗日(Lagrangian)函数如下:
最大化Lagrangian, 令
z(x)满足原始约束条件的x, 其值等于 :
满足初始约束, 则 , 拉格朗日函数第三项被消去:
又因为 , 所以 的最大值在 处取得.
所以原始带约束优化问题等价于以下无约束优化问题:
等价于:
上述问题称为 primal problem
总结:
dual problem 只是将primal proble调换了min和max位置:
注意上式和 并不等价.
令:
上式中 为拉格朗日对偶函数(Lagrange dual function), 是primal function的一个下界.
即, 若将primal proble的最小值记为 , 则对于所有的 , 有:
证明:
对所有满足约束条件的x, 总有:
因此
假设 在 处取得极值, 则
代入上式:
于是
这样, 的上界是 ,于是:
是primal problem的 最大下界 !
记dual problem 的最优值为 , 得到:
该性质称为weak duality, 对所有的优化问题都成立.
此外,
称为duality gap.
基于weak duality的重要结论:
当
成立时,称为strong duality.
严格满足约束条件的点x, 指 严格到 , 即存在x满足:
原始问题是convex且满足slater条件,则strong duality成立:
特例: 对某些 非convex optimization,strong duality也成立
条件(2)中若 必有 , 反之, 若 可得 , 此条件在SVM中用来证明非支持向量 对应的系数
complementary slacknes 加上其他约束条件即为KKT条件:
通过dual problem可求primal problem的解:
