时延情形下的分布式随机无梯度优化算法[权威资料].docVIP

时延情形下的分布式随机无梯度优化算法 　　摘要：由于多个体系统在信息交流的过程中存在通信时延，系统会出现接收信息滞后的情况，从而影响优化算法的收敛速度。为了解决时延对优化算法产生的影响， 提出了时延情形下的多个体系统分布式随机无梯度优化算法。假定系统中每个个体仅知道其自身的局部目标函数，利用系统中个体间交互时延信息来寻求这些局部目标函数之和的最小值， 通过系统扩维将有时延的优化问题转化为无时延的优化问题。由于个体的局部目标函数有可能非凸故其次梯度不一定存在或很难计算，因而采用分布式随机无梯度方法。理论分析表明只要个体间的通信时延有上界，所提算法依然收敛。 　　关键词：多个体系统；分布式优化；随机无梯度；通信时延 　　TP13 文献标志码：A1672-1098（2016）01-0034-06 　　Abstract：Considering the delay of information communication among agents， which affect the convergence speed of the algorithm， the randomized gradient-free method for multi-agent optimization with communication delay was proposed， where its assumed that every agent only knows its own local objective function. The optimization goal is to minimize a sum of local objective functions through the interaction of delay information among agents in the system. Firstly， the optimization problem with delay was converted into the optimization problem without delay through augmenting delay nodes. Because the local objective function of agent is likely to be nonconvex， its subgradient does not exist or it is hard to be calculated， the distributed randomized gradient-free method was used. The theoretical analysis showed that the proposed algorithm is still convergent if the communication delays are upper bounded. 　　Key words：multi-agent system； distributed optimization； randomized gradient-free， communication delay 　　近年来，多个体分布式凸优化问题及其优化算法引起了人们的广泛关注，而多个体分布式优化算法是在集总式算法的基础上发展起来的。所谓集总式算法是指在多个体系统中，不是所有个体都发挥同样的作用，只有某个个体处于中心地位，负责处理其他个体的数据，并将数据反馈给其他个体。和集总式算法不同，分布式算法则是指多个体系统中的每个个体都对应着一个局部凸目标函数，并且个体之间进行信息交流，最终求得凸目标函数的最小值。和以往的集总式算法相比，分布式算法有很多优点，尤其在许多大规模的优化问题中占有很大优势，并且在生物工程、人工智能等许多领域有广泛应用，因此研究多个体的分布式优化算法有很大的意义。 　　随着计算机的广泛应用，人们进入了大数据云计算的时代，因此对多个体分布式优化的研究也越来越深入。但这些方法主要是标准次梯度和一致性算法的结合。标准次梯度算法是将总的最优化任务分解，同时每个个体需要将自身的信息与周围邻居个体的信息进行加权组合，再根据自身的次梯度信息进行最优化，经过一系列的迭代运算，使得所有个体的状态都达到一致。事实上，一致性算法也是广泛研究的一个课题，即个体间通过信息交流使所有个体的状态最终达到一致并使结果达到最优。文献[1]最早给出了标准次梯度方法并分析了其收敛性。文献[2]922介绍了约束一致性和优化算法。在此基础上，文献[3]则介绍了基于随机投影的次梯度算法，文献[4]1715给出一种基于一致性算法的原