ADMM

简介

• 原问题

$$\begin{array}{ll}{\min } & {f(x)+g(z)} \\ {\text { s.t }} & {A x+B z=c}\end{array}$$

• $p^*$为原始优化问题的最优值

  $p^{*}=i n f\{f(x)+g(z) | A x+B z=c\}$

• 增广拉格朗日形式：

  $L_{\rho}(x, z, \lambda)=f(x)+g(z)+\lambda^{T}(A x+B z-c)+(\rho / 2)|A x+B z-c|_{2}^{2}$

• 迭代

$$\begin{array}{l}{ x^{k+1}:=\underset{x}{\operatorname{argmin}} L_{\rho}\left(x, z^{k}, \lambda^{k}\right)} \\ {z^{k+1}:=\underset{z}{\operatorname{argmin}} L_{\rho}\left(x^{k+1}, z, \lambda^{k}\right)} \\ {\lambda^{k+1}:=\lambda^{k}+\rho\left(A x^{k+1}+B z^{k+1}-c\right)} \end{array}$$

ADMM的简化

• 残差：$r=A x+B z-c$
• scaled处理：

$$\begin{aligned} \lambda^{T}(A x+B z-c)+(\rho / 2)\|A x+B z-c\|_{2}^{2} &= \lambda^{T} r+(\rho / 2)\|r\|_{2}^{2}\\ &=(\rho / 2)\|r+(1 / \rho) y\|_{2}^{2}-(1 / 2 \rho)\|\lambda\|_{2}^{2} \\ &=(\rho / 2)\|r+u\|_{2}^{2}-(\rho / 2)\|u\|_{2}^{2} \end{aligned}$$

• $u=(1 / \rho) \lambda$，$u$称为scaled对偶变量
• 迭代

$$\begin{array}{l}{x^{k+1}:=\underset{x}{\operatorname{argmin}}\left(f(x)+(\rho / 2)\left\|A x+B z^{k}-c+u^{k}\right\|_{2}^{2}\right)} \\ {z^{k+1}:=\underset{z}{\operatorname{argmin}}\left(g(z)+(\rho / 2)\left\|A x^{k+1}+B z-c+u^{k}\right\|_{2}^{2}\right)} \\ {u^{k+1}:=u^{k}+A x^{k+1}+B z^{k+1}-c}\end{array}$$

ADMM的两个假设

• The (extended-real-valued) functions $f$: $\mathbf{R}^{n} \rightarrow \mathbf{R} \cup \{+\infty\}$ and $g$: $\mathbf{R}^{m} \rightarrow \mathbf{R} \cup\{+\infty\}$are closed, proper, and convex.
• The unaugmented Lagrangian $L_0$ has a saddle point $\left(x^{\star}, z^{\star}, \lambda^{\star}\right)$, $L_{0}\left(x^{\star}, z^{\star}, \lambda\right) \leq L_{0}\left(x^{\star}, z^{\star}, \lambda^{\star}\right) \leq L_{0}\left(x, z, \lambda^{\star}\right)$

停止准则

$$\begin{aligned} \epsilon^{\mathrm{pri}} &=\sqrt{p} \epsilon^{\mathrm{abs}}+\epsilon^{\mathrm{rel}} \max \left\{\left\|A x^{k}\right\|_{2},\left\|B z^{k}\right\|_{2},\|c\|_{2}\right\} \\ \epsilon^{\mathrm{dual}} &=\sqrt{n} \epsilon^{\mathrm{abs}}+\epsilon^{\mathrm{rel}}\left\|A^{T} y^{k}\right\|_{2} \end{aligned}$$