Distributed multi-agent optimization with state-dependent communication
From MaRDI portal
Publication:644903
DOI10.1007/S10107-011-0467-XzbMATH Open1229.90201arXiv1004.0969OpenAlexW2136517470MaRDI QIDQ644903FDOQ644903
Authors: Ilan Lobel, Asuman Ozdaglar, Diego Feijer 
Publication date: 7 November 2011
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: We study distributed algorithms for solving global optimization problems in which the objective function is the sum of local objective functions of agents and the constraint set is given by the intersection of local constraint sets of agents. We assume that each agent knows only his own local objective function and constraint set, and exchanges information with the other agents over a randomly varying network topology to update his information state. We assume a state-dependent communication model over this topology: communication is Markovian with respect to the states of the agents and the probability with which the links are available depends on the states of the agents. In this paper, we study a projected multi-agent subgradient algorithm under state-dependent communication. The algorithm involves each agent performing a local averaging to combine his estimate with the other agents' estimates, taking a subgradient step along his local objective function, and projecting the estimates on his local constraint set. The state-dependence of the communication introduces significant challenges and couples the study of information exchange with the analysis of subgradient steps and projection errors. We first show that the multi-agent subgradient algorithm when used with a constant stepsize may result in the agent estimates to diverge with probability one. Under some assumptions on the stepsize sequence, we provide convergence rate bounds on a "disagreement metric" between the agent estimates. Our bounds are time-nonhomogeneous in the sense that they depend on the initial starting time. Despite this, we show that agent estimates reach an almost sure consensus and converge to the same optimal solution of the global optimization problem with probability one under different assumptions on the local constraint sets and the stepsize sequence.
Full work available at URL: https://arxiv.org/abs/1004.0969
Recommendations
- Distributed stochastic subgradient projection algorithms for convex optimization
- Distributed multi-agent optimization subject to nonidentical constraints and communication delays
- Distributed constrained stochastic optimal consensus
- Stochastic sub-gradient algorithm for distributed optimization with random sleep scheme
- Strong consistency of random gradient-free algorithms for distributed optimization
nonlinear programmingdistributed multi-agent optimizationprojected multi-agent subgradient algorithmstate-dependent communicationstochastic network models
Cites Work
- Subgradient methods for saddle-point problems
- Continuous-time average-preserving opinion dynamics with opinion-dependent communications
- Title not available (Why is that?)
- A Necessary and Sufficient Condition for Consensus Over Random Networks
- Constrained Consensus and Optimization in Multi-Agent Networks
- Coordination of groups of mobile autonomous agents using nearest neighbor rules
- Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
- Agreement over random networks
- Synchronization and Convergence of Linear Dynamics in Random Directed Networks
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Title not available (Why is that?)
- Spread of (mis)information in social networks
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- On Distributed Averaging Algorithms and Quantization Effects
- Distributed multi-agent optimization with state-dependent communication
- Convergence speed in distributed consensus and averaging
- Characterizations of linear suboptimality for mathematical programs with equilibrium constraints
- On Krause's Multi-Agent Consensus Model With State-Dependent Connectivity
- Incremental stochastic subgradient algorithms for convex optimization
Cited In (33)
- Decentralized algorithms for distributed integer programming problems with a coupling cardinality constraint
- Distributed constrained stochastic subgradient algorithms based on random projection and asynchronous broadcast over networks
- Distributed constraint optimization on networked multi-agent systems
- Opinion dynamics and learning in social networks
- Sequential threshold control in descent splitting methods for decomposable optimization problems
- Selective bi-coordinate variations for resource allocation type problems
- Distributed optimization over directed graphs with row stochasticity and constraint regularity
- Newton-like method with diagonal correction for distributed optimization
- Decentralized multi-agent optimization based on a penalty method
- Primal-dual method for optimization problems with changing constraints
- Parallel computing subgradient method for nonsmooth convex optimization over the intersection of fixed point sets of nonexpansive mappings
- A distributed accelerated optimization algorithm over time‐varying directed graphs with uncoordinated step‐sizes
- Splitting proximal with penalization schemes for additive convex hierarchical minimization problems
- Distributed stochastic gradient tracking methods
- Distributed multi-agent optimization with state-dependent communication
- A decentralized multi-objective optimization algorithm
- Partition-based multi-agent optimization in the presence of lossy and asynchronous communication
- Convergence analysis of iterative methods for nonsmooth convex optimization over fixed point sets of quasi-nonexpansive mappings
- On the gradient method for solving multi-agent systems
- Distributed optimisation for resource allocation with event-triggered communication over general directed topology
- A generalized alternating direction implicit method for consensus optimization: application to distributed sparse logistic regression
- Distributed optimization for discrete time-varying linear multi-agent systems with event-triggered communication
- Geometrical convergence rate for distributed optimization with time-varying directed graphs and uncoordinated step-sizes
- Distributed stochastic subgradient projection algorithms based on weight-balancing over time-varying directed graphs
- Distributed nonsmooth convex optimization over Markovian switching random networks with two step-sizes
- Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays
- Distributed algorithms with finite data rates that solve linear equations
- Variable metric primal-dual method for convex optimization problems with changing constraints
- Distributed optimization in multi-agent networks using one-bit of relative state information
- Distributed consensus-based multi-agent convex optimization via gradient tracking technique
- On the steady state of continuous-time stochastic opinion dynamics with power-law confidence
- Computing over unreliable communication networks
- Distributed multi-agent optimization subject to nonidentical constraints and communication delays
This page was built for publication: Distributed multi-agent optimization with state-dependent communication
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q644903)
