对偶理论的补充
http://blog.csdn.net/timingspace/article/details/50966105
* 对偶（duality）是优化中的一个很重要的一点，以对偶问题的特性为根本的KKT条件，在很多优化问题的求解上行之有效
1 什么是对偶？
- 对偶问题，就是将原问题（primal problem）转化为对偶问题（dual problem）然后在进行求解的方法。
* 通过对偶函数后，转化为凸优化问题，但是关键在于对偶问题和原问题是否是强对偶(就是说，是否最优值相等)
2 原问题
- 如果n,m都是0，优化问题为无约束优化问题（无优化问题的对偶问题就是自己）
- 如果n=0，则为等式约束问题。
3 如何得到对偶问题
* 首先写出拉格朗日函数
* 拉格朗日函数逐点对x求下确界得到对偶函数
* 对偶问题是凹的
- 那么g(u,v)为很多个仿射函数的逐点取最小值，而这样得到的函数一定是凹的
4 对偶问题的意义
这便是为什么要有对偶算法这个算法的一个原因，因为对偶问题都是凸问题（其实是凹问题，凹问题加个负号就是凸问题了），而凸优化问题在求解上会简单很多。一般而言，如果可以把一个问题表述成凸优化问题，那么就相当于基本解决了这个问题。
5 原问题和对偶问题的关系
* 原问题的最小值大于或等于对偶问题的最大值(弱对偶条件)
* 原问题最小值和对偶问题的最大值之差 叫 duality gap
* 强对偶的条件
- 如果满足原问题是凸优化问题，并且至少存在绝对一个绝对可行点（什么叫绝对可行点，就是一个可以让所有不等式约束都不取等号的可行点），那么就具有强对偶性。这个条件就是传说中的Slater’s condition。
* 等式约束的强对偶条件
由此可知一个只有等式约束的凸优化问题和其对偶问题一定具有强对偶性，因为根本就没有不等式约束（推论）。
* 既然只有强对偶条件时才能保证对偶问题的最大值是原问题的最小值，那对偶法还有用吗？
6. KKT条件（对偶性质的应用）
7. KKT的补充
* 对偶的意义
无论原问题是不是凸优化问题，都可以将原问题转化为凸优化问题来求解。
一个非凸函数的极小化不能转化为另一个凸函数的极小化；只能求出带有间隔的最优值下界
* 对偶结论
若原始约束目标函数不是凸函数，但是不等式约束均是凸函数，且等式约束均是仿射函数，则Lagrange目标函数满足KKT的店和， 一般不会是原始最优化点和对偶最优化点；对偶问题的最优解不是原问题的最优解
上述，若原始约束目标函数是凸函数，则满足KKT条件的店是原问题的最优解