在線分布式優(yōu)化研究進展

袁德明,張保勇,夏建偉

(1. 南京理工大學(xué) 自動化學(xué)院,江蘇 南京 210094;2. 聊城大學(xué) 數(shù)學(xué)科學(xué)學(xué)院, 山東 聊城 252059)

1 引言

近年來,多智能體系統(tǒng)技術(shù)作為改變未來社會生活方式和戰(zhàn)爭規(guī)則的顛覆性技術(shù)在世界范圍內(nèi)得到快速發(fā)展,不僅成為當(dāng)前國際學(xué)術(shù)界和產(chǎn)業(yè)界的研究熱點,而且已經(jīng)上升為我國國家戰(zhàn)略的核心內(nèi)容。多智能體系統(tǒng)(Multi-Agent Systems)是由一群具備一定的感知、通信、計算和執(zhí)行能力的智能體通過通訊等方式關(guān)聯(lián)成的一個網(wǎng)絡(luò)系統(tǒng)[1,2]。而分布式優(yōu)化是通過多智能體之間的協(xié)調(diào)合作有效地實現(xiàn)優(yōu)化的任務(wù)。與傳統(tǒng)集中式優(yōu)化相比,分布式協(xié)同優(yōu)化是一種“去中心”的優(yōu)化算法,不需要一對一的全局通信,每個智能體只需與其相鄰智能體進行信息交換。因此,可以用來解決許多傳統(tǒng)集中式算法難以勝任的大規(guī)模復(fù)雜的優(yōu)化問題。近十年來,因在機器學(xué)習(xí)、智能電網(wǎng)、傳感器網(wǎng)絡(luò)等諸多領(lǐng)域的廣泛應(yīng)用,分布式優(yōu)化研究得到了越來越多國內(nèi)外學(xué)者的廣泛關(guān)注,是當(dāng)今系統(tǒng)控制重要前沿發(fā)展方向之一[3-12]。

分布式優(yōu)化問題在優(yōu)化領(lǐng)域由來已久。早在20世紀(jì)80年代,麻省理工學(xué)院John N. Tsitsiklis,Dimitri P. Bertsekas 等教授在文獻[3]中提出了分布式優(yōu)化理論的計算框架?；诖碎_創(chuàng)性工作,Angelia Nedic教授和Asuman Ozdaglar教授首次在多智能體系統(tǒng)一致性框架下研究分布式優(yōu)化問題,并提出了著名的分布式次梯度算法[4]。此算法由兩部分構(gòu)成:局部優(yōu)化和一致性計算,前者是每個智能體使用次梯度算法來優(yōu)化其自身的目標(biāo)函數(shù),而后者是用一致性算法來協(xié)調(diào)每個智能體和其相鄰智能體的信息,以保持狀態(tài)一致。基于此工作,近年來國內(nèi)外學(xué)者在分布式優(yōu)化上取得了大量重要的研究成果,并見刊于系統(tǒng)控制領(lǐng)域國內(nèi)外權(quán)威刊物和會議上[5-12]。

在線分布式優(yōu)化的研究近年來得到了國內(nèi)外學(xué)者的廣泛關(guān)注。與離線分布式優(yōu)化不同的是,在線分布式優(yōu)化具有如下特征:(1) 優(yōu)化目標(biāo)不同:在線分布式優(yōu)化中,智能體的目標(biāo)函數(shù)是時變的,其產(chǎn)生甚至可以基于智能體歷史的決策信息和損失函數(shù)信息;而離線分布式優(yōu)化中,智能體的目標(biāo)函數(shù)是固定不變的;(2) 性能指標(biāo)不同:在分析在線分布式優(yōu)化算法的性能時,通常將網(wǎng)絡(luò)中的任意一個智能體的決策序列在所有損失函數(shù)上產(chǎn)生的損失與最優(yōu)決策所產(chǎn)生的損失相比較,其差值稱為遺憾(Regret);而離線分布式優(yōu)化是最小化智能體的狀態(tài)序列與最優(yōu)值之差。因此,在線分布式優(yōu)化是離線分布式優(yōu)化的延伸和拓展。在線分布式優(yōu)化根據(jù)決策空間類型可以分為一般凸集約束和不等式約束;根據(jù)信息反饋模型的不同可以分為完全信息下在線分布式優(yōu)化和Bandit信息下在線分布式優(yōu)化。本文將從決策空間、信息反饋模型這兩個角度對在線分布式優(yōu)化算法的最新研究成果進行總結(jié),著重討論算法的設(shè)計思路、參數(shù)設(shè)計以及收斂性分析結(jié)果,并對不同算法的優(yōu)勢和不足進行剖析。

本文結(jié)構(gòu)安排如下:第2節(jié)介紹了在線分布式優(yōu)化問題的模型和性能指標(biāo);第3節(jié)梳理了現(xiàn)有在線分布式優(yōu)化相關(guān)的代表性算法及其收斂性結(jié)果;第4節(jié)簡單討論了在線分布式優(yōu)化算法的應(yīng)用;第5節(jié)對全文進行總結(jié)并淺析未來可能的研究方向。

2 模型與性能指標(biāo)

2.1 模型

在線分布式優(yōu)化以多智能體系統(tǒng)為框架。多智能體系統(tǒng)是一群具有一定感知、計算和通信能力的個體組成的網(wǎng)絡(luò)系統(tǒng)。一般地,多智能體系統(tǒng)在t時刻的拓撲結(jié)構(gòu)或信息分享模型可以由有向圖Gt=(V,Et,Pt)表示,其中V={1,2,…,N}為頂點(智能體)集合,Et?V×V為t時刻的邊集,Pt=([Pt]ij)N×N為t時刻的權(quán)重矩陣,它刻畫了t時刻智能體之間的信息分享關(guān)系。下面介紹兩種經(jīng)典的網(wǎng)絡(luò)拓撲,它們廣泛地應(yīng)用于在線分布式優(yōu)化算法的設(shè)計和研究中。

(1) 無向連通固定拓撲[7,12]:G=(V,E,P)為無向圖,其中E為固定邊集,P=([P]ij)N×N為固定的權(quán)重矩陣。無向圖意味著對于任意的兩個智能體i,j∈V,(i,j)∈E當(dāng)且僅當(dāng)(j,i)∈E;而圖是連通的意味著對于任意的兩個智能體i和j之間都存在一條路徑。一般對權(quán)重矩陣做如下假設(shè)

(i) 對任意的i,j∈V,[P]ij≥0;

(ii) 當(dāng)(i,j)∈E有[P]ij>0;當(dāng)(i,j)?E有[P]ij=0;

在此假設(shè)下,權(quán)重矩陣P的第二大奇異值小于1,即σ2(P)<1,它決定了一致性收斂速度的快慢。

(2) 一致聯(lián)合強連通切換拓撲[4,9]:存在一個固定的正整數(shù)B使得對于所有的k≥0有(V,EkB∪EkB+1∪…∪E(k+1)B-1)是強連通的,即圖中的任意兩個頂點之間存在有向路徑。針對此拓撲,一般對權(quán)重矩陣做如下假設(shè)

(i) 對任意的i∈V有[Pt]ii≥β>0;

(ii) 當(dāng)(i,j)∈Et有[Pt]ij≥β>0;當(dāng)(i,j)?Et有[Pt]ij=0;

(iii)Pt為雙隨機矩陣。

定義矩陣Qt→s=PtPt-1…Ps+1Ps,?t≥s≥1,且Φt→t=Pt,有

在線分布式優(yōu)化可視為多智能體系統(tǒng)和環(huán)境/對手的博弈。一般來說,它由以下幾步構(gòu)成

(1) 智能體i∈V在t(t=1,2,…,T)時刻做出決策xi(t)∈X?Rd;

(2) 環(huán)境/對手透露關(guān)于損失函數(shù)li,t(x):X→R的信息并遭受損失li,t(xi(t));

(3) 智能體i與其相鄰智能體進行信息交互并基于環(huán)境/對手反饋的信息做出下一步?jīng)Q策xi(t+1)。

(1) 完全信息反饋[13,14]:智能體i∈V在t時刻做完決策后,環(huán)境/對手將損失函數(shù)li,t(x)的完全信息反饋給智能體i。因此,在算法設(shè)計時可以使用損失函數(shù)li,t(x)的梯度甚至Hessian矩陣,即?2li,t(x)。

(1) 單點梯度估計器(One-Point Gradient Estimator)[15]

(2) 兩點梯度估計器(Two-Point Gradient Estimator)[16,17]

式中εt>0為探索參數(shù),ui(t)∈Rd為服從某種概率分布的隨機探索向量。

2.2 性能指標(biāo)

2.2.2 動態(tài)遺憾。動態(tài)遺憾是一種更嚴(yán)格的性能指標(biāo)[18-21],它要求每個時刻智能體的決策向量與當(dāng)前時刻網(wǎng)絡(luò)所有損失函數(shù)的最優(yōu)決策相比較,其形式為

2.2.3 復(fù)合遺憾。當(dāng)智能體i∈V在t時刻的目標(biāo)函數(shù)由損失函數(shù)li,t(x)和正則項ri(x):X→R組成時,需要引入復(fù)合遺憾來刻畫算法的性能,即

2.2.4 累加約束違反度。當(dāng)決策空間是一組不等式約束時,即X={hs(x)≤0,s=1,…,M},其中hs(x)是凸函數(shù)。智能體無法在每一個時刻計算決策向量到?jīng)Q策空間X的精確投影。因此,需要引入累加約束違反度(Cumulative Constraint Violation)來刻畫所有智能體的決策向量在所有不等式約束上產(chǎn)生的偏差值

式中[z]+=max{0,z}。CCV存在正負相抵消的情況,因此考慮一種更嚴(yán)格的指標(biāo),即累加絕對約束違反度(Cumulative Absolute Constraint Violation)

相較于凸集決策空間情形,不僅要求所設(shè)計的算法的遺憾是次線性增長的,而且累加(絕對)約束違反度也需要是次線性增長的,即CCV(T)=o(T)或CACV(T)=o(T)。

3 算法設(shè)計

本節(jié)回顧現(xiàn)有經(jīng)典的在線分布式優(yōu)化算法,并對算法的設(shè)計思路和收斂性結(jié)果進行總結(jié)。

3.1 在線分布式次梯度算法

文獻[22]提出了完全信息反饋下的在線分布式次梯度算法,它可視為分布式次梯度法[4]的在線版本,也可視為在線學(xué)習(xí)中在線梯度下降法[14]的分布式版本

(1)

在算法中,智能體的初始決策設(shè)置為xi(1)∈X,?i∈V;P為權(quán)重矩陣;gi,t(xi(t))∈?li,t(xi(t))為損失函數(shù)li,t(x)在xi(t)點任意一個次梯度,當(dāng)損失函數(shù)可微時有?li,t(xi(t))={?li,t(xi(t))};ηt是t時刻的學(xué)習(xí)率。

3.2 在線分布式對偶平均算法

文獻[23,24]提出了完全信息反饋下的在線分布式對偶平均算法,它是經(jīng)典的分布式對偶平均算法[12]的在線推廣

(2)

3.3 在線分布式鏡面下降算法

文獻[25]提出了時變切換拓撲下的離線分布式鏡面下降算法,在此基礎(chǔ)上,文獻[26]考慮了在線分布式復(fù)合優(yōu)化問題并設(shè)計在線分布式復(fù)合鏡面下降算法。下面首先給出在線分布式鏡面下降算法的具體形式以及相關(guān)理論結(jié)果

(3)

在算法中,智能體的初始決策設(shè)置為xi(1)∈X,?i∈V;Φ:Rd→R為距離產(chǎn)生函數(shù),滿足可微性和強凸性;DΦ(x‖y)=Φ(x)-Φ(y)-?Φ(y)T(x-y)為Bregman散度。算法(3)前兩行亦可以寫成

下面給出兩種經(jīng)典的距離產(chǎn)生函數(shù)選取方案以及相應(yīng)的算法。

其形式和在線分布式次梯度算法(1)極為相似,其區(qū)別在于一致性算法和在線局部優(yōu)化算法的先后順序不同。

式中exp(s)=es。

文獻[26]進一步地研究了在線分布式復(fù)合優(yōu)化問題并提出了如下完全信息反饋下的在線分布式復(fù)合鏡面下降算法

(4)

(5)

式中(1-ξ)X={(1-ξ)x:x∈X}為收縮的決策空間,其作用是保證觀測點xi(t)±εtui(t)在決策空間X內(nèi)。值得注意的是,在Bandit信息反饋下一般對決策空間X做如下進一步的假設(shè)

B(0,r)?X?B(0,R),0

可見復(fù)合遺憾不僅與決策變量維數(shù)相關(guān),還與所選取的范數(shù)相關(guān),這是Bandit信息反饋下在線分布式優(yōu)化算法的共性。

(6)

3.4 在線分布式Frank-Wolfe算法

基于歐幾里得距離產(chǎn)生函數(shù)的算法涉及點到凸集的歐幾里得投影,當(dāng)決策空間X形式復(fù)雜或不具有特殊結(jié)構(gòu)時,求解投影問題本身就是一個凸優(yōu)化問題[30,31],這無疑對智能體的計算能力提出了挑戰(zhàn)?；诖丝紤],文獻[32]提出了基于Frank-Wolfe法(又稱條件梯度法)的在線分布式優(yōu)化算法,其基本思想是將歐氏投影轉(zhuǎn)化為一個線性優(yōu)化問題:

(7)

3.5 在線分布式原始-對偶次梯度算法

當(dāng)決策空間是一組不等式約束時,即X={hs(x)≤0,s=1,…,M},歐氏投影無法計算。因此,算法設(shè)計一般基于對偶域方法。文獻[34]引入了正則拉格朗日(Regularized Lagrangian)函數(shù):

式中λ=([λ]1,…,[λ]M)T∈RM為拉格朗日乘子,θt為正則參數(shù)。文獻[34]在M=1和決策空間滿足假設(shè)X?B(0,R)的前提下,設(shè)計了一種在線分布式原始-對偶次梯度算法:

(8)

式中αt和βt分別為原始和對偶變量更新的學(xué)習(xí)率;?xLi,t(xi(t),λi(t))和?λLi,t(xi(t),λi(t))分別是拉格朗日函數(shù)Li,t對于原始和對偶變量在點(xi(t),λi(t))處的次梯度和超梯度

文獻[35]對算法(8)進行了改進并得到了更優(yōu)的上界。具體地講,提出了如下形式的正則拉格朗日函數(shù)

并在此基礎(chǔ)上設(shè)計了如下算法

(9)

3.6 其它算法

4 在線分布式優(yōu)化算法的應(yīng)用

本節(jié)簡要介紹在線分布式優(yōu)化算法的應(yīng)用。

4.1 分布式機器學(xué)習(xí)

比如,當(dāng)選取預(yù)測函數(shù)h(xk,w)=wTxk并采用平方損失函數(shù)時,上述問題變?yōu)榻?jīng)典的線性回歸問題

隨著數(shù)據(jù)庫規(guī)模的日益增大,在單個處理器上對所有K個樣本進行訓(xùn)練將不切實際,因此可行的方法是在多處理器上進行分散訓(xùn)練后再進行綜合,此即為分布式優(yōu)化問題。進一步考慮在一些機器學(xué)習(xí)問題中樣本是在線產(chǎn)生的,比如垃圾郵件過濾,而在線分布式優(yōu)化可以作為工具解決這類問題[53],其目標(biāo)函數(shù)為

式中K=MN。我們可以利用第3節(jié)中的算法有效的解決此類問題。

4.2 多智能體Multi-Armed Bandit問題

考慮如下學(xué)習(xí)問題:N個決策者重復(fù)的在k個選項或動作中進行選擇。每次做出選擇之后,每個決策者會得到一定數(shù)值的收益,收益由決策者選擇的動作決定的平穩(wěn)概率分布產(chǎn)生。每個決策者的目標(biāo)是在總的T輪迭代內(nèi)最大化總收益的期望[54]。具體地講,智能體i希望最小化如下遺憾

式中μj為第j個選項或動作的期望收益,并假設(shè)μ1≥μ2≥…≥μk;ai(t)為智能體i在t時刻選擇的選項或動作。智能體之間的交互方式由網(wǎng)絡(luò)拓撲決定,它可以是固定拓撲或切換拓撲。智能體根據(jù)鄰居的獎勵信息進行信息綜合,然后根據(jù)經(jīng)典的MAB算法做出自己的決策,再將自己的獎勵信息反饋給相鄰智能體。多智能體Multi-Armed Bandit問題在強化學(xué)習(xí)、推薦系統(tǒng)、信息檢索、動態(tài)定價、異常檢測等諸多領(lǐng)域有著廣泛的應(yīng)用[55,56]。

5 總結(jié)與展望

本文從決策空間、性能指標(biāo)、信息反饋模型等角度對當(dāng)前在線分布式優(yōu)化算法的研究熱點進行了梳理和總結(jié),著重對算法的設(shè)計思路和收斂性分析結(jié)果進行了剖析。近年來,在線分布式優(yōu)化的研究得到了國內(nèi)外學(xué)者的廣泛關(guān)注,但相關(guān)研究仍處于起步階段,尚有許多重要的基本問題值得深入研究。一些未來可能的研究方向包括但不限于:

(1) 非凸優(yōu)化。在很多實際問題中,目標(biāo)函數(shù)往往是非凸的。比如,稀疏回歸問題,雖然目標(biāo)函數(shù)是凸函數(shù),而約束條件是非凸的;比如,推薦系統(tǒng)問題常常伴隨著非凸秩約束。非凸優(yōu)化問題往往存在局部解,同時非凸優(yōu)化問題的定義形式多樣、研究方法各異,這使得非凸優(yōu)化問題比凸優(yōu)化問題更具有挑戰(zhàn)性。因此,如何針對非凸損失函數(shù),定義相應(yīng)的性能指標(biāo)并給出相應(yīng)的在線分布式優(yōu)化算法設(shè)計方案是極具挑戰(zhàn)的。

(2) 遺憾下界。目前,現(xiàn)有工作大多致力于推導(dǎo)算法的遺憾上界,而對于此上界是否為最優(yōu)的討論極少。而我們知道,算法的遺憾下界決定了算法的收斂性能極限,這對深入研究在線分布式優(yōu)化算法的收斂性質(zhì)是極為關(guān)鍵的。因此,借助凸優(yōu)化理論刻畫算法的遺憾下界甚至證明遺憾上界和下界是階次一致的,是一個值得深入研究的課題。

(3) 自適應(yīng)學(xué)習(xí)率。現(xiàn)有部分工作在設(shè)計學(xué)習(xí)率時要么用到總的迭代輪數(shù)的信息,要么用到所有損失函數(shù)的次梯度的共同范數(shù)上界,而算法在更新當(dāng)前時刻的決策時是無法知道未來損失函數(shù)的信息。在分布式環(huán)境中,自適應(yīng)學(xué)習(xí)率的設(shè)計尤為關(guān)鍵,它可以減少智能體之間協(xié)調(diào)學(xué)習(xí)率的次數(shù),從而降低通信成本。因此,這些設(shè)計都存在局限性,如何設(shè)計一類只基于歷史信息的自適應(yīng)學(xué)習(xí)率是一個值得繼續(xù)探索的方向。