DC-DistADMM: ADMM Algorithm for Constrained Optimization Over Directed Graphs

• 成果类型: Article
• 署名作者: Khatana, Vivek; Salapaka, Murti V.
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3221856
• 发表日期: 2023
• 页码: 5365-5380
• 关键词: Alternating direction method of multipliers (ADMM); constrained optimization; Directed graphs; finite-time consensus; distributed optimization; multiagent networks

摘要

This article reports an algorithm formultiagent distributed optimization problems with a common decision variable, local linear equality, and inequality, constraints and set constraints with convergence rate guarantees. The algorithm accrues all the benefits of the alternating direction method of multipliers (ADMM) approach. It also overcomes the limitations of existing methods on convex optimization problems with linear inequality, equality, and set constraints by allowing directed communication topologies. Moreover, the algorithm can be synthesized distributively. The developed algorithm has: first, a O(1/k) rate of convergence, where k is the iteration counter, when individual functions are convex but not-necessarily differentiable, and second, a geometric rate of convergence to any arbitrary small neighborhood of the optimal solution, when the objective functions are smooth and restricted strongly convex at the optimal solution. The efficacy of the algorithm is evaluated by a comparison with state-of-theart constrained optimization algorithms in solving a constrained distributed l(1) -regularized logistic regression problem, and unconstrained optimization algorithms in solving a l(1)-regularized Huber loss minimization problem. Additionally, a comparison of the algorithm's performance with other algorithms in the literature that utilize multiple communication steps is provided.