Dynamic Average Consensus Algorithms In Multi-Agent Networks And Their Applications

In this thesis, we study an important dynamic average consensus problem in multi-agent networks. To be specific, the problem can be described as, all the agents in the network need to track the average of a set of time-varying reference inputs. Our re-search focus on solving this problem in a distributed manner. However, distributed computing can be grouped into two classes. One is computing with a fusion center in the network(distributed manner); the other is to compute without a fusion center in the network(decentralized manner). Compared with the former, the latter has advan-tages over communication load, robustness, privacy-preserving properties, e.t.c. As a result, decentralized computing has a wider application prospect. This thesis first in-troduces several decentralized dynamic average consensus algorithms, then develops a new decentralized dynamic average consensus algorithm, named DDAC, based on the previous research of others. Compared with some other algorithms, DDAC has a stepsize-like parameter for tuning and a better convergent accuracy in numerical ex-periments. Dynamic average consensus algorithms have a wide range of applications. Apart from being directly applied into some real problems that need to dynamically track time-varying signals, such as location tracking and formation control, dynamic average consensus algorithms are originally proposed to deal with some subproblems of optimization problems in this thesis. Taking low-rank matrix completion problem as a focused example, this thesis explains and shows how and how well this original idea works.The thesis also research the low-rank matrix completion problem. Base on a cen-tralized algorithm solving this problem, we develop two new decentralized low-rank matrix completion algorithms, named D-LMaFit and DDAC-LMaFit. In this process, we point out that the challenge and difficulty of designing a decentralized algorithm from a centralized algorithm which can be carried out in a distributed way is how to replace the fusion center’s role in the network with a certain decentralized algorithm. Our answer to this challenge is to utilize dynamic average consensus algorithms to do the averaging step in a decentralized manner. We solves this challenge in two different ways and accordingly develop two new algorithms mentioned above. Furthermore, take into account the need of privacy-preserving property in the real world, taking D-LMaFit as example, we prove that for a series of algorithms which can be rewritten into linear time-invariant systems, if the topology the the network satisfy certain conditions, then these algorithms have the privacy-preserving property.As extension, since we propose that dynamic average consensus algorithms can replace the fusion center and do the average step in a decentralized manner, apply-ing this proposal into gradient descent method and proximal gradient method we get three new decentralized gradient descent algorithms and three new decentralized proxi-mal gradient algorithms called DDAC-GD, FODAC-GD, EXTRA-GD and DDAC-PG, FODAC-PG, EXTRA-PG respectively.This thesis focuses on the decentralized dynamic average consensus algorithms and develop a state-of-art and efficient dynamic average consensus algorithm; and discuss-es how to use the dynamic average consensus algorithms to decentralize the distributed algorithms which need a fusion center and accordingly develops six state-of-art decen-tralized algorithms. Plenty of numerical experiments show that all the algorithms are efficient. This thesis provides new thoughts and guidance of designing decentralized algorithms.