A distributed ADMM-like method for resource sharing over time-varying networks

DOI10.1137/17M1151973zbMATH Open1427.90214arXiv1611.07393OpenAlexW2994958082WikidataQ126571596 ScholiaQ126571596MaRDI QIDQ5206938FDOQ5206938

Authors: N. S. Aybat, Erfan Yazdandoost Hamedani 

Publication date: 19 December 2019

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We consider cooperative multi-agent resource sharing problems over time-varying communication networks, where only local communications are allowed. The objective is to minimize the sum of agent-specific composite convex functions subject to a conic constraint that couples agents' decisions. We propose a distributed primal-dual algorithm DPDA-D to solve the saddle point formulation of the sharing problem on time-varying (un)directed communication networks; and we show that primal-dual iterate sequence converges to a point defined by a primal optimal solution and a consensual dual price for the coupling constraint. Furthermore, we provide convergence rates for suboptimality, infeasibility and consensus violation of agents' dual price assessments; examine the effect of underlying network topology on the convergence rates of the proposed decentralized algorithm; and compare DPDA-D with a centralized method on the basis pursuit denoising and multi-channel power allocation problems.

Full work available at URL: https://arxiv.org/abs/1611.07393

Recommendations

• Distributed resource allocation via multi-agent systems under time-varying networks
• Distributed inexact dual consensus ADMM for network resource allocation
• Decentralized Resource Allocation in Dynamic Networks of Agents
• Distributed resource allocation on dynamic networks in quadratic time
• Distributed constraint-coupled optimization via primal decomposition over random time-varying graphs

zbMATH Keywords

convex optimizationconvergence rateprimal-dual methodmultiagent distributed optimizationresource sharing problem

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Optimality conditions and duality in mathematical programming (90C46)

Cites Work

• Title not available (Why is that?)
• Compressed sensing
• Subgradient methods for saddle-point problems
• A first-order primal-dual algorithm for convex problems with applications to imaging
• Title not available (Why is that?)
• Consensus and Cooperation in Networked Multi-Agent Systems
• Convergence analysis of primal-dual algorithms for a saddle-point problem: from contraction perspective
• Distributed Subgradient Methods for Multi-Agent Optimization
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Title not available (Why is that?)
• Cooperative distributed multi-agent optimization
• On Distributed Averaging Algorithms and Quantization Effects
• Parallel multi-block ADMM with \(o(1/k)\) convergence
• Mirror Prox algorithm for multi-term composite minimization and semi-separable problems
• A first-order augmented Lagrangian method for compressed sensing
• On the ergodic convergence rates of a first-order primal-dual algorithm
• Optimal primal-dual methods for a class of saddle point problems
• Distributed Optimization Over Time-Varying Directed Graphs
• Decentralized Resource Allocation in Dynamic Networks of Agents
• Fastest Mixing Markov Chain on a Graph
• A Distributed Algorithm for Resource Allocation Over Dynamic Digraphs
• Distributed resource allocation on dynamic networks in quadratic time
• Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
• Achieving Geometric Convergence for Distributed Optimization Over Time-Varying Graphs
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization
• A Proximal Dual Consensus ADMM Method for Multi-Agent Constrained Optimization
• A distributed ADMM-like method for resource sharing over time-varying networks
• Distributed Saddle-Point Subgradient Algorithms With Laplacian Averaging
• Collaborative Resource Allocation Over a Hybrid Cloud Center and Edge Server Network

Cited In (13)

• Distributed convex optimization with coupling constraints over time-varying directed graphs
• Distributed resource allocation via multi-agent systems under time-varying networks
• Decentralized optimization with affine constraints over time-varying networks
• Distributed inexact dual consensus ADMM for network resource allocation
• A primal-dual algorithm with line search for general convex-concave saddle point problems
• Decentralized Resource Allocation in Dynamic Networks of Agents
• Distributed learning in congested environments with partial information
• On iteration complexity of a first-order primal-dual method for nonlinear convex cone programming
• A distributed methodology for approximate uniform global minimum sharing
• Privacy-preserving dual stochastic push-sum algorithm for distributed constrained optimization
• Regularized dual gradient distributed method for constrained convex optimization over unbalanced directed graphs
• Distributed delay-tolerant strategies for equality-constraint sum-preserving resource allocation
• A distributed ADMM-like method for resource sharing over time-varying networks

This page was built for publication: A distributed ADMM-like method for resource sharing over time-varying networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5206938)