A Study Of Fast Algorithms For Decentralized Consensus Optimization Over Directed Graphs

With the rapid development of information technology(IT),the demands for IT in communications,control,Internet and Internet of Things and other fields are characterized with real time,high concurrency and large-data distributed storage.In such an era,studies on decentralized consensus optimization algorithm have attracted extensive attention.The basic thought of decentralized optimization is the realization of the optimality and consistency of the whole network without the support of network center nodes and through the autonomous optimization of network center nodes and the intercommunication among network center nodes.Decentralized optimization usually has better network robustness and extendibility,communication and computing load balancing,no multi-hop communication and privacy protection and other advantages.Based on this,decentralized consensus optimization has been widely applied to blockchain,Internet of Vehicles,UAV coordination control,resource scheduling for smart power grid,machine learning and other fields.At present,most studies on decentralized consensus optimization concentrate on undirected graphs,i.e.two-way communication network.However,since there usually are security hierarchy or a trust mechanism and other problems in practical applications(for example,social network),the actual networks usually are directed graphs.Therefore,the studies on the decentralized consensus optimization algorithm in directed graphs are not only of significant scientific value,but also of important practical significance for the network application against the current background of big data.This paper concentrates on the fast decentralized consensus optimization algorithm in directed graphs,specifically as follows:1.A fast and efficient algorithm called ExtraPush was proposed on the basis of the decentralized smooth optimization model in directed graphs,i.e.the continuous differentiability of the objective function,and in combination with two existing algorithms: EXTRA and Subgradient-push algorithms.We found,from the perspective of numerical value,that the new algorithm can maintain the linear convergence of the EXTRA algorithm well and is much faster than the existing Subgradient-push algorithm,which has been proved to have sublinear convergence rate only.Theoretically,we gave the convergence of ExtraPush under a bounded sequence assumption.2.This paper further considered the decentralized composite optimization model in directed graphs,i.e.the “smooth + non-smooth” structure of the objective function,generalized ExtraPush algorithm to composite optimization model by introducing proximity operator to solve the equation,and proposed PG-ExtraPush algorithm.In the case of strong convex,this paper established the linear convergence of PG-ExtraPush algorithm.A series of numerical experiments confirmed the effectiveness of the algorithm.Surprisingly,we also found that PG-ExtraPush algorithm has linear convergence rate in some non-convex experimental examples.We will further study on this in the future.Since the algorithms mentioned in this paper require synchronization,a huge waste of computing resources is caused.Therefore,the asynchronous version of algorithm will be an important aspect of our future studies.