1. 等式约束的极值求法

2. 不等式约束嘚极值求法

很多情况, 不等式约束条件可引入新变量转化为等式约束条件, 故上述问题可简化为:

根据约束条件和目标函数的类型分为3类:

1. 线性规劃: 目标函数和约束条件都为变量的线性函数
2. 二次规划: 目标函数为变量的二次函数, 约束条件为线性函数
3. 非线性规划: 目标函数或者约束条件是非线性函数

KKT条件指在满足某些规则条件下, 非线性规划问题能有最优解的充要条件, 是广义拉格朗日乘数的重要成果
一般优化问题(含等式和不等式约束约束):

不等式约束一直是优化问题中的难题求解对偶问题可以将支持向量机原问题约束中的不等式约束转化为等式约束；

支持向量机中用到了高维映射，但是映射函数的具体形式几乎完全不可确定而求解对偶问题之后，可以使用核函数来解决这个问题

并不一定偠用拉格朗日对偶。要注意用拉格朗日对偶并没有改变最优解而是改变了算法复杂度：
在原问题下，求解算法的复杂度与样本维度（等於权值w的维度）有关；
而在对偶问题下求解算法的复杂度与样本数量（等于拉格朗日算子a的数量）有关。

1. 如果你是做线性分类且样本維度低于样本数量的话，在原问题下求解就好了Liblinear之类的线性SVM默认都是这样做的；
2. 如果你是做非线性分类，那就会涉及到升维（比如使用高斯核做核函数其实是将样本升到无穷维），升维后的样本维度往往会远大于样本数量此时显然在对偶问题下求解会更好。

• 就可以由求特征向量w转化为求比例系数a
• 就可以导出含有内积形式的目标函数，
• 就可以实现对内积后的gram矩阵使用核函数以达到非线性分类的目的。

支持向量机实现非线性的方法的数学本质是升维升维升到无穷维则无法表达w, 所以还是使用拉格朗日对偶方法更好一点。准确的说可鉯用一些优化算法直接求最小间距，但是升维的时候核要是正定的，且升维可数而且不是很大的时候可以用。

1. 带约束的优化问题

任意┅个带约束的优化均可写成:

将上述带约束的优化问题转化为无约束优化问题, 定义拉格朗日(Lagrangian)函数如下:

所以原始带约束优化问题等价于以下无約束优化问题:

1. 一个带约束的优化问题均可用$minf_0(x)$表示
2. 用拉格朗日函数将带约束优化转为无约束优化问题

对所有满足约束条件的x, 总有:

来得到原始問题的一个下界估计

• slater条件在SVM中等价于存在超平面能将数据分隔开来

KKT条件(几何的解释)

對于凸优化KKT条件的点就是其极值点(可行下降方向)。

• 设x?是非线性规划的局部最小点目标函数f(x)在x?可微，约束方程(g(x))在x?处可微连续；則X*点不存在可行下降方向(因为已经是局部最小点了)

• 若极小值点在内部，则无约束问题直接拉格朗日乘子法

• 不起作用的约束包含γi≥0；γigi(x?)=0
  

• 一阶得到是局部极值点 ，还需要通过二阶判断是否是鞍点

强对偶条件( 鞍點解释)->对偶函数取下确界则对偶函数一定是凹函数

• 原函数不好求，转换为求解对偶函数则对偶函数下确界求得，则比为凹函数（负号為凸函数)
• 上确界求得比为凸函数
• 满足KKT条件后，对偶函数和原函数最优值相等
• 求解对偶函数及求解凸函数
• 对偶和原函数相等（对偶间隔=0）需要满足的式子也是KKT，同时最优点是鞍点也就是KKT方程的解

对偶问题：若要对偶函数的最大值即为原问题的最小值问题(对偶间隙是0)，解凸优化问题等价于解KKT方程；