On Convergence Rate of Weighted-Averaging Dynamics for Consensus Problems
Authors:
Open Access
- 24 May 2016
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Automatic Control
- Vol. 62 (2) , 766-781
Abstract
This paper investigates the weighted-averaging dynamic for unconstrained and constrained consensus problems. Through the use of a suitably defined adjoint dynamic, quadratic Lyapunov comparison functions are constructed to analyze the behavior of weighted-averaging dynamic. As a result, new convergence rate results are obtained that capture the graph structure in a novel way. In particular, the exponential convergence rate is established for unconstrained consensus with the exponent of the order of $1-O(1/(m\log_{2}m))$ for special tree-like regular graphs. Also, the exponential convergence rate is established for constrained consensus over time-varying graphs, which nontrivially extends the existing result limited to the static graph case and the use of uniform weight matrices. Our main results are developed for directed graphs that are weakly connected, and we also provide statements regarding the rates in case of joint connectivity.
Keywords
Funding Information
- National Science Foundation
- Computing and Communication Foundations (11-11342)
- NSF Division Of Mathematical Sciences (1312907)
- Office of Naval Research Basic Research Challenge (N00014-12-1-0998)
This publication has 48 references indexed in Scilit:
- Stabilisation of infinitesimally rigid formations of multi-robot networksInternational Journal of Control, 2009
- Quantized consensusAutomatica, 2007
- Consensus Problems in Networks of Agents With Switching Topology and Time-DelaysIEEE Transactions on Automatic Control, 2004
- Fast linear iterations for distributed averagingSystems & Control Letters, 2004
- Coverage Control for Mobile Sensing NetworksIEEE Transactions on Robotics and Automation, 2004
- Coordination of groups of mobile autonomous agents using nearest neighbor rulesIEEE Transactions on Automatic Control, 2003
- Geometric Bounds for Eigenvalues of Markov ChainsThe Annals of Applied Probability, 1991
- Distributed asynchronous deterministic and stochastic gradient optimization algorithmsIEEE Transactions on Automatic Control, 1986
- Reaching a ConsensusJournal of the American Statistical Association, 1974
- The method of projections for finding the common point of convex setsUSSR Computational Mathematics and Mathematical Physics, 1967