Distributed Gradient Tracking for Unbalanced Optimization With Different Constraint Sets

• 成果类型: Article
• 署名作者: Cheng, Songsong; Liang, Shu; Fan, Yuan; Hong, Yiguang
• 署名单位: Anhui University; Tongji University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3192316
• 发表日期: 2023
• 页码: 3633-3640
• 关键词: Optimization; CONVERGENCE; Directed graphs; Convex functions; Multi-agent systems; linear programming; Heuristic algorithms; different constraint sets; distrib- uted optimization; gradient tracking; unbalanced graphs

摘要

tracking methods have become popular for distributed optimization in recent years, partially because they achieve linear convergence using only a constant step-size for strongly convex optimization. In this article, we construct a counterexample on constrained optimization to show that direct extension of gradient tracking by using projections cannot guarantee the correctness. Then, we propose projected gradient tracking algorithms with diminishing step-sizes rather than a constant one for distributed strongly convex optimization with different constraint sets and unbalanced graphs. Our basic algorithm can achieve O(ln T/T ) convergence rate. Moreover, we design an epoch iteration scheme and improve the convergence rate as O(1/T ).