Distributed estimation and optimization for networked systems: algorithms and convergence analysis

In this thesis, we propose a number of message-passing algorithms for solving distributed estimation and optimization problems, and study the convergence properties of the proposed algorithms. Specifically, our research problems include distributed algorithms for solving weighted average consensus, weighted least-squares, linear systems and convex optimization problems, which arise due to the expanding usage of networked systems in industrial applications. The use of these algorithms, which can be found in sensor networks, networked linear systems, network-based state estimation, multi-agent systems, and multi-agent optimization, have motivated our studies. In the first part of this thesis, we consider distributed estimation. The objective of distributed estimation is that each node infers certain unknown variables of common interest using its local measurements and information exchanged with its neighboring nodes. With the development of large-scale systems, e.g., power systems, urban transportation systems, wireless networks and automatic vehicle systems, distributed estimation algorithms have become an indispensable tool to monitor system states and maintain system stability. In the second part, we study distributed algorithms for optimization. The objective of distributed optimization is to design algorithms for processors or agents to derive the solution of a common optimization problem by using local information and inter-node communications. Applications of distributed optimization can be found in resource allocation, formation control, machine learning, network flow optimization, smart grids and so on. The main results of this thesis are as follows. Firstly, we propose a distributed algorithm for weighted average consensus and study its convergence performance. The algorithm belongs to the class of message-passing algorithms and is able to converge to the correct weighted average value in a finite number of iterations, when the induced graph of the problem is acyclic. It is worth mentioning that a strict finite-time consensus is very hard to achieve when applying Laplacian-matrix-based algorithms. For loopy graphs, we convert the weighted average consensus problem into an optimization problem which can be solved using a modified algorithm. The algorithm has low complexity in communications, computation and storage. Simulation results verify that the proposed algorithm yields the correct consensus with a faster convergence rate when compared to other Laplacian-based algorithms. Secondly, we study a known distributed algorithm in the literature for weighted least-squares estimation with linear measurement models. We establish the equivalence between the well-known Gaussian belief propagation (BP) algorithm and this distributed algorithm. Based on this relationship, we introduce the notion of block diagonal dominance and adopt the convergence analysis that is generalized from the so-called walk-sum approach. Inspired by the properties of Gaussian BP algorithm, we study the convergence rate of the distributed algorithm and derive a simple bound on the convergence rate which is associated with the spectral radius of an information matrix. Thirdly, we propose a message-passing algorithm for solving sparse linear systems under the assumption of generalized diagonal dominance. For this problem, using Gaussian graphical models is not feasible. The proposed algorithm is generalized from the Gaussian BP algorithm but is suitable for asymmetric systems. Using pure linear algebraic analysis, we reveal that the proposed algorithm enjoys the same convergence properties as the Gaussian BP algorithm does. We also derive several bounds for the proposed algorithm when applied to loopy graphs. These convergence results are also applicable to the Gaussian BP algorithm. Lastly, we study the convergence properties of a message-passing algorithm for convex optimization. The motivation of this problem is that, in the existing literature, the objective function of the optimization program is restricted to be pairwise convex separable, i.e., every pairwise component must be convex, which is a strong assumption. We manage to relax this assumption and provide novel analysis techniques. We show that the message-passing algorithm converges asymptotically under the relaxed assumption of scaled diagonal dominance. Moreover, a tighter and simpler bound for the convergence rate is presented. In particular, by specializing the results to quadratic optimization, a very simple and explicit bound for convergence rate is provided.