Push-Sum Distributed Dual Averaging Optimization Algorithm

Multi-agent network is a large-scale network optimization system,which is composed of several agents with autonomous working ability through local information exchange.When any agent in the network has problems,it will not affect the whole network,and it will have the advantage of cost saving,so multi-agent network has a very wide application prospect in the actual situation,such as wireless sensor network,network utility maxi-nization and distributed scheduling response.But there is a lack of centralized access to the exchange of information and changes in time.Therefore,the distributed optimiza-tion method of multi-agent network should be designed on the basis of local information exchange,computation and network topology change.The commonly used method is to solve the problem of this kind of subgradient algorithm,such as:the primal distribution algorithm,dual distribution algorithm,the primal-dual distribution algorithm,etc.And in this paper,we mainly studied the distributed push-sum dual averaging optimization algorithm,the main work is as follows:Firstly,we introduces the present status of distributed optimization problem both at home and abroad and the motivation of this article.Secondly,we investigates a distributed convex optimization problem with simple constraints over time-varying directed graphs.By combining the push-sum scheme and distributed dual averaging method,a distributed push-sum dual averaging algorithm is proposed,and the convergence of the proposed method is established,and the explicit convergence rate with order of O((?))is obtained.Meanwhile,a numerical example on linear regression problem is used to demonstrate the effectiveness of the proposed algorithm.Compared with existing works,our algorithm is not required the double stochasticity of the communication weight matrices.Thirdly,since each local function according to the order of network become an agent and with available time,the agent must communicate with each other between an online global function,by constantly to solve the subproblems to gradually solve the global solution.Therefore,we presented a online distributed push-sum dual average optimization algorithm.At the same time,because the subgradient accepted by the agent may not be accurate,a stochastic online distributed push-sum dual average optimization algorithm is proposed.Our results show that the regret analysis of the algorithm is bounded and O((?)),with a sublinear growth.Fourth,because the receive subgradient information may not be the current subgradient information,the distributed push-sum dual average algorithm with delays is proposed,the convergence of the proposed method is established and an explicit convergence rate with order of O((?))is given.Fifth,the research content and the prospect of the research work are summarized.In a word,in the time-varying directed graph or imbalance to the network,as well as the conditions of multi-agent network with delays,the proposed algorithm is convergent.From the theoretical analysis and numerical experiments of the algorithm,it can be seen that the existence of time-varying directed graph makes the convergence speed of the algorithm faster and the convergence error smaller.