分布式流言push-sum無(wú)梯度算法

李德權(quán)，王孝梅,馬 馳

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南，232001)

分布式流言push-sum無(wú)梯度算法

李德權(quán)，王孝梅,馬 馳

(安徽理工大學(xué)數(shù)學(xué)與大數(shù)據(jù)學(xué)院，安徽 淮南，232001)

研究多個(gè)體網(wǎng)絡(luò)中所有個(gè)體目標(biāo)函數(shù)之和最小值問(wèn)題，其中每個(gè)個(gè)體僅知其自身目標(biāo)函數(shù)且僅可與其鄰居個(gè)體交互信息。鑒于個(gè)體目標(biāo)函數(shù)通常非光滑，同時(shí)個(gè)體間單變量信息通信有一定局限性，本文提出一種分布式流言push-sum無(wú)梯度算法求解此優(yōu)化問(wèn)題。假設(shè)每個(gè)個(gè)體都具有一個(gè)服從泊松分布的控制時(shí)鐘，時(shí)鐘的每次轉(zhuǎn)動(dòng)表示隨機(jī)選擇的個(gè)體之間進(jìn)行信息更新。進(jìn)一步地，在網(wǎng)絡(luò)連通條件下證明了所提算法的收斂性。數(shù)值仿真結(jié)果表明，與現(xiàn)有的分布式流言無(wú)梯度優(yōu)化算法相比，本文算法具有更快的收斂速度。

多個(gè)體網(wǎng)絡(luò)；網(wǎng)絡(luò)優(yōu)化；分布式優(yōu)化；流言算法；push-sum算法；無(wú)梯度算法

近年來(lái)多個(gè)體網(wǎng)絡(luò)分布式優(yōu)化算法已成為研究熱點(diǎn)。眾多應(yīng)用領(lǐng)域問(wèn)題都可轉(zhuǎn)化為多個(gè)體網(wǎng)絡(luò)中的分布式優(yōu)化問(wèn)題，如：分布式控制、分布式信號(hào)處理、大規(guī)模機(jī)器學(xué)習(xí)和無(wú)線網(wǎng)絡(luò)分布式估計(jì)等。分布式優(yōu)化的目的是通過(guò)個(gè)體間局部交互信息求解關(guān)于整個(gè)網(wǎng)絡(luò)目標(biāo)函數(shù)的最小值，目前解決此類(lèi)問(wèn)題的一種經(jīng)典方法是流言算法。例如，Iutzeler等[1]針對(duì)無(wú)線傳感器網(wǎng)絡(luò)，結(jié)合權(quán)重結(jié)構(gòu)和廣播流言的特性,深入分析了Sum-Weight-like算法中初始值均值的收斂性，認(rèn)為其平方誤差隨時(shí)間呈指數(shù)級(jí)下降；Khosravi等[2]基于流言算法求解傳感器網(wǎng)絡(luò)中強(qiáng)連通拓?fù)浣Y(jié)構(gòu)下初始狀態(tài)的確切平均值，數(shù)值仿真結(jié)果表明，該算法在傳輸次數(shù)、收斂速度和精度等方面具有優(yōu)勢(shì)；Lu等[3]使用Pairwise Equalizing和Pairwise Bisectioning兩種流言算法求解時(shí)變無(wú)向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下無(wú)約束的、可分的、一致凸性的優(yōu)化問(wèn)題，其中每個(gè)個(gè)體函數(shù)是嚴(yán)格凸性的、連續(xù)可微的且有一個(gè)極小值；Aysal等[4]探討用于單變量信息通信的廣播流言算法，并證明了該算法的收斂性。需要指出的是，文獻(xiàn)[1-4]的研究主要基于個(gè)體間利用單變量信息通信達(dá)成一致，但單變量信息通信僅在有向平衡網(wǎng)絡(luò)中才能確保所有個(gè)體狀態(tài)達(dá)成平均一致性。實(shí)際應(yīng)用中，由于個(gè)體自身儲(chǔ)存能量有限或感知能力的不同，導(dǎo)致網(wǎng)絡(luò)往往是時(shí)變、非平衡的，故有向平衡網(wǎng)絡(luò)的條件難以保證。為了克服這一不足，F(xiàn)ranceschelli等[5]提出利用雙變量信息通信，即push-sum機(jī)制確保所有個(gè)體達(dá)成平均一致性，其中一個(gè)變量表示個(gè)體狀態(tài)估計(jì)的平均值，另一個(gè)變量表示個(gè)體的加權(quán)平均值，且每次迭代交互的信息是兩個(gè)變量的比值。張曉倩[6]提出了多個(gè)體系統(tǒng)分布式push-sum次梯度優(yōu)化算法，該算法中個(gè)體間同步進(jìn)行信息交流，即所有個(gè)體同時(shí)進(jìn)行更新迭代，因此個(gè)體間需要相互等待。

目前分布式優(yōu)化多是在網(wǎng)絡(luò)中個(gè)體目標(biāo)函數(shù)次梯度存在或易于計(jì)算這一關(guān)鍵假設(shè)下進(jìn)行研究的，但實(shí)際中存在大量個(gè)體目標(biāo)函數(shù)次梯度難以計(jì)算的情況[7-8]。無(wú)梯度算法采用高斯近似函數(shù)代替原來(lái)的目標(biāo)函數(shù)，可有效避免目標(biāo)函數(shù)次梯度的計(jì)算，因而適用范圍更廣。

本文基于隨機(jī)流言算法[9]和無(wú)梯度算法[7]，并結(jié)合push-sum機(jī)制提出分布式流言push-sum無(wú)梯度(distributed gossip-based push-sum gradient-free，DGPSGF)算法來(lái)求解多個(gè)體網(wǎng)絡(luò)優(yōu)化問(wèn)題，并對(duì)該算法在遞減步長(zhǎng)下的收斂性進(jìn)行證明，最后通過(guò)數(shù)值仿真驗(yàn)證該算法的有效性。

1 符號(hào)說(shuō)明

多個(gè)體網(wǎng)絡(luò)信息通信通常建模成有向圖G(k)=(V,E(k))，其中，V={1,2,…,n}表示網(wǎng)絡(luò)中個(gè)體的集合，E(k)={(i,j)|i,j∈V}表示個(gè)體間的有向邊集。N(i)表示個(gè)體i的鄰居集合，即N(i)={j∈V;{i,j}∈E(k)}。s(k)=[s1(k),s2(k),…,sn(k)]T表示個(gè)體在k時(shí)刻的狀態(tài)，‖s‖表示向量s的范數(shù)，E(s)表示向量期望，f(s)表示函數(shù)f(s)在s處的梯度。

2 問(wèn)題描述

本文考慮由n個(gè)個(gè)體構(gòu)成的多個(gè)體網(wǎng)絡(luò)，目的是個(gè)體間相互合作解決以下分布式優(yōu)化問(wèn)題：

(1)

其中fi(s):Rm→R表示個(gè)體i的目標(biāo)函數(shù)，每個(gè)個(gè)體僅知其自身的目標(biāo)函數(shù)。

設(shè)最優(yōu)解集為S*，當(dāng)所有個(gè)體狀態(tài)s1=s2=…=sn=s*∈S*時(shí)，則所有個(gè)體狀態(tài)達(dá)成一致，且f(s*)為優(yōu)化問(wèn)題(1)的最優(yōu)解。由于fi(s)的次梯度難以計(jì)算或不存在，為此本文采用一種無(wú)需計(jì)算每個(gè)個(gè)體目標(biāo)函數(shù)次梯度的方法來(lái)求解網(wǎng)絡(luò)優(yōu)化問(wèn)題。

3 算法介紹

3.1 異步時(shí)間網(wǎng)絡(luò)模型

3.2 假設(shè)條件

假設(shè)1Fk+1表示算法迭代到Zk時(shí)刻的一個(gè)σ域,即Fk+1={xi(0);i∈V}∪{Il,Jl;0≤l≤k+1}

假設(shè)2G(k)=(V,E(k))是連通圖，個(gè)體i隨機(jī)選擇鄰居的過(guò)程是獨(dú)立同分布的且選擇的概率為πji>0(當(dāng)j?N(i)時(shí),πji=0)。

3.3分布式流言push-sum無(wú)梯度算法

DGPSGF算法依據(jù)以下規(guī)則進(jìn)行迭代更新：

當(dāng)k>0、i?{Ik,Jk}時(shí)，xi(k)=xi(k-1)；否則,

si(k)=zi(k)/wi(k)

xi(k)=zi(k)-ηi(k)Gi(k)

式中：xi(k)是個(gè)體i在k時(shí)刻的狀態(tài)值；ηi(k)是逐漸遞減的迭代步長(zhǎng)；隨機(jī)無(wú)梯度預(yù)測(cè)值Gi(k)可表示為[10]

為便于分析，給出DGPSGF算法的另一個(gè)形式。首先定義非負(fù)矩陣A(k)=[aij(k)]∈Rn×n(aij(k)≥0)如下：

(2)

(3)

si(k)=zi(k)/wi(k)

(4)

xi(k)=zi(k)-ηi(k)Gi(k)i∈{Ik,Jk}

(5)

引理1[7]令G0(fi)是fi(s)的Lipschitz常數(shù)，對(duì)每一個(gè)i∈V有以下結(jié)論成立：

E[Gi(k)|Fk+1]=

(3) 隨機(jī)無(wú)梯度預(yù)測(cè)值Gi(k)滿(mǎn)足

4 收斂性分析

設(shè)s*∈Rn是任意向量，則有

(6)

參照文獻(xiàn)[11]可得：

(7)

將式(7)代入式(6)整理得：

證明：參照文獻(xiàn)[1]推得

(8)

此外，參照文獻(xiàn)[12]可得

(9)

證畢。

(10)

其中ηmax是個(gè)體i的最大步長(zhǎng)。

證明：由引理3和引理4得

(11)

(12)

當(dāng)ρ(R)<1且T→時(shí)，由式(12)可推得式(10)成立，證畢。

5 仿真實(shí)驗(yàn)分析

前面已理論上證明了DGPSGF算法求解優(yōu)化問(wèn)題(1)的收斂性。下面通過(guò)仿真實(shí)驗(yàn)來(lái)驗(yàn)證該算法的有效性，為此考慮一個(gè)具體的多個(gè)體優(yōu)化問(wèn)題[7]：

(a) (b) (c)

圖1隨機(jī)網(wǎng)絡(luò)(n=3)

Fig.1Randomnetworkwiththreeagents

(a)u=3.5×10-6

(b)u=3.5×100.5

圖3采用DGGF和DGPSGF算法的目標(biāo)函數(shù)誤差值對(duì)比

Fig.3ComparisonofobjectivefunctionerrorsbyDGGFandDGPSGFalgorithmsrespectively

6 結(jié)語(yǔ)

針對(duì)時(shí)變網(wǎng)絡(luò)中個(gè)體目標(biāo)函數(shù)具有非光滑性以及分布式單變量信息通信算法的局限性，本文提出分布式流言push-sum無(wú)梯度(DGPSGF)算法求解網(wǎng)絡(luò)優(yōu)化問(wèn)題。假設(shè)每個(gè)個(gè)體都具有一個(gè)服從泊松分布的控制時(shí)鐘，時(shí)鐘的每次轉(zhuǎn)動(dòng)表示隨機(jī)選擇的個(gè)體之間進(jìn)行信息更新，進(jìn)而在網(wǎng)絡(luò)連通的假設(shè)下，證明了該算法在遞減步長(zhǎng)下的收斂性。DGPSGF算法無(wú)需計(jì)算時(shí)變網(wǎng)絡(luò)中個(gè)體目標(biāo)函數(shù)的次梯度，且可有效克服單變量信息通信算法的局限性，因而更具實(shí)用性，并且與現(xiàn)有的分布式流言無(wú)梯度算法相比，本文算法具有更快的收斂速度。

[1] Iutzeler F, Ciblat P, Hachem W. Analysis of Sum-Weight-like algorithms for averaging in wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2013,61(11):2802-2814.

[2] Khosravi A, Kavian Y S. Broadcast gossip ratio consensus: asynchronous distributed averaging in strongly connected networks[J]. IEEE Transactions on Signal Processing, 2017,65(1):119-129.

[3] Lu J, Tang C Y, Regier P R, et al. Gossip algorithms for convex consensus optimization over networks[J]. IEEE Transactions on Automatic Control, 2011,56(12):2917-2923.

[4] Aysal T C, Yildiz M E, Sarwate A D, et al. Broad-cast gossip algorithms for consensus[J]. IEEE Transactions on Signal Processing, 2009,57(7):2748-2761.

[5] Franceschelli M, Giua A, Seatzu C. Distributed averaging in sensor networks based on broadcast gossip algorithms[J]. IEEE Sensors Journal,2011,11(3):808-817.

[6] 張曉倩. 多個(gè)體系統(tǒng)分布式Push-sum次梯度優(yōu)化算法的研究[D]. 淮南：安徽理工大學(xué), 2015.

[7] Nesterov Y, Spokoiny V. Random gradient-free minimization of convex function[J]. Foundations of Computational Mathematics,2017,17(2):527-566.

[8] Com A R, Scheinberg K, Vicente L N. Introduction to derivative-free optimization, MPS-SIAM series on optimization[M]. Philadelphia: Society for Industrial and Applied Mathematics, 2009.

[9] Boyd S, Ghosh A, Prabhakar B, et al. Randomized gossip algorithms[J]. IEEE Transactions on Information Theory,2006,52(6):2508-2530.

[10] Yuan Deming. Asynchronous gossip-based gradient-free method for multiagent optimization[J]. Abstract and Applied Analysis, 2014, Vol.2014: Article ID 618641.

[責(zé)任編輯尚晶]

Distributedgossip-basedpush-sumgradient-freealgorithm

LiDequan,WangXiaomei,MaChi

(School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan 232001, China)

This paper studies how to collaboratively minimize the whole objective function of the multi-agent network, wherein each agent just knows its own objective function and only interacts with its neighboring agents. Because each agent’s local objective function is usually non-smooth and the method of single variable information communication among agents has some limitations, a distributed gossip-based push-sum gradient-free (DGPSGF) algorithm is proposed to solve this optimization problem. It is assumed that each agent has a local Poisson clock, and at each tick of its clock rotation, the agent interacts with randomly selected agents. Furthermore, the convergence of DGPSGF algorithm is proved under the mild assumption on the network connectivity. Numerical simulation results show that, compared with the existing distributed gossip-based gradient-free algorithm, the proposed DGPSGF algorithm has faster convergence rate.

multi-agent network; network optimization; distributed optimization; gossip algorithm; push-sum algorithm; gradient-free algorithm

TP13

A

1674-3644(2017)06-0472-06

2017-07-26

國(guó)家自然科學(xué)基金資助項(xiàng)目(61472003)；高校學(xué)科(專(zhuān)業(yè))拔尖人才學(xué)術(shù)資助重點(diǎn)項(xiàng)目(gxbjZD2016049)；安徽省學(xué)術(shù)和技術(shù)帶頭人及后備人選科研活動(dòng)經(jīng)費(fèi)資助項(xiàng)目(2016H076).

李德權(quán)(1973-)，男，安徽理工大學(xué)教授，博士.E-mail：leedqcpp@126.com

10.3969/j.issn.1674-3644.2017.06.012