对偶理论碎碎念

http://www.hanlongfei.com/convex/2015/11/05/duality/

1 对偶问题的意义

* 两个重要性质

2 讨论

* 原问题：特别是非凸问题的对偶形式，经常是难以求解的

• 是不是我们可以获得任意原问题的对偶问题，这样就可以采用之前提到过的下降算法等来求解该凸优化问题？
• 答案：虽然无论原问题为何种形式，其对偶问题永远是凸优化问题，但是这里的关键并不是说不能用下降算法求解，而难点在于非凸问题一般无法获得或者较难获得其对偶问题的表达式$g(u,v)$，这就限制了我们对于非凸优化问题的求解方法。

* 对于对偶问题，弱对偶性永远成立

* 如何得到强对偶的性质？

3. 强对偶成立的条件

* Slater’s condition

4. SVM的例子

5. KKT条件

• 关于原问题的对偶问题，首先我们引入拉格朗日函数L(x,u,v)将有约束的优化问题转换为无约束的优化问题，然后对原问题的参数求导，获得使拉格朗日函数最小的拉格朗日对偶函数g(u,v)，最后使得对偶函数最大的问题则成为原问题的对偶问题。

* KKT的本质：强对偶性的条件

• 满足强对偶性，就可以通过求解对偶问题的解来间接地获得原问题的解。

* slater条件

• Slater’s Condition只是满足强对偶性的一个充分条件，但不是必要条件，即原问题的对偶问题具有强对偶性并不一定满足Slater’s Condition。

• 满足slater的具有强对偶性，但是具有强对偶性的不一定满足slater条件

* KKT条件：对于一般优化

KKT条件在SVM问题中的应用

6. KKT条件的几何解释

http://blog.csdn.net/ecnu18918079120/article/details/69961590 https://zhuanlan.zhihu.com/p/29677416 https://zhuanlan.zhihu.com/p/28859384

http://blog.csdn.net/Mr_KkTian/article/details/53750424

三类等式约束

* 等式约束和不等式约束转换为无约束优化问题

等式约束：以二次情况为例

* 目标函数表示为等高线

* 问题转换为求等高线和约束线的相切点

* lagrange法（等式情况）

• f(x,y)是原问题，
• g(x,y)=c是等式条件约束

$L(x,y) = f(x,y)+\lambda(g(x,y)-c)$

则：$\nabla L=\nabla (f+\lambda (g-c))$

$=\nabla f+ \lambda \nabla g =0$

$\nabla f= - \lambda \nabla g$

• 切点处，法线相互垂直

不等式约束情况

* 可行解：只能在 $g(x)<0$ 或者 g(x)=0的区域里面取得

* 落在 $g(x)<0$ 的区域内，此时直接极小化 f(x)

* 当可行解 x 落在 g(x)=0,此时等价于等式约束优化问题.

* 同时需要满足等式约束的条件

$\nabla_x f(x)= - \lambda \nabla_x g(x)$

* 对于不等式约束，只要满足一定的条件，依然可以使用拉格朗日乘子法解决，这里的条件便是 KKT 条件

* 满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。