基于近似投影的分布式零階Push-Sum優(yōu)化算法

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

安徽理工大學(xué)理學(xué)院，安徽淮南，232001

基于近似投影的分布式零階Push-Sum優(yōu)化算法

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

安徽理工大學(xué)理學(xué)院，安徽淮南，232001

近似投影；分布式優(yōu)化；零階方法；分布式算法；非平衡網(wǎng)絡(luò)

1 問(wèn)題提出

近年來(lái)，多個(gè)體分布式凸優(yōu)化問(wèn)題成為多個(gè)體優(yōu)化問(wèn)題的一個(gè)研究熱點(diǎn)。和以往的集總式算法相比，分布式算法在解決很多大規(guī)模計(jì)算問(wèn)題中有很大優(yōu)勢(shì)。集總式算法是指在多個(gè)體系統(tǒng)中所有個(gè)體并不發(fā)揮同樣的作用，而是其中某個(gè)個(gè)體處于中心地位，負(fù)責(zé)接收并處理其他個(gè)體的數(shù)據(jù)信息。而分布式算法主要是指在多個(gè)體系統(tǒng)中每個(gè)個(gè)體都處于相同的地位，相鄰個(gè)體之間進(jìn)行信息交流，最終達(dá)到優(yōu)化的目的。分布式優(yōu)化在很多領(lǐng)域如大規(guī)模機(jī)器學(xué)習(xí)、分布式跟蹤與定位以及無(wú)線傳感網(wǎng)絡(luò)都有廣泛的應(yīng)用。

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

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

2 符號(hào)說(shuō)明

3 問(wèn)題描述

(1)

記問(wèn)題(1)的最優(yōu)值F*是一個(gè)有限的確定值，并記其最優(yōu)解為：

4 算法介紹

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

對(duì)于任意k≥0，有：

(2)

(3)

為了更有效地利用無(wú)線廣播的性質(zhì),并將多個(gè)體分布式優(yōu)化算法應(yīng)用于非平衡網(wǎng)絡(luò)，使優(yōu)化算法在非平衡網(wǎng)絡(luò)中依然收斂，提出基于近似投影的分布式零階Push-sum優(yōu)化算法：

(4)

(5)

(6)

(7)

(8)

5 收斂性分析

假設(shè)1對(duì)每一個(gè)i∈V，函數(shù)fi是X上的Lipchitz連續(xù)函數(shù)且Lipchitz常數(shù)為L(zhǎng)i，即：

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

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

(1)梯度的預(yù)測(cè)值滿足：

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

(9)

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

(10)

(11)

(12)

(13)

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

(14)

由引理1(1)可得：

(15)

(16)

又因?yàn)?/p>

(17)

故可得：

(18)

另一方面，

綜上可得：

(19)

(20)

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

(21)

(22)

證明：由引理2可得：

(23)

(24)

(25)

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

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

(26)

證明：首先定義一個(gè)序列

(27)

由假設(shè)1及引理1可得：

(28)

由定理1中(14)可得：

則有：

(29)

(30)

(31)

令z=z*，則：

(32)

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

(33)

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

5 結(jié)束語(yǔ)

在文獻(xiàn)[9,10]的基礎(chǔ)上，本文研究了基于近似投影的分布式零階Push-sum優(yōu)化算法，首先給出基于近似投影的分布式零階優(yōu)化算法，針對(duì)有向非平衡網(wǎng)絡(luò)，結(jié)合Push-sum算法并最終證明了其收斂性。此外，本文還有一些問(wèn)題有待解決，比如時(shí)延情形下的優(yōu)化算法。

[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]張曉倩，李德權(quán)．有向網(wǎng)絡(luò)異步PUSH-SUM次梯度優(yōu)化算法的研究[J]．皖西學(xué)院學(xué)報(bào)，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

(責(zé)任編輯：汪材印)

10.3969/j.issn.1673-2006.2016.03.026

2015-11-30

國(guó)家自然科學(xué)基金(61472003)；國(guó)家自然科學(xué)青年基金(11401008)；安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目(KJ2014A067)。

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

TP13

A

1673-2006(2016)03-0100-07