A Unifying Approximate Method of Multipliers for Distributed Composite Optimization

• 成果类型: Article
• 署名作者: Wu, Xuyang; Lu, Jie
• 署名单位: Royal Institute of Technology; ShanghaiTech University
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3173171
• 发表日期: 2023
• 页码: 2154-2169
• 关键词: Convex composite optimization; distributed optimization; method of multipliers

摘要

This article investigates solving convex composite optimization on an undirected network, where each node, privately endowed with a smooth component function and a nonsmooth one, is required to minimize the sum of all the component functions throughout the network. To address such a problem, a general approximate method of multipliers (AMM) is developed, which attempts to approximate the method of multipliers by virtue of a surrogate function with numerous options. We then design the possibly nonseparable, time-varying surrogate function in various ways, leading to different distributed realizations of AMM. We demonstrate that AMM generalizes more than ten state-of-the-art distributed optimization algorithms, and certain specific designs of its surrogate function result in a variety of new algorithms to the literature. Furthermore, we show that AMM is able to achieve an O(1/k) rate of convergence to optimality, and the convergence rate becomes linear when the problem is locally restricted strongly convex and smooth. Such convergence rates provide new or stronger convergence results to many prior methods that can be viewed as specializations of AMM.