Decentralized Algorithms For Consensus Problem In Multi-agent Network

The multi-agent network, an important abstract in the objective world, has been widely applied in kinds of fields and disciplines in recent years. The typ-ical models of multi-agent network are biological network (e.g. bird flock and fish school), robotic network, wireless sensor network, vehicle network, comput-er network and even social network. In multi-agent network, each single agent is weak, limited in its ability to sense, compute and communicate, this together with being easily damaged make the single agent unable to undertake complex tasks. However, when agents consist the network, cooperating with each other and sense, compute and communicate in organized order, they can finish difficult assignments.The distributed architecture and system of multi-agent network decides its distributed method to deal with information. Generally, there are two kinds of distributed information processing methods. One is the distributed method with central agent (we call this method distributed method) and the other is that without central agent (we call this decentralized method). Both of these methods have their own pros and cons, and hence they both exist in natural world and complement each other. But the decentralized one, enjoying great features like being more balanced in communication and computation load for each node and link, more robust in algorithm operating, free from tedious routing process and safer in data protection, has attracted tremendous attention and extensive research. Among all the hot topics in decentralized algorithms, the one that how to analyze convergence rate of existing algorithms, and design more new efficient methods with linear convergence (or faster) rate has been the great focus.This paper talks about the decentralized algorithms for consensus problem in multi-agent network. Consensus problem is one kind of basic problems in multi- agent network because lots of actual applications, like average consensus, dis-tributed linear regression, spectrum sensing, etc., can be transformed directly or indirectly to consensus problems. This paper first makes a detail survey over sev-eral important decentralized algorithms, in which we talk about their basic ideas, mathematical iteration equations and up-to-date results. What’s more, this paper also tries hard to establish the relationship between the decentralized algorithms and their correspondent classic centralized methods, which is of great importance to understand the design and convergence property of these algorithms.After the survey, we carefully analyzed over the convergence of distributed ADMM and establish its linear convergence rate for the first time given the lo-cal objective function is strongly convex and its gradient is Lipschitz continuous. Secondly, this paper also discusses about the convergence conditions of distribut-ed gradient descent, proving that the convergence of the algorithm is actually decided by stepsize, which is the easiest condition so far to operate among all revelent articles. In addition, we also establish the nearly linear convergence rate of distributed gradient descent give the same assumptions as distributed ADMM.In the end, this paper takes a consideration for the distributed Basis Pursuit (BP) problem, which belongs to consensus problems with equality constraints. To make the algorithm lightweight in computation costs and fast in convergence, this paper designed a new decentralized linearized Bregman method. We established the nearly linear convergence of this algorithm and the numerical experiments validate its great performance.