曲志海，陸疌

(上?？萍即髮W(xué)信息科學(xué)與技術(shù)學(xué)院， 上海 201210； 中國科學(xué)院上海微系統(tǒng)與信息技術(shù)研究所， 上海 200050； 中國科學(xué)院大學(xué)， 北京 100049) (2020年1月6日收稿； 2020年2月26日收修改稿)

隨著多智體系統(tǒng)的發(fā)展，分布式優(yōu)化算法受到廣泛的重視并應(yīng)用于諸多領(lǐng)域，如資源調(diào)度[1]、分布式傳感器系統(tǒng)參數(shù)估計[2]、協(xié)同控制[3]及對分布式增強(qiáng)學(xué)習(xí)[4]等問題的相關(guān)研究。現(xiàn)存的分布式算法大多以各個節(jié)點目標(biāo)函數(shù)梯度作為下降方向，以漸進(jìn)收斂的方式達(dá)成最優(yōu)共識狀態(tài)，如分布式次梯度算法[5]、EXTRA[6]、DIGing[7]等。此類算法需要足夠多迭代算法才能收斂到共識狀態(tài)。另一類算法則以有限次迭代達(dá)成共識的FTC算法[8]為基礎(chǔ)，在一個迭代周期內(nèi)所有節(jié)點達(dá)到共識，如FADO[9]、FTC-NM[10]。其中FADO算法結(jié)合FTC與次梯度算法，因次梯度算法僅使用了函數(shù)基本的一階信息，算法不能得到理想的收斂速率。FTC-NM算法利用二階信息達(dá)到局部二次收斂速率。雖然收斂速率理想但需要傳輸二階導(dǎo)數(shù)矩陣不適用于通信受限的場景中。考慮通信量與收斂速率的折中，本文中提出一種FTC算法與重球法相結(jié)合的分布式一階算法。

本文貢獻(xiàn)如下：提出基于FTC的分布式一階加速優(yōu)化算法。給出收斂性分析及算法參數(shù)的選取范圍。證明本文算法與集中式重球法算法相同的收斂階數(shù)。最后通過在隨機(jī)生成的大規(guī)模網(wǎng)絡(luò)上求解機(jī)器學(xué)習(xí)問題并與多種算法進(jìn)行對比以體現(xiàn)算法的優(yōu)良性能。

1 問題描述

假設(shè)網(wǎng)絡(luò)中共有N個節(jié)點，每個節(jié)點有自己的目標(biāo)函數(shù)fi(x)。在分布式協(xié)同優(yōu)化中考慮如下問題

(1)

通過變量復(fù)制，問題(1)可以等價為如下問題

(2)

此處x為x1,…,xN堆疊成的向量。等價問題(2)在分布式系統(tǒng)中被廣泛應(yīng)用，由于通信受限，并非所有節(jié)點都可以實時保持變量值相同，所以考慮每個節(jié)點i擁有自己的變量xi。為了分析算法的收斂速率引入以下描述函數(shù)性質(zhì)的假設(shè)。

假設(shè)1(Li-光滑函數(shù))假設(shè)函數(shù)fi(x)為Li-光滑，則函數(shù)fi(x)滿足如下性質(zhì)，即對任意x,y∈dom(fi)，如下關(guān)系成立

Li-光滑的定義等價于函數(shù)fi的一階導(dǎo)數(shù)Li-Lipschitz連續(xù)，是對函數(shù)變化程度的一種約束。

F(x)-minF≥ν‖x-x*‖2，

ν-限制性強(qiáng)凸是比強(qiáng)凸更弱的條件。

假設(shè)3(強(qiáng)制函數(shù))函數(shù)fi(x)為強(qiáng)制函數(shù)，則當(dāng)‖x‖→+∞時，fi(x)→+∞。

對目標(biāo)函數(shù)的假設(shè)會用于收斂性分析，為保證各個節(jié)點達(dá)成共識，需要對網(wǎng)絡(luò)進(jìn)行如下常見假設(shè)

假設(shè)4(網(wǎng)絡(luò)連通)網(wǎng)絡(luò)中的每一個節(jié)點至少存在一條到其他任意節(jié)點的路徑。

只有在連通的網(wǎng)絡(luò)中各個節(jié)點才能通過通信獲取網(wǎng)絡(luò)中的相關(guān)信息并進(jìn)行協(xié)同。

假設(shè)5加權(quán)矩陣W為行隨機(jī)矩陣而且當(dāng)(i,j)∈ε時wij>0，其他情況下wij=0，且W1=1。

2 FTC算法

(3)

(4)

下面介紹α(i)的一種分布式計算方法[13]。以勒貝格測度下為0的集合中的起始狀態(tài)x0進(jìn)行式(3)迭代(最多N次)，組成如下Hankel矩陣

定理1(通過qi計算共識[8])當(dāng)假設(shè)4，假設(shè)5滿足且WT為行隨機(jī)矩陣時，則共識可通過前Di次式(3)迭代得到，即

定理1給出了計算共識的方法，此方法是文中的信息融合的關(guān)鍵所在。

3 FTCHB算法設(shè)計

結(jié)合FTC算法與重球法本章節(jié)提出算法1(finite-time-consensus-based heavy-ball method，F(xiàn)TCHB)。為避免二階算法的巨大通信與計算量及經(jīng)典梯度算法緩慢的收斂速率，本文決定結(jié)合使用歷史信息的重球法以獲取下降方向以求解問題(1)。重球法屬于一階算法，僅需要對梯度進(jìn)行計算，避免了二階算法計算量與通信量的缺陷。此外重球法在病態(tài)條件數(shù)的情況下可以保持良好的收斂速率。使用FTC算法輔助以達(dá)到共識。

9) 越控。當(dāng)控制位置在集控臺時，按下集控臺上的“越控”按鈕，取消遙控系統(tǒng)相關(guān)限制保護(hù)功能，同時向電噴控制系統(tǒng)發(fā)出越控指令。

算法1:FTCHB初始化: 1 對每個節(jié)點i∈,隨機(jī)生成起始狀態(tài)xi(0)。選擇合適的步長參數(shù)γk與動量參數(shù)βk,每個節(jié)點通過第3節(jié)的方法計算α^(i)。 2 fort=1,2,…,N-1do 3 xi(t)=∑j∈iwijxj(t-1). 4 end for 5 x-1c(i)=x0c(i)=∑Dil=0α^(i)lxi(l).主要迭代部分: 6 fork=0,1,2,…do 7 xk+1c(i)=xkc(i)-γkΔfi(xkc(i))+βk(xkc(i)-xk-1c(i)). 8 xi(0)=xk+1c(i). 9 fort=1,2,…,N-1do 10 xi(t)=∑j∈iwijxj(t-1). 11 end for 12 xk+1c(i)=∑Dil=0α^(i)lxi(l). 13 end for

4 收斂性分析

本節(jié)給出FTCHB算法的收斂性分析。注意到重球法中的更新方向單調(diào)下降方向，所以無法采用文獻(xiàn)[10]中的方法進(jìn)行分析。為分析收斂速率我們嘗試通過找到一個Lyapunov函數(shù)以輔助收斂性證明。首先給出下降引理，并根據(jù)下降引理構(gòu)造Lyapunov函數(shù)。此后在L-光滑與凸假設(shè)下得到一個目標(biāo)函數(shù)F(x)有非各態(tài)歷經(jīng)的(1/k)收斂速率以及在ν-限制性強(qiáng)凸情況下目標(biāo)函數(shù)F(x)線性收斂速率。

上面的等價形式在證明中起著重要作用。算法1利用了變量復(fù)制后問題(2)的形式。下面通過FTC算法給出算法1的集中式等價解釋。集中式理解方式允許我們參考重球法中的收斂性分析方法[14-15]。下面利用算法1主要迭代的等價形式結(jié)合文獻(xiàn)[15]中的集中式處理分析方法獲取非各態(tài)歷經(jīng)的收斂速率。

引理1假設(shè)fi(x)是凸函數(shù)且一階可導(dǎo)，且滿足假設(shè)1，minF>-∞。假設(shè)動量系數(shù){βk}k≥0?[0,1)。通過選擇步長

(5)

在等價迭代式(5)及假設(shè)條件滿足的情況下參考文獻(xiàn)[15]中引理1的證明。

證明：結(jié)合算法迭代更新的等價形式(5)及文獻(xiàn)[15]中的引理2的證明可得。

此處的x*∈argminx∈dF(x)是問題(1)的一個最優(yōu)解。

定理2引理1中的假設(shè)成立的情況下，若0

證明：結(jié)合算法迭代更新的等價形式(5)及文獻(xiàn)[15]定理1的證明可得。

下面說明加上限制性強(qiáng)凸的假設(shè)之后，算法可以獲得的非各態(tài)歷經(jīng)的線性收斂速率。

定理3假設(shè)定理2中的條件均滿足并且F滿足假設(shè)2，那么有

5 數(shù)值仿真

圖1 不同網(wǎng)絡(luò)規(guī)模的收斂結(jié)果比較(λ=1)

圖2 不同λ情況下收斂結(jié)果的比較(N=100)

其中：N為網(wǎng)絡(luò)中節(jié)點的總數(shù)，λ>0為嶺回歸所對應(yīng)的正則化參數(shù)，qi表示節(jié)點i上分配的數(shù)據(jù)個數(shù)，在此仿真中qi=6。uil表示節(jié)點i上的第l個數(shù)據(jù)，而vil∈{-1,+1}表示此數(shù)據(jù)對應(yīng)的標(biāo)簽。在我們的仿真中隨機(jī)生成數(shù)據(jù)uil∈3，其中每個維度滿足均值為±10,方差為1的正態(tài)分布。每個節(jié)點的6個數(shù)據(jù)中有3個正樣本，3個負(fù)樣本。對于給定隨機(jī)網(wǎng)絡(luò)的生成，首先生成N-1條邊，構(gòu)成一個滿足假設(shè)4的連通網(wǎng)絡(luò)，在此基礎(chǔ)上隨機(jī)選擇沒有連接的節(jié)點添加鏈接直至鏈接的邊數(shù)達(dá)到我們設(shè)置的節(jié)點平均度的要求，在此數(shù)值仿真中網(wǎng)絡(luò)節(jié)點平均度設(shè)置為5。通過YAMLIP軟件包[17]進(jìn)行集中式求解問題(1)獲取參考最優(yōu)解。網(wǎng)絡(luò)加權(quán)矩陣設(shè)置為

從圖1，圖2可以看出除FTCHB外，相比其他一階算法收斂比較接近，二階算法之間的收斂也比較接近。與此同時FTCHB相對于其他一階算法可以更快地收斂到更高的精度。二階算法收斂最終收斂精度超過一階算法。對比不同網(wǎng)絡(luò)規(guī)模的情況，通過圖1可得知在網(wǎng)絡(luò)規(guī)模變化的情況下FTCHB算法與其他算法的相對關(guān)系沒有改變并且可以較快收斂到較高精度。從圖2可以看出當(dāng)λ=10(對應(yīng)條件數(shù)3.46×103)時所有算法表現(xiàn)均強(qiáng)于λ=0.01(對應(yīng)條件數(shù)3.7×106)，這可以看出條件數(shù)對一階算法影響較大而對二階算法影響較小。比較圖2(a)和2(b)兩圖可知FTCHB作為一階算法在條件數(shù)大時可以很快收斂到較高精度。

此外，通過數(shù)值仿真可以看到設(shè)計算法的等價形式與集中式的重球法求解的最優(yōu)值相差無幾。兩者有一定差別的主要原因是在算法初始化步驟1過程中的計算誤差，如何減小此誤差是一個單獨的開放問題。

6 總結(jié)

本文提出一種解決基于共識的多智體系統(tǒng)協(xié)同優(yōu)化問題的分布式算法FTCHB。通過結(jié)合FTC及重球法，在凸假設(shè)和L-光滑假設(shè)下可以達(dá)到(1/k)的速率，并且加入限制性強(qiáng)凸的條件之后目標(biāo)函數(shù)可以達(dá)到非各態(tài)歷經(jīng)性的線性收斂速率。