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

Fast online distributed dual average optimization algorithm

为提高分布式在线优化算法的收敛速度,对底层网络拓扑依次添边,提出一种快速的一阶分布式在线对偶平均优化(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.