多個體切換網(wǎng)絡(luò)分布式量化次梯度優(yōu)化算法

李甲地，馬　馳，李德權(quán)，王俊雅

(安徽理工大學(xué) 數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南 232001)(*通信作者電子郵箱1378475744@qq.com)

0　引言

由于因特網(wǎng)、移動互聯(lián)網(wǎng)和無線傳感網(wǎng)絡(luò)等大規(guī)模網(wǎng)絡(luò)的出現(xiàn)，多個體網(wǎng)絡(luò)分布式優(yōu)化成為一個研究熱點。分布式優(yōu)化要求所設(shè)計的算法僅基于網(wǎng)絡(luò)中個體間的局部信息通信協(xié)調(diào)，即可求解網(wǎng)絡(luò)目標(biāo)函數(shù)的最優(yōu)值。例如，并行計算[1]、數(shù)據(jù)研究[2-3]、機器人研究[4]或無線網(wǎng)絡(luò)資源的分配問題[5]等都可歸結(jié)為分布式優(yōu)化算法。

現(xiàn)有的多個體網(wǎng)絡(luò)分布式算法一般都基于一致性算法，且都基于一個理想化的假設(shè):即構(gòu)成網(wǎng)絡(luò)的個體間通信的是各個個體某個狀態(tài)變量的完全精確的信息。這意味著如果傳輸?shù)臓顟B(tài)變量是實值情形，則要求網(wǎng)絡(luò)通道具有無限帶寬，且算法能夠以無限精度被執(zhí)行。此外，還通常假定網(wǎng)絡(luò)中個體間的信息交流是平衡的，這其實要求網(wǎng)絡(luò)拓?fù)涫怯邢蚱胶獾摹６@些條件在實際應(yīng)用中過于苛刻。例如,Google之所以能成為搜索引擎霸主，其技術(shù)原因是第一個把WWW真正視為“網(wǎng)(Web)”的搜索引擎[6]。Google的網(wǎng)頁排序技術(shù)PageRank算法把所有網(wǎng)頁構(gòu)成的網(wǎng)頁網(wǎng)絡(luò)視為有向非平衡網(wǎng)絡(luò)，并且所構(gòu)成的網(wǎng)頁網(wǎng)絡(luò)是隨著時間動態(tài)切換的。顯然，現(xiàn)有的關(guān)于網(wǎng)絡(luò)是有向平衡圖的理想化假設(shè)并不適用，考慮更一般的切換有向非平衡網(wǎng)絡(luò)更有必要。

因為多個體網(wǎng)絡(luò)有空間分布特性，個體間通常基于遠(yuǎn)程通信和無線傳感網(wǎng)絡(luò)實現(xiàn)信息共享[7]。尤其是網(wǎng)絡(luò)運行在非常惡劣的環(huán)境中時，由于數(shù)據(jù)丟包或節(jié)點的連接失敗，或不同個體有不同的感知范圍，往往一樣會造成網(wǎng)絡(luò)個體間的通信網(wǎng)絡(luò)是有向非平衡的。例如，在多移動車輛系統(tǒng)的編隊控制中，由于不同車輛具有不同的感知范圍,或有些車輛僅裝備信息發(fā)射器或接收器，同時可能因障礙物阻斷或消失，使得構(gòu)成的通信網(wǎng)絡(luò)是一個有向非平衡切換網(wǎng)絡(luò)[8]。戰(zhàn)斗機編隊在惡劣天氣中執(zhí)行飛行任務(wù)，由于通信連接失敗或重連，使得構(gòu)成的通信網(wǎng)絡(luò)也是一個典型的有向非平衡切換網(wǎng)絡(luò)。對于有向非平衡網(wǎng)絡(luò)，不僅意味著更弱的網(wǎng)絡(luò)拓?fù)錀l件，還意味著所設(shè)計的優(yōu)化算法不需要額外的通信成本用于信息回復(fù)，降低網(wǎng)絡(luò)個體達到一致性所需的信息量。而且個體間的信息傳輸受無線通信網(wǎng)絡(luò)帶寬限制，導(dǎo)致個體間信息交流之前個體狀態(tài)信息通常是量化的而非精確信息。因此，文獻[9-10]將網(wǎng)絡(luò)拓?fù)浜土炕畔⒔y(tǒng)一考慮，考慮了更一般的非平衡網(wǎng)絡(luò)，研究了基于量化信息通信的量化一致性問題。

一般來說，分布式無約束優(yōu)化問題主要有兩種不同的方法:基于次梯度的方法和無梯度的方法。在假定每個個體的目標(biāo)函數(shù)是凸的但不一定光滑的情形下，文獻[11-12]提出的分布式算法可確保每個個體產(chǎn)生并保持其對全局最優(yōu)解的估計，并且與其鄰居在時變網(wǎng)絡(luò)上進行信息交流來更新自身狀態(tài)。文獻[13-15]介紹了量化一致性算法的編碼/解碼策略，研究了量化一致性。

最近，文獻[16]針對切換多個體網(wǎng)絡(luò)中個體僅與其鄰居個體通過量化信息進行平衡交流，亦即所對應(yīng)的通信網(wǎng)絡(luò)為有向平衡網(wǎng)絡(luò),提出量化分布式次梯度投影優(yōu)化算法解決了帶約束的平均一致性優(yōu)化問題。顯然，文獻[16]中所提算法并不適用于文獻[8]中類似情況。文獻[16]還在文中考慮了確定性量化器和概率量化器兩種類型[17-19]，分析了量化信息交流對算法的收斂性的影響，但它所給出的量化器具有無限量化水平以及僅考慮在切換有向平衡網(wǎng)絡(luò)中，因此本文采用具有有限量化水平的一致對稱量化器及相關(guān)量化策略[9,20-21]，針對更一般的切換有向非平衡多個體網(wǎng)絡(luò)提出了基于量化信息通信的分布式量化次梯度優(yōu)化算法。研究表明在相同的通信網(wǎng)絡(luò)帶寬的條件下，個體與其鄰居個體交換量化信息進行非平衡交流，可提高信息傳輸速率，使得多個體網(wǎng)絡(luò)中個體更快地達到一致。

1　問題描述與量化通信策略

1.1　問題描述

考慮有m個個體的切換非平衡網(wǎng)絡(luò)，其通信網(wǎng)絡(luò)可建模成一個有向圖G(t)=(V,E(t),A(t))。其中：V={1,2,…,m}是節(jié)點集；邊集E(t)?V×V；A(t)=(aij(t))m×m表示有向圖G(t)所對應(yīng)的隨機鄰接矩陣，其中aij(t)表示有向邊(j,i)的權(quán)重，刻畫了個體j向個體i發(fā)送信息的可信度。由于本文考慮帶有自環(huán)的切換平衡網(wǎng)絡(luò)，所以定義Ni(t)={(j,i)∪(i)∈E(t)|i,j∈V}是個體i在t時刻的入度鄰居集合，表示t時刻發(fā)送信息給個體i的全體個體。考慮如下分布式無約束優(yōu)化問題:

(1)

s.t.x∈Rn

1.2　相關(guān)假設(shè)

假設(shè)1 最優(yōu)解為X*={x∈Rn|f(x*)=f*}是存在的。

假設(shè)2對于每個個體i∈V，與其對應(yīng)的目標(biāo)函數(shù)fi在Rn上是凸函數(shù)但不一定可微，并且存在常量G>0使得對所有的i∈V有

‖di(x)‖≤G，?di(x)∈?fi(x)，x∈Rn

其中，?fi(x)表示函數(shù)fi在x處的所有次梯度的集合。

1.3　量化器及編譯碼協(xié)議

考慮動態(tài)切換有向非平衡網(wǎng)絡(luò)，由于信道的容量或帶寬受限，個體必須在將信息發(fā)送給其鄰居個體之前量化信息,這里將借鑒基于邊的自適應(yīng)動態(tài)一致量化器的量化通信策略[9，20-21]。定義具有有限量化水平的動態(tài)一致量化器如下：

(2)

其中：x是一個實數(shù)，K是一個正整數(shù)。量化水平集Γ={0,±i,i=1,2,…,K}，其僅含有有限的元素。事實上，式(2)中量化器Q(x):R→Γ是R到量化水平集Γ的映射。

為了降低通信成本，提高信息傳輸效率，為網(wǎng)絡(luò)中每個個體的信道提出編碼譯碼協(xié)議，以獲得從鄰居個體發(fā)送的狀態(tài)估計值。對發(fā)送個體j對應(yīng)的有向邊(j,i)的編碼器Φji的編碼算法定義如下：

t=1,2,…

(3)

(4)

為了確保個體i在t時刻可以接收到j(luò)的估計值Δji(t)(具有某種的量化誤差)，與個體j相關(guān)聯(lián)的通信信道(j,i)∈E的解碼器Ψji定義如下：

t=1,2,…

(5)

并由式(3)和(5)知：

(6)

2　分布式量化次梯度優(yōu)化算法與收斂性分析

2.1　分布式量化次梯度優(yōu)化算法

下面介紹在切換非平衡網(wǎng)絡(luò)中的量化分布式次梯度優(yōu)化算法，其中每個個體僅與其鄰居個體交換量化信息。xi(t+1)表示個體i在t+1時刻的狀態(tài)，個體i接收來自其鄰居j∈Ni(t)發(fā)送的量化信息，先計算這些狀態(tài)的加權(quán)平均值，然后通過使用它們各自的次梯度信息執(zhí)行局部優(yōu)化。本文針對問題(1)有如下量化分布式次梯度優(yōu)化算法:

(7)

xi(t+1)=yi(t)-αtdi(t)

(8)

2.2　收斂性分析

由于通信網(wǎng)絡(luò)所對應(yīng)的是切換有向非平衡圖，所以文獻[22]主要基于轉(zhuǎn)移矩陣φ(t,s)的性質(zhì)來證明算法收斂性的方法對本文所研究問題將不再適用。受文獻[14,21]啟發(fā)，下面利用非二次李雅普諾夫函數(shù)方法[21，23]以及文獻[24]中的部分相關(guān)結(jié)論來證明有向非平衡圖的量化分布式次梯度優(yōu)化算法的收斂性。

先定義:

并進一步定義：

D(t)=M(t)-m(t),ΔR(t)=Δrmax(t)-Δrmin(t)。

eji(t)=xj(t)-ξji(t)

(9)

Eij(t)=(xj(t+1)-ξji(t))/g(t)-Δji(t+1)

(10)

將假設(shè)4，式(6)、(7)和(9)代入式(8)，改寫為如下形式：

(11)

根據(jù)矩陣A(t)的隨機性，可得：

因此可得如下關(guān)系式:

(12)

此外，對假設(shè)3有，對于任意正整數(shù)s≥0，令個體κ∈V，并定義集合D0={κ}。由假設(shè)3可知，一定存在一個非空集合D1=VD0使得在時間間隔[s,s+(B-1)]內(nèi)對于任意i∈D1，個體κ都與其至少發(fā)生一次信息交換。類似地，通過數(shù)學(xué)歸納法可知，存在這樣一個集合Dl+1?V(D0∪D1∪…∪Dl)，使得在時間間隔[sl,s+((l+1)B-1)]內(nèi)一定存在某個個體i∈(D0∪D1∪…∪Dl)與個體j∈Dl+1至少交換一次信息。由假設(shè)3進一步可知，只要V(D0∪D1∪…∪Dl)不等于空集，則Dl+1不等于空集。因此，集合D0∪D1∪…∪DL是個體集合V的一個分割，其中L≤m-1。

所以，本文提出的量化分布式次梯度優(yōu)化算法(7)和(8)以及變式(11)，與文獻[24]中所提出的一階動態(tài)一致性算法具有完全相同的形式；當(dāng)假設(shè)3，4以及式(12)成立時，滿足文獻[24]中引理3.1的所有假設(shè)條件。因此，下面借用文獻[24]中引理3.1的相關(guān)結(jié)論給出如下引理1及定理1。

引理1假定假設(shè)3和4成立，令s≥0且固定k∈V，集合D0∪D1∪…∪DL是個體集合V的一個分割，則對任意l∈{1,2,…,L}(L≤m-1)，一定存在μl>0，其中滿足μ0=ρmB-1，使得對正整數(shù)p∈[LB,LB-1]和i∈Dl，當(dāng)t=s+p時，如下兩式成立：

(13)

(14)

(15)

證明由引理1有

μ(M(k)-xκ(k)+xκ(k)-m(k))≤

此外，對正整數(shù)h≥1，定義h(mB-1)=Th。進而對任意的正整數(shù)t≥1，令s為滿足s(mB-1)=Ts≤t<(s+1)(mB-1)的最大整數(shù)，從而可得:

(16)

其中，Ω(t)為

2αtGi|[(1-μ)s-1+(1-μ)s-2+…+(1-μ)+1]≤

(17)

證畢。

eji(t+1)=g(t)Εij(t)

(18)

由式(18)可知，如果量化誤差Eij(t)有界，當(dāng)t→∞時，g(t)→0，則估計誤差漸近趨于0，而成立的關(guān)鍵是如何設(shè)計動態(tài)比例函數(shù)g(t)以及量化水平參數(shù)Kji(t)，所以有如下定理2。

(19)

(20)

(21)

其中:

(22)

那么在量化次梯度算法(7)、(8)的作用下，式(11)滿足：

(23)

若當(dāng)t→∞時g(t)→0(t→∞)，則有：

即系統(tǒng)中的個體達到一致。

證明由eji(t)、Eij(t)以及式(3)、(6)，可以得到：

aij(t)eij(t)=aij(t)g(t-1)Eij(t-1)

(24)

則式(11)可寫為：

(25)

由式(3)、(4)知：

(26)

當(dāng)aji>0時，再由式(18)、(26)可得：

g(t-1)Eij(t-1)=xi(t)-ξij(t-1)-g(t-1)Δij(t)

(27)

進而利用A(t)是隨機矩陣以及式(27)可知：當(dāng)aji>0時，即有向邊(i,j)在第t時刻連通，則下式成立：

(28)

當(dāng)aij=0時，即有向邊(i,j)在第t時刻斷開，有類似式(28)的不等式成立。

(29)

則由式(28)知，當(dāng)aji>0時有式(30)成立：

t=1,2,3…

(30)

同理，當(dāng)aji=0時，類似不等式成立。

下面利用數(shù)學(xué)歸納法對式(11)進行收斂性分析。

由定理1和式(19)及ξij(0)=0可知：

(31)

由式(2)定義的一致量化器的性質(zhì)和式(6)，則有

(32)

同理，當(dāng)aij(1)>0，由式(20)和(28)可得：

(33)

當(dāng)aij(1)=0，則有類似式(33)的不等式成立。

綜合上述兩種情況可知：

(34)

(35)

當(dāng)aij(t)=0時，有類似式(35)的不等式成立。

其中推導(dǎo)過程利用了定理2的假設(shè)條件，易推得:

(36)

綜合上述可得:

(37)

t→∞

(38)

當(dāng)t→∞時g(t)→0，有定理2成立，即所有個體達到一致。

(39)

其中D(t)由定理2給出。

證明證明全局函數(shù)f(x)收斂到最優(yōu)值f(x*)，有以下不等式成立:

(40)

由假設(shè)2，有

f(xi(t+1))-f(x*)≤

(41)

考慮到fi(xi(t+1))-fi(x*)，有以下不等式成立:

fi(xi(t+1))-fi(x*)≤

G‖xi(t+1)-yi(t)‖+〈di(t),yi(t)-x*〉≤

GD(t)+〈di(t),yi(t)-x*〉

(42)

將式(42)代入式(40)，并由文獻[16]中引理3及文獻[25]有下式成立，定理3即證。

由定理3可知，在分布式量化次梯度算法(7)、(8)作用下，全局目標(biāo)函數(shù)f(x)漸進地收斂到最優(yōu)值f(x*)。

3　仿真分析

為了驗證本文所提算法理論，考慮由4個個體組成的帶有自環(huán)的有向切換非平衡網(wǎng)絡(luò)G(t)=(V,E(t))。其中個體集合為V={1,2,3,4}，E(t)是個體在t時刻的邊集，個體的局部目標(biāo)函數(shù)為fi(x)=(x-ai)2,ai∈R(i=1,2,3,4)。有向切換非平衡網(wǎng)絡(luò)周期B=3的有向聯(lián)合圖表示如下:E(3t)∪E(3t+1)∪E(3t+2)=E(a)∪E(b)∪E(c),說明在某個時刻所對應(yīng)的通信網(wǎng)絡(luò)圖是弱連通的，也就是說個體間進行的信息交流是不充分的；但在一個切換網(wǎng)絡(luò)周期B內(nèi)，其聯(lián)合圖是強連通的，保證了個體間信息的充分交流。一個周期內(nèi)各個子圖對應(yīng)的隨機鄰接矩陣A(t)如下:

圖1　4個個體的有向切換網(wǎng)絡(luò)Fig. 1　A switching directed network with four nodes

圖2表示γ=0.978 8時4個個體的狀態(tài)軌跡圖，當(dāng)?shù)螖?shù)達到250左右，在誤差允許的范圍內(nèi)，多個體網(wǎng)絡(luò)中的所有個體狀態(tài)值達到一致，其狀態(tài)最優(yōu)值在3的鄰域內(nèi)。圖3表示γ=0.878 8時4個個體的狀態(tài)軌跡圖，通過對量化參數(shù)γ進行調(diào)節(jié)，迭代次數(shù)僅達到50后，多個體網(wǎng)絡(luò)中的所有個體狀態(tài)值達到一致，其狀態(tài)最優(yōu)值也在3鄰域內(nèi)。圖2和圖3表明：網(wǎng)絡(luò)中所有個體通過非平衡信息交流在分布式量化次梯度算法的作用下最終達到一致，并且通過調(diào)節(jié)量化參數(shù)γ可提高網(wǎng)絡(luò)中個體的收斂速率，γ越小收斂越快，降低了對網(wǎng)絡(luò)帶寬的要求。

圖4表示γ=0.978 8以及γ=0.878 8時全局目標(biāo)函數(shù)的誤差。圖4表明：γ=0.978 8和γ=0.878 8的全局目標(biāo)函數(shù)的誤差漸進地趨于零，表明在所提分布式量化次梯度算法的作用下，多個體網(wǎng)絡(luò)中個體最終達到一致，且在一致性值時全局目標(biāo)函數(shù)達成最優(yōu)。此外，由全局函數(shù)誤差下降速度可知，當(dāng)γ=0.878 8時收斂更快。這也說明在相同的網(wǎng)絡(luò)帶寬下，通過調(diào)節(jié)量化器的參數(shù)，可使整個網(wǎng)絡(luò)以更快收斂速率實現(xiàn)優(yōu)化目標(biāo)，從而減少對網(wǎng)絡(luò)無限帶寬的依賴。

圖2　γ=0.978 8時4個個體的狀態(tài)軌跡Fig. 2　Trajectories of four agents’ states with γ=0.978 8

圖3　γ=0.878 8時4個個體的狀態(tài)軌跡Fig. 3　Trajectories of four agents’ states with γ=0.878 8

圖4　γ=0.978 8及γ=0.878 8時全局目標(biāo)函數(shù)的誤差Fig. 4　Global objective function error with γ=0.978 8 and γ=0.878 8

4　結(jié)語

在文獻[9, 16，21-22]的研究基礎(chǔ)上，本文在有向非平衡切換網(wǎng)絡(luò)中通過設(shè)計自適應(yīng)一致量化器使個體間通過量化信息進行交流，并利用非二次李雅普諾夫函數(shù)法刻畫了算法的收斂性誤差,證明了所提出的量化次梯度優(yōu)化算法是收斂的，從而可有效避免個體間的交流必須是互惠的以及對帶寬是無限的苛刻要求，擴大了算法的適用范圍，提高了個體間信息傳輸速率，更貼合實際應(yīng)用。

參考文獻:

[1]OZDEN S G, SMITH A E, GUE K R. Solving large batches of traveling salesman problems with parallel and distributed computing [J]. Computers & Operations Research, 2017, 85: 87-96.

[2]RAM S S, VEERAVALLI V V, NEDIC A. Distributed and recursive parameter estimation in parametrized linear state-space models [J]. IEEE Transactions on Automatic Control, 2010, 55(2): 488-492.

[3]ZHANG S, ZHANG J, SO H C. Mean square deviation analysis of LMS and NLMS algorithms with white reference inputs [J]. Signal Processing, 2017, 131: 20-26.

[4]SAGHIRI A M, MEYBODI M R. An approach for designing cognitive engines in cognitive peer-to-peer networks [J]. Journal of Network and Computer Applications, 2016, 70: 17-40.

[5]OGBE E, LI X. A new cross decomposition method for stochastic mixed-integer linear programming [J]. European Journal of Operational Research, 2017, 256(2): 487-499.

[6]汪小帆，李翔，陳關(guān)榮.網(wǎng)絡(luò)科學(xué)導(dǎo)論[M].北京:高等教育出版社，2012:6. (WANG X F, LI X, CHEN G R. Introduction to Network Science[M]. Beijing: Higher Education Press, 2012: 6.)

[7]CRUZ D, McCLINTOCK J, PERTEET B, et al. Decentralized cooperative control: a multivehicle platform for research in networked embedded systems [J]. IEEE Control Systems Magazine, 2007, 27(3): 58-78.

[8]WANG B, TIAN Y-P. Consensus seeking in second-order multi-agent systems with relative-state-dependent noises [J]. IFAC-Papers Online, 2016, 22(49): 204-209.

[9]LI D, LIU Q, WANG X, et al. Quantized consensus over directed networks with switching topologies [J]. System & Control Letters, 2014, 65: 13-22.

[10]LI D, LIU Q, WANG X, et al. Consensus seeking over directed networks with limited information communication [J]. Automatica, 2013, 49(2): 610-618.

[11]LOBEL I, OZDAGLAR A. Convergence analysis of distributed subgradient methods over random networks [C]// Proceedings of the 2008 46th Annual Allerton Conference on Communication, Control, and Computing. Piscataway, NJ: IEEE, 2008: 353-360.

[12]RAM S S, NEDIC A, VEERAVALLI V V. Incremental stochastic subgradient algorithms for convex optimization [J]. SIAM Journal on Optimization, 2009, 20(2): 691-717.

[14]CARLI R, BULLO F. Quantized coordination algorithms for rendezvous and deployment [J]. SIAM Journal on Control and Optimization， 2009, 48(3): 1251-1274.

[15]CARLI R, FAGNANI F, FRASCA P, et al. Gossip consensus algorithms via quantized communication [J]. Automatica， 2010, 46(1): 70-80.

[16]LI J, CHEN G, WU Z, et al. Distributed subgradient method for multi-agent optimization with quantized communication [J]. Mathematical Methods in the Applied Sciences,2016, 40(4): 1201-1213.

[17]NEDIC A, OZDAGLAR A. TSITSIKLIS J N. Distributed subgradient methods and quantization effects [C]// CDC 2008: Proceedings of the 47th IEEE Conference on Decision and Control. Piscataway, NJ: IEEE, 2008: 4177-4184.

[18]YUAN D, XU S, ZHAO H, et al. Distributed dual averaging method for multi-agent optimization with quantized communication [J]. Systems & Control Letters, 2012, 61(11): 1053-1061.

[19]AYSAL T C, COATES M J, RABBAT M G.Distributed average consensus with dithered quantization [J]. IEEE Transactions on Signal Processing, 2008, 56(10): 4905-4918.

[20]LI T, FU M, XIE L, et al. Distributed consensus with limited communication data rate [J]. IEEE Transactions on Automatic Control, 2011, 56(2): 279-291.

[21]李德權(quán).有向網(wǎng)絡(luò)多個體系統(tǒng)的量化與魯棒一致性研究[D].上海:上海交通大學(xué).2012:10. (LI D Q. Quantitative and robust consistency study of multi-individual system with network [D]. Shanghai: Shanghai Jiao Tong University, 2012: 10.)

[22]NEDIC A, OZDAGLAR A. Distributed subgradient methods for multi-agent optimization [J]. IEEE Transactions on Automatic Control, 2009, 54(1): 48-61.

[23]RAMS S S, NEDIC A, VEERAVALLI V V. Distributed stochastic subgradient projection algorithms for convex optimization [J]. Journal of Optimization Theory and Applications, 2011, 147(3): 516-545.

[25]SHI W, LING Q, WU G, et al. A proximal gradient algorithm for decentralized composite optimization [J]. IEEE Transactions on Signal Processing, 2015, 63(22): 6013-6023.