ADMM算法學(xué)習(xí)

• ADMM定義和背景
• ADMM方法
• • 問題模型
  • 增廣拉格朗日函數(shù)
  • 算法流程
• 算法測試
• 算法擴展
• 參考資料

ADMM定義和背景

交替向乘子法（Alternating Direction Method of Multipliers, ADMM）是一種求解具有可分離的凸優(yōu)化問題的重要方法，由于處理速度快，收斂性能好，ADMM算法在統(tǒng)計學(xué)習(xí)、機器學(xué)習(xí)等領(lǐng)域有著廣泛應(yīng)用。

交替方向乘子法（ADMM）是一種求解優(yōu)化問題的計算框架, 適用于求解分布式凸優(yōu)化問題，特別是統(tǒng)計學(xué)習(xí)問題。 ADMM 通過分解協(xié)調(diào)（Decomposition-Coordination）過程，將大的全局問題分解為多個較小、較容易求解的局部子問題，并通過協(xié)調(diào)子問題的解而得到大的全局問題的解。ADMM 最早分別由 Glowinski & Marrocco 及 Gabay & Mercier 于 1975 年和 1976 年提出，并被 Boyd 等人于 2011 年重新綜述并證明其適用于大規(guī)模分布式優(yōu)化問題。由于 ADMM 的提出早于大規(guī)模分布式計算系統(tǒng)和大規(guī)模優(yōu)化問題的出現(xiàn)，所以在 2011 年以前，這種方法并不廣為人知。【7】

ADMM 是ALM算法的一種延伸，只不過將無約束優(yōu)化的部分用塊坐標(biāo)下降法（block coordinate descent，或叫做 alternating minimization）來分別優(yōu)化。產(chǎn)生這種方法主要是為了彌補二次懲罰的缺點。在一些問題當(dāng)中，用二次懲罰來近似約束問題在最優(yōu)點附近需要懲罰項的系數(shù)趨近于無窮，而這種要求會使得海森矩陣很大，因此近似的目標(biāo)函數(shù)很不穩(wěn)定。為了解決這個問題，引入了線性逼近的部分，通過線性項系數(shù)不斷的接近最優(yōu)解（對偶上升），使得在二次懲罰項的系數(shù)很小的情況下，也能得到滿足要求精度的解。ADMM目前是比較成熟，比較受歡迎的約束問題最優(yōu)化通用框架?！?】

歸根結(jié)底，就是解決 loss function + regulation. 當(dāng)regulation為L1范數(shù)的時候沒有合適的算法解決這個凸優(yōu)化問題。原來boyd的老師提出過 最小角方法 方法解決這個問題，但是因為方法不直觀并且難以操作。所以，這些大牛們一直在尋找一種比較合適的算法解決這個問題。直至2011年左右提出比較通用和直觀的ADMM算法。對于ADMM算法，其實是一種交替求解的方式。不斷的將問題分解，進(jìn)而逐個解決。其中在解決的過程中，發(fā)現(xiàn)將惱人的L1 Norm中的變量進(jìn)行替換，從而形成 L1+L2 norm的形式比較容易求解（proximal algorithm），所以挺好的。而如果我們直接進(jìn)行Loss function + regulation，求解的話，很難得到解。所以從上面我們可以發(fā)現(xiàn)，變量替換成為解決問題的關(guān)鍵。而逐次求解，使問題得到解決。其實只要將最簡單的L1 norm的形式理解。對于各種proximal直接查詢相關(guān)解就可以了?！?】

ADMM方法

問題模型

交替方向乘子法（ADMM）通常用于解決存在兩個優(yōu)化變量的等式約束優(yōu)化類問題，其一般形式為：$$\begin{gathered} \underset{x,z}{\min }f(x)+g(z) \\ s.t.Ax+Bz=c \end{gathered}$$
其中 $x\in {\mathbb{R}}^n,z\in {\mathbb{R}}^m$ 為優(yōu)化變量，等式約束中 $A\in {\mathbb{R}}^{p\times n},B\in {\mathbb{R}}^{p\times m},c\in {\mathbb{R}}^p$, 目標(biāo)函數(shù)中 $f,g$ 都是凸函數(shù).

• 標(biāo)準(zhǔn)的ADMM算法解決的是一個等式約束的問題，且該問題兩個函數(shù) $f$ 和 $g$ 是成線性加法的關(guān)系。這意味著兩者實際上是整體優(yōu)化的兩個部分，兩者的資源占用符合一定等式，對整體優(yōu)化貢獻(xiàn)不同，但是是簡單加在一起的。
• 事實上分布式中的一致性優(yōu)化問題（consensus），分享問題（sharing problem）等等都很好寫成這樣的形式，因為每個節(jié)點的變量還要跟周圍節(jié)點變量產(chǎn)生關(guān)聯(lián)、

增廣拉格朗日函數(shù)

ADMM算法的核心是原始對偶算法的增廣拉格朗日法（ALM）。拉格朗日函數(shù)是解決了多個約束條件下的優(yōu)化問題，這種方法可以求解一個有n個變量與k個約束條件的優(yōu)化問題。原始對偶方法中的增廣拉格朗日法（Augmented Lagrangian）是加了懲罰項的拉格朗日法，目的是使得算法收斂的速度更快。
$$L_{\rho }(x,z,u)=f(x)+g(z)+u^T(Ax+Bz?c)+\frac{\rho }{2}\Vert Ax+Bz?c{\Vert }_2^2$$

增廣拉格朗日函數(shù)就是在關(guān)于原問題的拉格朗日函數(shù)【4】之后增加了一個和約束條件有關(guān)的懲罰項，懲罰項參數(shù) $\rho >0$ .懲罰項參數(shù)影響迭代效率。
增廣拉格朗日函數(shù)對min是＋對偶項和懲罰項，對max是 - 對偶項和懲罰項。

• 原問題 ${\min }_{x,z}f(x)+g(z)$，對偶問題 ${\max }_u{\min }_{x,z}{L}_{\rho }(x,z,u)$，兩個問題的最優(yōu)解等價，并且沒有了約束條件。

算法流程

每一步只更新一個變量而固定另外兩個變量，如此交替重復(fù)更新。

Step 1: $x^{(i)}={\mathrm{argmin}}_x{L}_{\rho }(x,z^{(i?1)},u^{(i?1)})$

Step 2: $z^{(i)}={\mathrm{argmin}}_z{L}_{\rho }(x^{(i)},z,u^{(i?1)})$

Step 3: $u^{(i)}=u^{(i?1)}+\rho (A{x}^{(i)}+B{z}^{(i)}?c)$ %Ascend

不斷重復(fù)以上三步直到收斂。

• 使用和增廣拉格朗日類似的對偶上升方法，固定其中兩個變量，去更新第三個變量的值。
• ADMM 算法提供了一個將多優(yōu)化變量問題轉(zhuǎn)化為單優(yōu)化變量問題的轉(zhuǎn)化方式（即，交替方向），并未涉及具體的下降方法，其中關(guān)于 $x$ 和 $z$ 的更新過程需要結(jié)合具體的下降類算法，如梯度下降算法等。
• ADMM的另一種形式：
  

算法測試

求解例子

構(gòu)造出該目標(biāo)函數(shù)的增廣拉格朗日表達(dá)式
$$L(x,y,\lambda )=f(x)+g(y)+{\lambda }^T(2x+3y?5)+\frac{\rho }{2}\Vert 2x+3y?5{\Vert }_2^2$$

使用 Matlab 編碼【5】求解如下:

• 主函數(shù)

%% 定義參數(shù) % x0,y0都是可行解 param.x0 = 1; param.y0 = 1; param.lambda = 1; param.maxIter = 30; param.beta = 1.1; % a constant param.rho = 0.5;[Hx,Fx] = getHession_F('f1'); [Hy,Fy] = getHession_F('f2');param.Hx = Hx; param.Fx = Fx; param.Hy = Hy; param.Fy = Fy;%% solve problem using admm algrithm [x,y] = solve_admm(param);%% disp minimum disp(['[x,y]:' num2str(x) ',' num2str(y)]);

• ADMM求解函數(shù)：solve_admm

function [x,y] = solve_admm(param) x = param.x0; y = param.y0; lambda = param.lambda; beta = param.beta; rho = param.rho; Hx = param.Hx; Fx = param.Fx; Hy = param.Hy; Fy = param.Fy; %% xlb = 0; % the lower bound of x xub = 3; % the upper bound of x ylb = 1; yub = 4; maxIter = param.maxIter; i = 1; funval = zeros(maxIter-1,1); iterNum = zeros(maxIter-1,1); while 1if i == maxIterbreak;end% solve xHxx = eval(Hx);Fxx = eval(Fx);x = quadprog(Hxx,Fxx,[],[],[],[],xlb,xub,[]); % Quadratic programming function% solve yHyy = eval(Hy);Fyy = eval(Fy);y = quadprog(Hyy,Fyy,[],[],[],[],ylb,yub,[]);% update lambdalambda = lambda + rho*(2*x + 3*y -5); % ascendfunval(i) = compute_fval(x,y);iterNum(i) = i;i = i + 1; end plot(iterNum,funval,'-r'); end

• 求解函數(shù)的 Hessian 矩陣和導(dǎo)數(shù)的函數(shù)：getHession_F

function [H,F] = getHession_F(fn) % fn : function name % H : hessian matrix % F : 一次項數(shù)系數(shù) syms x y lambda rho; if strcmp(fn,'f1') % 判斷輸入函數(shù)是 f1 的話f = (x-1)^2 + lambda*(2*x + 3*y -5) + rho/2*(2*x + 3*y -5)^2;H = hessian(f,x); % 計算函數(shù)的 Hessian 矩陣F = (2*lambda + (rho*(12*y - 20))/2 - 2); % x 的系數(shù)fcol = collect(f,{'x'}); % 固定y，默認(rèn)x為符號變量disp(fcol); elseif strcmp(fn,'f2') % 判斷輸入函數(shù)是 f2 的話f = (y-2)^2 + lambda*(2*x + 3*y -5) + rho/2*(2*x + 3*y -5)^2;H = hessian(f,y); F = (3*lambda + (rho*(12*x - 30))/2 - 4); % y 的系數(shù)fcol = collect(f,{'y'}); % 固定x，默認(rèn)y為符號變量disp(fcol); end end

• 計算 $(x,y)$ 對應(yīng)的目標(biāo)函數(shù)值函數(shù)：compute_fval

function fval = compute_fval(x,y)fval = (x-1)^2 + (y-2)^2; end

算法擴展

這里寫一些關(guān)于ADMM算法擴展應(yīng)用的個人理解：
在通信優(yōu)化問題中，聯(lián)合優(yōu)化問題存在多個優(yōu)化變量（比如，$\{x,y,z\}$），等式或不等式約束中的多變量耦合導(dǎo)致問題直接求解的復(fù)雜度過大（尤其是當(dāng)變量的維度過大時），但是由于占用了共同的資源約束又不可以直接進(jìn)行變量分解，這時候為了利用ADMM并行求解的思想來處理較大規(guī)模的問題，就需要某種辦法來引入等式約束將問題變成可以分解的形式。

ADMM方法就是通過 decomposition-coordination 的過程，通過連續(xù)協(xié)調(diào)規(guī)模小的局部的子問題的解來找到一個大規(guī)模的全局問題的解。

• 觀察變量耦合的等式或不等式約束，看是引入“輔助變量”還是“復(fù)制變量”合適；
• 輔助變量可以替代原來的變量或約束，比如UAV集群軌跡優(yōu)化中的防碰撞約束 $\Vert q_i[t]?q_j[t]{\Vert }_2\ge d_{\min }$，可以通過引入輔助變量 $z_{i,j}[t]=q_i[t]?q_j[t]$ 來替代防碰撞約束中的 $q_i[t]$ 和 $q_j[t]$ 以差值方式耦合的情況，原問題中增加了輔助變量 $z_{i,j}$, 防碰撞約束可以被等式約束 $Aq=Z$ 替代，通過該方法可以將優(yōu)化問題根據(jù)不同的UAVs進(jìn)行分解，即 $q_i[t]$ 和 $q_j[t]$以并行方式求解。再比如某個UAV軌跡在相鄰時隙之間的最大距離約束 $\Vert q[t]?q[t?1]{\Vert }_2\le v_{\max }\delta$，也可以引入輔助變量 $z[t]=q[t]?q[t?1]$ 來將優(yōu)化問題在不同的slot的上進(jìn)行分解，$q[t]$ 和 $q[t?1]$以并行方式求解。
• 復(fù)制變量就是增加原全局優(yōu)化變量的一個局部替代變量，通過引入變量的復(fù)制變量來保證相同的變量最多出現(xiàn)在一個不等式約束中。比如，全局變量 $x$ 和 $y$ 的線性組合讓問題不可分解，通過引入全局變量 $x$ 的局部 copying variables $\bar{x}$ 來替代原優(yōu)化問題中的原變量 $x$ 在目標(biāo)函數(shù)和約束的位置，注意此時也引入了等式約束 $x=\bar{x}$。這樣變量 $x$ 和 $y$ 就可以以并行的方式求解了，同前面標(biāo)準(zhǔn)ADMM的 x 和 z 中的更新類似。
• 注意，一般而言原變量（global variables）和引入變量（local variables: 輔助變量、復(fù)制變量）的更新雖然都是基于 min/max (增廣拉格朗日函數(shù))實現(xiàn)，但二者的更新都是基于對方本次迭代中的值已知的前提下的，所以這樣可以進(jìn)行問題分解；local variables, global variables 和 lagrange multiples 是交替進(jìn)行更新的。

參考資料

【1】http://www.stat.cmu.edu/~ryantibs/convexopt/lectures/admm.pdf （CMU凸優(yōu)化課件-admm）
【2】https://www.cnblogs.com/wildkid1024/p/11041756.html
【3】Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends? in Machine learning, 2011, 3(1): 1-122.
【4】https://zhuanlan.zhihu.com/p/103961917 （拉格朗日對偶（Lagrange duality）、KKT條件）
【5】https://zhuanlan.zhihu.com/p/286235184 （matlab實例代碼）
【6】直接在matlab中搜索 doc quadprog，會顯示該二次規(guī)劃函數(shù)的使用方法.
【7】https://www.zhihu.com/question/36566112/answer/82474155
【8】https://www.zhihu.com/question/36566112/answer/79535746
【9】https://www.zhihu.com/question/36566112/answer/213686443
【10】ADMM的一些參考文獻(xiàn)

總結(jié)

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

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