李德權(quán)，陳 平

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

多個體網(wǎng)絡(luò)分布式隨機(jī)投影無梯度優(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.

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

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

1 引言

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

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

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

2 問題描述

2.1 符號說明

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

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

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

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

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

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

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

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

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

3.1DRPGF算法

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

在t時刻個體i有如下迭代：

注1在式（3）中：

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

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

在式（4）中：

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

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

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

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

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

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

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

對于每個個體i，分布式隨機(jī)投影無梯度優(yōu)化算法可以生成一組隨機(jī)序列，用Ft定義遍歷整個σ領(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說明任意時刻網(wǎng)絡(luò)可以是不連通的，但在每個周期T內(nèi)這些圖集合的并必須是強(qiáng)連通的[10]。強(qiáng)連通是指有向圖中任意兩點間都存在一個有向路徑，即對?v1,v2∈G,必存在一條有向路徑連接v1和v2。

3.3 相關(guān)引理

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

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

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

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

4 收斂性分析

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

5 結(jié)束語

本文提出了一種分布式隨機(jī)投影無梯度優(yōu)化算法，并用于解決目標(biāo)函數(shù)是無梯度或其梯度計算難度較大，以及約束集未知或整個約束集被限制的多個體分布式優(yōu)化問題。通過對其收斂性分析可以知道，優(yōu)化解幾乎必然收斂到優(yōu)化集里。由于個體在傳遞信息的過程中可能會產(chǎn)生信息丟失或信息延遲的情況，下一步將考慮具有丟包的分布式隨機(jī)投影無梯度優(yōu)化算法及具有時延的分布式隨機(jī)投影無梯度優(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].控制理論與應(yīng)用,2014,31(7):850-857.

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

[6]劉軍,李德權(quán).具有通信時延的多個體分布式次梯度優(yōu)化算法[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(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)域為多個體網(wǎng)絡(luò)，分布式優(yōu)化等。發(fā)表學(xué)術(shù)論文50余篇，主持國家自然科學(xué)基金面上項目。

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—），女，安徽鳳臺人，安徽理工大學(xué)碩士研究生，主要研究領(lǐng)域為分布式優(yōu)化，分布式無梯度優(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(國家自然科學(xué)基金);the National Natural Science Youth Foundation of China under Grant No.11401008(國家自然科學(xué)青年基金);the Natural Science Research Key Project of Anhui Provincial Education Department under Grant No.KJ2014A067(安徽省教育廳自然科學(xué)研究重點項目);the Academic Key Project ofAnhui Provincial Discipline(Professional)Talent(安徽省高校學(xué)科(專業(yè))拔尖人才學(xué)術(shù)資助重點項目).

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