Analysis And Design Of Distributed Algorithms And Their Applications

Recently,there are new challenges for the design based on computation,communication,and control due to the increasing scale of practical problems.Centralized algorithms may lose effectiveness for large-scale problems which can be dealt by distributed methods.Furthermore,the distributed algorithms have been applied to various fields including automatic control,signal processing and machine learning.Compared to parallel algorithms,distributed methods are with better scalability because a computation center is not required.Distributed optimization and computation have received intensive research attention,motivated by its broad applications in various areas including natural science,engineering technology and social science.This thesis is devoted to the analysis and design of distributed algorithms and their applications.Main contributions are summarized as follows.1.This thesis revisits a well-known distributed projected subgradient algorithm which aims to minimize a sum of cost functions with a common set constraint.In contrast to most of existing results,weight matrices of the time-varying multiagent network are assumed to be more general,i.e.,they are only required to be row stochastic instead of doubly stochastic.We focus on analyzing convergence properties of this algorithm under general graphs.We first show that there generally exists a graph sequence such that the algorithm is not convergent when the network switches freely within finitely many general graphs.Then to guarantee the convergence of this algorithm under any uniformly jointly strongly connected general graph sequence,we provide a necessary and sufficient condition,i.e.,the intersection of optimal solution sets to all local optimization problems is not empty.Furthermore,we surprisingly find that the algorithm is convergent for any periodically switching general graph sequence,and the converged solution minimizes a weighted sum of local cost functions.Finally,we consider a slightly broader class of quasi-periodically switching graph sequences,and show that the algorithm is convergent for any quasi-periodic graph sequence if and only if the network switches between only two graphs.2.This thesis develops an exponentially convergent distributed algorithm to minimize a sum of nonsmooth cost functions with a set constraint.Compared with existing results,the algorithm achieves an exponential rate for the first time.We remove the consensus constraints by an exact penalty method,and then propose a distributed projected subgradient algorithm by virtue of a differential inclusion and a differentiated projection operator.Resorting to nonsmooth approaches,we prove the convergence for this algorithm,and moreover,provide both the sublinear and exponential rates under some mild assumptions.3.This thesis investigates the distributed design to minimize the nuclear norm(the sum of all singular values)under linear equality constraints over a multiagent network.The problem is reformulated as a distributed trace norm minimization one by introducing auxiliary variables.With the help of projection operators and derivative feedbacks,a distributed primal-dual algorithm is proposed.It is shown that the algorithm converges to an optimal solution with a sublinear rate.Numerical simulations on three classical problems,including linear matrix equality constraints,cardinality minimization,and low-rank matrix completion,are carried out for illustration.4.This thesis considers the distributed computation for semi-definite programming(SDP)problems over multi-agent networks.Two SDP problems,including a nonsparse case and a sparse case,are transformed into distributed optimization problems,respectively,by fully exploiting their structures and introducing consensus constraints.Inspired by primal-dual and consensus methods,we propose two distributed algorithms for the two cases with the help of projection and derivative feedback techniques.Furthermore,we prove that the algorithms converge to their optimal solutions,and moreover,their sublinear rates are evaluated.