時延情形下的分布式隨機無梯度優化算法

任芳芳+李德權

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

關鍵詞：多個體系統；分布式優化；隨機無梯度；通信時延

中圖分類號：TP13 文獻標志碼：A文章編號：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

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

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

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

本文主要研究時延情形下的分布式隨機無梯度優化算法。

1符號說明

網絡中個體間的信息通信通?？梢越３梢粋€有向圖G（k）=（V，E（k），P（k）），其中V=（1，2，…，n）表示個體集合，n表示個體數目，E=（e1，e2，…，en）表示邊集，P（k）表示網絡拓撲圖G在k時刻的權重鄰接矩陣，并且G是一個有向圖[13]。令Rn為一個n維向量空間，‖x‖為向量x的歐幾里得范數，ΠX[x]表示向量x到集合X上的歐幾里得投影，[x]i表示向量x的第i個分量，xT表示向量x的轉置，[P]ij代表矩陣P的第i行j列的元素，E[x]代表向量x的期望值。f（x）則表示函數f（x）在x處的梯度。

2問題描述

考慮如下由n個個體組成的多個體系統分布式凸優化問題：

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

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

考慮每個hi不一定是光滑的且可能是非凸函數。因此其次梯度不存在或很難計算。故已有相關基于次梯度的分布式優化算法對本文不再適用。為此，用一個高斯函數hiμi 來近似代替hi，此時式（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代表函數fiμi 的光滑系數，是一個非負標量，ξ是隨機向量。

3算法介紹

31DRGF法

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

1） 初始化

① 選擇一個隨機向量xi（0）∈X，x∈X；

② 對每一個i，用高斯分布的方式生成一個局部隨機序列{ξki}k≥0。

2） 迭代

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

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

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

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

隨機無梯度的預測值可表示為：

gui（xi（k））=

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

32系統擴維

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

由于每個時刻通信網絡每條邊上的時延cij（k）都是不同的，所以令q=max ij。原來系統中的n個節點增加nq個節點即擴維后的多個體系統，共有n+nq個節點。為了不影響優化式（1），假設新增的時延個體所對應的局部目標函數值均為零。系統擴維后的權重矩陣為Φ（k）=[Φ1（k），Φ2（k）]T，其中[Φ1（k）]i，nl+j=（Φ（k））ij，l=cij（k）

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

4收斂性分析

首先，做出如下假設：

假設1對于有向圖G以及任意有向邊上的時變時延cij（k），有：

1）有向圖G是強連通圖，其所對應的鄰接矩陣Φ（k）是行隨機的，而不一定是雙隨機的；

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

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

引理1[7]1 122對每一個i∈V有以下結論成立：

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

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

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

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

3）隨機無梯度的預測值gui（xi（k））滿足：

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

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

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

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

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

定理1給出了目標函數的期望值E和最優值h（x*）之間的誤差，不難看出，該誤差和個體數n，系統擴維后增加的節點數nq，迭代步長η和Lipschitz常數有關。由定理1看出只要通信時延cij有上界，算法依然收斂。當cij=0時，則轉化為無時延的情況。此外，還可以看出，時延情形下的迭代誤差比無時延的迭代誤差大，這表明若個體在信息交流的過程中存在通信時延，則會對個體間協同解決優化問題造成一定的影響。

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

由推論1可以看出個體i在k時刻的狀態xi（k）收斂到k時刻所有個體狀態的平均值k。即此時多個體狀態達到平均一致。此外多個體優化問題此時也取得最優值。

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

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中的結論帶入式（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）

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

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

6結束語

在文獻[2，7]的基礎上，本文研究了時延情形下的分布式隨機無梯度優化算法。首先給出時延情形下的分布式隨機無梯度方法，然后通過系統擴維將時延優化問題轉化為無時延優化問題，并利用轉移矩陣的相關結論分析并證明了其收斂性。當然，還有一些問題有待解決，比如在無向圖網絡拓撲下中有時延的隨機無梯度算法以及切換網絡下的優化算法。

參考文獻：

[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]李德權，張曉倩. 時延情形下的分布式Push-sum 次梯度優化算法的研究[J].安徽理工大學學報（自然科學版），2015，35（2）：6-12.

[12]劉德進， 劉成林. 具有通信時延的離散時間二階多個體網絡的一致性問題[J]. 控制理論與應用， 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.