一类时变有向图中的PUSH-SUM分布式对偶平均优化算法

Distributed Push-Sum Dual Averaging for Convex Optimizationover Time-Varying Directed Graphs

利用push-sum通信协议并结合分布式对偶平均方法,在时变有向图中,讨论了一类带有简单约束集的分布式凸优化问题.首先提出了push-sum分布式对偶平均算法,然后分析了算法的收敛性,并得到了算法的收敛率为O(1/√T),最后用l1线性回归问题的数值结果验证了所提出算法的有效性.对比现有的一些结果,所提出的算法能用于求解带约束的分布式优化问题,并且去掉了网络通讯权矩阵是双随机的限制.

A distributed convex optimization problem with simple constraints over time-varying directed graphs has been investigated in this paper. By combining the push-sum scheme and distributed dual averaging method, a distributed dual averaging algorithm with push-sum protocolhas first beenproposed. Then, the convergenceof the proposed method has beenestablished,and the explicit convergence rate with order of O(1/√T) been obtained.Finally, a numerical example on linear regression problem has beenused to demonstrate the effectiveness of the proposed algorithm. Compared with existing works, our algorithm is not required the doublestochasticity of the communication weight matrices. Meanwhile, the proposed algorithm can be used to solve a large class of constrained convex optimization.