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

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

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

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

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

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

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

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

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

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

1 符號(hào)說明

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

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

subject toz∈Rd

(1)

當(dāng)個(gè)體間信息交互不存在通信時(shí)延時(shí)， 文獻(xiàn)[3]6 856提出一種Push-sum分布式次梯度優(yōu)化算法并分析了其收斂性。但由于網(wǎng)絡(luò)中信息的同步交互會(huì)引起網(wǎng)絡(luò)阻塞從而產(chǎn)生時(shí)延。因此，當(dāng)個(gè)體間信息通信存在時(shí)延時(shí)，針對(duì)式(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ò)中個(gè)體i在t時(shí)刻的狀態(tài)值；zi(t)為一個(gè)比值；A(t)=(aij(t))n×n為網(wǎng)絡(luò)拓?fù)渌鶎?duì)應(yīng)的隨機(jī)鄰接權(quán)矩陣；τij(t)為t時(shí)刻個(gè)體j到個(gè)體i的通信時(shí)延，當(dāng)所有τij(t)=0時(shí)，式(2)即退化為文獻(xiàn)[3]所研究的情形；εi(t)=-αi(t)gi(t)，i=1，…，n為第i個(gè)個(gè)體的攝動(dòng)；αi(t)為t時(shí)刻個(gè)體i的迭代步長(zhǎng)。

假設(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)是一個(gè)具有正對(duì)角線元素的隨機(jī)矩陣，即對(duì)所有i∈V和t≥0，一直成立aii=1-∑aij(t)>0；

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

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

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

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

(4)

3 時(shí)延情形下的Push-sum算法收斂性

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

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

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

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

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

證 明 由文獻(xiàn)[3]可知，無時(shí)延的Push-sum算法成立

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

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

則帶有時(shí)延的算法可以寫為

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

(5)

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

(7)

即定理1a得證。

(8)

證 明 因?yàn)?/p>

(9)

并且由定理1可知

(10)

所以推論1得證。

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

(11)

證 明 由式(10)可得

(12)

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

(13)

證明 由推論1可得下式

因?yàn)?/p>

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

4 仿真實(shí)驗(yàn)

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

設(shè)目標(biāo)函數(shù)以實(shí)數(shù)集上的二次函數(shù)為例，網(wǎng)絡(luò)中個(gè)體所對(duì)應(yīng)的函數(shù)fi(z)=(z-ai)2，ai∈R，i=1，2，3，增加的虛擬節(jié)點(diǎn)即時(shí)延個(gè)體所對(duì)應(yīng)的函數(shù)fj(z)=0，j=4，5，6，其中ai為隨機(jī)選取的實(shí)數(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軟件運(yùn)行有時(shí)延和無時(shí)延情形的Push-sum分布式次梯度優(yōu)化算法，繪制網(wǎng)絡(luò)的凸優(yōu)化目標(biāo)軌跡如圖2所示，該優(yōu)化算法在有時(shí)延和無時(shí)延的情況下均會(huì)收斂到最優(yōu)狀態(tài)，但有一定的誤差。圖2還表明由于存在通信時(shí)延，本文所提算法的收斂速度比文獻(xiàn)[3]中無時(shí)延情形的算法的收斂速度要慢。

5 結(jié)束語

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

[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é)基金資助項(xiàng)目(61472003)；國家自然科學(xué)青年基金資助項(xiàng)目(11401008)；安徽省教育廳自然科學(xué)研究重點(diǎn)資助項(xiàng)目(KJ2014A067)資助。

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

TP13

A

1672-1098(2015)02-0006-07