Constrained Consensus and Optimization in Multi-Agent Networks

2010/02/11 by A. Nedic, A. Nedić, Asuman Ozdaglar +3 · 107 citations
Computer Science · #Distributed Control Multi-Agent Systems #Energy Efficient Wireless Sensor Networks #Mobile Ad Hoc Networks

paper · doi:10.1109/tac.2010.2041686

Abstract

<para xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. </para>

Citations

• Consensus Problems in Networks of Agents With Switching Topology and Time-Delays

Cited by

• Multi-agent flocking control with complex obstacles and adaptive distributed convex optimization
• Distributed stochastic gradient tracking methods
• Distributed Optimization via Energy Conservation Laws in Dilated Coordinates
• Continuous-Time Distributed Algorithms for Extended Monotropic Optimization Problems
• Energy management for building district cooling: a distributed approach to resource sharing
• Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm
• Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors
• Distributed Algorithms that Solve Boolean Equations with Local and Differential Privacies
• Distributed Adaptive Gradient Optimization Algorithm
• Distributed Online Linear Regression
• Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization
• Analysis of Newton-Raphson Consensus for multi-agent convex optimization\n under asynchronous and lossy communications
• Distributed Nonlinear Equality-Constrained Optimization via Feedback Linearization and Singular Perturbation
• Tight Nonparametric Convergence Rates for Stochastic Gradient Descent under the Noiseless Linear Model
• Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications
• Distributed Least Squares Solver for Network Linear Equations
• Asynchronous and time-varying proximal type dynamics multi-agent network games
• NEXT: In-Network Nonconvex Optimization
• An Accelerated Primal Dual Algorithm with Backtracking for Decentralized Constrained Optimization
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• Distributed Riemannian Optimization in Geodesically Non-convex Environments
• Non-Ergodic Convergence Algorithms for Distributed Consensus and Coupling-Constrained Optimization
• Stochastic Proximal Gradient Consensus Over Random Networks
• Distributed Continuous-Time Algorithm for Constrained Convex Optimizations via Nonsmooth Analysis Approach
• Targeted Algorithmic Purpose-Driven Cyber Attacks in Distributed Multi-Agent Optimization
• Resilient and Efficient Allocation for Large-Scale Autonomous Fleets via Decentralized Coordination
• Secure and Privacy-Preserving Consensus
• Privacy Preservation in Distributed Subgradient Optimization Algorithms
• Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks
• A Coordinate Descent Primal-Dual Algorithm and Application to\n Distributed Asynchronous Optimization
• Distributed Algorithms for Aggregative Games on Graphs
• Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
• Differentially Private Linear Regression over Fully Decentralized Datasets
• Structural Controllability on Graphs for Drifted Bilinear Systems over Lie Groups
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• A Bregman Splitting Algorithm for Distributed Optimization over Networks
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• The Minimax Complexity of Distributed Optimization
• Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization
• Distributed Aggregative Optimization over Multi-Agent Networks
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• Distributed coordination for nonsmooth convex optimization via\n saddle-point dynamics
• Characterizing Trust and Resilience in Distributed Consensus for Cyberphysical Systems
• Randomized Optimal Consensus of Multi-agent Systems
• Privacy-Preserving Average Consensus via State Decomposition
• Distributed Online Optimization with Long-Term Constraints
• Convergence Analysis of Noisy Distributed Gradient Descent for Non-convex Optimization -- Saddle Point Escape
• Distributed Solver for Discrete-Time Lyapunov Equations Over Dynamic Networks with Linear Convergence Rate
• Communication-Efficient Algorithms For Distributed Optimization
• Optimal Consensus for Uncertain High-order Multi-agent Systems by Output Feedback
• An Approximate Projected Consensus Algorithm for Computing Intersection of Convex Sets
• Optimization over time-varying directed graphs with row and column-stochastic matrices
• Resilient Multi-Dimensional Consensus and Distributed Optimization against Agent-Based and Denial-of-Service Attacks
• Multi-Agent Distributed Optimization With Feasible Set Privacy
• A "Safe Kernel" Approach for Resilient Multi-Dimensional Consensus
• Linear convergence in optimization over directed graphs with row-stochastic matrices
• Distributed Sparse Regression via Penalization
• Performance of a Distributed Stochastic Approximation Algorithm
• Nested Distributed Gradient Methods with Stochastic Computation Errors
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• Differentially Private Distributed Computation via Public-Private Communication Networks
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• Balancing Communication and Computation in Distributed Optimization
• An Overview of Recent Progress in the Study of Distributed Multi-agent Coordination
• Distributed Estimation of Sparse Inverse Covariances
• Reaching an Optimal Consensus: Dynamical Systems that Compute Intersections of Convex Sets
• Control of Multi-Layer Mobile Autonomous Systems in Adversarial Environments: A Games-in-Games Approach
• A Decentralized Multi-Objective Optimization Algorithm
• Towards time-varying proximal dynamics in Multi-Agent Network Games
• Distributed Subgradient Projection Algorithm over Directed Graphs
• Mass-spring-damper Networks for Distributed Optimization in Non-Euclidean Spaces
• An Arrow-Hurwicz-Uzawa Type Flow as Least Squares Solver for Network Linear Equations
• Distributed optimization: designed for federated learning
• Towards an O((1)/(t)) convergence rate for distributed dual averaging
• From Global Linear Computations to Local Interaction Rules
• Products of Generalized Stochastic Sarymsakov Matrices
• Distributed Integer Balancing under Weight Constraints in the Presence of Transmission Delays and Packet Drops
• Rate of Convergence for Distributed Optimization with Uncertain Communications
• Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery
• Receding Horizon Consensus of General Linear Multi-agent Systems with Input Constraints: An Inverse Optimality Approach
• Decentralized online stochastic generalized Nash Equilibrium seeking for multi-cluster games: A Byzantine-resilient algorithm
• Energy Aware Architecture for Coordinated Mobility: An Approximate Dynamic Programming Approach
• Dynamical Privacy in Distributed Computing -- Part I: Privacy Loss and PPSC Mechanism
• On the Distributed Optimization over Directed Networks
• ReCoDe: Reinforcement Learning-based Dynamic Constraint Design for Multi-Agent Coordination
• Cybersecurity Challenges in Distributed Control
• Distributed Multi-agent Video Fast-forwarding
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• Randomized Gradient-Free Distributed Online Optimization via a Dynamic Regret Analysis
• Distributed Stochastic Optimization With Unbounded Subgradients Over Randomly Time-Varying Networks
• Convergence Properties of the Distributed Projected Subgradient Algorithm over General Graphs
• Byzantine Fault-Tolerance in Decentralized Optimization under Minimal Redundancy
• Dynamics Based Privacy Protection for Average Consensus on Directed Graphs
• Continuous-Time Consensus under Non-Instantaneous Reciprocity
• Distributed Nash Equilibrium Seeking in Non-Monotone Games over the Simplex
• A Distributed Algorithm for Least Square Solutions of Linear Equations
• Distributed Interval Optimization with Stochastic Zeroth-order Oracle
• A Private and Finite-Time Algorithm for Solving a Distributed System of Linear Equations
• On the stability and convergence of a class of consensus systems with a nonlinear input
• No-regret distributed learning in subnetwork zero-sum games
• Robust Consensus Analysis and Design under Relative State Constraints or Uncertainties
• Robust Consensus of Linear Multi-Agent Systems under Input Constraints or Uncertainties
• Energy-Based Acoustic Source Localization Methods: A Survey. [europepmc]
• Robust consensus tracking control of multiple mechanical systems under fixed and switching interaction topologies. [europepmc]
• EDDA: An Efficient Distributed Data Replication Algorithm in VANETs. [europepmc]
• Experimental Validation of Entropy-Driven Swarm Exploration under Sparsity Constraints with Sparse Bayesian Learning. [europepmc]
• Decentralized Primal-Dual Proximal Operator Algorithm for Constrained Nonsmooth Composite Optimization Problems over Networks. [europepmc]

Related

• Multi-agent constrained optimization of a strongly convex function over\n time-varying directed networks
• Distributed algorithms for solving convex inequalities
• Distributed Optimization under Edge Agreements: A Continuous-Time Algorithm
• A primal-dual method for conic constrained distributed optimization problems
• An approximate dual subgradient algorithm for multi-agent non-convex optimization