On the Convergence Properties of a Distributed Projected Subgradient Algorithm
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.
|ESI Research Field|
Cited Times [WOS]:0
|Document Type||Journal Article|
|Department||School of System Design and Intelligent Manufacturing|
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
|First Author Affilication||School of System Design and Intelligent Manufacturing|
|First Author's First Affilication||School of System Design and Intelligent Manufacturing|
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).
|Files in This Item:||There are no files associated with this item.|
|Recommend this item|
|Export to Endnote|
|Export to Excel|
|Export to Csv|
|Similar articles in Google Scholar|
|Similar articles in Baidu Scholar|
|Similar articles in Bing Scholar|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.