分布式流言push-sum無梯度算法

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

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

分布式流言push-sum無梯度算法

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

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

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

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

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

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

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

1 符號說明

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

2 問題描述

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

(1)

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

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

3 算法介紹

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

3.2 假設(shè)條件

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

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

3.3分布式流言push-sum無梯度算法

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

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

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

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

式中：xi(k)是個體i在k時刻的狀態(tài)值；ηi(k)是逐漸遞減的迭代步長；隨機無梯度預(yù)測值Gi(k)可表示為[10]

為便于分析，給出DGPSGF算法的另一個形式。首先定義非負(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ù)，對每一個i∈V有以下結(jié)論成立：

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

(3) 隨機無梯度預(yù)測值Gi(k)滿足

4 收斂性分析

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

(6)

參照文獻[11]可得：

(7)

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

證明：參照文獻[1]推得

(8)

此外，參照文獻[12]可得

(9)

證畢。

(10)

其中ηmax是個體i的最大步長。

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

(11)

(12)

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

5 仿真實驗分析

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

(a) (b) (c)

圖1隨機網(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ù)誤差值對比

Fig.3ComparisonofobjectivefunctionerrorsbyDGGFandDGPSGFalgorithmsrespectively

6 結(jié)語

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

[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] 張曉倩. 多個體系統(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

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

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

10.3969/j.issn.1674-3644.2017.06.012