Distributed Optimization Algorithms Based On Network Topology Design

This paper studies how to improve the convergence speed of distributed online algorithms and solve the problem of communication delay in unbalanced directed switching networks.For the former,it is mainly based on the edge-adding strategy for Laplace matrix,and optimizes the network topology to increase its algebraic connectivity,thus the two classic optimization algorithms,distributed online dual averaging(ODDA)algorithm and distributed online free-projection(DOCG)algorithms,have faster convergence speeds.For the latter,the unconstrained convex optimization problem with communication delay is changed into an unconstrained convex optimization problem without delay by mainly expanding the communication network topology,so that the problem of communication delay can be solved efficiently.The main contributions in the dissertation are divided into three parts:In the first part,the algorithm has a faster convergence speed by improving the distributed dual average algorithm.Firstly,the algorithm is extended to the online setting.Then,the most optimal edge is selected by edge selection method,and mixes with the network topology to establish a mathematical model.Meantime,a fast distributed online dual average algorithm(F-ODDA)is proposed.The convergence of F-ODDA is proved and the convergence speed is given.Finally,theories and numerical experiments show that F-ODDA has a faster convergence rate than the existing online distributed dual average algorithm(ODDA).In the second part,the distributed online free-projection algorithm has better performance by improving the algorithm's strategy.Firstly,the Erdos-Renyi stochastic model is established and the adding edge algorithm(AE)is proposed.Secondly,by combining the edge expansion algorithm with free-projection distributed online algorithm,a fast free-projection distributed online algorithm(F-DOCG)is proposed.Under the guarantee of sufficient accuracy,the F-DOCG algorithm not only avoids the high projection calculation problem by linear approximation,but also it reveals the relationship between the underlying topology and algebraic connectivity.At the same time,it improves the Regret bound,and proves this algorithm with faster convergence speed.Finally,theories and numerical experiments show that F-DOCG has better performance than the existing free-projection distributed online algorithm(DOCG).In the third part,it mainly solves the problem of communication delay between individuals in a general unbalanced directed switching network.By expanding the communication network topology,the unconstrained convex optimization problem with communication delay is converted into the unconstrained convex optimization problem without communication delays,and a distributed subgradient optimization algorithm with delay communication in switched network is proposed to solve this problem.The non-quadratic Lyapunov function method is used to prove the convergence of the distributed subgradient algorithm based on time delay communication when the unbalanced directed switching network has periodical strong connectivity and the communication delay has upper bound.Finally,theories and numerical experiments were given to demonstrate the convergence and effectiveness of the raised algorithm.Figure[28]Table[1]Reference[69]...