Graph Labels-aided Decentralized Optimization

With the advent of the big data era,how to deal with the massive amount of data has become the top priority of information science research.Traditional signal processing and optimization methods are usually deployed in a centralized manner,whcih means that a single device undertakes all the computing tasks,so these centralized methods can not overcome the challenge brought by the rapid increase of data volume.Thanks to the rapid development of distributed system and optimization theory,the distributed optimization theory has attracted more and more research attention.In recent years,distributed optimization has been widely used in wireless sensor networks,large-scale machine learning,UAV networks,power grid systems,social systems,Internet of things,urban transportation systems and wireless spectrum sensing.Distributed optimization has some unique characteristics that are different from traditional optimization theory.These characteristics bring difficulties and challenges to the development of distributed optimization algorithms.Among the vast number of challenges faced by distributed optimization,how to make the local variables to satisfy the consensus constraint as well as how to enable the algorithm to handle more general problems are two key problems.For the former,existing methods usualy introduce some extra proximal term to decouple the coupling between local variables such that the algorithm can be implemented in a decentralized manner.Unfortunately,the extra proximal term slows down the convergence speed of the algorithm? For the latter,existing methods usually approximates the complex objective function via some simple function.Obviously,the approximation also slows down the convergence speed of the algorithm.In order to solve or alleviate the above two critical problems,research is carried out from the following aspects:(1)how to deal with the objective functions that have a complex structure?(2)How to use the label information of graphs to improve the performance of optimization algorithms?(3)How to improve the performance of the algorithm by using its label information without changing the structure of the graph.To resolve these problems such that distributed optimization can better serve the activity of social production,a series of simple and efficient distributed optimization algorithms are proposed.The contents and contributions of this dissertation are summarized as follows:(1)It is clarified that the core to realize distributed deployment by traditional distributed algorithm is the introduction of extra proximal terms.Then,a proximal alternating direction multiplier method(ADMM)is proposed to solve the distributed optimization problem that has a complex objective function.The idea at the heart of this method is to introduce some auxiliary variables to decouple the complex objective function and disassemble it into simpler objective functions,such that the requirements on the objective functions can be released.The proposed algorithm can be applied to more general optimization problems.Moreover,as opposed to tranditional methods,this method does not need to approximate the objective function,so it can obtain a faster convergence speed.(2)It is essential for tranditional distributed optimization algorithms to introduce extra proximal terms to achieve decentralized implementation.However,the extra proximal term forces the current solution to stay close to the solution obtained in the last iteration,which slows down the convergence speed of the algorithm.To avoid the introduction of the extra proximal term,a simplest bipartite graph-based decentralized ADMM algorithm is proposed.The proposed algorithm first transforms the original graph into a simplest bipartite graph.Then,by utilizing the label information provided by the simplest bipartite graph,a graph simplification-aided decentralized ADMM algorithm is constructed.The proposed algorithm can achieve decentralized implementation without introducing extra proximal terms,thus this algorithm has a fast convergence speed.(3)Despite that the graph simplification-aided decentralized ADMM algorithm has a fast convergence speed,this algorithm is required to run on a simplest bipartite graph which is fragile and can not adapt to complex external environments.Following the idea of improving the algorithm performance by combining graph label information,two graph labeling-aided decentralized ADMM algorithm are proposed.The proposed two algorithms utilize the labeling information provided by the graph cut and thus can obtain a fast convergence speed without changing the original graph.In particular,the first proposed algorithm utilizes the labeling information to reduce extra proximal terms,while the second algorithm combines the labeling information and a new operator splitting method in a way such that the extra proximal term is completely eliminated.Both of these two algorithms run on the original graph,which means that they strike a good balance between algorithm speed and system robustness.