分布式有限時(shí)間重球法*

曲志海，陸疌

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

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

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

1 問題描述

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

(1)

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

(2)

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

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

Li-光滑的定義等價(jià)于函數(shù)fi的一階導(dǎo)數(shù)Li-Lipschitz連續(xù)，是對(duì)函數(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‖→+∞時(shí)，fi(x)→+∞。

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

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

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

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

2 FTC算法

(3)

(4)

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

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

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

3 FTCHB算法設(shè)計(jì)

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

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

算法1:FTCHB初始化: 1 對(duì)每個(gè)節(jié)點(diǎn)i∈,隨機(jī)生成起始狀態(tài)xi(0)。選擇合適的步長(zhǎng)參數(shù)γk與動(dòng)量參數(shù)βk,每個(gè)節(jié)點(diǎn)通過(guò)第3節(jié)的方法計(jì)算α^(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)下降方向，所以無(wú)法采用文獻(xiàn)[10]中的方法進(jìn)行分析。為分析收斂速率我們嘗試通過(guò)找到一個(gè)Lyapunov函數(shù)以輔助收斂性證明。首先給出下降引理，并根據(jù)下降引理構(gòu)造Lyapunov函數(shù)。此后在L-光滑與凸假設(shè)下得到一個(gè)目標(biāo)函數(shù)F(x)有非各態(tài)歷經(jīng)的(1/k)收斂速率以及在ν-限制性強(qiáng)凸情況下目標(biāo)函數(shù)F(x)線性收斂速率。

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

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

(5)

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

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

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

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

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

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

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

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

6 總結(jié)

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