學(xué)習(xí)筆記，僅供參考，有錯(cuò)必糾
轉(zhuǎn)載自：機(jī)器學(xué)習(xí)與運(yùn)籌優(yōu)化（六）對(duì)偶算法與ADMM算法

---

文章目錄

• • • 摘要
    • ADMM算法
    • 參考文獻(xiàn)

---

摘要

上文我們介紹了約束優(yōu)化問題和拉格朗日對(duì)偶思想。對(duì)偶算法就像是男生女生互相挑選，最終走到一起的過程，今天我們具體介紹幾種常見的對(duì)偶算法，特別介紹在大數(shù)據(jù)時(shí)代大放異彩的ADMM算法。

回憶一下男生女生互相挑選的過程，哦不，回憶一下對(duì)偶算法的思想——構(gòu)造拉格朗日函數(shù)，把約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題求解。

ADMM算法

例如原問題是在線性約束下極小化函數(shù)f：

我們用之前介紹的梯度下降法求解這個(gè)無約束優(yōu)化問題，對(duì)于原始變量求解極小化問題（如果f可微可以應(yīng)用梯度下降），對(duì)于對(duì)偶變量應(yīng)用梯度上升，這就是Uzawa算法，或者叫原始-對(duì)偶上升法，講究的是“敵進(jìn)我退”：

Uzawa算法的收斂性對(duì)函數(shù)f和步長(zhǎng)均有要求，需要f是強(qiáng)凸的，并且梯度上升的步長(zhǎng)不能太大，受到f的強(qiáng)凸性的限制。感興趣的同學(xué)可以參考Nitfy Theorem，原函數(shù)的強(qiáng)凸性對(duì)應(yīng)對(duì)偶函數(shù)的連續(xù)性。

我們希望增強(qiáng)f的凸性，一個(gè)自然的想法是給f加上一個(gè)凸二次函數(shù)，于是我們準(zhǔn)備構(gòu)造一個(gè)增廣拉格朗日函數(shù)（Augmented Lagrangian）：

對(duì)于這個(gè)新的拉格朗日函數(shù)， Uzawa算法可以改進(jìn)為ALM算法（Augmented Lagrangian Method of Multipliers）：

可以證明，由于增廣拉格朗日的強(qiáng)凸性和步長(zhǎng)的聯(lián)系，ALM算法對(duì)于任意步長(zhǎng)都是收斂的。

ALM算法的問題是，如果f不可微，每一步求解都需要解一個(gè)極小化的子問題，計(jì)算代價(jià)可能較大。而在機(jī)器學(xué)習(xí)的很多問題中，f具有特殊的結(jié)構(gòu)，一般可以分解為兩個(gè)或多個(gè)函數(shù)，單個(gè)函數(shù)是利于求解的，比如統(tǒng)計(jì)和圖像處理中非常有名的LASSO問題：

其中第一步需要求解整個(gè)f+g的增廣拉格朗日函數(shù)的極小值，而f和g單獨(dú)的增廣拉格朗日函數(shù)的極小值更易于求解，于是我們采用“分而治之”的思想，于是得到了交替方向乘子法，ADMM算法（Alternating Direction Method of Multipliers）：

ADMM算法廣泛應(yīng)用于統(tǒng)計(jì)學(xué)習(xí)和機(jī)器學(xué)習(xí)的各個(gè)領(lǐng)域，包括LASSO和約束線性回歸模型；支持向量機(jī)；壓縮感知；稀疏優(yōu)化；分布式計(jì)算；其他大型分布式機(jī)器學(xué)習(xí)問題等等。

原始-對(duì)偶上升法體現(xiàn)了兵法中的“敵進(jìn)我退”思想，而ADMM算法則體現(xiàn)了兵法中的“分而治之”思想。研究者在提出和改進(jìn)新算法時(shí)，idea往往都很簡(jiǎn)單易懂，但背后體現(xiàn)了研究者的深刻的洞察力，需要對(duì)問題結(jié)構(gòu)和算法思想的足夠的理解，加上一點(diǎn)點(diǎn)靈感的火花。也許下一次，讀者也能應(yīng)用“三十六計(jì)”，提出更有效的機(jī)器學(xué)習(xí)優(yōu)化算法。

參考文獻(xiàn)

[1] Boyd Stephen, Parikh Neal，Chu Eric，Peleato Borja. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, 2010.

[2]Boyd, Stephen, and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.

[3]袁亞湘, 孫文瑜. “最優(yōu)化理論與方法.” 科學(xué)出版社, 1997 年 1 月 (1997).

總結(jié)

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

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