ADMM
http://joegaotao.github.io/cn/2014/02/admm
1.对偶上升(dual_ascent)
- 对于凸函数的优化问题，对偶上升法核心思想就是引入一个对偶变量，然后利用交替优化的思路，使得两者同时达到optimal。
- 一个凸函数的对偶函数其实就是原凸函数的一个下界，因此可以证明一个较好的性质：在强对偶性假设下，即最小化原凸函数（primal）等价于最大化对偶函数（dual），两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多，以利于做优化。
* 在强对偶性的假设下，primal和dual问题同时达到最优
- 若对偶函数g(y)可导，便可以利用梯度上升法，交替更新参数，使得同时收敛到最优
* x-最小化步
* 对偶变量更新, 是步长
* g(x)不可微，可以使用subgradient代替，但是使用效果不好，一般不直接使用
2. 对偶分解
- 虽然dual ascent方法有缺陷，要求有些严格，但是他有一个非常好的性质，当目标函数f是可分的（separable）时候（参数抑或feature可分），整个问题可以拆解成多个子参数问题，分块优化后汇集起来整体更新。这样非常有利于并行化处理
- 因此可以看到其实下面在迭代优化时， x-minimization步即可以拆分为多个子问题的并行优化，对偶变量更新不变这对于feature特别多时还是很有用的。
3. 增高lagrangians函数
- 从上面可以看到dual ascent方法对于目标函数要求比较苛刻，为了放松假设条件，同时比较好优化，于是就有了Augmented Lagrangians方法，目的就是放松对于f(x)f(x)严格凸的假设和其他一些条件，同时还能使得算法更加稳健。
从上面可以看到该问题等价于最初的问题，因为只要是可行解对目标函数就没有影响。
但是加了后面的(/2)惩罚项的好处是对偶函数在一般条件下可导
- 虽然Augmented Lagrangians方法有优势，但也破坏了dual ascent方法的利用分解参数来并行的优势。当ff是separable时，对于Augmented Lagrangians却是not separable的（因为平方项写成矩阵形式无法用之前那种分块形式），因此在x−minx−min步时候无法并行优化多个参数xixi。如何改进，继续下面的议题就可以慢慢发现改进思想的来源。
4. ADMM
* 增广拉格朗日算法的扩展
http://blog.csdn.net/shanglianlm/article/details/46808793
* 缩放形式（scaled_form）
* 优化条件和停止条件
5. L1正则化
http://blog.csdn.net/shanglianlm/article/details/46805675
* lasso是L1正则化的特例： L1 regularized linear regression。
