交替方向乘子法（ADMM）演算法的流程和原理是怎樣的？

12-31

ADMM演算法是機器學習中比較廣泛使用的約束問題最優化方法，它是ALM演算法的一種延伸，只不過將無約束優化的部分用塊坐標下降法（block coordinate descent，或叫做 alternating minimization）來分別優化。其中的原理可以參考大牛S.Boyd的文獻「Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers」。產生這種方法主要是為了彌補二次懲罰的缺點。在一些問題當中，用二次懲罰來近似約束問題在最優點附近需要懲罰項的係數趨近於無窮，而這種要求會使得海森矩陣很大，因此近似的目標函數很不穩定。為了解決這個問題，引入了線性逼近的部分，通過線性項係數不斷的接近最優解（對偶上升），使得在二次懲罰項的係數很小的情況下，也能得到滿足要求精度的解。ADMM目前是比較成熟，比較受歡迎的約束問題最優化通用框架。詳細的討論樓主可以參考大牛的文獻，希望能幫到你。

@Richard Wei 寫得很不錯，我再來簡單說一下 ADMM 在分散式統計學習方面的應用。

我也是最近看了 Boyd 2011 年的那篇文章，之後自己做了一些片面的總結（只針對分散式統計學習問題）：

交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）是一種求解優化問題的計算框架, 適用於求解分散式凸優化問題，特別是統計學習問題。 ADMM 通過分解協調（Decomposition-Coordination）過程，將大的全局問題分解為多個較小、較容易求解的局部子問題，並通過協調子問題的解而得到大的全局問題的解。

ADMM 最早分別由 Glowinski Marrocco 及 Gabay Mercier 於 1975 年和 1976 年提出，並被 Boyd 等人於 2011 年重新綜述並證明其適用於大規模分散式優化問題。由於 ADMM 的提出早於大規模分散式計算系統和大規模優化問題的出現，所以在 2011 年以前，這種方法並不廣為人知。

完整的總結在我的博客上，此文可以作為 ADMM 的快速入門：

用ADMM實現統計學習問題的分散式計算 · MullOver

因為使用ADMM比較多，所以不妨說一下自己的理解。

歸根結底，就是解決 loss function + regulation.

當regulation為L1範數的時候沒有合適的演算法解決這個凸優化問題。

原來boyd的老師提出過最小角方法方法解決這個問題，但是因為方法不直觀並且難以操作。所以，這些大牛們一直在尋找一種比較合適的演算法解決這個問題。直至2011年左右提出比較通用和直觀的ADMM演算法。

對於ADMM演算法，其實是一種交替求解的方式。不斷的將問題分解，進而逐個解決。其中在解決的過程中，發現將惱人的L1 Norm中的變數進行替換，從而形成 L1+L2 norm的形式比較容易求解（proximal algorithm），所以挺好的。而如果我們直接進行Loss function + regulation，求解的話，很難得到解。

所以從上面我們可以發現，變數替換成為解決問題的關鍵。而逐次求解，使問題得到解決。

其實只要將最簡單的L1 norm的形式理解。對於各種proximal直接查詢相關解就可以了。~

查找楊健老師，看到ADMM，順藤摸瓜到這裡，學習下！

占坑，如果我能把這個問題講的通俗易懂的話，我就能心滿意足一陣子啦~