原文鏈接：http://www.cnblogs.com/breezedeus/p/3496819.html

----------------------------------------------------------------------------------

從等式約束的最小化問題說起：??????????????????????????????????

????????????????????????????????????????????????????? ?
上面問題的拉格朗日表達(dá)式為：
????????????????????????????????????????????? ?
也就是前面的最小化問題可以寫為：
???????????????????????????????????????????????。
它對應(yīng)的對偶問題為：
??????????????????????????????????????????????。
下面是用來求解此對偶問題的 對偶上升迭代方法：
??????????????????????????????????? ?
這個(gè)方法在滿足一些比較強(qiáng)的假設(shè)下可以證明收斂。

?

為了弱化對偶上升方法的強(qiáng)假設(shè)性，一些研究者在上世紀(jì)60年代提出使用擴(kuò)展拉格朗日表達(dá)式（augmented Lagrangian）代替原來的拉格朗日表達(dá)式：
??????????????????????????????????
其中。對應(yīng)上面的對偶上升方法，得到下面的乘子法（method of multipliers）：
?????????????????????????????????????????????????????

?

注意，乘子法里把第二個(gè)式子里的改成了擴(kuò)展拉格朗日表達(dá)式中引入的。這不是一個(gè)隨意行為，而是有理論依據(jù)的。利用可以導(dǎo)出上面最小化問題對應(yīng)的原始和對偶可行性條件分別為（，）：
???????????????????????????????????????????????
既然?最小化?，有：
????????????????????????????????????????
上面最后一個(gè)等式就是利用了。從上面可知，這種的取法使得滿足對偶可行條件。而原始可行條件在迭代過程中逐漸成立。

?

乘子法弱化了對偶上升法的收斂條件，但由于在x-minimization步引入了二次項(xiàng)而導(dǎo)致無法把x分開進(jìn)行求解（詳見[1])。而接下來要講的Alternating Direction Method of Multipliers (ADMM)就是期望結(jié)合乘子法的弱條件的收斂性以及對偶上升法的可分解求解性。ADMM求解以下形式的最小化問題：
??????????????????????????????????????????????
其對應(yīng)的擴(kuò)展拉格朗日表達(dá)式為：?
????????????????????
ADMM包括以下迭代步驟：
????????????????????????????????????????
ADMM其實(shí)和乘子法很像，只是乘子法里把和放一塊求解，而ADMM是分開求解，類似迭代一步的Gauss-Seidel方法。其中(3.4)中的推導(dǎo)類似于乘子法，只是使用了最小化：
???????????????????????????????????????
其中用到了對應(yīng)的對偶可行性式子：
???????????????????????????????????????????????????

?

定義新變量，那么(3.2-3.4)中的迭代可以變?yōu)橐韵滦问?#xff1a;
???????????????????????????
在真正求解時(shí)通常會(huì)使用所謂的over-relaxation方法，也即在和中使用下面的表達(dá)式代替其中的：
?????????????????????????????????????????，
其中為relaxation因子。有實(shí)驗(yàn)表明可以改進(jìn)收斂性([2])。

?

下面讓我們看看ADMM怎么被用來求解大型的機(jī)器學(xué)習(xí)模型。所謂的大型，要不就是樣本數(shù)太多，或者樣本的維數(shù)太高。下面我們只考慮第一種情況，關(guān)于第二種情況感興趣的讀者可以參見最后的參考文獻(xiàn)[1, 2]。樣本數(shù)太多無法一次全部導(dǎo)入內(nèi)存，常見的處理方式是使用分布式系統(tǒng)，把樣本分塊，使得每塊樣本能導(dǎo)入到一臺(tái)機(jī)器的內(nèi)存中。當(dāng)然，我們要的是一個(gè)最終模型，它的訓(xùn)練過程利用了所有的樣本數(shù)據(jù)。常見的機(jī)器學(xué)習(xí)模型如下：
????????????????????????????????????，
其中為模型參數(shù)，對應(yīng)第個(gè)樣本的損失函數(shù)，而為懲罰系數(shù)，如。

?

假設(shè)把個(gè)樣本分成份，每份可以導(dǎo)入內(nèi)存。此時(shí)我們把上面的問題重寫為下面的形式：?
????????????????????????????????????????????
除了把目標(biāo)函數(shù)分成塊，還額外加了個(gè)等式約束，使得利用每塊樣本計(jì)算出來的模型參數(shù)都相等。那么，ADMM中的求解步驟(3.2)-(3.4)變?yōu)?#xff1a;?
?????????????????????????????
例如求解L1懲罰的LR模型，其迭代步驟如下（，）：?
????????????????????????????????????
其中，的定義類似。

?

在分布式情況下，為了計(jì)算方便通常會(huì)把的更新步驟挪在最前面，這樣和的更新可以放在一塊：?
?????????????????????????????????????

?

ADMM的框架確實(shí)很牛逼，把一個(gè)大問題分成可分布式同時(shí)求解的多個(gè)小問題。理論上，ADMM的框架可以解決大部分實(shí)際中的大尺度問題。我自己全部實(shí)現(xiàn)了一遍這個(gè)框架，主要用于求解LR問題，下面說說我碰到的一些問題：
1.?收斂不夠快，往往需要迭代幾十步。整體速度主要依賴于更新時(shí)所使用的優(yōu)化方法，個(gè)人建議使用liblinear里算法，但是不能直接拿來就用，需要做一些調(diào)整。
2.?停止準(zhǔn)則和的選取：停止準(zhǔn)則主要考量的是和之間的差異和它們本身的變動(dòng)情況，但這些值又受的取值的影響。它們之間如何權(quán)衡并無定法。個(gè)人建議使用模型在測試集上的效果來確定是否停止迭代。
3.?不適合MapReduce框架實(shí)現(xiàn)：需要保證對數(shù)據(jù)的分割自始至終都一致；用MPI實(shí)現(xiàn)的話相對于其他算法又未必有什么優(yōu)勢（如L-BFGS、OwLQN等）。
4.?relaxation步驟要謹(jǐn)慎：的取值依賴于具體的問題，很多時(shí)候的確可以加快收斂速度，但對有些問題甚至可能帶來不收斂的后果。用的時(shí)候不論是用x -> z -> u的更新步驟，還是用u -> x -> z的更新步驟，在u步使用的x_hat要和在z步使用的相同（使用舊的z），而不是使用z步剛更新的z重算。
5.?warm start 和子問題求解逐漸精確的策略可以降低更新時(shí)的耗時(shí)，但也使得算法更加復(fù)雜，需要設(shè)定的參數(shù)也增加了。

[References]
[1] S. Boyd.? Alternating Direction Method of Multipliers ?(Slides).

[2] S. Boyd et al.?Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, 2010.

stanford的比較好的一個(gè)源碼和實(shí)例鏈接

http://www.stanford.edu/~boyd/papers/admm/

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。