時延情形下分布式Push-sum次梯度優(yōu)化算法的研究

李德權(quán)，張曉倩

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

時延情形下分布式Push-sum次梯度優(yōu)化算法的研究

李德權(quán)，張曉倩

(安徽理工大學(xué)理學(xué)院，安徽 淮南 232001)

針對多個體系統(tǒng)在個體間進行信息交換時發(fā)生接收信息滯后，存在通信時延，影響優(yōu)化算法的收斂速度的問題，提出一種時延情形下的分布式Push-sum次梯度優(yōu)化算法，該方法在權(quán)矩陣不具有正對角線元素時仍適用，并應(yīng)用系統(tǒng)擴維的方法將有時延優(yōu)化問題轉(zhuǎn)化為無時延優(yōu)化問題。在時延和次梯度有界且有向切換網(wǎng)絡(luò)周期強連通的條件下，證明了所提出的分布式Push-sum次梯度優(yōu)化算法的收斂性。研究表明：存在通信時延時的算法收斂速度比無時延時的收斂速度要慢，并具有較大的收斂誤差。最后，通過數(shù)值仿真驗證了研究的結(jié)論。

時延；Push-sum算法；次梯度；分布式優(yōu)化

近年來，基于局部信息交互協(xié)同的整個網(wǎng)絡(luò)的優(yōu)化問題成為多個體網(wǎng)絡(luò)新的研究熱點[1-2]，因而引起了眾多學(xué)者的廣泛興趣?？茖W(xué)與工程領(lǐng)域的眾多問題，如大規(guī)模機器學(xué)習(xí)、分布式跟蹤與定位等，都可以歸類于多個體網(wǎng)絡(luò)分布式優(yōu)化問題。目前分布式優(yōu)化算法主要分為三種：原始優(yōu)化算法[3]6 857，對偶優(yōu)化算法，原始-對偶優(yōu)化算法，且這三種優(yōu)化算法通常解決的問題具有如下特點：整個網(wǎng)絡(luò)優(yōu)化的目標(biāo)函數(shù)可以分解成網(wǎng)絡(luò)中各個個體的目標(biāo)函數(shù)之和，每個個體僅知道其自身的目標(biāo)函數(shù)，且只能通過和其鄰居個體信息交互協(xié)同地解決整個網(wǎng)絡(luò)的問題，即此時所有個體狀態(tài)趨于一致且這個一致性值還是網(wǎng)絡(luò)優(yōu)化問題目標(biāo)函數(shù)的最優(yōu)解[4]。由于分布式優(yōu)化問題涉及到個體間的局部信息交互，因而與多個體網(wǎng)絡(luò)的一致性問題，特別是平均一致性(即每個個體狀態(tài)收斂到所有個體初始狀態(tài)的算術(shù)平均值)密切相關(guān)。目前一致性的研究主要分為基于單變量信息通信[5]和雙變量信息通信兩類。單變量信息通信即個體間交互的僅是某一個狀態(tài)變量，目前絕大部分多個體網(wǎng)絡(luò)一致性的研究是基于單變量信息通信，但其缺點是，只有有向平衡網(wǎng)絡(luò)中的個體才能達到平均一致性，這要求網(wǎng)絡(luò)對應(yīng)的鄰接矩陣必須是雙隨機矩陣，因而具有很大的局限性。但實際多個體網(wǎng)絡(luò)通常是動態(tài)切換、有向非平衡的，這就需要用到雙變量信息通信。因此，基于雙變量信息通信的Push-sum算法的一致性研究近年來引起學(xué)者的極大興趣，Push-sum一致性算法并不要求網(wǎng)絡(luò)是有向平衡的，但要求網(wǎng)絡(luò)中每個個體有兩個狀態(tài)變量，每次迭代交互的是這兩個狀態(tài)變量的比值。

當(dāng)個體間進行信息交換時，信息會因為網(wǎng)絡(luò)擁塞或受實際通信設(shè)備的影響，不能及時的送達接收端，即出現(xiàn)信息接收滯后的情況，這導(dǎo)致多個體網(wǎng)絡(luò)信息傳遞產(chǎn)生時延。因此對有時延的多個體網(wǎng)絡(luò)的一致性研究成為一個熱點。在時延有界的情況下，文獻[6-7]分別研究了一致性問題、受限一致性問題和平均一致性問題，其共同之處均是隨機鄰接矩陣需具有正對角元素，但當(dāng)隨機鄰接矩陣需不具有正對角元素時，這些方法均不再適用。

在上述文獻的基礎(chǔ)上，針對個體間信息交互存在通信時延情形的分布式優(yōu)化問題，本文提出一種分布式Push-sum次梯度優(yōu)化算法，首先通過增加虛擬的網(wǎng)絡(luò)節(jié)點即通過系統(tǒng)擴維的方法，將有通信時延的優(yōu)化問題轉(zhuǎn)化為無通信時延的優(yōu)化問題。在時延、次梯度有界和有向網(wǎng)絡(luò)一致強連通的條件下，證明了所提出的Push-sum次梯度優(yōu)化算法的收斂性。研究表明所提算法的收斂速度比無時延情形慢且有較大的收斂誤差，亦即當(dāng)個體間通信時延有界時所有個體會收斂到最優(yōu)解，但是時延影響了個體達到最優(yōu)解的速度。

1 符號說明

2 具有時延的優(yōu)化問題

在具有n個個體的有向切換網(wǎng)絡(luò)中，每個個體有其自身的凸函數(shù)fi(zi(t))：Rd→R，其中zi∈Rd的為決策變量?？紤]以下關(guān)于整個網(wǎng)絡(luò)的凸優(yōu)化問題：

subject toz∈Rd

(1)

當(dāng)個體間信息交互不存在通信時延時， 文獻[3]6 856提出一種Push-sum分布式次梯度優(yōu)化算法并分析了其收斂性。但由于網(wǎng)絡(luò)中信息的同步交互會引起網(wǎng)絡(luò)阻塞從而產(chǎn)生時延。因此，當(dāng)個體間信息通信存在時延時，針對式(1)提出如下的Push-sum次梯度優(yōu)化算法，其迭代格式如下：

zi(t+1)=wi(t+1)/yi(t+1)

xi(t+1)=wi(t+1)+εi(t+1)

(2)

式中：wi(t)∈R，yi(t)∈R，xi(t)∈R，xi∈R(1，…，n)為網(wǎng)絡(luò)中個體i在t時刻的狀態(tài)值；zi(t)為一個比值；A(t)=(aij(t))n×n為網(wǎng)絡(luò)拓撲所對應(yīng)的隨機鄰接權(quán)矩陣；τij(t)為t時刻個體j到個體i的通信時延，當(dāng)所有τij(t)=0時，式(2)即退化為文獻[3]所研究的情形；εi(t)=-αi(t)gi(t)，i=1，…，n為第i個個體的攝動；αi(t)為t時刻個體i的迭代步長。

假設(shè)初始條件wi(0)=1，zi(0)=1，yi(0)=1，i=1，…，n。則式(2)表示為以下矩陣形式：

w(t+1)=A(t)x(t-τ(t))

y(t+1)=A(t)y(t-τ(t))

zi(t+1)=wi(t+1)/yi(t+1)

x(t+1)=w(t+1)+ε(t+1)

(3)

假設(shè)：

1) 鄰接矩陣A(t)是一個具有正對角線元素的隨機矩陣，即對所有i∈V和t≥0，一直成立aii=1-∑aij(t)>0；

2) 每個個體的目標(biāo)函數(shù)fi(t)是凸函數(shù)且集合Z*=argminz∈RdF(z)非空；

3) 存在常數(shù)Li<∞使得‖gi‖2

4) 存在一個正整數(shù)B≥1，有向聯(lián)合圖(V，E(t)∪V，E(t+1)∪…∪V，E(t+B-1))，t≥1是強連通的；

對系統(tǒng)中每個個體的每個狀態(tài)變量進行重新定義，令

(4)

3 時延情形下的Push-sum算法收斂性

引理1[7]假設(shè)1、假設(shè)4成立，令Ψ(k，s)=[Φ(k)Φ(k-1)…Φ(s)]T，則可得以下結(jié)論：

b) 存在正整數(shù)v和0<α<1，對于任意的i，j∈{1，…，n(q+1)}和任意的k≥s，有下式成立：

‖[Ψ(t，s)]ij-φ(s)‖≤

定理1 對于序列{zi(t)}，i=1，…，n由式(4)迭代產(chǎn)生，假設(shè)1成立，有如下結(jié)論成立：

a) 存在δ>0，正整數(shù)v和0<α<1，有

證 明 由文獻[3]可知，無時延的Push-sum算法成立

w(t+1)=φ(t)1Tx(t)+(A(t，0)-

y(t+1)=φ(t)n+(A(t，0)-φ(t)1T)1

則帶有時延的算法可以寫為

各組計量資料以均數(shù)±標(biāo)準(zhǔn)差表示，兩組間采用t檢驗進行均值的比較；多組間采用單因素方差分析進行比較，數(shù)據(jù)分析使用SPSS統(tǒng)計分析軟件，P＜0.05為差異有統(tǒng)計學(xué)意義。

(5)

zi(t+1)=wi(t+1)/yi(t+1)，則有下面不等式成立

(7)

即定理1a得證。

(8)

證 明 因為

(9)

并且由定理1可知

(10)

所以推論1得證。

下面證明文中兩個重要的結(jié)論，即在通訊時延有界和其它假設(shè)成立的情況下Push-sum次梯度優(yōu)化算法的收斂性。

(11)

證 明 由式(10)可得

(12)

又根據(jù)文獻[3]6 859引理13可得

(13)

證明 由推論1可得下式

因為

由定理2～定理3可知，本文所提出的帶有時延的Push-sum次梯度優(yōu)化算法在有向切換網(wǎng)絡(luò)中是收斂的，且收斂速度取決于網(wǎng)絡(luò)中的個體數(shù)目n和時延上界q，而在無時延情形下可知收斂速度只取決于網(wǎng)絡(luò)中的個體數(shù)目n[6]。與文獻[6]中的收斂速度相比較，因為n，q≥1，所以帶有時延的算法收斂速度要稍慢，從整個多個體系統(tǒng)來看，雖然時延有界個體會收斂到最優(yōu)解，但是時延影響了個體達到最優(yōu)狀態(tài)的速度，使得系統(tǒng)運行效率降低，即在一般的多個體網(wǎng)絡(luò)中信息傳遞要比理想的、不帶時延的網(wǎng)絡(luò)中的信息傳遞要慢。

4 仿真實驗

在理論上已證明了時延對分布式優(yōu)化算法收斂性的影響，現(xiàn)將通過仿真驗證理論結(jié)論。假設(shè)有三個個體的周期切換網(wǎng)絡(luò)(見圖1)，并設(shè)周期B=3。在一個周期內(nèi)每個子圖都是非平衡且不連通的，但在一個周期內(nèi)這三個子圖的并是強連通的。

設(shè)目標(biāo)函數(shù)以實數(shù)集上的二次函數(shù)為例，網(wǎng)絡(luò)中個體所對應(yīng)的函數(shù)fi(z)=(z-ai)2，ai∈R，i=1，2，3，增加的虛擬節(jié)點即時延個體所對應(yīng)的函數(shù)fj(z)=0，j=4，5，6，其中ai為隨機選取的實數(shù)。假設(shè)在圖1a中各邊的權(quán)值為a11=0.8，a21=0.2，a22=a33=1，τ12=1；圖1b中a22=a23=0.5，a11=a33=1，τ32=1； 圖1c中a31=0.3，a33=0.7，

a11=a22=1，τ31=1。則權(quán)矩陣A(t)滿足假設(shè)1。

應(yīng)用MATLAB軟件運行有時延和無時延情形的Push-sum分布式次梯度優(yōu)化算法，繪制網(wǎng)絡(luò)的凸優(yōu)化目標(biāo)軌跡如圖2所示，該優(yōu)化算法在有時延和無時延的情況下均會收斂到最優(yōu)狀態(tài)，但有一定的誤差。圖2還表明由于存在通信時延，本文所提算法的收斂速度比文獻[3]中無時延情形的算法的收斂速度要慢。

5 結(jié)束語

針對存在通信時變時延情形的有向切換網(wǎng)絡(luò)的一類優(yōu)化問題，在文獻[6-7]的研究基礎(chǔ)上提出了時延Push-sum次梯度優(yōu)化算法次梯度優(yōu)化算法。并假設(shè)1～假設(shè)4成立且鄰接矩陣是列隨機矩陣時，證明了當(dāng)網(wǎng)絡(luò)中通信時延有界時所提出的分布式優(yōu)化算法收斂，并通過仿真驗證了所提算法的有效性。

[1]GHARESIFARDB，CORTESJ.Continuous-timedistributedconvexoptimizationonweight-balanceddigraphs[C]//51thIEEEAnnualConferenceon.DecisionandControl， 2012：7 451-7 456.

[2]TSIANOSKI，LAWLORS，RABBATMG.Consensus-baseddistributedoptimization：Practicalissuesandapplicationsinlarge-scalemachinelearning[C]//50thIEEEAnnualAllertonConferenceon.Communication，ControlandComputing(Allerton)， 2012：1 543-1 550.

[3]NEDICA，OLSHEVSKYA.Distributedoptimizationovertime-varyingdirectedgraphs[C]// 52thIEEEAnnualConferenceonDecisionandControl，2013.6 855-6 860.

[4]FIUTZELERF，CIBLATP，HACHEMW.AnalysisofSum-Weight-likealgorithmsforaveraginginWirelessSensorNetworks[J].IEEETransactionsonsignalprocessing， 2013，61(11)：2 802-2 814.

[5]DIMAKISADG，SARWATEAD，WAINWRIGHTMJ.Geographicgossip：Efficientaveragingforsensornetworks[J].IEEETransactionsonSignalProcessing， 2008，56(3)： 1 205-1 216.

[6]LINP，RENW.Distributedconstrainedconsensusinthepresenceofunbalancedswitchinggraphsandcommunicationdelays[C]//52thIEEEAnnualConferenceonDecisionandControl， 2012： 2 238-2 243.

[7]HADJICOSTISCN，CHARALAMBOUST.AverageConsensusinthePresenceofDelaysinDirectedGraphTopologies[J].IEEETransactionsonAutomaticControl， 2014， 59(3)：763-768.

[8]NEDICA，OZDAGLARA.Convergencerateforconsensuswithdelays[J].JournalofGlobalOptimization， 2010， 47(3)： 437-456.

(責(zé)任編輯：何學(xué)華)

Distributed Push-sum Subgradient Optimization Algorithm under Time-varying Communication Delay

LI De-quan，ZHANG Xiao-qian

(School of Science, Anhui University of Science and Technology, Huainan Anhui 232001, China.)

The distributed optimization problem in directed switching networks with time-varying delay communication among the agents was studied. Due to delay may happen when agents communicate with each other in the multi-agent system, this paper proposes a distributed Push-sum subgradient optimization algorithm in the context of communication delays, which will affect the convergence rate of optimization algorithm. Then based on state augmentation method, the analysis is carried out by reducing the optimization problem with delays to a problem without delays and this algorithm does not require the diagonal elements of the adjacency matrix are all positive.Under the assumptions that communication delays and the subgradients are bounded, and the switching directed networks are periodically strongly connected, we prove that the convergence of the proposed distributed Push-sum subgradient optimization algorithm. It is shown that the convergence rate in the case of communication delays is slower than that without communication delays, and meanwhile the proposed algorithm may bring out large convergence error. Finally, the conclusion is verified by numerical simulation.

time-varying delays; Push-sum algorithm; subgradient; distributed optimization

2014-12-16

國家自然科學(xué)基金資助項目(61472003)；國家自然科學(xué)青年基金資助項目(11401008)；安徽省教育廳自然科學(xué)研究重點資助項目(KJ2014A067)資助。

李德權(quán)(1973-)，男，安徽肥東人，教授，博士，研究方向：分布式優(yōu)化理論與應(yīng)用。

TP13

A

1672-1098(2015)02-0006-07