基于近似投影的分布式零階Push-Sum優化算法

任芳芳，李德權

安徽理工大學理學院，安徽淮南，232001

基于近似投影的分布式零階Push-Sum優化算法

任芳芳，李德權

安徽理工大學理學院，安徽淮南，232001

近似投影；分布式優化；零階方法；分布式算法；非平衡網絡

1 問題提出

近年來，多個體分布式凸優化問題成為多個體優化問題的一個研究熱點。和以往的集總式算法相比，分布式算法在解決很多大規模計算問題中有很大優勢。集總式算法是指在多個體系統中所有個體并不發揮同樣的作用，而是其中某個個體處于中心地位，負責接收并處理其他個體的數據信息。而分布式算法主要是指在多個體系統中每個個體都處于相同的地位，相鄰個體之間進行信息交流，最終達到優化的目的。分布式優化在很多領域如大規模機器學習、分布式跟蹤與定位以及無線傳感網絡都有廣泛的應用。

文獻[1]最早給出了對分布式優化算法的分析，即基于一致性算法的分布式次梯度算法。為了進一步研究約束優化問題，文獻[2-3]給出一種基于一致性算法的原始對偶次梯度方法以及分別在等式和不等式約束下的原始對偶算法。文獻[4]提出了分布式對偶平均優化算法。此外，投影算法在分布式優化問題中也有重要的應用，例如文獻[5]提出了投影次梯度算法;對于投影無法準確計算的情況，文獻[6]給出了一種近似投影一致性算法。然而，以上算法都是適用于多個體系統中的每個個體對應的目標函數的梯度信息可以獲得或者投影可以準確計算的情況，在另外一些情況下，個體對應的目標函數的梯度無法獲得或無法計算[7]，投影也僅能近似得到[8]，針對這兩種問題，文獻[9]給出了一種基于近似投影的零階分布式優化算法。而文獻[8]僅僅研究了基于單變量通信的系統。

考慮多個體網絡無線通信的廣播特性，基于雙變量通信的Push-sum算法引起了學者的廣泛興趣[9-12]。和單變量通信相比，基于雙變量通信的Push-sum算法能夠更有效地利用無線廣播的性質并可以應用于非平衡網絡，使得優化算法在非平衡網絡中依然收斂。因此，研究基于近似投影的分布式零階Push-sum優化算法具有很大的意義。

2 符號說明

3 問題描述

(1)

記問題(1)的最優值F*是一個有限的確定值，并記其最優解為：

4 算法介紹

基于近似投影的分布式零階算法[8]表示如下：

對于任意k≥0，有：

(2)

(3)

為了更有效地利用無線廣播的性質,并將多個體分布式優化算法應用于非平衡網絡，使優化算法在非平衡網絡中依然收斂，提出基于近似投影的分布式零階Push-sum優化算法：

(4)

(5)

(6)

(7)

(8)

5 收斂性分析

假設1對每一個i∈V，函數fi是X上的Lipchitz連續函數且Lipchitz常數為Li，即：

假設2存在一個正整數B，使得有向圖(V,E(A(kB))∪…∪E(A((k+1)B-1)))對所有k≥0都是強連通圖并且B是強連通周期。

引理1令Fk是一個隨機變量，且滿足Fk={(xi(0),i∈V);(u1,i(τ),u2,i(τ),i∈V),0≤τ≤k-1)且F0={xi(0),i∈V}。

(1)梯度的預測值滿足：

(3)存在一個常數使得下式成立：

(9)

定理1 在假設1,2,3和引理1成立的情況下，對于任意i∈V和k≥0，有下式成立：

(10)

(11)

(12)

(13)

令z為一個輔助向量，則由(13)可得：

(14)

由引理1(1)可得：

(15)

(16)

又因為

(17)

故可得：

(18)

另一方面，

綜上可得：

(19)

(20)

兩邊同時除以2α(k+1)，可得：

(21)

(22)

證明：由引理2可得：

(23)

(24)

(25)

將(25)式代入(23)式，故(22)式成立。

定理2 在假設1,2,3成立，定理1和推論2也成立的前提下：

(26)

證明：首先定義一個序列

(27)

由假設1及引理1可得：

(28)

由定理1中(14)可得：

則有：

(29)

(30)

(31)

令z=z*，則：

(32)

將推論2中(22)式代入(32)式可得：

(33)

綜上(28),(33)式，最終可得：

5 結束語

在文獻[9,10]的基礎上，本文研究了基于近似投影的分布式零階Push-sum優化算法，首先給出基于近似投影的分布式零階優化算法，針對有向非平衡網絡，結合Push-sum算法并最終證明了其收斂性。此外，本文還有一些問題有待解決，比如時延情形下的優化算法。

[1]Nedic A,Ozdaglar A.Distributed subgradient methods for Multi-Agent optimization[J].IEEE Transactions on Automatic Control,2009,54(1):48-61

[2]ZHU Minghui,MartInez S.On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods[J].IEEE Trans.autom.control,2010,57(1):151-164

[3]YUAN D,XU S,ZHAO H.Distributed Primal-Dual subgradient method for multiagent optimization via consensus algorithms[J].IEEE Transactions on Systems,Man,and Cybernetics.Part B,Cybernetics :a Publication of the IEEE Systems,Man,and Cybernetics Society,2011,41(6):1715-1724

[4]YUAN De-ming,XU Sheng-yuan,ZHAO Huan-yu,et al.Distributed dual averaging method for multi-agent optimization with quantized communication[J].Systems & Control Letters,2012,61(11):1053-1061

[5]Lee S,Nedic A.Distributed random projection algorithm for convex optimization[J].IEEE Journal of Selected Topics in Signal Processing,2013,7(2):221-229

[6]LOU You-cheng,SHI Guo-dong,Johansson K H,et al.Approximate projected consensus for convex intersection computation:convergence analysis and critical error angle[J].IEEE Transactions on Automatic Control,2014,59(7):1722-1736

[7]Nesterov Y,Spokoiny V.Random Gradient-Free minimization of convex functions[J].Foundations of Computational Mathematics,2015,36(16):1-40

[8]Duchi J C,Jordan M I,Wainwright M J,et al.Optimal rates for Zero-Order convex optimization:the power of two function evaluations[J].IEEE Transactions on Information Theory,2013,61(5):2788-2806

[9]YUAN Deming,Ho D W,XU Shengyuan.Zeroth-Order method for distributed optimization with approximate projections[J].IEEE Transactions on Neural Networks and Learning Systems,2016,27(2):284-294

[10]Nedic A.Olshevsky A.distributed optimization over Time-Varying directed graphs[J].Automatic Control,IEEE Transactions on,2015,60(3):601-615

[11]Boyd S,Ghosh A,Prabhakar B,et al.Randomized gossip algorithms[J].IEEE Transactions on Information Theory,2006,52(6):2508-2530

[12]張曉倩，李德權．有向網絡異步PUSH-SUM次梯度優化算法的研究[J]．皖西學院學報，2014(5)：11-15

[13]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

(責任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.03.026

2015-11-30

國家自然科學基金(61472003)；國家自然科學青年基金(11401008)；安徽省教育廳自然科學研究重點項目(KJ2014A067)。

任芳芳(1990-)，女,安徽宿州人，在讀碩士研究生，主要研究方向：分布式優化理論與應用。

TP13

A

1673-2006(2016)03-0100-07