Distributed multi-agent optimization with state-dependent communication
From MaRDI portal
Publication:644903
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.
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
Cites work
- scientific article; zbMATH DE number 51132 (Why is no real title available?)
- scientific article; zbMATH DE number 2121575 (Why is no real title available?)
- A Necessary and Sufficient Condition for Consensus Over Random Networks
- Agreement over random networks
- Characterizations of linear suboptimality for mathematical programs with equilibrium constraints
- Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
- Constrained Consensus and Optimization in Multi-Agent Networks
- Continuous-time average-preserving opinion dynamics with opinion-dependent communications
- Convergence speed in distributed consensus and averaging
- Coordination of groups of mobile autonomous agents using nearest neighbor rules
- Distributed asynchronous deterministic and stochastic gradient optimization algorithms
- Distributed multi-agent optimization with state-dependent communication
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- Incremental stochastic subgradient algorithms for convex optimization
- On Distributed Averaging Algorithms and Quantization Effects
- On Krause's Multi-Agent Consensus Model With State-Dependent Connectivity
- Spread of (mis)information in social networks
- Subgradient methods for saddle-point problems
- Synchronization and Convergence of Linear Dynamics in Random Directed Networks
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
- Selective bi-coordinate variations for resource allocation type problems
- Sequential threshold control in descent splitting methods for decomposable optimization 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 multi-agent optimization with state-dependent communication
- Distributed stochastic gradient tracking methods
- 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
- Distributed optimization in multi-agent networks using one-bit of relative state information
- Variable metric primal-dual method for convex optimization problems with changing constraints
- 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)
