ADMM

https://joegaotao.github.io/2014/02/11/%E5%88%86%E5%B8%83%E5%BC%8F%E8%AE%A1%E7%AE%97%E7%BB%9F%E8%AE%A1%E5%AD%A6%E4%B9%A0%E4%B8%8Eadmm%E7%AE%97%E6%B3%95/

http://joegaotao.github.io/cn/2014/02/admm

1.对偶上升(dual_ascent)

• 对于凸函数的优化问题，对偶上升法核心思想就是引入一个对偶变量，然后利用交替优化的思路，使得两者同时达到optimal。
• 一个凸函数的对偶函数其实就是原凸函数的一个下界，因此可以证明一个较好的性质：在强对偶性假设下，即最小化原凸函数（primal）等价于最大化对偶函数（dual），两者会同时达到optimal。这种转化可以将原来很多的参数约束条件变得少了很多，以利于做优化。

* 在强对偶性的假设下，primal和dual问题同时达到最优

• 若对偶函数g(y)可导，便可以利用梯度上升法，交替更新参数，使得同时收敛到最优

2. 对偶分解

• 虽然dual ascent方法有缺陷，要求有些严格，但是他有一个非常好的性质，当目标函数f是可分的（separable）时候（参数抑或feature可分），整个问题可以拆解成多个子参数问题，分块优化后汇集起来整体更新。这样非常有利于并行化处理

$\begin{array}{lc} \min & f(x) = \sum\limits^N_{i = 1} f_i(x_i), \ \ \ \ \ x_i \in \mathbf{R}^{ni}, x \in \mathbf{R}^n \newline s.t. & Ax = \sum\limits^N_{i = 1} A_i x_i = b, \quad \text{(对 A A矩阵按列切分开)} \newline \end{array}$

$$\Longrightarrow L(x, y) = \sum\limits^N_{i = 1}L_i(x_i, y) = \sum\limits^N_{i = 1}(f_i(x_i) + y^TA_ix_i - \frac{1}{N}y^Tb)$$

• 因此可以看到其实下面在迭代优化时， x-minimization步即可以拆分为多个子问题的并行优化，对偶变量更新不变这对于feature特别多时还是很有用的。

3. 增广lagrangians函数

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。