Constrained Consensus

Abstract

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 estimate of each agent is restricted to lie in a different constraint set. To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed ``projected consensus algorithm'' in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed ``projected subgradient algorithm'' which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set.

35 pages. Included additional results, removed two subsections, added references, fixed typos

References in corpus (3)

• Novel type of phase transition in a system of self-driven particles
• Constrained Consensus
• Incremental Stochastic Subgradient Algorithms for Convex Optimization

Cited by in corpus (240)

• Constrained Consensus
• Gossip Algorithms for Distributed Signal Processing
• Initialization-free Distributed Algorithms for Optimal Resource Allocation with Feasibility Constraints and its Application to Economic Dispatch of Power Systems
• Multi-Agent Distributed Optimization via Inexact Consensus ADMM
• Optimal parameter selection for the alternating direction method of multipliers (ADMM): quadratic problems
• Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
• Distributed Convex Optimization for Continuous-Time Dynamics with Time-Varying Cost Function
• Distributed Random Projection Algorithm for Convex Optimization
• ADD-OPT: Accelerated Distributed Directed Optimization
• Optimal Output Consensus of High-Order Multi-Agent Systems with Embedded Technique
• Optimal Output Consensus for Nonlinear Multi-agent Systems with Both Static and Dynamic Uncertainties
• Distributed Optimization for Smart Cyber-Physical Networks
• Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents
• Asynchronous Distributed Optimization over Lossy Networks via Relaxed ADMM: Stability and Linear Convergence
• A Polyhedral Approximation Framework for Convex and Robust Distributed Optimization
• Distributed Continuous-Time and Discrete-Time Optimization With Nonuniform Unbounded Convex Constraint Sets and Nonuniform Stepsizes
• On the Influence of Bias-Correction on Distributed Stochastic Optimization
• Linear Time Average Consensus on Fixed Graphs and Implications for Decentralized Optimization and Multi-Agent Control
• Convergence Rates of Distributed Nesterov-like Gradient Methods on Random Networks
• On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods
• Minibatch vs Local SGD for Heterogeneous Distributed Learning
• On the O(1/k) Convergence of Asynchronous Distributed Alternating Direction Method of Multipliers
• Distributed Optimization for a Class of High-order Nonlinear Multi-agent Systems with Unknown Dynamics
• A unitary distributed subgradient method for multi-agent optimization with different coupling sources
• A Distributed Algorithm for Computing a Common Fixed Point of a Finite Family of Paracontractions
• A Sharp Estimate on the Transient Time of Distributed Stochastic Gradient Descent
• Distributed Online Optimization in Time-Varying Unbalanced Networks without Explicit Subgradients
• On Distributed Non-convex Optimization: Projected Subgradient Method For Weakly Convex Problems in Networks
• On the Linear Convergence of Distributed Optimization over Directed Graphs
• DC-DistADMM: ADMM Algorithm for Constrained Distributed Optimization over Directed Graphs
• Distributed Training of Graph Convolutional Networks
• Multi-hop Diffusion LMS for Energy-constrained Distributed Estimation
• Distributed Constrained Online Learning
• Distributed Gradient Methods with Variable Number of Working Nodes
• A System Theoretical Perspective to Gradient-Tracking Algorithms for Distributed Quadratic Optimization
• Reinforcement Learning for Distributed Transient Frequency Control with Stability and Safety Guarantees
• Distributed Stochastic Approximation: Weak Convergence and Network Design
• Distributed coordination for nonsmooth convex optimization via saddle-point dynamics
• Recurrent Averaging Inequalities in Multi-Agent Control and Social Dynamics Modeling
• Differential Inequalities in Multi-Agent Coordination and Opinion Dynamics Modeling
• Generalized gradient optimization over lossy networks for partition-based estimation
• Fault-Tolerant Distributed Optimization (Part IV): Constrained Optimization with Arbitrary Directed Networks
• Distributed Nonconvex Multiagent Optimization Over Time-Varying Networks
• Optimal scaling of the ADMM algorithm for distributed quadratic programming
• Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
• Continuous-Time Distributed Algorithms for Extended Monotropic Optimization Problems
• Stochastic Proximal Gradient Consensus Over Random Networks
• Distributed Mirror Descent over Directed Graphs
• A Multitask Diffusion Strategy with Optimized Inter-Cluster Cooperation
• Distributed Stochastic Gradient Tracking Methods
• Distributed Online Linear Regression
• Distributed Primal-dual Interior-point Methods for Solving Loosely Coupled Problems Using Message Passing
• Newton-Raphson Consensus under asynchronous and lossy communications for peer-to-peer networks
• Novel Stability Conditions for Nonlinear Monotone Systems and Consensus in Multi-Agent Networks
• Optimization over time-varying directed graphs with row and column-stochastic matrices
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• A Distributed Algorithm for Least Square Solutions of Linear Equations
• Distributed Safe Control Design and Probabilistic Safety Verification for Multi-Agent Systems
• A distributed primal-dual interior-point method for loosely coupled problems using ADMM
• Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
• Distributed Stochastic Approximation for Solving Network Optimization Problems Under Random Quantization
• Extensions of Fast-Lipschitz Optimization
• Modulus consensus in discrete-time signed networks and properties of special recurrent inequalities
• A Distributed Algorithm for Solving a Linear Algebraic Equation
• Accelerated Dual Averaging Methods for Decentralized Constrained Optimization
• Distributed Algorithms for Linearly-Solvable Optimal Control in Networked Multi-Agent Systems
• Primal-Dual Distributed Temporal Difference Learning
• Distributed interpolatory algorithms for set membership estimation
• Balancing Communication and Computation in Distributed Optimization
• Distributed Aggregative Optimization over Multi-Agent Networks
• Distributed Stochastic Approximation Algorithm With Expanding Truncations: Algorithm and Applications
• Average Consensus in the Presence of Delays and Dynamically Changing Directed Graph Topologies
• Byzantine Fault-Tolerance in Peer-to-Peer Distributed Gradient-Descent
• Rate of Convergence for Distributed Optimization with Uncertain Communications
• On the Distributed Optimization over Directed Networks
• Network Flows that Solve Least Squares for Linear Equations
• Distributed Optimization: Convergence Conditions from a Dynamical System Perspective
• Lyapunov Approach to Consensus Problems
• Distributed Continuous-Time Algorithm for Constrained Convex Optimizations via Nonsmooth Analysis Approach
• Optimal Distributed Stochastic Mirror Descent for Strongly Convex Optimization
• Transmission-Constrained Consensus of Multiagent Networks
• Passivity-Based Distributed Optimization with Communication Delays Using PI Consensus Algorithm
• Improving the Transient Times for Distributed Stochastic Gradient Methods
• Distributed Zero-Order Optimization under Adversarial Noise
• Distributed Optimization with Projection-free Dynamics
• Randomized Block Proximal Methods for Distributed Stochastic Big-Data Optimization
• Push-sum on random graphs
• A Distributed Stochastic Gradient Tracking Method
• Differentially Private Distributed Computation via Public-Private Communication Networks
• NEXT: In-Network Nonconvex Optimization
• A Continuous-Time Nesterov Accelerated Gradient Method for Centralized and Distributed Online Convex Optimization
• Distributed Subgradient Projection Algorithm over Directed Graphs
• Small-Gain Theorem Based Distributed Prescribed-Time Convex Optimization For Networked Euler-Lagrange Systems
• An Approximate Projected Consensus Algorithm for Computing Intersection of Convex Sets
• Privacy Preservation in Distributed Subgradient Optimization Algorithms
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• Communication-Efficient Algorithms For Distributed Optimization
• Distributed Nonconvex Optimization: Gradient-free Iterations and $\epsilon$-Globally Optimal Solution
• A "Safe Kernel" Approach for Resilient Multi-Dimensional Consensus
• Distributed Abstract Optimization via Constraints Consensus: Theory and Applications
• Distributed Autonomous Online Learning: Regrets and Intrinsic Privacy-Preserving Properties
• Distributed Weight Selection in Consensus Protocols by Schatten Norm Minimization
• Distributed Submodular Minimization And Motion Coordination Over Discrete State Space
• Distributed Online Optimization with Long-Term Constraints
• Network Flows that Solve Sylvester Matrix Equations
• Asynchronous and time-varying proximal type dynamics multi-agent network games
• Byzantine Fault-Tolerance in Decentralized Optimization under Minimal Redundancy
• Distributed Stochastic Nonconvex Optimization and Learning based on Successive Convex Approximation
• No-regret distributed learning in subnetwork zero-sum games
• Collaborative Multi-Agent Video Fast-Forwarding
• A cutting-surface consensus approach for distributed robust optimization of multi-agent systems
• Distributed Mirror Descent for Online Composite Optimization
• Projected Push-Sum Gradient Descent-Ascent for Convex Optimizationwith Application to Economic Dispatch Problems
• Randomized Gradient-Free Distributed Online Optimization via a Dynamic Regret Analysis
• Dynamical Privacy in Distributed Computing -- Part I: Privacy Loss and PPSC Mechanism
• Dynamics Based Privacy Protection for Average Consensus on Directed Graphs
• Linearly Convergent Asynchronous Distributed ADMM via Markov Sampling
• Dynamical Privacy in Distributed Computing -- Part II: PPSC Gossip Algorithms
• A Resilient Convex Combination for consensus-based distributed algorithms
• Secure and Privacy-Preserving Consensus
• Linear convergence in optimization over directed graphs with row-stochastic matrices
• Subgradient-Free Stochastic Optimization Algorithm for Non-smooth Convex Functions over Time-Varying Networks
• Network Flows that Solve Linear Equations
• Distributed continuous-time convex optimization on weight-balanced digraphs
• Fast Decentralized Optimization over Networks
• Products of Generalized Stochastic Sarymsakov Matrices
• Distributed robust adaptive equilibrium computation for generalized convex games
• Distributed Continuous-time Approximate Projection Protocols for Shortest Distance Optimization Problems
• Tight Linear Convergence Rate of ADMM for Decentralized Optimization
• Cybersecurity Challenges in Distributed Control
• A Unification and Generalization of Exact Distributed First Order Methods
• From Global Linear Computations to Local Interaction Rules
• Characterizing Trust and Resilience in Distributed Consensus for Cyberphysical Systems
• A Bregman Splitting Algorithm for Distributed Optimization over Networks
• Energy management for building district cooling: a distributed approach to resource sharing
• Geometrical Convergence Rate for Distributed Optimization with Time-Varying Directed Graphs and Uncoordinated Step-Sizes
• Distributed soft thresholding for sparse signal recovery
• Distributed Computation of Linear Matrix Equations: An Optimization Perspective
• An Overview of Recent Progress in the Study of Distributed Multi-agent Coordination
• The Minimax Complexity of Distributed Optimization
• Distributed Least Squares Solver for Network Linear Equations
• Resource-aware Exact Decentralized Optimization Using Event-triggered Broadcasting
• An Arrow-Hurwicz-Uzawa Type Flow as Least Squares Solver for Network Linear Equations
• Dual decomposition for multi-agent distributed optimization with coupling constraints
• Robust Consensus Analysis and Design under Relative State Constraints or Uncertainties
• Fuzzy Opinion Networks: A Mathematical Framework for the Evolution of Opinions and Their Uncertainties Across Social Networks
• Mass-spring-damper Networks for Distributed Optimization in Non-Euclidean Spaces
• Decentralized Dictionary Learning Over Time-Varying Digraphs
• Distributed Algorithms for Solving a Class of Convex Feasibility Problems
• Robust Distributed Averaging in Networks
• Structural Controllability on Graphs for Drifted Bilinear Systems over Lie Groups
• A Private and Finite-Time Algorithm for Solving a Distributed System of Linear Equations
• Constrained Optimal Consensus in Multi-agent Systems with First and Second Order Dynamics
• Distributed coordination for optimal energy generation and distribution in smart grid networks
• Energy Aware Architecture for Coordinated Mobility: An Approximate Dynamic Programming Approach
• Consensus of Multi-agent System via Constrained Invariant Set of a class of Unstable System
• Convergence Properties of the Distributed Projected Subgradient Algorithm over General Graphs
• A Decentralized Multi-Objective Optimization Algorithm
• Quadratically constrained quadratic programming for classification using particle swarms and applications
• Distributed Stochastic Optimization With Unbounded Subgradients Over Randomly Time-Varying Networks
• Distributed Random-Fixed Projected Algorithm for Constrained Optimization Over Digraphs
• Data Rates for Network Linear Equations
• Optimal Consensus for Uncertain High-order Multi-agent Systems by Output Feedback
• An approximate dual subgradient algorithm for multi-agent non-convex optimization
• RLC Circuits based Distributed Mirror Descent Method
• Distributed Resource Allocation Over Random Networks Based on Stochastic Approximation
• Time-varying constrained proximal type dynamics in multi-agent network games
• Consensus with Preserved Privacy against Neighbor Collusion
• Distributed Algorithms that Solve Boolean Equations with Local and Differential Privacies
• Decentralized Approximate Newton Methods for Convex Optimization on Networked Systems
• Graph Balancing for Distributed Subgradient Methods over Directed Graphs
• Equilibrium Computation of Generalized Nash Games: A New Lagrangian-Based Approach
• Detection of Insider Attacks in Distributed Projected Subgradient Algorithms
• Distributed Sparse Regression via Penalization
• Distributed proximal gradient algorithm for non-smooth non-convex optimization over time-varying networks
• Deterministic and Randomized Diffusion based Iterative Generalized Hard Thresholding (DiFIGHT) for Distributed Sparse Signal Recovery
• Energy Efficient Massive MIMO through Distributed Precoder Design
• ELM-Based Distributed Cooperative Learning Over Networks
• A Distributed Parallel Optimization Algorithm via Alternating Direction Method of Multipliers
• On the convergence of discrete-time linear systems: A linear time-varying Mann iteration converges iff the operator is strictly pseudocontractive
• Distributed Solver for Discrete-Time Lyapunov Equations Over Dynamic Networks with Linear Convergence Rate
• Receding Horizon Consensus of General Linear Multi-agent Systems with Input Constraints: An Inverse Optimality Approach
• A Fully Decentralized Tuning-free Inexact Projection Method for P2P Energy Trading
• Distributed Interval Optimization with Stochastic Zeroth-order Oracle
• Bayesian Nash Equilibrium Seeking for Distributed Incomplete-information Aggregative Games
• Success and Failure of Adaptation-Diffusion Algorithms for Consensus in Multi-Agent Networks
• Feedback Capacity over Networks
• Distributed Optimization on Riemannian Manifolds for multi-agent networks
• Paradigms of Computational Agency
• Distributed, scalable and gossip-free consensus optimization with application to data analysis
• Delay Robustness of Consensus Algorithms: Beyond The Uniform Connectivity (Extended Version)
• RC Circuits based Distributed Conditional Gradient Method
• Constrained H-infinity Consensus with Nonidentical Constraints
• Privacy-Preserving Average Consensus via State Decomposition
• Performance of a Distributed Stochastic Approximation Algorithm
• Reaching an Optimal Consensus: Dynamical Systems that Compute Intersections of Convex Sets
• Towards time-varying proximal dynamics in Multi-Agent Network Games
• A Distributed Methodology for Approximate Uniform Global Minimum Sharing
• Randomized Optimal Consensus of Multi-agent Systems
• A Method for Distributed Transactive Control in Power Systems based on the Projected Consensus Algorithm
• A dual ascent algorithm for asynchronous distributed optimization with unreliable directed communications
• Networked Aggregative Games with Linear Convergence
• Subdifferentiable functions and partial data communication in a distributed deterministic asynchronous Dykstra's algorithm
• Distributed Partitioned Big-Data Optimization via Asynchronous Dual Decomposition
• Distributed Dual Gradient Tracking for Priority-Considered Load Shedding
• Analysis of Newton-Raphson Consensus for multi-agent convex optimization under asynchronous and lossy communications
• Distributed Estimation of Sparse Inverse Covariances
• Differentially Private Linear Regression over Fully Decentralized Datasets
• Distributed Second-order Multi-Agent Optimization over unbalanced network without boundedness of gradients
• Distributed remote estimation over the collision channel with and without local communication
• Distributed Algorithms for Aggregative Games on Graphs
• Potential Games for Distributed Constrained Consensus
• Robust Consensus of Linear Multi-Agent Systems under Input Constraints or Uncertainties
• Distributed Multi-agent Video Fast-forwarding
• Distributed Maximization of Submodular and Approximately Submodular Functions
• Nested Distributed Gradient Methods with Stochastic Computation Errors
• Newton-Raphson Consensus for Distributed Convex Optimization
• Distributed stochastic subgradient-free algorithm for Nash equilibrium seeking in two-network zero-sum games
• Communication-Efficient Network-Distributed Optimization with Differential-Coded Compressors
• Control of Multi-Layer Mobile Autonomous Systems in Adversarial Environments: A Games-in-Games Approach
• On Local Computation for Optimization in Multi-Agent Systems
• Distributed velocity-constrained consensus of discrete-time multi-agent systems with nonconvex constraints, switching topologies, and delays
• On the stability and convergence of a class of consensus systems with a nonlinear input
• Distributed Estimation of Graph Spectrum
• Primal Recovery from Consensus-Based Dual Decomposition for Distributed Convex Optimization
• Network Synchronization with Convexity
• Accelerated Distributed Primal-Dual Dynamics using Adaptive Synchronization
• Continuous-Time Consensus under Non-Instantaneous Reciprocity
• Distributed Integer Balancing under Weight Constraints in the Presence of Transmission Delays and Packet Drops
• Distributed Interior-point Method for Loosely Coupled Problems
• Nash Equilibrium Computation in Subnetwork Zero-Sum Games with Switching Communications
• Distributed Constrained Optimization over Networked Systems via A Singular Perturbation Method
• Exponential Convergence of a Distributed Algorithm for Solving Linear Algebraic Equations
• Distributed Adaptive Gradient Optimization Algorithm
• Non-Asymptotic Connectivity of Random Graphs and Their Unions
• Towards an $O(\frac{1}{t})$ convergence rate for distributed dual averaging
• Collective Learning
• Distributed Stochastic Block Coordinate Descent for Time-Varying Multi-Agent Optimization
• Asymptotic Network Independence and Step-Size for A Distributed Subgradient Method
• Distributed optimization with nonconvex velocity constraints, nonuniform position constraints and nonuniform stepsizes