Distributed Proximal Point Algorithm for Constrained Optimization over Unbalanced Graphs
Xiuxian Li, Gang Feng, Lihua Xie · 2019
This paper studies the convergence rate for distributed constrained optimization problems over unbalanced time-varying graphs, where the objective function is composed of an aggregate sum of local objective functions which are known to individual agents. In order to deal with the problem, a distributed proximal point algorithm (DPPA) is revisited, which does not necessitate the computation of subgradients, and the convergence is rigorously analyzed under mild assumptions with a class of general stepsizes, i.e., positive, decaying and nonsummable. Besides, it is proved that the algorithm converges √ at the rate of O(1/ k) in the ergodic sense with respect to the weight-averaged state of all agents, where k > 0 is the iteration number. Moreover, the efficacy of the proposed algorithm is validated by a numerical example.