多個(gè)體網(wǎng)絡(luò)分布式隨機(jī)投影無(wú)梯度優(yōu)化算法*

李德權(quán)，陳 平

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

多個(gè)體網(wǎng)絡(luò)分布式隨機(jī)投影無(wú)梯度優(yōu)化算法*

李德權(quán)，陳 平+

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

LI Dequan,CHEN Ping.Distributed random projection gradient-free optimization algorithm for multi-agent networks.Journal of Frontiers of Computer Science and Technology,2016,10(11):1564-1570.

研究了有向多個(gè)體網(wǎng)絡(luò)的無(wú)梯度優(yōu)化問(wèn)題，提出了一種分布式隨機(jī)投影無(wú)梯度優(yōu)化算法。假定網(wǎng)絡(luò)的優(yōu)化目標(biāo)函數(shù)可分解成所有個(gè)體的目標(biāo)函數(shù)之和，每個(gè)個(gè)體僅知其自身的目標(biāo)函數(shù)及其自身的狀態(tài)約束集。運(yùn)用無(wú)梯度方法解決了因個(gè)體目標(biāo)函數(shù)可能非凸而引起的次梯度無(wú)法計(jì)算問(wèn)題，并結(jié)合隨機(jī)投影算法解決了約束集未知或約束集投影運(yùn)算受限的問(wèn)題。在該算法作用下，所有個(gè)體狀態(tài)幾乎必然收斂到優(yōu)化集內(nèi)，并且網(wǎng)絡(luò)目標(biāo)函數(shù)得到最優(yōu)。

多個(gè)體網(wǎng)絡(luò)；隨機(jī)投影；無(wú)梯度算法；分布式優(yōu)化

1 引言

近年來(lái)，互聯(lián)網(wǎng)和分布式計(jì)算的迅猛發(fā)展造就了從大型集成電路計(jì)算機(jī)到分布式無(wú)線傳感網(wǎng)絡(luò)工作站的一個(gè)躍變。如，在工業(yè)應(yīng)用中，人們期望能夠應(yīng)用許多價(jià)格低廉的小型設(shè)備之間的相互協(xié)調(diào)來(lái)替代原來(lái)造價(jià)昂貴、設(shè)計(jì)復(fù)雜的大型集成電路設(shè)備。這使得許多已有的集總式優(yōu)化計(jì)算方法已無(wú)法用來(lái)解決現(xiàn)在的各種大規(guī)模復(fù)雜網(wǎng)絡(luò)化優(yōu)化問(wèn)題。由此發(fā)展而來(lái)的由多個(gè)具有有限信息獲取和有限數(shù)據(jù)處理能力，并可以進(jìn)行自主決策的智能個(gè)體所組成的網(wǎng)絡(luò)化多個(gè)體網(wǎng)絡(luò)的分布式優(yōu)化理論，由于不需要集中式控制和全局信息，從而為克服集總式優(yōu)化算法存在的上述缺點(diǎn)提供了一條有效途徑[1-2]。因此，目前基于復(fù)雜多個(gè)體網(wǎng)絡(luò)的分布式優(yōu)化問(wèn)題的研究已成為當(dāng)前大規(guī)模優(yōu)化問(wèn)題的一個(gè)熱點(diǎn)。文獻(xiàn)[3-5]介紹了分布式凸優(yōu)化的一般應(yīng)用，得出一般的分布式優(yōu)化問(wèn)題的特點(diǎn)是：整個(gè)網(wǎng)絡(luò)優(yōu)化問(wèn)題的目標(biāo)函數(shù)是凸函數(shù)，且可以表示為網(wǎng)絡(luò)中所有個(gè)體各自的凸目標(biāo)函數(shù)之和，而且每個(gè)個(gè)體僅知道其自身的目標(biāo)函數(shù)，且僅能與其鄰居個(gè)體進(jìn)行信息交流來(lái)實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)目標(biāo)函數(shù)達(dá)成最優(yōu)[6]。但在實(shí)際應(yīng)用中，并非所有目標(biāo)函數(shù)均為凸函數(shù)，也就無(wú)法應(yīng)用有關(guān)凸目標(biāo)函數(shù)的分布式優(yōu)化算法來(lái)解決此類(lèi)優(yōu)化問(wèn)題。為此，文獻(xiàn)[7]提出了高斯近似方法解決該類(lèi)問(wèn)題。

隨機(jī)投影（random projections，RP）是一種距離保持的數(shù)據(jù)壓縮方法，其核心是通過(guò)一組隨機(jī)向量將高維數(shù)據(jù)投影到低維空間，實(shí)現(xiàn)數(shù)據(jù)的壓縮。這樣，針對(duì)多個(gè)體網(wǎng)絡(luò)優(yōu)化問(wèn)題中個(gè)體狀態(tài)約束集未知或整個(gè)約束集受限下，應(yīng)用隨機(jī)投影算法在投影誤差允許范圍內(nèi)可以將個(gè)體狀態(tài)投影到“簡(jiǎn)單集”里，從而使一些約束集未知或約束集受限的優(yōu)化問(wèn)題得以處理，便于求解目標(biāo)函數(shù)的最優(yōu)解。而文獻(xiàn)[8]則進(jìn)一步介紹了凸約束條件下近似投影相關(guān)概念，分析了近似投影的收斂性及臨界誤差角的存在問(wèn)題。目前，分布式優(yōu)化問(wèn)題的研究主要側(cè)重于分布式次梯度優(yōu)化算法方面。如文獻(xiàn)[9]最早針對(duì)網(wǎng)絡(luò)凸目標(biāo)函數(shù)可分解成所有個(gè)體各自凸目標(biāo)函數(shù)之和的最小化分布式原始優(yōu)化問(wèn)題模型，提出了分布式次梯度優(yōu)化算法來(lái)解決該問(wèn)題，并對(duì)該算法的收斂性進(jìn)行了分析。隨著研究的深入，網(wǎng)絡(luò)目標(biāo)函數(shù)非凸的分布式優(yōu)化問(wèn)題越來(lái)越引起人們的廣泛興趣。本文正是基于這一背景，利用高斯近似方法將非凸優(yōu)化問(wèn)題轉(zhuǎn)化為凸優(yōu)化問(wèn)題來(lái)求解，但是并沒(méi)有應(yīng)用次梯度方法，而是應(yīng)用無(wú)梯度方法解決該問(wèn)題。這樣一方面避免了有關(guān)分布式次梯度計(jì)算的復(fù)雜、繁瑣性問(wèn)題；另一方面也使得對(duì)于那些沒(méi)有次梯度的目標(biāo)函數(shù)的問(wèn)題得以解決[10]。

此外，按照個(gè)體狀態(tài)是否存在約束集，分布式優(yōu)化問(wèn)題還可以分為分布式無(wú)約束優(yōu)化和分布式帶約束優(yōu)化兩種情形。其中分布式帶約束優(yōu)化的約束形式包括受限集、等式及不等式約束，還有約束集是不確定的情況。對(duì)于約束集，文獻(xiàn)[11]特別討論了在約束集下連續(xù)時(shí)間里的分布式凸優(yōu)化。本文將討論在約束集未知時(shí)，或整個(gè)約束集的投影運(yùn)算被限制時(shí)，應(yīng)用無(wú)梯度隨機(jī)投影算法解決分布式優(yōu)化問(wèn)題。

2 問(wèn)題描述

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

本文所提到的向量如無(wú)特殊說(shuō)明則均為列向量。Rm表示m維列向量空間。yT表示向量y的轉(zhuǎn)置。表示向量y的歐氏范數(shù)。表示向量y和向量x的內(nèi)積。yi(t)表示向量y的第i個(gè)分量在t時(shí)刻的迭代值。

2.2 多個(gè)體網(wǎng)絡(luò)分布式優(yōu)化

本文主要考慮如下優(yōu)化問(wèn)題：

其中，fi：Rn→R是個(gè)體i的局部目標(biāo)函數(shù)；γi?Rn是個(gè)體i的局部凸約束集。本文考慮的γi是由許多有限閉凸集的交組成的情況，即，其中I=(1,2,…,n),并且，i∈V=(1,2,…,m)，且當(dāng)i≠j時(shí)，Ii?Ij=?。這里的是“簡(jiǎn)單集”，而在大數(shù)據(jù)情況下,在γi上的投影可能是復(fù)雜的，因此用代替γi使其最優(yōu)解可求。設(shè)該問(wèn)題的最優(yōu)解為y*，最優(yōu)值為 f(y*)。

由于目標(biāo)函數(shù) fi既可能是凸（凹）函數(shù)，也可能是非凸（凹）函數(shù)。若是凸（凹）函數(shù)，則其梯度或次梯度存在，這樣可以應(yīng)用（次）梯度優(yōu)化算法；若是非凸（凹）函數(shù)，則其梯度或次梯度不一定存在，因而無(wú)法應(yīng)用（次）梯度優(yōu)化算法解決此類(lèi)優(yōu)化問(wèn)題。下面，應(yīng)用高斯近似方法將（1）中的一般目標(biāo)函數(shù) fi轉(zhuǎn)化為其高斯近似函數(shù)，且由文獻(xiàn)[11]知函數(shù) fi的高斯近似函數(shù)定義如下：

其中，σi是的非負(fù)光滑參數(shù)。

從而問(wèn)題（1）可變?yōu)椋?/p>

3 分布式隨機(jī)投影無(wú)梯度算法

本部分將文獻(xiàn)[7]中的無(wú)梯度方法與文獻(xiàn)[12]中的隨機(jī)投影方法相結(jié)合，提出分布式隨機(jī)投影無(wú)梯度優(yōu)化（distributed random projection gradient-free optimization，DRPGF）算法來(lái)解決問(wèn)題（1）中的優(yōu)化問(wèn)題。

3.1DRPGF算法

設(shè)t時(shí)刻個(gè)體間的信息傳遞構(gòu)成的網(wǎng)絡(luò)可建模為有向圖G(t)=(V,E(t))，其中V={1,2,…,m}為節(jié)點(diǎn)集，m表示節(jié)點(diǎn)或個(gè)體的個(gè)數(shù)；邊集為E(t)?V×V，A(t)為網(wǎng)絡(luò)G(t)所對(duì)應(yīng)的隨機(jī)鄰接矩陣。(i,j)∈E(t)表示個(gè)體 j向i發(fā)送信息，對(duì)應(yīng)的邊權(quán)[A(t)]ij∈A(t)滿足[A(t)]ij>0，否則[A(t)]ij=0。個(gè)體i的鄰居集合表示為Ni(t)={j∈|V(i,j)∈E(t)}。

在t時(shí)刻個(gè)體i有如下迭代：

注1在式（3）中：

（1）A(t)是雙隨機(jī)的，即方陣A(t)的每一個(gè)元素都是非負(fù)的，且其每一行每一列元素的和均為1，則稱(chēng)這個(gè)矩陣為雙隨機(jī)的。

（2）A(t)對(duì)角線上元素是正的，即?v>0，s.t.?i∈V,[A(t)]ii>v。此時(shí)如果[A(t)]ij>0，則?v>0,s.t.?i,j∈V,[A(t)]ij≥v。

在式（4）中：

（1）vi(t)是個(gè)體i沿著局部目標(biāo)函數(shù) fi的高斯預(yù)測(cè)負(fù)方向的平均向量。

3.2 相關(guān)假設(shè)算法

以下均假設(shè){Ωi(t)},i∈V是隨機(jī)序列。

假設(shè)1隨機(jī)序列{Ωi(t)},i∈V是獨(dú)立同分布的，不同的初始值yi(0),i∈V有：

變量Ωi(t)是隨機(jī)變量Ωi以概率,j∈Ii在t時(shí)刻的隨機(jī)抽樣，多數(shù)情況下概率分布并不由個(gè)體i控制，而是隨機(jī)選擇的。在這些情形下每個(gè)個(gè)體i選擇一個(gè)指標(biāo)集Ii上的均勻分布πi，在,j∈Ii中是有效的。

假設(shè)2?i∈V,?常數(shù)c>0,s.t.?y∈Rm：

當(dāng)約束集為線性不等式或線性等式時(shí)[13]，或者當(dāng)其交集是非空的[14]，易知假設(shè)2成立。而常數(shù)c則取決于概率分布πi和約束集的一些幾何性質(zhì)。

對(duì)于每個(gè)個(gè)體i，分布式隨機(jī)投影無(wú)梯度優(yōu)化算法可以生成一組隨機(jī)序列，用Ft定義遍歷整個(gè)σ領(lǐng)域的隨機(jī)變量，即:

并且F0={yi(0),i=1,2,…,n}。

假設(shè)3[10]?t≥0,?T∈N+,s.t.圖(V,E(A(tT))?…?E(A((t+1)T-1)))是強(qiáng)連通的。

注2假設(shè)3說(shuō)明任意時(shí)刻網(wǎng)絡(luò)可以是不連通的，但在每個(gè)周期T內(nèi)這些圖集合的并必須是強(qiáng)連通的[10]。強(qiáng)連通是指有向圖中任意兩點(diǎn)間都存在一個(gè)有向路徑，即對(duì)?v1,v2∈G,必存在一條有向路徑連接v1和v2。

3.3 相關(guān)引理

對(duì)于算法中的非擴(kuò)張性投影有以下性質(zhì)。

引理1[15]γ?Rh是非空凸集。函數(shù)Πγ:Rh→γ是連續(xù)且非擴(kuò)張的。即：

注3任意兩個(gè)數(shù)據(jù)間的距離經(jīng)過(guò)投影運(yùn)算并沒(méi)有擴(kuò)大。

引理2[7]?i∈V，L是函數(shù) fi(y)的Lipschitz約束，有：

4 收斂性分析

注4定理1、定理2基于期望差、投影距離等方法，并結(jié)合本文提出的DRPGF算法證明了問(wèn)題（1）具有最優(yōu)解且最優(yōu)解幾乎必然收斂到優(yōu)化集內(nèi)。

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

本文提出了一種分布式隨機(jī)投影無(wú)梯度優(yōu)化算法，并用于解決目標(biāo)函數(shù)是無(wú)梯度或其梯度計(jì)算難度較大，以及約束集未知或整個(gè)約束集被限制的多個(gè)體分布式優(yōu)化問(wèn)題。通過(guò)對(duì)其收斂性分析可以知道，優(yōu)化解幾乎必然收斂到優(yōu)化集里。由于個(gè)體在傳遞信息的過(guò)程中可能會(huì)產(chǎn)生信息丟失或信息延遲的情況，下一步將考慮具有丟包的分布式隨機(jī)投影無(wú)梯度優(yōu)化算法及具有時(shí)延的分布式隨機(jī)投影無(wú)梯度優(yōu)化算法等。

[1]Hong Yiguang,Zhang Yanqiong.Distributed optimization algorithm:algorithm design and convergence analysis[J]. Control Theory andApplication,2014,31(7):850-857.

[2]Liu Chenlin,Tian Yuping.Survey on consensus problem of multi-agent systems with time delay[J].Control and Decision,2009,24(11):1601-1608.

[3]Nedic A,Olshevsky A.Distributed optimization over timevarying directed graphs[J].IEEE Transactions on Automatic Control,2014,60(3):601-615.

[4]Zhu Minghui,Martinez S.On distributed convex optimization under inequality and equality constraints[J].IEEE Transactions onAutomatic Control,2012,57(1):151-164.

[5]Gharesifard B,Cortes J.Continuous-time distributed convex optimization on weight-balanced digraphs[J].IEEE Transactions onAutomatic Control,2012,59(3):7451-7456.

[6]Liu Jun,Li Dequan.Distributed optimization method for multi-agent system with communication delays[J].Hefei In-stitute of Technology:Natural Science Edition,2013,36 (5):559-565.

[7]Nesterov Y.Random gradient-free minimization of convex functions[R].Center for Operations Research and Econometrics(CORE),Catholic University of Louvain,Jan 2011.

[8]Lou Youcheng,Shi Guodong,Johansson K H,et al.Approximate projected consensus for convex intersection computation:convergence analysis and critical error angle[J].IEEE Transactions onAutomatic Control,2014,59(7):1722-1736.

[9]Nedic A,Ozdaglar A.Distributed subgradient methods for multi-agent optimization[J].IEEE Transactions on Automatic control,2009,54(1):48-61.

[10]Yuan Deming,Xu Shengyuan,Lu Junwei.Gradient-free method for distributed multi-agent optimization via push-sum algorithms[J].International Journal of Robust and Nonlinear Control,2015,10(25):1569-1580.

[11]Liu Shuai,Qiu Zhirong,Xie Lihua.Continuous-time distributed convex optimization with set constraints[J].IFAC Proceedings Volumes,2014,47(3):9762-9767.

[12]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.

[13]Burke J V,Ferris M C.Weak sharp minima in mathematical programming[J].SIAM Journal on Control and Optimization,1993,31(5):1340-1359.

[14]Gubin L,Polyak B,Raik E.The method of projections for finding the common point of convex sets[J].USSR Computational Mathematics and Mathematical Physics,1967,7 (6):1-24.

[15]Bertsekas D,Nedic A,Ozdaglar A.Convex analysis and optimization[J].Athena Scientific,2003,129(2):420-432.

附中文參考文獻(xiàn)：

[1]洪奕光,張艷瓊.分布式優(yōu)化:算法設(shè)計(jì)和收斂性分析[J].控制理論與應(yīng)用,2014,31(7):850-857.

[2]劉成林,田玉平.具有時(shí)延的多個(gè)體系統(tǒng)的一致性問(wèn)題綜述[J].控制與決策,2009,24(11):1601-1608.

[6]劉軍,李德權(quán).具有通信時(shí)延的多個(gè)體分布式次梯度優(yōu)化算法[J].合肥工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2013,36(5): 559-565.

LI Dequan was born in 1973.He received the Ph.D.degree in control theory and control engineering from Shanghai Jiaotong University in 2012.Now he is a professor at Anhui University of Science and Technology.His research interests include multi-agent networks and distributed optimization,etc.

李德權(quán)（1973—），男，安徽肥東人，2012年于上海交通大學(xué)獲得博士學(xué)位，現(xiàn)為安徽理工大學(xué)教授，主要研究領(lǐng)域?yàn)槎鄠€(gè)體網(wǎng)絡(luò)，分布式優(yōu)化等。發(fā)表學(xué)術(shù)論文50余篇，主持國(guó)家自然科學(xué)基金面上項(xiàng)目。

CHEN Ping was born in 1988.She is an M.S.candidate at Anhui University of Science and Technology.Her research interests include distributed optimization and distributed free-gradient optimization,etc.

陳平（1988—），女，安徽鳳臺(tái)人，安徽理工大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)榉植际絻?yōu)化，分布式無(wú)梯度優(yōu)化等。

Distributed Random Projection Gradient-Free Optimization Algorithm for Multi-Agent Networks*

LI Dequan,CHEN Ping+
School of Science,Anhui University of Science and Technology,Huainan,Anhui 232001,China
+Corresponding author:E-mail:chenp0554@foxmail.com

This paper proposes a distributed random projection gradient-free optimization algorithm for multi-agent networks.It is assumed that the objective function of the network is the sum of the objective functions of all individuals, and each individual only knows its own objective function and its own state constraint set.Due to each agent’s objective function maybe nonconvex,the problem that the subgradient of each agent’s objective function hard to be calculated can be solved by using the gradient method.Then applying the random projection algorithm at each iteration,the problem of the constrained set maybe unknown or the projection of the constrained set hard to be computed can also be solved.It is proved that,under the proposed algorithm,all agents’states converge to the optimization set almost surely and the objective function of the network also achieves optimization.

multi-agent network;random projection;gradient-free algorithm;distributed optimization

10.3778/j.issn.1673-9418.1509066

A

TP301.6

*The National Natural Science Foundation of China under Grant No.61472003(國(guó)家自然科學(xué)基金);the National Natural Science Youth Foundation of China under Grant No.11401008(國(guó)家自然科學(xué)青年基金);the Natural Science Research Key Project of Anhui Provincial Education Department under Grant No.KJ2014A067(安徽省教育廳自然科學(xué)研究重點(diǎn)項(xiàng)目);the Academic Key Project ofAnhui Provincial Discipline(Professional)Talent(安徽省高校學(xué)科(專(zhuān)業(yè))拔尖人才學(xué)術(shù)資助重點(diǎn)項(xiàng)目).

Received 2015-08,Accepted 2015-10.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.012.html