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

摘 要：針對(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é)論。

關(guān)鍵詞：時(shí)延；Push-sum算法；次梯度；分布式優(yōu)化

中圖分類號(hào)：TP13 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1672-1098（2015）02-0006-07

（School of Science， Anhui University of Science and Technology， Huainan Anhui 232001， China.）

Abstract：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.

Key words：time-varying delays； Push-sum algorithm； subgradient； distributed optimization

近年來，基于局部信息交互協(xié)同的整個(gè)網(wǎng)絡(luò)的優(yōu)化問題成為多個(gè)體網(wǎng)絡(luò)新的研究熱點(diǎn)[1-2]，因而引起了眾多學(xué)者的廣泛興趣。科學(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í)，這些方法均不再適用。endprint