時(shí)延情形下的分布式隨機(jī)無梯度優(yōu)化算法

任芳芳+李德權(quán)

摘要：由于多個(gè)體系統(tǒng)在信息交流的過程中存在通信時(shí)延，系統(tǒng)會(huì)出現(xiàn)接收信息滯后的情況，從而影響優(yōu)化算法的收斂速度。為了解決時(shí)延對(duì)優(yōu)化算法產(chǎn)生的影響， 提出了時(shí)延情形下的多個(gè)體系統(tǒng)分布式隨機(jī)無梯度優(yōu)化算法。假定系統(tǒng)中每個(gè)個(gè)體僅知道其自身的局部目標(biāo)函數(shù)，利用系統(tǒng)中個(gè)體間交互時(shí)延信息來尋求這些局部目標(biāo)函數(shù)之和的最小值， 通過系統(tǒng)擴(kuò)維將有時(shí)延的優(yōu)化問題轉(zhuǎn)化為無時(shí)延的優(yōu)化問題。由于個(gè)體的局部目標(biāo)函數(shù)有可能非凸故其次梯度不一定存在或很難計(jì)算，因而采用分布式隨機(jī)無梯度方法。理論分析表明只要個(gè)體間的通信時(shí)延有上界，所提算法依然收斂。

關(guān)鍵詞：多個(gè)體系統(tǒng)；分布式優(yōu)化；隨機(jī)無梯度；通信時(shí)延

中圖分類號(hào)：TP13 文獻(xiàn)標(biāo)志碼：A文章編號(hào)：1672-1098（2016）01-0034-06

Abstract：Considering the delay of information communication among agents， which affect the convergence speed of the algorithm， the randomized gradient-free method for multi-agent optimization with communication delay was proposed， where its assumed that every agent only knows its own local objective function. The optimization goal is to minimize a sum of local objective functions through the interaction of delay information among agents in the system. Firstly， the optimization problem with delay was converted into the optimization problem without delay through augmenting delay nodes. Because the local objective function of agent is likely to be nonconvex， its subgradient does not exist or it is hard to be calculated， the distributed randomized gradient-free method was used. The theoretical analysis showed that the proposed algorithm is still convergent if the communication delays are upper bounded.

Key words：multi-agent system； distributed optimization； randomized gradient-free， communication delay

近年來，多個(gè)體分布式凸優(yōu)化問題及其優(yōu)化算法引起了人們的廣泛關(guān)注，而多個(gè)體分布式優(yōu)化算法是在集總式算法的基礎(chǔ)上發(fā)展起來的。所謂集總式算法是指在多個(gè)體系統(tǒng)中，不是所有個(gè)體都發(fā)揮同樣的作用，只有某個(gè)個(gè)體處于中心地位，負(fù)責(zé)處理其他個(gè)體的數(shù)據(jù)，并將數(shù)據(jù)反饋給其他個(gè)體。和集總式算法不同，分布式算法則是指多個(gè)體系統(tǒng)中的每個(gè)個(gè)體都對(duì)應(yīng)著一個(gè)局部凸目標(biāo)函數(shù)，并且個(gè)體之間進(jìn)行信息交流，最終求得凸目標(biāo)函數(shù)的最小值。和以往的集總式算法相比，分布式算法有很多優(yōu)點(diǎn)，尤其在許多大規(guī)模的優(yōu)化問題中占有很大優(yōu)勢(shì)，并且在生物工程、人工智能等許多領(lǐng)域有廣泛應(yīng)用，因此研究多個(gè)體的分布式優(yōu)化算法有很大的意義。

隨著計(jì)算機(jī)的廣泛應(yīng)用，人們進(jìn)入了大數(shù)據(jù)云計(jì)算的時(shí)代，因此對(duì)多個(gè)體分布式優(yōu)化的研究也越來越深入。但這些方法主要是標(biāo)準(zhǔn)次梯度和一致性算法的結(jié)合。標(biāo)準(zhǔn)次梯度算法是將總的最優(yōu)化任務(wù)分解，同時(shí)每個(gè)個(gè)體需要將自身的信息與周圍鄰居個(gè)體的信息進(jìn)行加權(quán)組合，再根據(jù)自身的次梯度信息進(jìn)行最優(yōu)化，經(jīng)過一系列的迭代運(yùn)算，使得所有個(gè)體的狀態(tài)都達(dá)到一致。事實(shí)上，一致性算法也是廣泛研究的一個(gè)課題，即個(gè)體間通過信息交流使所有個(gè)體的狀態(tài)最終達(dá)到一致并使結(jié)果達(dá)到最優(yōu)。文獻(xiàn)[1]最早給出了標(biāo)準(zhǔn)次梯度方法并分析了其收斂性。文獻(xiàn)[2]922介紹了約束一致性和優(yōu)化算法。在此基礎(chǔ)上，文獻(xiàn)[3]則介紹了基于隨機(jī)投影的次梯度算法，文獻(xiàn)[4]1715給出一種基于一致性算法的原始對(duì)偶次梯度方法。在文獻(xiàn)[4]1720的啟發(fā)下，文獻(xiàn)[5-6]提出了一種分布式對(duì)偶平均算法（DDA）以及基于Push-sum的DDA算法。上述研究都是適用于多個(gè)體系統(tǒng)中的每個(gè)個(gè)體對(duì)應(yīng)的局部目標(biāo)函數(shù)存在凸函數(shù)且次梯度的情況。而文獻(xiàn)[7-8]研究的是個(gè)體的局部目標(biāo)函數(shù)是非凸的、次梯度不存在或很難計(jì)算的情況，因此文獻(xiàn)[9]提出了一種分布式隨機(jī)無梯度優(yōu)化算法。

然而，以上都是假設(shè)在任何時(shí)刻每個(gè)個(gè)體都可以即時(shí)的和周圍個(gè)體之間進(jìn)行信息交流。而在文獻(xiàn)[10-12]1108中，由于有限的帶寬，隨機(jī)的傳輸延遲以及不確定的連接拓?fù)?，個(gè)體之間的信息交流可能出現(xiàn)延時(shí)的情況。為此，文獻(xiàn)[12]1139給出了時(shí)延情形下的分布式次梯度優(yōu)化算法以及具有通信時(shí)延的二階系統(tǒng)一致性。

本文主要研究時(shí)延情形下的分布式隨機(jī)無梯度優(yōu)化算法。

1符號(hào)說明

網(wǎng)絡(luò)中個(gè)體間的信息通信通常可以建模成一個(gè)有向圖G（k）=（V，E（k），P（k）），其中V=（1，2，…，n）表示個(gè)體集合，n表示個(gè)體數(shù)目，E=（e1，e2，…，en）表示邊集，P（k）表示網(wǎng)絡(luò)拓?fù)鋱DG在k時(shí)刻的權(quán)重鄰接矩陣，并且G是一個(gè)有向圖[13]。令Rn為一個(gè)n維向量空間，‖x‖為向量x的歐幾里得范數(shù)，ΠX[x]表示向量x到集合X上的歐幾里得投影，[x]i表示向量x的第i個(gè)分量，xT表示向量x的轉(zhuǎn)置，[P]ij代表矩陣P的第i行j列的元素，E[x]代表向量x的期望值。f（x）則表示函數(shù)f（x）在x處的梯度。

2問題描述

考慮如下由n個(gè)個(gè)體組成的多個(gè)體系統(tǒng)分布式凸優(yōu)化問題：

minx∈Rmh（x）=∑ni=1hi（x） （1）

這里h（x）為目標(biāo)函數(shù)，x∈Rm是一個(gè)全局決策向量，hi∶Rm→R是個(gè)體i（i∈V）的自身目標(biāo)函數(shù)并僅為個(gè)體i知道，同時(shí)假設(shè)其是Lipschitz連續(xù)的且Lipschitz常數(shù)為G0（hi），XRm是非空閉凸集。式（1）表明整個(gè)系統(tǒng)的目標(biāo)函數(shù)可以分解成系統(tǒng)中各個(gè)個(gè)體自身目標(biāo)函數(shù)之和。

考慮每個(gè)hi不一定是光滑的且可能是非凸函數(shù)。因此其次梯度不存在或很難計(jì)算。故已有相關(guān)基于次梯度的分布式優(yōu)化算法對(duì)本文不再適用。為此，用一個(gè)高斯函數(shù)hiμi 來近似代替hi，此時(shí)式（1）的光滑版本如下：

minx∈Xhu（x）=∑ni=1hiui （x） （2）

這里hiui （x）是hi（x）的高斯近似[7]1116且滿足：

hiui （x）=1ω∫Rmhi（x+μiξ）e-12‖ξ‖2dξ （3）

這里ω=∫Rme-12‖ξ‖2dξ=（2π）m2，μi代表函數(shù)fiμi 的光滑系數(shù)，是一個(gè)非負(fù)標(biāo)量，ξ是隨機(jī)向量。

3算法介紹

31DRGF法

在實(shí)際情況中，由于多個(gè)體在信息交流的過程中存在通信時(shí)延，為此提出如下的時(shí)變時(shí)延情形下的分布式隨機(jī)無梯度優(yōu)化算法（DRGF法）。

1） 初始化

① 選擇一個(gè)隨機(jī)向量xi（0）∈X，x∈X；

② 對(duì)每一個(gè)i，用高斯分布的方式生成一個(gè)局部隨機(jī)序列{ξki}k≥0。

2） 迭代

① 計(jì)算平均權(quán)重θi（k+1）=∑nj=1[Φ（k）ij]xj（k-cji（k））=∑n（q+1）j=1[Φ（k）ij]xj；

② 計(jì)算xi（k+1）=ΠX[θi（k+1）-ηkgui（xi（k））]，這里ΠX[x]代表向量x到集合X上的投影，通過投影將約束集中的個(gè)體與其他個(gè)體分開，只討論在約束集中的個(gè)體。

這里的ηk>0是迭代步長，且步長滿足：

ηk>0，∑∞k=0ηk=∞，∑∞k=0η2k<∞。

隨機(jī)無梯度的預(yù)測(cè)值可表示為：

gui（xi（k））=

hi（xi（k）+uiξi（k））-hi（xi（k））uiξi（k）

32系統(tǒng)擴(kuò)維

為了方便研究時(shí)延情形下的分布式隨機(jī)無梯度優(yōu)化算法的收斂性，下面將介紹如何利用系統(tǒng)擴(kuò)維把有時(shí)延的優(yōu)化問題轉(zhuǎn)化為無時(shí)延的優(yōu)化問題。在網(wǎng)絡(luò)圖G（k）中增加一些虛擬節(jié)點(diǎn)（見圖1），這些節(jié)點(diǎn)的作用只是為了消耗信息在系統(tǒng)傳遞中的時(shí)延，自身沒有自環(huán)。和增加的虛擬節(jié)點(diǎn)相比，網(wǎng)絡(luò)中真實(shí)存在的點(diǎn)不僅可以傳遞信息，自己也可以處理信息。因此可以看出，虛擬節(jié)點(diǎn)只起到信息傳遞的作用，而不參與算法的迭代。

由于每個(gè)時(shí)刻通信網(wǎng)絡(luò)每條邊上的時(shí)延cij（k）都是不同的，所以令q=max ij。原來系統(tǒng)中的n個(gè)節(jié)點(diǎn)增加nq個(gè)節(jié)點(diǎn)即擴(kuò)維后的多個(gè)體系統(tǒng)，共有n+nq個(gè)節(jié)點(diǎn)。為了不影響優(yōu)化式（1），假設(shè)新增的時(shí)延個(gè)體所對(duì)應(yīng)的局部目標(biāo)函數(shù)值均為零。系統(tǒng)擴(kuò)維后的權(quán)重矩陣為Φ（k）=[Φ1（k），Φ2（k）]T，其中[Φ1（k）]i，nl+j=（Φ（k））ij，l=cij（k）

0，otherwise，Φ2（k）=[Inq，0nq×n]，對(duì)于任意的l=1，2…q，i，j∈I，可以看出Φ（k）仍為行隨機(jī)矩陣，但其主對(duì)角元素已不再是全部為正，因此無時(shí)延情形下的文獻(xiàn)[7]，[8]，[13]的方法對(duì)本文都不再適用。

4收斂性分析

首先，做出如下假設(shè)：

假設(shè)1對(duì)于有向圖G以及任意有向邊上的時(shí)變時(shí)延cij（k），有：

1）有向圖G是強(qiáng)連通圖，其所對(duì)應(yīng)的鄰接矩陣Φ（k）是行隨機(jī)的，而不一定是雙隨機(jī)的；

2）假設(shè)0≤cij（k）≤ij（k）<∞，即時(shí)變時(shí)延有界，令q=max（vi，vj）∈Eij

為了方便分析DRGF算法的收斂性，給出下列引理：

引理1[7]1 122對(duì)每一個(gè)i∈V有以下結(jié)論成立：

1） hiui （x）是可微凸集并且滿足：

hi（x）≤hiui （x）≤muiG0（hi）

2） 梯度hiui （xi（k））滿足：

E[giuixi（k）|Hk]=hiui （xi（k））

3）隨機(jī)無梯度的預(yù)測(cè)值gui（xi（k））滿足：

E[giui xi（k）|Hk]≤（m+4）2G20 （hi）

引理2[2]777令Ψ（k·s）=[Φ（k）Φ（k-1），…Φ（s）]，則可得以下結(jié)論：

1） 當(dāng)k→+∞時(shí)，Ψ（k，s）的每一列[Ψ（k，s）]j收斂到一個(gè)正向量j（s）1，即：limk→+∞（[Ψ（k，s）]j-j（s）1）=0對(duì)所有j∈{1，2，…，n（q+1）}都成立。這里j（s）>0且∑n（q+1）j=1j（s）=1。

2） 存在一個(gè)正整數(shù)ν和一個(gè)非負(fù)數(shù)0≤α<1，使得：‖[Ψ（k，s）]ij-j（s）‖≤（q+1）4n4αk-s-3M-MvMv‖Ψ（s，s）‖j對(duì)所有i，j∈{1，…，q}和所有k≥s成立。

定理1在假設(shè)1，引理1成立的情況下，用上述DRGF法生成一個(gè)序列{xi（k）}k≥0，這里假設(shè)每一個(gè)hi都是Lipschitz連續(xù)的， 則對(duì)每一個(gè)t≥1和 j∈V，有：

定理1給出了目標(biāo)函數(shù)的期望值E和最優(yōu)值h（x*）之間的誤差，不難看出，該誤差和個(gè)體數(shù)n，系統(tǒng)擴(kuò)維后增加的節(jié)點(diǎn)數(shù)nq，迭代步長η和Lipschitz常數(shù)有關(guān)。由定理1看出只要通信時(shí)延cij有上界，算法依然收斂。當(dāng)cij=0時(shí)，則轉(zhuǎn)化為無時(shí)延的情況。此外，還可以看出，時(shí)延情形下的迭代誤差比無時(shí)延的迭代誤差大，這表明若個(gè)體在信息交流的過程中存在通信時(shí)延，則會(huì)對(duì)個(gè)體間協(xié)同解決優(yōu)化問題造成一定的影響。

推論1當(dāng)假設(shè)1成立時(shí)，用上述方法生成一個(gè)序列{xi（k）}k≥0，步長為{ηk}k≥0且limk→∞ηk=。則有：

由推論1可以看出個(gè)體i在k時(shí)刻的狀態(tài)xi（k）收斂到k時(shí)刻所有個(gè)體狀態(tài)的平均值k。即此時(shí)多個(gè)體狀態(tài)達(dá)到平均一致。此外多個(gè)體優(yōu)化問題此時(shí)也取得最優(yōu)值。

定理2在上述引理1，引理2以及推論1成立的前提下，又假設(shè)：若limk→∞ηk=且=0，則∑∞k=0ηk=∞。則有如下結(jié)論成立：

lim supt→∞E[f（j（t））]≤m 0∑n（q+1）i=1μi+D0 （16）

其中D=（n（q+1））（m+5）2（92+2（n（（q+1））/B2（1-）））

證明首先易得：

∑∞k=0ηk=∞，limt→∞1∑t-1k=0ηk12∑n（q+1）i=1E[‖xi（0）-x*‖2]=0 （17）

且有：lim supk→∞∑t-1k=0η2k∑t-1k=0ηk≤lim supk→∞ηk=

則

lim supt→∞1∑t-1k=0ηk12（n（q+1））（m+4）2 20 ∑t-1k=0η2k≤

12（n（q+1））（m+4）220 （18）

將推論1中的結(jié)論帶入式（18）得

lim supt→∞1∑t-1k=0ηk（n（q+1））（m+

5）0∑t-1k=0ηkΩk≤2（n（q+1））（m+4）（m+

5）（2+n（q+1）α2（1-））20 （19）

利用定理1，將式（18）～式（19）帶入式（10），最終可得：

lim supt→∞E[h（j（t））]-h*≤m 0∑n（q+1））i=1ui+

12（n（q+1））（m+4）220 +2（n（q+1））（m+

4）（m+5）×（2+n（q+1）α2（1-））20 （20）

事實(shí)上，定理2表明誤差值lim supt→∞

E[h（j（t））]-h*是由兩個(gè)方面來決定的。一方面是式（7）中所呈現(xiàn)的誤差值，由于原始局部目標(biāo)函數(shù)hi（x）的次梯度不存在或很難計(jì)算，用高斯近似函數(shù)hiμi （x）來代替hi（x），從而導(dǎo)致了該誤差。另一方面，迭代步長在迭代的過程中逐步減小而ηk>0始終成立， 事實(shí)上， 當(dāng)ηk=0時(shí)， 式（17）右側(cè)變?yōu)閘im supt→∞E[h（j（t））]-h*≤m0∑n（q+1）i=1μi，可見此時(shí)的誤差值和約束集的維數(shù)m，lipschitz常數(shù)以及系統(tǒng)擴(kuò)維所增加的時(shí)延節(jié)點(diǎn)數(shù)nq有關(guān)。

6結(jié)束語

在文獻(xiàn)[2，7]的基礎(chǔ)上，本文研究了時(shí)延情形下的分布式隨機(jī)無梯度優(yōu)化算法。首先給出時(shí)延情形下的分布式隨機(jī)無梯度方法，然后通過系統(tǒng)擴(kuò)維將時(shí)延優(yōu)化問題轉(zhuǎn)化為無時(shí)延優(yōu)化問題，并利用轉(zhuǎn)移矩陣的相關(guān)結(jié)論分析并證明了其收斂性。當(dāng)然，還有一些問題有待解決，比如在無向圖網(wǎng)絡(luò)拓?fù)湎轮杏袝r(shí)延的隨機(jī)無梯度算法以及切換網(wǎng)絡(luò)下的優(yōu)化算法。

參考文獻(xiàn)：

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

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

[3]SUNDHAR RAM S， NEDI A， V VEERAVALLI V. Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization [J]. Journal of Optimization Theory & Applications， 2010， 147（3）：516-545.

[4]D Y，S X，H Z.Distributed Primal—Dual Subgradient Method for Multiagent Optimization via Consensus Algorithms[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics， 2011，41（6）：1 715-1 724.

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

[6]TSIANOS K I， LAWLOR S， RABBAT M G. Push-Sum Distributed Dual Averaging for convex optimization [C]// IEEE Conference on Decision & Control， 2012.

[7]NESTEROV Y. Random gradient-free minimization of convex functions [J]. General Information， international association for research and teaching， 2011， 36（16）：1 112-1 142

[8]LI J， WU C， WU Z， et al. Gradient-free method for nonsmooth distributed optimization [J]. Journal of Global Optimization， 2015， 61：325-340.

[9]YUAN D， HO D W C. Randomized Gradient-Free Method for Multiagent Optimization Over Time-Varying Networks [J]. IEEE Transactions on Neural Networks & Learning Systems， 2015， 26：1 342-1 347.

[10]TSIANOS K I， RABBAT M G. Distributed consensus and optimization under communication delays[C]//49th Annual Allerton Conference on Communication， Control， and Computing， 2011：974-982.

[11]李德權(quán)，張曉倩. 時(shí)延情形下的分布式Push-sum 次梯度優(yōu)化算法的研究[J].安徽理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2015，35（2）：6-12.

[12]劉德進(jìn)， 劉成林. 具有通信時(shí)延的離散時(shí)間二階多個(gè)體網(wǎng)絡(luò)的一致性問題[J]. 控制理論與應(yīng)用， 2010， 27（8）：1 108-1 158.

[13]A BONDY J，S R MURTY U，A BONDY J，et al. Graph Theory with Applications[J]. American Elsevier Publishing Co.inc.new York，1976，62（419）：379-381.