A Geometrically Converging Dual Method for Distributed Optimization Over Time-Varying Graphs

• 成果类型: Article
• 署名作者: Maros, Marie; Jalden, Joakim
• 署名单位: Royal Institute of Technology; Purdue University System; Purdue University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.3018743
• 发表日期: 2021
• 页码: 2465-2479
• 关键词: Optimization; CONVERGENCE; linear programming; Convex functions; Symmetric matrices; Europe; Information science; Convex Optimization; distributed optimization; time-varying networks

摘要

In this article, we consider a distributed convex optimization problem over time-varying undirected networks. We propose a dual method, primarily averaged network dual ascent (PANDA), that is proven to converge R-linearly to the optimal point given that the agents' objective functions are strongly convex and have Lipschitz continuous gradients. Like dual decomposition, PANDA requires half the amount of variable exchanges per iterate of methods based on DIGing, and can provide with practical improved performance as empirically demonstrated.