Convergence Rate of Distributed Averaging Dynamics and Optimization in Networks
- 11 June 2015
- journal article
- research article
- Published by Emerald Publishing in Foundations and Trends® in Systems and Control
- Vol. 2 (1) , 1-100
Abstract
Recent advances in wired and wireless technology lead to the emergence of large-scale networks such as Internet, wireless mobile ad-hoc networks, swarm robotics, smart-grid, and smart-sensor networks. The advances gave rise to new applications in networks including decentralized resource allocation in multi-agent systems, decentralized control of multi-agent systems, collaborative decision making, decentralized learning and estimation, and decentralized in-network signal processing. The advances also gave birth to new large cyber-physical systems such as sensor and social networks. These network systems are typically spatially distributed over a large area and may consists of hundreds of agents in smart-sensor networks to millions of agents in social networks. As such, they do not possess a central coordinator or a central point for access to the complete system information. This lack of central entity makes the traditional (centralized) optimization and control techniques inapplicable, thus necessitating the development of new distributed computational models and algorithms to support efficient operations over such networks. This tutorial provides an overview of the convergence rate of distributed algorithms for coordination and its relevance to optimization in a system of autonomous agents embedded in a communication network, where each agent is aware of (and can communicate with) its local neighbors only. The focus is on distributed averaging dynamics for consensus problems and its role in consensusbased gradient methods for convex optimization problems, where the network objective function is separable across the constituent agents.Keywords
This publication has 114 references indexed in Scilit:
- Distributed Bregman-Distance Algorithms for Min-Max Optimization2013
- Distributed multi-agent optimization with state-dependent communicationMathematical Programming, 2011
- Random algorithms for convex minimization problemsMathematical Programming, 2011
- Distributed Stochastic Subgradient Projection Algorithms for Convex OptimizationJournal of Optimization Theory and Applications, 2010
- Error Bounds: Necessary and Sufficient ConditionsSet-Valued and Variational Analysis, 2010
- Gossip consensus algorithms via quantized communicationAutomatica, 2010
- Convergence rate for consensus with delaysJournal of Global Optimization, 2008
- Average consensus problems in networks of agents with delayed communicationsAutomatica, 2008
- Quantized consensusAutomatica, 2007
- Optimal Scaling of a Gradient Method for Distributed Resource AllocationJournal of Optimization Theory and Applications, 2006