最近研究二次判别分析（Quadratic Discriminant Analysis，QDA），發現運用到了交替方向乘數法（ADMM），就很迷。（關鍵是太菜）
很多部落客都是直接翻譯或者搬運的，搜羅且了解了很多相關知識，那就來個大總結及其一些自己的想法吧！
（内力有限，僅供學習交流）
确實很難，理論性很強，沒有虛的，閱讀完内容需要有“勇氣”！
ADMM
背景
咱們先來了解了解，ADMM到底是個什麼東西？
交替方向乘數法（Alternating Direction Method of Multipliers），從字面意思上了解，交替方向？是不是很迷？交替計算？交替求解？。。。難道是對偶問題？對偶求解？
先不管了，再看後半句，乘數法？咦~是不是感覺有點熟悉。
la.la.la…Lagrange乘數法？？？
（沒錯，就是Lagrange，直接幹起來，等等，這裡隻說對了一半，具體咱們下面慢慢道來~）
ADMM是一個不算是太新的算法，其實就是一種求解優化問題的計算架構, 适用于求解分布式凸優化問題，特别是統計學習問題。 ADMM 通過分解協調（Decomposition-Coordination）過程，将大的全局問題分解為多個較小、較容易求解的局部子問題，并通過協調子問題的解而得到大的全局問題的解。
簡單的了解就是，整個算法隻是整合許多不少經典優化思路，然後結合現代統計學習所遇到的問題，提出了一個比較一般的比較好實施的分布式計算架構。
而他的曆史可以追溯到看下面：
ADMM 最早分别由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976年提出，并被 Boyd 等人于 2011 年重新綜述并證明其适用于大規模分布式優化問題。由于 ADMM的提出早于大規模分布式計算系統和大規模優化問題的出現，是以在 2011 年以前，這種方法并不廣為人知。
作為搞自動化、控制、優化、診斷…的本菜來說，當然是奔着優化求解去學習的。
先來看看一個大佬對目前大資料及其優化的見解，簡直是一針見血，說出來我的心聲：
業界一直在談論大資料，對于統計而言，大資料其實意味着要不是樣本量增加n → ∞ n\rightarrow \inftyn→∞，要不就是次元的增加p → ∞ p \rightarrow \inftyp→∞，亦或者兩者同時增加，并且次元與樣本量的增長速度呈線性或者指數型增長。在稀疏性的假設條件下，再加上一些正則性方法，統計學家可以證明各種加penalty的模型所給出的參數估計具有良好的統計性質，收斂速度也有保證，同時還會給出一些比較好的疊代算法，但是，他們并沒有考慮真實環境下的所消耗的計算時間。雖然統計學家也希望盡量尋求疊代數目比較少的算法（比如one-step估計），但是面對真實的Gb級别以上的資料，很多時候我們還是無法直接用這些算法，原因是一般的硬體都無法支撐直接對所有資料進行運算的要求。如果想減少抽樣誤差，不想抽樣，又想提高估計的精度，那麼還是需要尋求其他思路，結合已有的模型思想來解決這些問題。在目前條件下，并行化、分布式計算是一種比較好的解決思路，利用多核和多機器的優勢，這些好算法便可以大規模應用，處理大資料優勢便展現出來了。對于統計而言，資料量越大當然資訊越可能充分（假設備援成分不是特别多），因為大樣本性質本身就希望樣本越多越好嘛。—源自此處
還需要知道的一點，我們都知道搞優化會遇到很多問題，無非是資料量上和次元的變化，關鍵詞大都為：降維，收斂，疊代等等，而這裡的ADMM算法不同于那些梯度下降法或其他改進的SGDM、RMSProp、Adam等等更多進階算法，應用的大多為以GB級别的資料量的資料集，如果與SGDM、Adam這些算法在同樣的低維資料（這裡指的是較GB級别低的）進行比較，收斂速度絕壁沒它們好，很慢，實際的收斂速度往往比那些算法慢得多。ADMM的主要應用，主要是在解空間規模非常大的情況下（比如X、Y 都是存儲空間上GB的超大規模矩陣），這個時候很多傳統的方法不好用，強制需要分塊求解，而且對解的絕對精度往往要求也沒那麼高。是以我覺得這是，需要提前知道的一點。
确實，這個算法很難了解，公式也很難，不敢保證，我能将其解釋清楚，抱着互相學習的态度寫這篇Blog！（望各位大佬批評指正）
具體結構，從ADMM需要用到的背景知識、ADMM原理、具體應用這幾塊進行解釋。
下面咱們從基本架構結構入手吧~
背景知識
《Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers》文章中提到了一些預備知識，學過最優化或最優估計等優化課程的童鞋應該能夠很快能夠了解，對偶問題若很陌生的小夥伴，可以補充補充相關的知識。
先來了解一些基本算法思想吧~
對偶上升
對于凸函數的優化問題，對偶上升法核心思想就是引入一個對偶變量，然後利用交替優化的思路，使得兩者同時達到optimal。
讀到這裡，讓我們想起咱們的主題，“交替方向”，是不是有點感覺了。
對于凸函數，我們隻需要知道，凸優化問題有一個良好的性質即：局部最優解便是全局最優解
對凸函數有不解的地方，可看這位大佬的部落格。
一個凸函數的對偶函數其實就是原凸函數的一個下界，是以可以證明一個較好的性質：在強對偶性假設下，即最小化原凸函數（primal）等價于最大化對偶函數（dual），兩者會同時達到optimal。這種轉化可以将原來很多的參數限制條件變得少了很多，以利于做優化。具體表述如下：
在強對偶的假設下，原問題和對偶問題的解都是一樣的，同時達到最優。
什麼是強對偶性？就是指原問題的解與對偶問題的解是相同的，也即是：
arg 是變元（即自變量argument）的英文縮寫。
arg min 就是使後面這個式子達到最小值時的變量的取值>
arg max 就是使後面這個式子達到最大值時的變量的取值
假如g ( y ) g(y)g(y)可求其導數，那麼利用梯度上升法，交替更新參數，使得同時收斂到最優。疊代如下：
對偶分解
雖然對偶上升的方法有所缺陷，導緻我們在實際操作中會遇到重重困難。
但是世界萬物都是存在着兩面，有其弊也有其利，就如下面的太極雙魚圖
那麼，我們可以利用其優秀的一面，當目标函數 f 是可分的（separable）時候（參數亦或feature可分），整個問題可以拆解成多個子參數問題，分塊優化後彙集起來整體更新。
這也就是快接近咱們的主題了，分布式凸優化問題。
我們可以分塊，然後并行化處理。
由此，我們可分離的目标函數為：
對偶分解是非常經典的優化方法，可追溯到1960年代。這種思想對後面的分布式優化方法影響較大，比如近期的graph-structure優化問題。（具體可自行查詢一下下）
增廣的拉格朗日乘數法
反正，記住一點即可：增加懲罰項，擴大限制條件的容納範圍，放松假設條件。
可使其收斂的更快。
那麼，增加懲罰項的拉格朗日項為：
其中，最後加了的L2正則化，二範數，也就是嶺回歸優化項就是懲罰項。ρ \rhoρ 則為我們的松弛因子（懲罰系數），用于更加精細的調節擴大的範圍邊界。
我們可以将其等價為優化的目标函數形式：
我們增加的懲罰函數的好處是為了讓對偶函數
更具有可導性，更新參數的計算過程和對偶上升的一緻。除最小化x xx的時候加上懲罰項：
解除嚴格凸函數的限制的任務已經完成了，但是同時又存在另外一個問題，當增加懲罰項後，其平方項寫成矩陣形式無法是用之前那種分塊形式的，是以，在更新x xx最小化時，無法做到并行優化多個x i
參數，關于新的問題的解決辦法，ADMM則殺出重圍了！！！
ADMM算法原理
在上述的層層遞進的方法中，你是否也發現了其中的奧秘，對偶上升法解決了可分解性問題，增廣乘子法解決了嚴格的凸函數限制條件，增強了收斂性。那麼是否，我們可以将二者集合在一起，取其各自的優點呢？
答案當然是肯定的，那就是ADMM算法，同時解決了将原函數進行分解和擴充函數的限制範圍問題。使得f ( x ) f(x)f(x)能夠适應于更多的更廣泛的限制條件求解問題。
結合兩者的優點，就有了下式目标函數：
和上面的增廣拉格朗日一樣，隻不過增加了新的變量z zz而已。
于是ADMM的優化就變成了如下序貫型疊代（這正是被稱作alternating direction交替方向的緣由）：
可以看出，每次疊代分為三步：
求解與 x 相關的最小化問題，更新變量 x
求解與 z 相關的最小化問題，更新變量 z
更新對偶變量 u
ADMM名稱中的“乘子法”是指這是一種使用增廣拉格朗日函數（帶有二次懲罰項）的對偶上升（Dual Ascent）方法，而“交替方向”是指變量 x 和 z 是交替更新的。兩變量的交替更新是在 f ( x )或 g ( z )可分時可以将優化問題分解的關鍵原因。
到此，通過以上的内容來了解“交替方向乘數法（ADMM）”是不是就豁然開朗了許多，開篇說很難，其實是不是并沒有那麼的難。
當然，寫成這種形式有利于後面簡化優化問題，也可不作任何的處理。
具體應用
大佬回答及點評
ADMM( Alternating Direction Method of Multipliers)算法是機器學習中比較廣泛使用的限制問題最優化方法，它是ALM算法的一種延伸，隻不過将無限制優化的部分用塊坐标下降法（block coordinate descent，或叫做 alternating minimization）來分别優化。産生這種方法主要是為了彌補二次懲罰的缺點。
在一些問題當中，用二次懲罰來近似限制問題在最優點附近需要懲罰項的系數趨近于無窮，而這種要求會使得海森矩陣很大，是以近似的目标函數很不穩定。為了解決這個問題，引入了線性逼近的部分，通過線性項系數不斷的接近最優解（對偶上升），使得在二次懲罰項的系數很小的情況下，也能得到滿足要求精度的解。ADMM目前是比較成熟，比較受歡迎的限制問題最優化通用架構。（引用源自知乎大佬）
受限制的凸優化問題
一般的受限制的凸優化問題可以寫成如下形式：
可将此類型寫成ADMM形式，增加新變量，以分解原始變量：
相應的增廣拉格朗日項為：
其中的 g 函數即 C 的示性函數，上述是scaled形式，那麼具體算法就是:
，顧名思義，是表示自變量性态的一個函數。
統計學習中的應用
統計學習問題也是模型拟合問題（我們知道有拟合和過拟合），可表示為：
對于帶L1正則化項的線性回歸（Lasso），其平方損失函數為
對于邏輯回歸（Logistic Regression），其極大似然損失函數為
對于線性支援向量機（Linear Support Vector Machine），其合頁（Hinge）損失函數為
将訓練資料在其原始樣本M次元下将其劃分為N塊：
由此我們可得到分塊的目标函數來實作分布式計算：
相應的簡潔疊代更新D 、 d 、 x 的計算方式為：
個人見解
最後說兩句，雖然優化算法千千萬，在不同時期，随着科技的發展與進步，老的算法暫時過時，新的算法逐漸崛起，但終歸要落實到實際應用當中才是真正的好算法，并不是說一味的提高求解速度，提高精度，有些時候成本會很高，有些時候老的算法會被拾起成為yyds，新的算法未必就好。終究說來，希望能夠有更多更實際應用範圍更加廣泛的優化算法逐漸崛起吧~