王孝梅 李德權(quán)

摘要：針對多個體網(wǎng)絡(luò)中個體信息交互常會出現(xiàn)數(shù)據(jù)丟包及個體目標函數(shù)次梯度難以計算或不存在的問題，提出數(shù)據(jù)丟包情形下分布式無梯度Push-sum算法，該算法要求網(wǎng)絡(luò)的權(quán)矩陣為列隨機而無需是雙隨機。通過增加虛擬節(jié)點進行系統(tǒng)擴維，從而建立一個有限的非均勻的馬爾可夫鏈，并結(jié)合遍歷性系數(shù)的結(jié)論證明了所提算法的收斂性。研究表明：收斂誤差值與高斯近似函數(shù)的光滑參數(shù)、目標函數(shù)的Lipschitz常數(shù)成正比，從而有效解決了數(shù)據(jù)丟包及個體目標函數(shù)次梯度不存在或難以計算的分布式優(yōu)化問題。

關(guān)鍵詞：多個體網(wǎng)絡(luò)；push-sum算法；無梯度；數(shù)據(jù)丟包

中圖分類號： TP13 文獻標志碼：A文章編號：1672-1098（2017）03-0023-08

Abstract：The problem of distributed optimization in unbalanced networks with data packet-dropping communication among the agents is investigated in this paper.Due to the fact that data packet-dropping may occur when agents communicate with each other in the multi-agent network and the subgradient of each agents local objective function is computationally infeasible or does not exist，this paper proposes a distributed Push-sum gradient-free optimization algorithm under the condition of data packet-dropping， which requires that the weight matrix associated with the multi-agent network be column stochastic but not necessarily doubly stochastic. By adding virtual nodes for system expansion， a finite inhomogenous Markov chain was obtained， and the convergence of the proposed method to an approximate solution was testified by combining results of ergodic coefficients，. It is shown that the error level of the convergence is proportional to the smoothing parameters of Gaussian approximation function and the Lipschitz constant of the objective function， so it can effectively solve the distributed optimization problem of data packet-dropping when the subgradient of each agents local objective function is computationally infeasible or does not exist.

Key words：multi-agent network； push-sum algorithm； gradient-free； data packet-dropping

近年來，伴隨著網(wǎng)絡(luò)、通信、計算機技術(shù)等的快速發(fā)展，多個體網(wǎng)絡(luò)的分布式優(yōu)化問題研究受到廣泛關(guān)注。多個體網(wǎng)絡(luò)是由一群具有感知、處理和通信能力的個體或子系統(tǒng)通過信息交流耦合成的網(wǎng)絡(luò)化系統(tǒng)。一類典型的網(wǎng)絡(luò)優(yōu)化問題要求網(wǎng)絡(luò)中個體通過信息傳遞協(xié)同解決關(guān)于整個網(wǎng)絡(luò)目標函數(shù)的優(yōu)化問題，其中每個個體僅知其自身的目標函數(shù)。這類網(wǎng)絡(luò)優(yōu)化問題解法通常分為集中式和分布式兩類。集中式要求多個體網(wǎng)絡(luò)中，存在一個個體作為中心個體，其他個體感知的信息必須傳遞給中心個體，再由中心個體反饋給其他個體來完成網(wǎng)絡(luò)優(yōu)化問題。而分布式則僅要求網(wǎng)絡(luò)中的每個個體只需與其鄰居個體交換信息。兩者相比，針對復(fù)雜大規(guī)模網(wǎng)絡(luò)計算問題，集中式求解耗時耗財且實用性較差；而分布式求解則較為靈活且在復(fù)雜環(huán)境下具有極強的魯棒性。因此分布式優(yōu)化近年來發(fā)展迅速且在眾多領(lǐng)域均有廣泛應(yīng)用，如信號處理[1]、電網(wǎng)[2]、大規(guī)模機械學(xué)習(xí)中的回歸與分類[3]等實際問題都可以歸類為多個體網(wǎng)絡(luò)分布式優(yōu)化問題。由于分布式優(yōu)化要求網(wǎng)絡(luò)中個體交互信息達成一致協(xié)同解決網(wǎng)絡(luò)優(yōu)化問題，因此分布式優(yōu)化方法主要是由標準次梯度算法和一致性算法構(gòu)成。文獻[4]介紹了標準次梯度算法，文獻[5]給出約束一致性算法?；谖墨I[4-5]提出了分布式原始對偶優(yōu)化算法[6]和分布式對偶優(yōu)化平均算法[7]。在此基礎(chǔ)上進而研究了分布式push-sum對偶平均優(yōu)化算法[8]。

上述文獻是在假設(shè)任意時刻下個體間都可以及時進行信息交流。而文獻[9-12]中，信息會因為通信鏈不可靠導(dǎo)致信息不能及時發(fā)送到接受端，即出現(xiàn)數(shù)據(jù)丟包的情況。因此數(shù)據(jù)丟包情形下的一致性算法及應(yīng)用引起了學(xué)者的關(guān)注。文獻[9]考慮通訊網(wǎng)絡(luò)圖是無向圖時，一條通信鏈出現(xiàn)數(shù)據(jù)丟包時直接影響兩方向的通訊，但是個體能及時發(fā)現(xiàn)且進行補救。文獻[10]則考慮通訊網(wǎng)絡(luò)是有向的，并提出兩種補救方法來解決數(shù)據(jù)丟包問題，但節(jié)點達成一致性的值不一定是平均值。而文獻[11]先通過設(shè)計校正迭代算法，每個節(jié)點再基于迭代計算修改狀態(tài)中的錯誤，進而重發(fā)信息作為一種減少數(shù)據(jù)丟包的有害影響。文獻[12]提出一種算法，該算法中個體通過建立一個有限的非均勻的馬爾可夫鏈解決了有向網(wǎng)絡(luò)中的數(shù)據(jù)丟包問題。

上述算法[9-13]都是在假設(shè)個體目標函數(shù)次梯度存在的前提下研究數(shù)據(jù)丟包。而個體目標函數(shù)的次梯度通常不存在或難以計算[14-16]，解決這一問題的一種有效方法就是采用無梯度法[17-19]。文獻[17]研究隨機無梯度算法的收斂性并說明了收斂速度與高斯近似函數(shù)的光滑參數(shù)、lipschitz常數(shù)有關(guān)。文獻[18]針對時變網(wǎng)絡(luò)拓撲情形，采用無梯度Push-sum算法來解決整個網(wǎng)絡(luò)的優(yōu)化問題并證明了算法的收斂性且收斂速度為O（LnTT）。文獻[19]研究了時延情形下的分布式隨機無梯度優(yōu)化算法，只要個體間的通信時延有上界，提出的優(yōu)化算法依然收斂。

為了解決通信中的數(shù)據(jù)丟包和個體目標函數(shù)非凸或非光滑問題，本文在文獻[12]的基礎(chǔ)上提出一種魯棒的分布式無梯度Push-sum算法，該算法可以有效地應(yīng)付通信中的數(shù)據(jù)丟包，并無需計算個體目標函數(shù)的次梯度。由于數(shù)據(jù)丟包，通信網(wǎng)絡(luò)所對應(yīng)的權(quán)矩陣是列隨機矩陣而無需是雙隨機矩陣。進而通過建立有限非均勻的馬爾可夫鏈，并結(jié)合遍歷性系數(shù)的相關(guān)結(jié)論證明算法的收斂性。

1符號說明

多個體網(wǎng)絡(luò)信息通信通?？山３捎邢驁DG（k）=（V，E（k）），其中V={1，2，…，n}表示網(wǎng)絡(luò)中個體的集合；n為個體的數(shù)目；E（k）={（i，j）|i，j∈V}表示個體間的有向邊集，dk∈Rn×n是權(quán)矩陣且非負，若（i，j）∈E（k）表示個體i發(fā)送信息給個體j則對應(yīng)的邊權(quán)[Dk]ij≥0，否則[Dk]ij=0；（i，i）表示個體i給自己發(fā)送信息。Nini （k）={j|（j，i）∈E（k）}，Nouti （k）={j|（i，j）∈E（k）}分別表示個體i的輸入鄰居集和輸出鄰居集（i∈Nini 且i∈Nouti），di（k）=|Nouti （k）|表示i的出度。令Rn為一個n維向量空間，E（x）表示向量的期望，f（x）代表函數(shù)f（x）在x處的梯度。

2問題描述

3算法介紹

3.1網(wǎng)絡(luò)模型

文獻[12]考慮存在通信數(shù)據(jù)丟包且目標函數(shù)次梯度存在的分布式優(yōu)化問題，而本文則討論個體目標函數(shù)次梯度難以計算或不存在及存在數(shù)據(jù)丟包的分布式優(yōu)化問題。因此，文獻[12]算法將對本文研究不再適用。為此本文提出數(shù)據(jù)丟包情形下分布式無梯度Push-sum算法。假定有向圖序列{G（k）}∞k=0 滿足下列假設(shè)。

3.2DPSGF法

本文提出數(shù)據(jù)丟包情形下分布式無梯度Push-sum算法（DPSGF法），除了考慮xi（k），zi（k），wi（k）外還需考慮出現(xiàn)數(shù)據(jù)丟包時發(fā)送端和接受端的權(quán)梯度和權(quán)。當(dāng)k≥0時，σi（k）和i（k）分別表示個體i已發(fā)送信息的權(quán)梯度和權(quán)；ρji（k）和ji（k）分別表示個體i已接受信息的權(quán)梯度和權(quán)。它們的初始值全為0。

式中：β=1maxDii∈V，γ=1-β2nB，B≥1，Di是i的出度。由定理1可以看出在T+1時刻所有個體狀態(tài)平均值的函數(shù)值近似收斂到最優(yōu)值，即所有個體狀態(tài)達成一致（s1=s2=…=sn=s*∈S*），同時表明誤差值limT→∞E[f（i（T+1））]-E[f（s*）]與高斯近似函數(shù)的光滑參數(shù)ui、lipschitz常數(shù)有關(guān)，即無梯度代替次梯度導(dǎo)致的懲罰項。5 結(jié)論與已有算法相比，該算法不僅可以有效地應(yīng)付時變非平衡網(wǎng)絡(luò)通信中的數(shù)據(jù)丟包，而且無需計算個體目標函數(shù)的次梯度，從而有效克服了個體目標函數(shù)的次梯度不存在或難以計算的問題。

參考文獻：

[1] OLSHEVSKY A.Efficient Information Aggregation Strategies for Distributed Control and Signal Processing[J].Mathematics，2010，56：345-356.

[2] RAM S S， VEERAVALLI V V， NEDIC A. Distributed Non-Autonomous Power C-ontrol through Distributed Convex Optimization[C]//IEEE. International Conference on Computer Communications. Pacific Grove：IEEE Xplore， 2009：3 001-3 005.

[3] D P BERTSEKAS，博塞卡斯. convex optimization algorithms[M].北京：清華大學(xué)出版社， 2016：33-79.

[4] NEDIC A，OZDAGLAR A.Distributed Subgradient Methods for Multi-Agent Opti-mization[J]. IEEE Transactions on Automatic Control， 2009， 54（1）：48-61.

[5] NEDIC A，OZDAGLAR A， PARRILO P A. Constrained Consensus and Optimizati-on in Multi-Agent Networks[J]. IEEE Transactions on Automatic Control， 2010，55 （4）：922-938.

[6] YUAN D， XU S， ZHAO H. Distributed Primal—Dual Subgradient Method for Multia-gent Optimization via Consensus Algorithms[J]. IEEE Transactions on Systems Man and Cybernetics Part B，2011，41（6）：1 715-1 724.

[7] DUCHI J C， AGARWAL A， WAINWRIGHT M J. Dual Averaging for Distributed Optimization： Convergence Analysis and Network Scaling[J]. IEEE Transactions on Automatic Control， 2011， 57（3）：592-606.

[8] TSIANOS K I， LAWLOR S， RABBAT M G. Push-Sum Distributed Dual Averaging for convex optimization[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：5 453-5 458.

[9] PATTERSON S， BAMIEH B， El ABBADI A. Distributed average consensus with s-tochastic communication failures[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2008：4 215-4 220.

[10] FAGNANI F， ZAMPIERI S. Average Consensus with Packet Drop Communication [J]. Siam Journal on Control and Optimization， 2009， 48（1）：102-133.

[11] CHEN Y， TRON R， TERZIS A， et al. Corrective consensus： Converging to the exa-ct average[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2010：1 221-1 228.

[12] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCI A D. Robust average consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.

[13] VAIDYA N H， HADJICOSTIS C N， DOMINGUEZ-GARCIA A D. Robust avera-ge consensus over packet dropping links： Analysis via coefficients of ergodicity[C]//IEEE Conference on Decision and Control. Singapore： IEEE， 2012：2 761-2 766.

[14] YU N. Random gradient-free minimization of convex functions[J]. Foundations of Computational Mathematics， 2011（1）：1-40.

[15] ORBAN， DOMINIQUE. Introduction to Derivative-Free Optimization[J]. Siam Re-view， 2011（2）：395-396.

[16] LI J， WU C， WU Z， et al. Gradient-free method for nonsmooth distributed optimiz-ation[J]. Journal of Global Optimization， 2014， 61（2）：325-340.

[17] YUAN D， HO D W. Randomized gradient-free method for multiagent optimization over time-varying networks[J]. IEEE Transactions on Neural Networks and Leanin-g Systems， 2015， 26（6）：1 342-1 347.

[18] YUAN D， XU S， LU J. Gradient-free method for distributed multi-agent optimizati-on via push-sum algorithms[J]. International Journal of Robust and Nonlinear Con-trol， 2015， 25（10）：1 569-1 580.

[19] 任芳芳， 李德權(quán). 時延情形下的分布式隨機無梯度優(yōu)化算法[J]. 安徽理工大學(xué)學(xué)報（自然科學(xué)版）， 2016， 36（1）：34-39.

（責(zé)任編輯：李 麗，編輯：丁 寒）