On the Convergence Properties of a Distributed Projected Subgradient Algorithm

• 成果类型: Article
• 署名作者: Li, Weijian; Chen, Zihan; Lou, Youcheng; Hong, Yiguang
• 署名单位: Southern University of Science & Technology; Huawei Technologies; Chinese Academy of Sciences; Tongji University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2023.3284599
• 发表日期: 2023
• 页码: 7546-7559
• 关键词: Communication network; constrained distributed optimization; convergence analysis; projected subgradient algorithm

摘要

A weight-balanced network plays an important role in the exact convergence of a distributed optimization algorithm, but is not always satisfied in practice. Different from most of existing works focusing on designing distributed algorithms, in this article, 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.