多个体网络分布式随机投影无梯度优化算法*
2016-11-22李德权
李德权，陈 平
安徽理工大学 理学院，安徽 淮南 232001
多个体网络分布式随机投影无梯度优化算法*
李德权，陈 平+
安徽理工大学 理学院，安徽 淮南 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.
研究了有向多个体网络的无梯度优化问题，提出了一种分布式随机投影无梯度优化算法。假定网络的优化目标函数可分解成所有个体的目标函数之和，每个个体仅知其自身的目标函数及其自身的状态约束集。运用无梯度方法解决了因个体目标函数可能非凸而引起的次梯度无法计算问题，并结合随机投影算法解决了约束集未知或约束集投影运算受限的问题。在该算法作用下，所有个体状态几乎必然收敛到优化集内，并且网络目标函数得到最优。
多个体网络；随机投影；无梯度算法；分布式优化
1 引言
近年来，互联网和分布式计算的迅猛发展造就了从大型集成电路计算机到分布式无线传感网络工作站的一个跃变。如，在工业应用中，人们期望能够应用许多价格低廉的小型设备之间的相互协调来替代原来造价昂贵、设计复杂的大型集成电路设备。这使得许多已有的集总式优化计算方法已无法用来解决现在的各种大规模复杂网络化优化问题。由此发展而来的由多个具有有限信息获取和有限数据处理能力，并可以进行自主决策的智能个体所组成的网络化多个体网络的分布式优化理论，由于不需要集中式控制和全局信息，从而为克服集总式优化算法存在的上述缺点提供了一条有效途径[1-2]。因此，目前基于复杂多个体网络的分布式优化问题的研究已成为当前大规模优化问题的一个热点。文献[3-5]介绍了分布式凸优化的一般应用，得出一般的分布式优化问题的特点是：整个网络优化问题的目标函数是凸函数，且可以表示为网络中所有个体各自的凸目标函数之和，而且每个个体仅知道其自身的目标函数，且仅能与其邻居个体进行信息交流来实现整个网络目标函数达成最优[6]。但在实际应用中，并非所有目标函数均为凸函数，也就无法应用有关凸目标函数的分布式优化算法来解决此类优化问题。为此，文献[7]提出了高斯近似方法解决该类问题。
随机投影（random projections，RP）是一种距离保持的数据压缩方法，其核心是通过一组随机向量将高维数据投影到低维空间，实现数据的压缩。这样，针对多个体网络优化问题中个体状态约束集未知或整个约束集受限下，应用随机投影算法在投影误差允许范围内可以将个体状态投影到“简单集”里，从而使一些约束集未知或约束集受限的优化问题得以处理，便于求解目标函数的最优解。而文献[8]则进一步介绍了凸约束条件下近似投影相关概念，分析了近似投影的收敛性及临界误差角的存在问题。目前，分布式优化问题的研究主要侧重于分布式次梯度优化算法方面。如文献[9]最早针对网络凸目标函数可分解成所有个体各自凸目标函数之和的最小化分布式原始优化问题模型，提出了分布式次梯度优化算法来解决该问题，并对该算法的收敛性进行了分析。随着研究的深入，网络目标函数非凸的分布式优化问题越来越引起人们的广泛兴趣。本文正是基于这一背景，利用高斯近似方法将非凸优化问题转化为凸优化问题来求解，但是并没有应用次梯度方法，而是应用无梯度方法解决该问题。这样一方面避免了有关分布式次梯度计算的复杂、繁琐性问题；另一方面也使得对于那些没有次梯度的目标函数的问题得以解决[10]。
此外，按照个体状态是否存在约束集，分布式优化问题还可以分为分布式无约束优化和分布式带约束优化两种情形。其中分布式带约束优化的约束形式包括受限集、等式及不等式约束，还有约束集是不确定的情况。对于约束集，文献[11]特别讨论了在约束集下连续时间里的分布式凸优化。本文将讨论在约束集未知时，或整个约束集的投影运算被限制时，应用无梯度随机投影算法解决分布式优化问题。
2 问题描述
2.1 符号说明
本文所提到的向量如无特殊说明则均为列向量。Rm表示m维列向量空间。yT表示向量y的转置。表示向量y的欧氏范数。
2.2 多个体网络分布式优化
本文主要考虑如下优化问题：
其中，fi：Rn→R是个体i的局部目标函数；γi⊆Rn是个体i的局部凸约束集。本文考虑的γi是由许多有限闭凸集的交组成的情况，即，其中I=(1,2,…,n),并且，i∈V=(1,2,…,m)，且当i≠j时，Ii⋂Ij=∅。这里的是“简单集”，而在大数据情况下,在γi上的投影可能是复杂的，因此用代替γi使其最优解可求。设该问题的最优解为y*，最优值为 f(y*)。
由于目标函数 fi既可能是凸（凹）函数，也可能是非凸（凹）函数。若是凸（凹）函数，则其梯度或次梯度存在，这样可以应用（次）梯度优化算法；若是非凸（凹）函数，则其梯度或次梯度不一定存在，因而无法应用（次）梯度优化算法解决此类优化问题。下面，应用高斯近似方法将（1）中的一般目标函数 fi转化为其高斯近似函数，且由文献[11]知函数 fi的高斯近似函数定义如下：
其中，σi是的非负光滑参数。
从而问题（1）可变为：
3 分布式随机投影无梯度算法
本部分将文献[7]中的无梯度方法与文献[12]中的随机投影方法相结合，提出分布式随机投影无梯度优化（distributed random projection gradient-free optimization，DRPGF）算法来解决问题（1）中的优化问题。
3.1DRPGF算法
设t时刻个体间的信息传递构成的网络可建模为有向图G(t)=(V,E(t))，其中V={1,2,…,m}为节点集，m表示节点或个体的个数；边集为E(t)⊆V×V，A(t)为网络G(t)所对应的随机邻接矩阵。(i,j)∈E(t)表示个体 j向i发送信息，对应的边权[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)是双随机的，即方阵A(t)的每一个元素都是非负的，且其每一行每一列元素的和均为1，则称这个矩阵为双随机的。
（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沿着局部目标函数 fi的高斯预测负方向的平均向量。
3.2 相关假设算法
以下均假设{Ωi(t)},i∈V是随机序列。
假设1随机序列{Ωi(t)},i∈V是独立同分布的，不同的初始值yi(0),i∈V有：
变量Ωi(t)是随机变量Ωi以概率,j∈Ii在t时刻的随机抽样，多数情况下概率分布并不由个体i控制，而是随机选择的。在这些情形下每个个体i选择一个指标集Ii上的均匀分布πi，在,j∈Ii中是有效的。
假设2∀i∈V,∃常数c>0,s.t.∀y∈Rm：
当约束集为线性不等式或线性等式时[13]，或者当其交集是非空的[14]，易知假设2成立。而常数c则取决于概率分布πi和约束集的一些几何性质。
对于每个个体i，分布式随机投影无梯度优化算法可以生成一组随机序列，用Ft定义遍历整个σ领域的随机变量，即:
并且F0={yi(0),i=1,2,…,n}。
假设3[10]∀t≥0,∃T∈N+,s.t.图(V,E(A(tT))⋃…⋃E(A((t+1)T-1)))是强连通的。
注2假设3说明任意时刻网络可以是不连通的，但在每个周期T内这些图集合的并必须是强连通的[10]。强连通是指有向图中任意两点间都存在一个有向路径，即对∀v1,v2∈G,必存在一条有向路径连接v1和v2。
3.3 相关引理
对于算法中的非扩张性投影有以下性质。
引理1[15]γ⊆Rh是非空凸集。函数Πγ:Rh→γ是连续且非扩张的。即：
注3任意两个数据间的距离经过投影运算并没有扩大。
引理2[7]∀i∈V，L是函数 fi(y)的Lipschitz约束，有：
4 收敛性分析
注4定理1、定理2基于期望差、投影距离等方法，并结合本文提出的DRPGF算法证明了问题（1）具有最优解且最优解几乎必然收敛到优化集内。
5 结束语
本文提出了一种分布式随机投影无梯度优化算法，并用于解决目标函数是无梯度或其梯度计算难度较大，以及约束集未知或整个约束集被限制的多个体分布式优化问题。通过对其收敛性分析可以知道，优化解几乎必然收敛到优化集里。由于个体在传递信息的过程中可能会产生信息丢失或信息延迟的情况，下一步将考虑具有丢包的分布式随机投影无梯度优化算法及具有时延的分布式随机投影无梯度优化算法等。
[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.
附中文参考文献：
[1]洪奕光,张艳琼.分布式优化:算法设计和收敛性分析[J].控制理论与应用,2014,31(7):850-857.
[2]刘成林,田玉平.具有时延的多个体系统的一致性问题综述[J].控制与决策,2009,24(11):1601-1608.
[6]刘军,李德权.具有通信时延的多个体分布式次梯度优化算法[J].合肥工业大学学报:自然科学版,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.
李德权（1973—），男，安徽肥东人，2012年于上海交通大学获得博士学位，现为安徽理工大学教授，主要研究领域为多个体网络，分布式优化等。发表学术论文50余篇，主持国家自然科学基金面上项目。
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—），女，安徽凤台人，安徽理工大学硕士研究生，主要研究领域为分布式优化，分布式无梯度优化等。
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(国家自然科学基金);the National Natural Science Youth Foundation of China under Grant No.11401008(国家自然科学青年基金);the Natural Science Research Key Project of Anhui Provincial Education Department under Grant No.KJ2014A067(安徽省教育厅自然科学研究重点项目);the Academic Key Project ofAnhui Provincial Discipline(Professional)Talent(安徽省高校学科(专业)拔尖人才学术资助重点项目).
Received 2015-08,Accepted 2015-10.
CNKI网络优先出版:2015-10-20,http://www.cnki.net/kcms/detail/11.5602.TP.20151020.1042.012.html
