Study Of Accelerated Distributed Optimization Algorithms Over Directed Graphs

With the rapid development of computer science and communication technology in recent years,large-scale sensor networks and internet-of-things are growing quickly,which generate huge amount of data with spatially distributed storage and then demand more efficient optimization algorithms.As a result,distributed optimization,which relies on information exchanging and is scalable,has been becoming a research hot topic.It is of great importance to develop accelerated mechanism in distributed optimization algorithms to improve the convergence rate.Most existing accelerated distributed optimization algorithms are based on static and undirected communication networks,which requires bidirectional communication in practice and thus might not be suitable for the time-varying communication networks in real environment.In order to overcome the limitation of existing works,this thesis studies distributed optimization algorithms over directed communication networks,and proposes two kinds of algorithms with rigorously theoretical analysis.The details are given below.(1)Accelerated distributed optimization algorithm over static directed networks.A static directed network represents a fixed communication network that does not change over time.This type of network is common and simple,which allows agents in the network to send oneway messages.At the background of static directed communication networks,we propose a new distributed algorithm based on row-stochastic weight matrix,which is called RSM.The algorithm uses the count of messages each node receive from its neighbors in one iteration to construct a row-stochastic weight matrix,that is,the indegree of each node in the directed graph.We creatively use the row-stochastic weight matrix,combined with the Heavy-ball momentum method to accelerate convergence and get a more stable,more reliable and faster distributed optimization algorithm on static directed communication networks.(2)Accelerated distributed optimization algorithm over time-varying networks.A time-varying directed network represents a variable communication network that changes with time.Compared with static directed networks,the algorithm over time-varying directed networks not only includes all the application scenarios of static directed networks,but also suits many other complex and changeable network environments.At the background of time-varying directed communication networks,we propose a new distributed algorithm by combining Heavy-ball momentum and Barzilai-Borwein adaptive stepsizes,which is called HBBB.The algorithm uses the Push-Sum method to solve the consistency deviation caused by the imbalance of time-varying directed networks.At the same time,the stepsizes of each iteration are automatically adjusted to make a faster convergence.In particular,in order to reduce the difficulty of estimating preset parameters,we propose an improved loop distributed optimization algorithm based on HBBB over static directed networks,which is called HBBBL.The algorithm does not perform better than HBBB when optimal parameters,but the difficulty of estimation is significantly reduced.The thesis focuses on the acceleration research of distributed optimization algorithms over static and time-varying directed communication networks.Combined with Heavy-ball momentum and Barzilai-Borwein stepsizes,RSM algorithm and HBBB algorithm are proposed.The research results of this thesis enrich the use scenarios of distributed optimization algorithms,help to improve the convergence rate of distributed optimization algorithms,reduce time consumption and resource waste.It has important theoretical and practical significance.