ADMM and Large Scale Regression

摘要：	简单的阐述ADMM的算法原理，并且结合具体的场景给出一些代码实现。

预备知识

共轭函数，凸优化，对偶函数，对偶问题

首先，以等价约束的凸优化问题为例：

$\text{minimize} \; f(x) \\\\ \text{subject to} \; Ax = b$

f(x)是凸函数, x是N维变量

该问题的拉格朗日问题是：

$L(x,y) = f(x) + y^t(Ax-b)$

对偶函数： $$ g(y) = \inf_{x}{L(x,y)} = -f^\star(-A^Ty)-b^Ty $$

y是对偶变量，$f^\star$是f的凸共轭函数

对偶问题

$\text{maximize}\; g(y)$

ADMM的方法：先确定y，然后根据y得到x;交换顺序，确定x，计算y

$x^{k+1} = argminL(x,y^k) \\ y^{k+1} = y^k + \alpha^k (Ax^{k+1} - b)$