On the Convergence Properties of a Distributed Projected Subgradient Algorithm

Li，Weijian1; Chen，Zihan2; Lou，Youcheng3; Hong，Yiguang4

2023

10.1109/TAC.2023.3284599

IEEE Transactions on Automatic Control   Impact Factor & Quartile

0018-9286

1558-2523

A weight-balanced network plays an important role in the exact convergence of distributed optimization algorithms, but is not always satisfied in practice. Different from most of existing works focusing on designing distributed algorithms, we analyze the convergence of a well-known distributed projected subgradient algorithm over time-varying general graph sequences, i.e., the weight matrices of the network are only required to be row stochastic instead of doubly stochastic. We first show that there may exist a graph sequence such that the algorithm is not convergent when the network switches freely within finitely many graphs. Then to guarantee its convergence under any uniformly jointly strongly connected graph sequence, we provide a necessary and sufficient condition on the cost functions, i.e., the intersection of optimal solution sets to all local optimization problems is not empty. Furthermore, we surprisingly find that the algorithm is convergent for any periodically switching graph sequence, but the converged solution minimizes a weighted sum of local cost functions, where the weights depend on the Perron vectors of some product matrices of the underlying switching graphs. Finally, we consider a slightly broader class of quasi-periodically switching graph sequences, and show that the algorithm is convergent for any quasi-periodic graph sequence if and only if the network switches between only two graphs. This work helps us understand impacts of communication networks on the convergence of distributed algorithms, and complements existing results from a different viewpoint.

Communication network constrained distributed optimization Convergence convergence analysis Distributed algorithms Heuristic algorithms Network topology projected subgradient algorithm Stochastic processes Switches Topology

English

First

ENGINEERING

2-s2.0-85162647244

Scopus

1.School of System Design and Intelligent Manufacturing, South University of Science and Technology of China, Shenzhen, Guangdong, China
2.Huawei Technologies Co., Ltd., Beijing, China
3.MDIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
4.Department of Control Science and Engineering, Tongji University, China

Li，Weijian,Chen，Zihan,Lou，Youcheng,et al. On the Convergence Properties of a Distributed Projected Subgradient Algorithm[J]. IEEE Transactions on Automatic Control,2023.

Li，Weijian,Chen，Zihan,Lou，Youcheng,&Hong，Yiguang.(2023).On the Convergence Properties of a Distributed Projected Subgradient Algorithm.IEEE Transactions on Automatic Control.

Li，Weijian,et al."On the Convergence Properties of a Distributed Projected Subgradient Algorithm".IEEE Transactions on Automatic Control (2023).