Distributed Convex Optimization with State-Dependent (Social) Interactions over Random Networks
Preprint
Abstract
This paper aims at distributed multi-agent convex optimization where the communications network among the agents are presented by a random sequence of possibly state-dependent weighted graphs. This is the first work to consider both random arbitrary communication networks and state-dependent interactions among agents. The state-dependent weighted random operator of the graph is shown to be quasi-nonexpansive; this property neglects a priori distribution assumption of random communication topologies to be imposed on the operator. Therefore, it contains more general class of random networks with or without asynchronous protocols. A more general mathematical optimization problem than that addressed in the literature is presented, namely minimization of a convex function over the fixed-value point set of a quasi-nonexpansive random operator. A discrete-time algorithm is provided that is able to converge both almost surely and in mean square to the global solution of the optimization problem. Hence, as a special case, it reduces to a totally asynchronous algorithm for the distributed optimization problem. The algorithm is able to converge even if the weighted matrix of the graph is periodic and irreducible under synchronous protocol. Finally, a case study on a network of robots in an automated warehouse is given where there is distribution dependency among random communication graphs.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Distributed Multiagent Convex Optimization Over Random DigraphsIEEE Transactions on Automatic Control, 2019
- Emergence of Consensus in a Multi-Robot Network: From Abstract Models to Empirical ValidationIEEE Robotics and Automation Letters, 2016
- Constrained distributed algebraic connectivity maximization in robotic networksAutomatica, 2013
- Reaching an Optimal Consensus: Dynamical Systems That Compute Intersections of Convex SetsIEEE Transactions on Automatic Control, 2012
- Distributed multi-agent optimization with state-dependent communicationMathematical Programming, 2011
- Spread of (mis)information in social networksGames and Economic Behavior, 2010
- Opinion Dynamics and Learning in Social NetworksDynamic Games and Applications, 2010
- On Krause's Multi-Agent Consensus Model With State-Dependent ConnectivityIEEE Transactions on Automatic Control, 2009
- Emergent Behavior in FlocksIEEE Transactions on Automatic Control, 2007
- On Maximizing the Second Smallest Eigenvalue of a State-Dependent Graph LaplacianIEEE Transactions on Automatic Control, 2006