快速在线分布式对偶平均优化算法  

Fast online distributed dual average optimization algorithm

作　　者：李德权 王俊雅 马驰 周跃进 LI Dequan, WANG Junya, MA Chi, ZHOU Yuejin(School of Mathematics and Big Data, Anhui University of Science and Technology, Huainan Anhui 232000, Chin)

机构地区：[1]安徽理工大学数学与大数据学院,安徽淮南232000

出　　处：《计算机应用》2018年第8期2337-2342,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61472003;11701007);安徽省高校学科(专业)拔尖人才学术资助重点项目(gxbj ZD2016049);安徽省学术和技术带头人及后备人选科研活动项目(2016H076);安徽省自然科学基金资助项目(KJ2017A087)~~

摘　　要：为提高分布式在线优化算法的收敛速度,对底层网络拓扑依次添边,提出一种快速的一阶分布式在线对偶平均优化(FODD)算法。首先,对于分布式在线优化问题,运用添边方法使所选的边与网络模型快速混合,进而建立数学模型并设计FODD算法对其进行优化求解。其次,揭示了网络拓扑和在线分布式对偶平均收敛速度之间的关系,通过提高底层拓扑网络的代数连通度改进了Regret界,将在线分布式对偶平均(ODDA)算法从静态网络拓展到时变网络拓扑上,并证明了FODD算法的收敛性,同时解析地给出了收敛速度。最后的数值仿真表明:和ODDA算法相比,所提出的FODD算法具有更快的收敛速度。To improve the convergence speed of distributed online optimization algorithms,a fast first-order Online Distributed Dual Average optimization（ FODD） algorithm was proposed by sequentially adding edges to the underlying network topology. Firstly,aiming at solving the problem of the online distributed optimization to make the selected edge and network model mix quickly by using the method of edge addition,a mathematical model was established and solved by FODD.Secondly,the relationship between network topology designed and the convergence rate of the online distributed dual average algorithm was revealed,which clearly showed that,by improving the algebraic connectivity of the underlying topology network,the Regret bound could also be greatly improved. The Online Distributed Dual Average（ ODDA） algorithm was extended from static networks to time-varying networks. Meanwhile,the proposed FODD algorithm was proved to be convergent and the convergence rate was specified. Finally,the results of numerical simulations show that,compared with existing algorithms such as ODDA,the proposed FODD algorithm has better convergence performance.

关 键 词：分布式网络 在线分布式对偶平均 Regret界 代数连通度 拉普拉斯矩阵 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]