On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers

Abstract

We consider a network of agents that are cooperatively solving a global optimization problem, where the objective function is the sum of privately known local objective functions of the agents and the decision variables are coupled via linear constraints. Recent literature focused on special cases of this formulation and studied their distributed solution through either subgradient based methods with O(1/sqrt(k)) rate of convergence (where k is the iteration number) or Alternating Direction Method of Multipliers (ADMM) based methods, which require a synchronous implementation and a globally known order on the agents. In this paper, we present a novel asynchronous ADMM based distributed method for the general formulation and show that it converges at the rate O(1/k).

Short version 30 pages

References in corpus (1)

• Asynchronous Distributed Optimization using a Randomized Alternating Direction Method of Multipliers

Cited by in corpus (25)

• Distributed Nash Equilibrium Seeking under Partial-Decision Information via the Alternating Direction Method of Multipliers
• Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
• A Distributed Asynchronous Method of Multipliers for Constrained Nonconvex Optimization
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• A Distributed, Asynchronous and Incremental Algorithm for Nonconvex Optimization: An ADMM Based Approach
• A Simple Convergence Time Analysis of Drift-Plus-Penalty for Stochastic Optimization and Convex Programs
• Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems
• Stochastic Proximal Gradient Consensus Over Random Networks
• Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
• Private Learning on Networks: Part II
• Distributed Augmented Lagrangian Method for Link-Based Resource Sharing Problems of Multi-Agent Systems
• Decentralized Consensus Optimization with Asynchrony and Delays
• Communication-Efficient Algorithms for Decentralized and Stochastic Optimization
• Decentralized Consensus Algorithm with Delayed and Stochastic Gradients
• Asynchronous decentralized accelerated stochastic gradient descent
• A Simple Parallel Algorithm with an $O(1/t)$ Convergence Rate for General Convex Programs
• A Fully-Distributed Asynchronous Approach for Multi-Area Coordinated Network-Constrained Unit Commitment
• Distributed Optimization for Client-Server Architecture with Negative Gradient Weights
• A Randomized Block Coordinate Iterative Regularized Gradient Method for High-dimensional Ill-posed Convex Optimization
• Cloud-Assisted Remote Sensor Network Virtualization for Distributed Consensus Estimation
• Toward Creating Subsurface Camera
• Distributed Online Modified Greedy Algorithm for Networked Storage Operation under Uncertainty
• A randomized primal distributed algorithm for partitioned and big-data non-convex optimization
• Distributed Partitioned Big-Data Optimization via Asynchronous Dual Decomposition
• On linear convergence of a distributed dual gradient algorithm for linearly constrained separable convex problems