ADMM

什么是ADMM

Alternating Direction Method of Multipliers (ADMM) 是一种求解凸优化问题的迭代算法，它将原问题分解为两个子问题，然后通过交替的方式求解这两个子问题。ADMM算法的优点是可以很好的处理带有约束的优化问题，比如线性约束、非负约束等。

ADMM用于求解如下最优化问题： $$ \begin{align*} \min_{{\bf x}, {\bf z}} & \, f({\bf x}) + g({\bf z}) \\ \text{s.t.} & \, {\bf A}{\bf x} + {\bf B}{\bf z} = {\bf c} \end{align*} $$

其中： $x \in \mathbb{R}^p, \quad z \in \mathbb{R}^q, \quad A \in \mathbb{R}^{m \times p}, \quad B \in \mathbb{R}^{m \times q}, \quad c \in \mathbb{R}^k;$ $f: \mathbb{R}^p \to \mathbb{R}, \quad g: \mathbb{R}^q \to \mathbb{R}.$

这一优化问题的目标函数包含两组可分离自变量（\(x,z\)），且存在线性等式约束。

对于这一优化问题，ADMM算法首先对目标函数进行增广，将原始优化问题转化为：

$$ \begin{align*} \min_{{\bf x}, {\bf z}} Q_{\rho}({\bf x}, {\bf z}) &= f({\bf x}) + g({\bf z}) + \frac{\rho}{2} \|{\bf A}{\bf x} + {\bf B}{\bf z} - {\bf c}\|_2^2 \\ \text{s.t.} \, & {\bf A}{\bf x} + {\bf B}{\bf z} = {\bf c} \end{align*} $$

\(\rho\) 通常表示惩罚参数（penalty parameter）。
进一步写出该问题的拉格朗日函数式子：

$$ L_\rho (\mathbf{x}, \mathbf{z}, \boldsymbol{\lambda}) = Q_\rho (\mathbf{x}, \mathbf{z}) + \boldsymbol{\lambda}^\top (\mathbf{Ax} + \mathbf{Bz} - \mathbf{c}) $$

\[ = f(\mathbf{x}) + g(\mathbf{z}) + \frac{\rho}{2} \| \mathbf{Ax} + \mathbf{Bz} - \mathbf{c} \|_2^2 + \boldsymbol{\lambda}^\top (\mathbf{Ax} + \mathbf{Bz} - \mathbf{c}) \]

其中 \(\lambda \in \mathbb{R}^k\) 是一个向量，为拉格朗日乘子。

接着使用如下更新步骤进行迭代（第 \(k\) 步更新）直至收敛：

1. 更新 \(x : x^{(k)} = \arg \min_x L_\rho (x, z^{(k-1)}, \lambda^{(k-1)})\)
   
2. 更新 \(z : z^{(k)} = \arg \min_z L_\rho (x^{(k)}, z, \lambda^{(k-1)})\)
   
3. 更新 \(\lambda : \lambda^{(k)} = \lambda^{(k-1)} + \rho (\mathbf{A}_x^{(k)} + \mathbf{B}_z^{(k)} - \mathbf{c})\)