有了前面標準Lagrangian乘子法與對偶上升法和增廣Lagrangian法的基礎，理解ADMM就容易了很多。本文主要來自張賢達《矩陣分析與優化（第二版）》4.7.4節。

ADMM算法

ADMM認為，在統計學與機器學習中，經常會遇到大尺度的等式約束優化問題，即$x\in {\mathbb{R}}^n$的維數$n$很大。如果$x$可以分解為幾個子向量，即$x=(x_1,?,x_r)$，其目標函數也可以分解為：
$$\begin{gathered} f(x)=\sum _{i=1}^r{f}_i(x) \\ {x}_i\in {\mathbb{R}}^{n_i},\sum _{i=1}^r{n}_i=n \end{gathered}$$
則大尺度的優化問題可以轉化為分布式優化問題。相應的，等式約束矩陣$Ax=b$也分塊為：
$$A=[A_1,?,A_r],Ax=\sum _{i=1}^r{A}_i{x}_i=b$$
于是增廣Lagrangian目標函數$L_{\rho }(x,\lambda )$可以寫作：
$$L_{\rho }(x,\lambda )=\sum _{i=1}^r(f_i(x_i)+{\lambda }^T{A}_i{x}_i)?{\lambda }^{T}b+\frac{\rho }{2}\Vert \sum _{i=1}^r(A_i{x}_i)?b{\Vert }_2^2$$
所取的罰函數與增廣Lagrangian乘子法中的仍相同。再采用對偶上升法，即可得到能進行并行運算的分散算法：
$$\begin{gathered} x_i^{k+1}=\underset{x_i\in {\mathbb{R}}^{n_i}}{\mathrm{argmin}}{L}_i(x_i,{\lambda }_k),i=1,?,r \\ {\lambda }_{k+1}={\lambda }_k+{\rho }_k(\sum _{i=1}^r{A}_i{x}_i^{k+1}?b) \end{gathered}$$
這里的$x_i$是可以獨立更新的。由于$x_i$以一種交替的或序貫的方式進行更新，所以稱為“交替方向”乘子法（ADMM算法）。

舉個$r=2$的例子

$r=2$，則目標函數為：
$$\begin{gathered} \min f(x)+g(z) \\ s.t.Ax+Bz=c \end{gathered}$$
上式中，$x\in {\mathbb{R}}^n,z\in {\mathbb{R}}^m,A\in {\mathbb{R}}^{p\times n},B\in {\mathbb{R}}^{p\times m},c\in {\mathbb{R}}^p$。則增廣Lagrangian目標函數為：
$$\begin{gathered} L_{\rho }(x,z,\lambda )=f(x)+g(z)+{\lambda }^T(Ax+Bz?c)+\frac{\rho }{2}\Vert Ax+Bz?c{\Vert }_2^2 \\ \text{\hspace{1em}(1)} \end{gathered}$$
上式的交替方向乘子法的更新公式為：
$$\begin{gathered} x_{k+1}=\underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}{L}_{\rho }(x,z_k,{\lambda }_k) \\ {z}_{k+1}=\underset{z\in {\mathbb{R}}^m}{\mathrm{argmin}}{L}_{\rho }(x_{k+1},z,{\lambda }_k) \\ {\lambda }_{k+1}={\lambda }_k+{\rho }_k(A{x}_{k+1}+B{z}_{k+1}?c) \end{gathered}$$

誤差分析與停止條件

公式$(1)$的最優化條件分為原始可行性：
$$Ax+Bz?c=0$$
和對偶可行性：
$$\begin{gathered} 0\in ?f(x)+A^T\lambda +\rho A^T(Ax+Bz?c)=?f(x)+A^T\lambda \\ 0\in ?f(x)+B^T\lambda +\rho B^T(Ax+Bz?c)=?g(z)+B^T\lambda \\ \text{\hspace{1em}(2)} \end{gathered}$$
根據我的企業級理解，這原始和對偶可行性關系分別是等式約束成立和偏導為0，是從KKT條件來的，都是必要條件。不過書里沒有明確指出是或者不是。
關于推導，這里用的是$0\in$而不是$0=$，這是什么企業級邏輯我沒弄懂，不過我覺得不影響理解，意思差不多。書上這里求導有問題，疑似紕漏，我改成了公式$(1)$的正確的求導結果，這樣也和后文更對的上。要記得，公式$(1)$中向量$Ax+Bz?c$二范數平方的一階導等于向量的二倍，再乘一個系數$A^T$，就可以得到這個結果。求導法則可以參考我的這篇總結。再加上$Ax+Bz?c=0$的約束，就能推導下來了。

在迭代的過程中，原始可行性不可能完全滿足，設其誤差為：
$$r_k=A{x}_k+B{z}_k?c$$
稱為第$k$次迭代的原始殘差（向量），這樣Lagrangian乘子向量的更新可以用這個殘差重寫為：
$${\lambda }_{k+1}={\lambda }_k+{\rho }_k{r}_{k+1}$$
同樣，對偶可行性也不會完全滿足：
$$\begin{gathered} 0\in ?f(x_{k+1})+A^T{\lambda }_k+\rho A^T(A{x}_{k+1}+B{z}_k?c) \\ =?f(x_{k+1})+A^T[{\lambda }_k+\rho (A{x}_{k+1}+B{z}_{k+1}?c)+\rho B(z_k?z_{k+1})] \\ =?f(x_{k+1})+A^T[{\lambda }_k+\rho r_{k+1}+\rho B(z_k?z_{k+1})] \\ =?f(x_{k+1})+A^T{\lambda }_{k+1}+\rho A^{T}B(z_k?z_{k+1}) \end{gathered}$$
注意，由于書上公式$(2)$求導是錯的，所以這一步更別扭，怎么看都不對勁，這里我也改成了我認為的正確的推導形式。
對照公式$(2)$中的第一個式子可知對偶殘差為：
$$s_{k+1}=\rho A^{T}B(z_k?z_{k+1})$$
交替方向乘子法的停止條件就是兩個殘差都小于閾值：
$$\Vert r_{k+1}{\Vert }_2\le {\epsilon }_{pri}and\Vert s_{k+1}\Vert \le {\epsilon }_{dual}$$

縮放形式的ADMM

令$v=(1/\rho )\lambda$為經過$1/\rho$縮放的Lagrangian乘子向量，則更新公式變為：
$$\begin{gathered} x_{k+1}=\underset{x\in {\mathbb{R}}^n}{\mathrm{argmin}}{L}_{\rho }(x,z_k,v_k) \\ {z}_{k+1}=\underset{z\in {\mathbb{R}}^m}{\mathrm{argmin}}{L}_{\rho }(x_{k+1},z,v_k) \\ {v}_{k+1}=v_k+A{x}_{k+1}+B{z}_{k+1}?c=v_k+r_{k+1} \end{gathered}$$
其第$k$次迭代的殘差$r_k$為：
$$r_k=A{x}_k+B{z}_k?c=v_0+\sum _{i=1}^k{r}_i$$
即，第$k$次迭代的縮放對偶向量是所有$k$次迭代的原始殘差之和。這種方法稱為有縮放的交替方向乘子法。

最后，個人認為，不論是對偶上升法，增廣Lagrangian乘子法，還是ADMM算法，核心思想都相似，而且具體使用時都要與其他最優化方法結合，因為$\mathrm{argmin}L(x,z,\lambda )$的求解是還需要別的方法的，停止條件需要根據使用環境具體再去確定。

總結

以上是生活随笔為你收集整理的ADMM算法（交替方向乘子法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。