Convergence Analysis of Dual Decomposition Algorithm in Distributed Optimization: Asynchrony and Inexactness

• 成果类型: Article
• 署名作者: Su, Yifan; Wang, Zhaojian; Cao, Ming; Jia, Mengshuo; Liu, Feng
• 署名单位: Tsinghua University; Shanghai Jiao Tong University; University of Groningen; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3213608
• 发表日期: 2023
• 页码: 4767-4782
• 关键词: Asynchronous algorithm; distributed optimization; dual decomposition; inexact algorithm; Multiagent system (MAS)

摘要

Dual decomposition is widely utilized in the distributed optimization of multiagent systems. In practice, the dual decomposition algorithm is desired to admit an asynchronous implementation due to imperfect communication, such as time delay and packet drop. In addition, computational errors also exist when the individual agents solve their own subproblems. In this article, we analyze the convergence of the dual decomposition algorithm in the distributed optimization when both the communication asynchrony and the subproblem solution inexactness exist. We find that the interaction between asynchrony and inexactness slows down the convergence rate from O(1/k) to O(1/v/k). Specifically, with a constant step size, the value of the objective function converges to a neighborhood of the optimal value, and the solution converges to a neighborhood of the optimal solution. Moreover, the violation of v/ the constraints diminishes in O(1/ k). Our result generalizes and unifies the existing ones that only consider either asynchrony or inexactness. Finally, numerical simulations validate the theoretical results.