
Dual decomposition is widely utilized in distributed optimization of multi-agent 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 individual agents solve their own subproblems. In this paper, we analyze the convergence of the dual decomposition algorithm in distributed optimization when both the asynchrony in communication and the inexactness in solving subproblems exist. We find that the interaction between asynchrony and inexactness slows down the convergence rate from $\mathcal{O} ( 1 / k )$ to $\mathcal{O} ( 1 / \sqrt{k} )$. Specifically, with a constant step size, the value of objective function converges to a neighborhood of the optimal value, and the solution converges to a neighborhood of the exact optimal solution. Moreover, the violation of the constraints diminishes in $\mathcal{O} ( 1 / \sqrt{k} )$. Our result generalizes and unifies the existing ones that only consider either asynchrony or inexactness. Finally, numerical simulations validate the theoretical results.
Optimization, Asynchronous algorithm, dual decomposition, Multi-agent systems, inexact algorithm, Systems and Control (eess.SY), Electrical Engineering and Systems Science - Systems and Control, Power systems, Newton method, Optimization and Control (math.OC), Linear programming, multi-agent system, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Heuristic algorithms, Convergence, distributed optimization, Mathematics - Optimization and Control
Optimization, Asynchronous algorithm, dual decomposition, Multi-agent systems, inexact algorithm, Systems and Control (eess.SY), Electrical Engineering and Systems Science - Systems and Control, Power systems, Newton method, Optimization and Control (math.OC), Linear programming, multi-agent system, FOS: Mathematics, FOS: Electrical engineering, electronic engineering, information engineering, Heuristic algorithms, Convergence, distributed optimization, Mathematics - Optimization and Control
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 8 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
