前言

這篇博客旨在介紹下最近在通信中經常用到的 ADMM 算法。 算法的全稱為 Alternating Direction Method of Multipliers, 中文直譯為： 交替方向乘子法。 本文的參考文獻為 Boyd 的經典著作： Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers， 事實上從名字就可以看出， 正如Boyd在摘要中所提到的， ADMM算法的優勢是可以將問題進行分布式優化，從而解決大規模計算問題。 然而在通信的應用中， 更多時候則是把一個多變量問題進行解耦，通過對每個單變量進行迭代求解來簡化問題本身。

對偶上升法與增廣拉格朗日乘數法

在介紹ADMM算法前， 我想先簡要介紹下對偶上升法與增廣拉格朗日乘數法， 兩者可以視為ADMM算法的前身或簡化版本， 而ADMM算法則又可視為兩者的結合體。

對偶上升法

對偶上升法，在之前的博客中有更為詳細的介紹， 對偶上升法 (Dual Ascent)。 這里我們只簡述其核心。 對于一個等式約束的凸優化問題如下：
$$\begin{array}{ll}\mathrm{minimize}& f(x)\\ \text{?subject?to?}& Ax=b,\end{array}$$
其中， $f(x)$為凸函數。我們可以通過拉格朗日乘子法將限制條件寫入目標函數中， 從而得到：
$$L(x,y)=f(x)+y^T(Ax?b)$$

那么，其對偶函數為：
$$g(y)=\underset{x}{\inf }L(x,y)$$
相應的對偶問題為：
$$\text{?maximize?}g(y)$$
對偶上升法表示， 通過如下的步驟：
$$\begin{array}{rl}& x^{k+1}:=\underset{x}{\mathrm{argmin}}L\left(x,y^k\right)\\ & y^{k+1}:=y^k+{\alpha }^k\left(A{x}^{k+1}?b\right),\end{array}$$
等價于求解對偶問題。這里 ${\alpha }_k$ 為步長。 而從步驟的形式上看， 就是簡單的先固定 $y$ 優化 $x$， 再固定 $x$ 優化 $y$。 但是是可以保證收斂的。 可以看到， 對偶上升法的優點是可以將多變量解耦開來。 值得一提的是， 迎合ADMM類所期望的分布式優化的特點， 對偶上升法也可以通過將變量分解為多個維度較低的變量再進行并行求解， 此時優化步驟變為：
$$\begin{array}{rl}{x}_i^{k+1}& :=\underset{x_i}{\mathrm{argmin}}{L}_i\left(x_i,y^k\right)\\ y^{k+1}& :=y^k+{\alpha }^k\left(A{x}^{k+1}?b\right)\end{array}$$
即將原高維變量 $x$ 拆分成了多個 低維變量 $x_i$ 進行依次優化。 在多個變量之間交替優化，迭代求解， 可以說是ADMM類算法貫徹的準則。

增廣拉格朗日乘數法

增廣拉格朗日乘數法可以看做是對偶上升法的進階， 但也不完全是。 他將拉格朗日函數寫為：
$$L_{\rho }(x,y)=f(x)+y^T(Ax?b)+(\rho /2)\Vert Ax?b{\Vert }_2^2$$
可以看到， 相比于普通的拉格朗日函數（比如剛剛對偶上升法中所給出的）， 他多了第三項，其中 $\rho$ 為懲罰參數。 顯然當 $x$ 為最優值時， $Ax?b=0$， 因此這兩個拉格朗日函數其實是相等的。 但是在迭代過程中， 有了這一項懲罰項后， 無論 $f(x)$ 本身是否強凸， 由于增加了一個強凸懲罰項， 因此這個增廣拉格朗日函數可視作$x$的強凸函數， 從而對算法的收斂更有幫助。 增廣拉格朗日乘數法的步驟為：
$$\begin{array}{rl}{x}^{k+1}& :=\underset{x}{\mathrm{argmin}}{L}_{\rho }\left(x,y^k\right)\\ y^{k+1}& :=y^k+\rho \left(A{x}^{k+1}?b\right)\end{array}$$
注意到，這幾乎和對偶上升的步驟完全一致。 但除了目標函數的改變之外（增加了懲罰項）， 另一個變化是步長默認為是懲罰參數 $\rho$。 這樣的選取是有其道理的，具體可以參見boyd的書， 是從收斂性的角度進行了考慮。 總之， 增廣拉格朗日乘數法改善了收斂性能， 但同時由于增加了這一項， 因此無法拆分為多個$x_i$進行分布式并行求解。

ADMM算法

結合了對偶上升法的 可拆解性 和 增廣拉格朗日乘數法的 易收斂性， ADMM算法呼之欲出。 我們將優化變量拆分為獨立的兩部分， $x$ 和 $z$， 那么問題可以改寫為：
$$\begin{array}{ll}\mathrm{minimize}& f(x)+g(z)\\ \text{?subject?to?}& Ax+Bz=c\end{array}$$
這里 $f$ 和 $g$ 都是凸函數。 此時， 其對應的增廣拉格朗日函數為：
$$L_{\rho }(x,z,y)=f(x)+g(z)+y^T(Ax+Bz?c)+(\rho /2)\Vert Ax+Bz?c{\Vert }_2^2$$
而其優化步驟為：
$$\begin{array}{rl}{x}^{k+1}:=& \underset{x}{\mathrm{argmin}}{L}_{\rho }\left(x,z^k,y^k\right)\\ z^{k+1}:=& \mathrm{argmin}{L}_{\rho }\left(x^{k+1},z,y^k\right)\\ y^{k+1}:=& y^k+\rho \left(A{x}^{k+1}+B{z}^{k+1}?c\right)\end{array}$$
可以清晰的看到， 這正是對偶上升法與增廣拉格朗日乘數法的結合體。 理論上可以進一步把優化變量拆分為更多的block， 如 $x$, $z$, $z_1$, $?$。 如果我們將原問題的最優解表示為：
$$p^{?}=\inf \{f(x)+g(z)\mid Ax+Bz=c\}$$
那么ADMM算法在滿足很基本的假設的情況下， 可以確保：
$$f\left(x^k\right)+g\left(z^k\right)\to p^{?}\text{?as?}k\to \infty$$
這也體現了算法的收斂性，即最終得到全局最優解。 這在boyd的著作中給出了詳盡的證明。

ADMM算法的Scaled Form

ADMM算法還有另一種常見形式。 如果我們令 $r=Ax+Bz?c$ 來代表當前值與實際約束間的殘差， 那么我們有：
$$\begin{array}{rl}{y}^{T}r+(\rho /2)\Vert r{\Vert }_2^2& =(\rho /2)\Vert r+(1/\rho )y{\Vert }_2^2?(1/2\rho )\Vert y{\Vert }_2^2\\ & =(\rho /2)\Vert r+u{\Vert }_2^2?(\rho /2)\Vert u{\Vert }_2^2\end{array}$$
其中， $u=(1/\rho )y$ 代表被 scaled 后的 對偶變量， 這也是 所謂 scaled form的由來。 由此， ADMM步驟可以被簡化寫為：

$$\begin{array}{rl}{x}^{k+1}& :=\underset{x}{\mathrm{argmin}}\left(f(x)+(\rho /2){\Vert Ax+B{z}^k?c+u^k\Vert }_2^2\right)\\ z^{k+1}& :=\underset{z}{\mathrm{argmin}}\left(g(z)+(\rho /2){\Vert A{x}^{k+1}+Bz?c+u^k\Vert }_2^2\right)\\ u^{k+1}& :=u^k+A{x}^{k+1}+B{z}^{k+1}?c.\end{array}$$
可以看到一次項已經被寫進$\Vert {\Vert }^2$中了。

ADMM算法的收斂性

總結

以上是生活随笔為你收集整理的ADMM算法简介的全部內容，希望文章能夠幫你解決所遇到的問題。

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