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

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

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

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

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

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

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

1 問題提出

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

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

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

2 符號說明

3 問題描述

(1)

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

4 算法介紹

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

對于任意k≥0，有：

(2)

(3)

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

(4)

(5)

(6)

(7)

(8)

5 收斂性分析

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

假設(shè)2存在一個正整數(shù)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)梯度的預(yù)測值滿足：

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

(9)

定理1 在假設(shè)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 在假設(shè)1,2,3成立，定理1和推論2也成立的前提下：

(26)

證明：首先定義一個序列

(27)

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

(28)

由定理1中(14)可得：

則有：

(29)

(30)

(31)

令z=z*，則：

(32)

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

(33)

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

5 結(jié)束語

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

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

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

TP13

A

1673-2006(2016)03-0100-07