作者：覃含章
編者按
本文介紹ADMM最基本情形的推導(dǎo)。通過這篇文章，你將了解ADMM算法的基本思路，收斂性分析的基本原理，和它理論上的一些局限性。
本文的內(nèi)容主要來自著名的講義：
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.
正文開始前多說幾句。Stephen Boyd作為一名優(yōu)化科學(xué)家，除了自己的很多研究，這輩子最杰出的貢獻(xiàn)就是廣泛地將優(yōu)化理論嚴(yán)謹(jǐn)?shù)亟榻B給了工程界。其中，ADMM就是一個(gè)很重要的例子。這個(gè)方法其實(shí)理論優(yōu)化界早就研究了幾十年（何炳生老師語），但是也只是到了最近幾年，如Boyd包括Stanford的Yinyu Ye老師等人，才對這方面的研究進(jìn)行了“再挖掘”，引起了大家的廣泛注意。
經(jīng)典的ADMM算法適用于求解如下2-block的凸優(yōu)化問題（
Block指我們可以將決策域分塊，分成兩組變量，
都是凸的。分成2-block是因?yàn)?-block及以上的問題性質(zhì)會差一點(diǎn)，分析起來不太好說清楚（雖然實(shí)際當(dāng)中基本上幾個(gè)block都可以用，一般都會收斂...）。
那么我們這里就可以寫出這個(gè)凸優(yōu)化問題的增廣拉格朗日函數(shù)（augmented Lagrangian function）：
注意到這個(gè)增廣的意思就是在原來的拉格朗日函數(shù)后面加了個(gè)平方的正則項(xiàng)（系數(shù)
Dual ascent的原理非常簡單，本質(zhì)上來說就是primal variable迭代方向取拉格朗日函數(shù)對primal variable的次微分，dual variable迭代方向取拉格朗日函數(shù)對dual variable的次微分（這里的話就是
那么ADMM，也就是所謂“交替方向”的乘子法就是在原基礎(chǔ)上（
在兩個(gè)不太強(qiáng)的假設(shè)前提下，本節(jié)給出ADMM基本形式的收斂性證明的思路。
假設(shè)1：凸函數(shù)
假設(shè)2：（非增廣）拉格朗日函數(shù)
假設(shè)1等價(jià)于epigraph
的解一定是存在的。注意，這個(gè)假設(shè)仍然沒有限制
假設(shè)2主要是為了保證強(qiáng)對偶（strong duality）對這個(gè)問題成立（在假設(shè)1成立的基礎(chǔ)上），即原問題和對偶問題的最優(yōu)值相等。熟悉凸優(yōu)化理論的同學(xué)應(yīng)該一下子就能明白，這邊就留給大家作為思考。注意假設(shè)2也沒有怎么限制
基于這兩個(gè)假設(shè)，我們證明如下結(jié)果：
殘差收斂。隨著
目標(biāo)函數(shù)值收斂。隨著
對偶變量收斂。隨著
注意這里隱含了一個(gè)ADMM的有意思的特性，即原變量，primal variable，
好了，為了說明思路，一開始我們先定義一個(gè)李雅普諾夫函數(shù)（Lyapunov function），
和對偶空間上的殘差
證明的思路主要由三個(gè)不等式組成。
注意不等式
這就直接表明了隨著
因此我們就知道，證明了這三個(gè)不等式就能直接推出我們所要的收斂性結(jié)果。
下一節(jié)就給出三個(gè)不等式的證明。順序是先證明
所以我們看到其實(shí)掌握了證明的主要思路，具體證明其實(shí)沒什么技術(shù)難度，頂多就是algebra稍微有點(diǎn)繞。這也是ADMM算法分析的一般特點(diǎn)，我們這還是最基本的情況，復(fù)雜情況的分析就是繞得多了（主要是因?yàn)榈臅r(shí)候各種“交替”）...
注意我這邊只給出了關(guān)于ADMM算法收斂到最優(yōu)可行解（原變量還不一定最優(yōu)）和最優(yōu)目標(biāo)函數(shù)值的證明。這里我完全沒有討論收斂速率的問題。收斂速率，在很多其它優(yōu)化算法里面都是比較容易分析的，像一階二階算法，內(nèi)點(diǎn)法等等。但在ADMM的分析里面，收斂速率分析確實(shí)是這塊領(lǐng)域的一大難點(diǎn)。事實(shí)上，實(shí)際當(dāng)中你如果寫代碼跑ADMM會發(fā)現(xiàn)它不像那些梯度下降，牛頓法，很容易快速收斂到一個(gè)較高的誤差精度，ADMM實(shí)際的收斂速度往往比那些算法慢得多。。ADMM的主要應(yīng)用，主要是在解空間規(guī)模非常大的情況下（比如
不過這個(gè)算法分析起來確實(shí)各種難點(diǎn)。除了最前面已經(jīng)提到從2-block到multi-block的推廣不trivial。還有一個(gè)實(shí)際中常用的trick不好分析：往往這個(gè)
最后說一下如果我們固定
里面的
二、ADMM在分布式并行計(jì)算中的應(yīng)用
作者：王志濤
轉(zhuǎn)載自公眾號：智能駕駛課題組
摘要：智能汽車的網(wǎng)聯(lián)化協(xié)同駕駛將進(jìn)一步提升道路交通的通行效率。隨著受控車群規(guī)模的增長，所求解的問題規(guī)模增加迅速，這對云控或邊緣平臺的計(jì)算效率提出了很高的要求。智能駕駛課題組（iDLab）提出了一種適用于大規(guī)模網(wǎng)聯(lián)車群集中式控制的并行求解算法，將問題計(jì)算復(fù)雜度將多項(xiàng)式級降低為線性級。通過引入一致性約束解耦原問題，進(jìn)一步結(jié)合ADMM（交替方向乘子法）框架分解為一系列可并行計(jì)算的子問題，每一個(gè)子問題可分配一個(gè)計(jì)算單元，利用單元之間的信息交互達(dá)到最優(yōu)解的一致性收斂，實(shí)現(xiàn)了大規(guī)模網(wǎng)聯(lián)多車協(xié)同問題的并行加速求解。
1.介紹
通過ADMM（交替方向乘子法）框架對大規(guī)模智能網(wǎng)聯(lián)汽車協(xié)同控制問題進(jìn)行求解。通過對車車間的約束進(jìn)行解耦，將問題分解為可以同時(shí)求解而不是順序計(jì)算的子問題。之后利用計(jì)算節(jié)點(diǎn)組成的集群網(wǎng)絡(luò)對問題進(jìn)行并行求解，以期望達(dá)到計(jì)算復(fù)雜度與規(guī)模無關(guān)的目的，從而極大提高求解效率，拓展問題的求解規(guī)模。由于車輛之間的空間位置關(guān)系復(fù)雜多變，車車交互耦合難以處理；因此如何應(yīng)用合理的解耦方案，實(shí)現(xiàn)車車耦合約束的分解，從而實(shí)現(xiàn)并行計(jì)算是本工作的研究重點(diǎn)。課題組研究工作的主要貢獻(xiàn)：a.設(shè)計(jì)了用于分布式計(jì)算方法部署的計(jì)算節(jié)點(diǎn)網(wǎng)絡(luò)結(jié)構(gòu)。b.提出了用于求解大規(guī)模協(xié)同控制問題的并行計(jì)算方法。
2. 交替方向乘子法
科學(xué)研究與工程實(shí)踐中，諸多問題都可以構(gòu)建為凸優(yōu)化問題。當(dāng)規(guī)模較大時(shí)，計(jì)算效率往往成為問題求解的瓶頸。將問題進(jìn)行解耦，使其可以分布式并行計(jì)算，是解決大規(guī)模問題求解效率低的可行方案之一。交替方向乘子法（alternating direction method of multipliers, ADMM），適用于大規(guī)模凸優(yōu)化問題的分布式并行求解。ADMM提出于上個(gè)世紀(jì)70年代，經(jīng)過多年的研究，理論逐漸完善，由于它在機(jī)器學(xué)習(xí)、網(wǎng)絡(luò)優(yōu)化等領(lǐng)域應(yīng)用，受到研究界的關(guān)注。ADMM適用于求解如下2-block的優(yōu)化問題：
其中, , , , ，與均為凸函數(shù)。ADMM的求解思路如下，為了處理約束，首先將問題寫為增廣拉格朗日乘子的形式：該問題可以通過對偶上升進(jìn)行迭代：
該過程相當(dāng)于迭代求解的過程。
ADMM在對偶上升法的基礎(chǔ)之上，將與單獨(dú)交替迭代，即：
這使得與為可分解函數(shù)（類似于這種形式）時(shí)，問題的求解過程可以實(shí)現(xiàn)解耦，從而為分布式并行計(jì)算提供了條件。
3.網(wǎng)聯(lián)多車協(xié)同控制問題的構(gòu)建
首先，構(gòu)建集中式協(xié)同的最優(yōu)控制問題。思路是采用分層式處理方案，首先每個(gè)車輛從導(dǎo)航模塊獲取各自的行駛路線；之后以此為參考軌跡行駛，由于參考軌跡未考慮約束關(guān)系，時(shí)空上存在重疊，導(dǎo)致車車間有碰撞風(fēng)險(xiǎn)，因此需要在行駛過程中進(jìn)行動(dòng)態(tài)避撞。
工作用圖論來描述整個(gè)車群系統(tǒng)，構(gòu)建車車交互拓?fù)鋱D。車車交互拓?fù)鋱D為一無向圖，即節(jié)點(diǎn)間不存在次序關(guān)系。圖中每一節(jié)點(diǎn)和每一輛車相對應(yīng)，圖中的邊對應(yīng)兩輛車間存在的潛在沖突關(guān)系。同時(shí)，可以定義與每一個(gè)節(jié)點(diǎn)有鄰接關(guān)系的節(jié)點(diǎn)集合為該節(jié)點(diǎn)鄰域。通過鄰域節(jié)點(diǎn)的定義，構(gòu)建如下的車車避撞約束：
該約束為一個(gè)非凸約束，而非凸約束在優(yōu)化問題中比較難以處理，工作結(jié)合車輛的空間位置變化特點(diǎn)和有限時(shí)域優(yōu)化問題的特性，利用泰勒展開線性化的方式，將非凸約束轉(zhuǎn)化為凸約束近似處理。
據(jù)此，構(gòu)建如下的集中式最優(yōu)控制問題
在優(yōu)化問題中以車輛待優(yōu)化的性能指標(biāo)為目標(biāo)函數(shù)，同時(shí)考慮自車動(dòng)力學(xué)約束，以及車車交互拓?fù)鋱D描述的協(xié)同避撞約束。
4.并行求解算法設(shè)計(jì)
對該最優(yōu)控制問題中的耦合關(guān)系進(jìn)行分析。利用指示函數(shù)，可以將約束寫入目標(biāo)函數(shù)中，得到一個(gè)更為簡潔的問題形式。
對優(yōu)化問題新的形式進(jìn)行分析，問題分為兩個(gè)加和部分，分別為自車性能部分和交互約束部分。兩部分的變量存在重疊而互相關(guān)聯(lián)，造成整個(gè)問題耦合在一起，如何對這一約束進(jìn)行解耦，是實(shí)現(xiàn)并行計(jì)算的關(guān)鍵。我們期望對問題的原形式進(jìn)行變形，令其可以通過ADMM框架進(jìn)行分解，以期實(shí)現(xiàn)問題解耦及并行計(jì)算。首先觀察原問題，自車性能部分與交互約束部分變量相同，互相重疊，造成兩部分耦合。工作通過引入一致性約束的方法對原問題進(jìn)行處理，從而實(shí)現(xiàn)解耦。方法流程如下：對交互約束部分的求解變量生成一個(gè)與之前不同的副本。為了使得問題的與原來等價(jià)，通過引入約束，使這兩部分的變量相等于同一個(gè)值，從而做到問題的不變，因?yàn)樵摷s束形式是使不同變量相等于同一個(gè)值，因此稱之為一致性約束，而這種優(yōu)化形式稱為一致性優(yōu)化問題。下圖展現(xiàn)了這一變換過程。
經(jīng)過轉(zhuǎn)化后，可以發(fā)現(xiàn)，一致性優(yōu)化問題的形式與ADMM求解的優(yōu)化形式相同。因此，該一致性優(yōu)化問題也可以通過三步迭代求解，并且發(fā)現(xiàn)迭代的求解過程可以并行進(jìn)行。一致性優(yōu)化問題按照ADMM的三步迭代求解，需要分別更新三種變量，分別是：第一步更新一致性變量，第二步更新控制變量，第三步更新對偶變量。第一步：
第二步：
第三步：
每一步迭代過程中，其他步驟更新的變量都為定值，這就實(shí)現(xiàn)了不同變量約束的解耦。而由于問題的加和形式，每一步迭代更新中，加和形式內(nèi)部的各個(gè)變量獨(dú)立無關(guān)。以上兩點(diǎn)特性，使得我們通過ADMM迭代求解一致性優(yōu)化問題，得到并行求解算法。為了算法的部署，還需要設(shè)計(jì)一個(gè)可以實(shí)現(xiàn)并行計(jì)算的計(jì)算節(jié)點(diǎn)組成的集群網(wǎng)絡(luò)。我們以車輛交互拓?fù)鋱D為基礎(chǔ)，圖中與每輛車對應(yīng)的綠色節(jié)點(diǎn)負(fù)責(zé)更新自車本地優(yōu)化問題的控制量和對偶量的更新。
進(jìn)而為每一條邊分配一個(gè)紅色節(jié)點(diǎn)，用于更新避撞約束部分的控制量和對偶量。綠色節(jié)點(diǎn)和紅色節(jié)點(diǎn)統(tǒng)稱為從節(jié)點(diǎn)。最后，為了進(jìn)行一致性變量的更新，為每一個(gè)綠色節(jié)點(diǎn)和與之對應(yīng)的紅色節(jié)點(diǎn)集匹配一個(gè)黃色節(jié)點(diǎn)，稱為主節(jié)點(diǎn)。主節(jié)點(diǎn)與從節(jié)點(diǎn)分別負(fù)責(zé)完成各自的計(jì)算任務(wù)，同時(shí)二者之間進(jìn)行通訊，交換計(jì)算所需的信息。之后通過不斷迭代，算法不斷逼近最優(yōu)點(diǎn)。設(shè)定包括原始變量半徑和對偶變量半徑的收斂條件，當(dāng)收斂條件達(dá)到時(shí)，算法終止。
5.算法性能驗(yàn)證
智能駕駛課題對所提出的集中式協(xié)同控制及其并行求解算法的效果進(jìn)行驗(yàn)證。計(jì)算環(huán)境為8線程機(jī)器，即計(jì)算節(jié)點(diǎn)數(shù)量為8個(gè)。優(yōu)化問題的求解器為qpOASES，并行計(jì)算的多線程API為OpenMP。對三種比較典型的場景進(jìn)行仿真，分別是多車道超車，以及兩種無信號交叉口的通行場景。
傳統(tǒng)求解方法由于計(jì)算復(fù)雜度始終與車輛數(shù)量相關(guān)，隨著規(guī)模增大，求解負(fù)擔(dān)急劇增加，也限制了問題的求解規(guī)模。所提出的并行計(jì)算方法，當(dāng)網(wǎng)絡(luò)計(jì)算節(jié)點(diǎn)數(shù)量有限時(shí)，算法的計(jì)算復(fù)雜度為線性級，即此時(shí)計(jì)算時(shí)間與車輛規(guī)模呈線性增長。仿真結(jié)果驗(yàn)證了所提出并行算法的計(jì)算效率和對于大規(guī)模場景的適用性。
6.結(jié)論
課題組研究工作提出了一種適用于大規(guī)模智能網(wǎng)聯(lián)汽車協(xié)同控制的并行計(jì)算方法。算法通過引入一致性約束實(shí)現(xiàn)了優(yōu)化問題中約束的解耦，實(shí)現(xiàn)了集中式問題的并行求解。仿真結(jié)果證明了本工作提出的并行算法相對于集中式求解，降低了計(jì)算復(fù)雜度，解決了問題求解時(shí)間隨車輛規(guī)模多項(xiàng)式攀升的難題，為云控網(wǎng)聯(lián)式自動(dòng)駕駛奠定了基礎(chǔ)。
參考文獻(xiàn)：
[1]S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein et al., “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol. 3, no. 1, pp. 1–122, 2011.
[2]Z. Wang, Y. Zheng, S. Li, K. You, K. Li., “Parallel Optimal Control for Cooperative Automation of Large-scale Connected Vehicles via ADMM,” In:2018 21st International Conference on Intelligent Transportation Systems (ITSC). IEEE, 2018. p. 1633-1639.
[3]S. Li, Z. Wang, Y. Zheng, Q. Sun, J. Gao, F. Ma, K. Li, “Synchronous and Asynchronous Parallel Computation for Large-Scale Optimal Control of Connected Vehicles,” Under reviewing, 2019.
