Distributed Push-sum Gradient-free Algorithms For Switched Networks

In recent years,with the rapid development of network,communication and computer technologies,the research subject of distributed optimization has drawn much attention by scholars,especially the advent of big data era has brought a new research topic for distributed optimization algorithms.The multi-agent network is a networked system which is composed of multi-agents through local information interaction,in which each agent has the capabilities to perceive,process and communicate.The purpose of distributed optimization is to solve the minimum problem about the sum of individual objective functions through team to work between individuals,the advantages of which not only can effectively save the capital problem in enterprises or companies,but also its robustness is strong.In reality,the communication between individuals will be affected by many communication conditions,such as the network is switching unbalanced,the subgradient of each agent's local objective function is computationally infeasible,communication channel is not reliable and other constraints,so it is of great significance to study the distributed optimization algorithm under the switching network.This paper studies the problem of the agents of a multi-agent network how to collaboratively minimize value of the sum of individual objective functions and each agent just knows its own objective function and can only interact with its neighboring agents.The computationally infeasible or not exist situation of each agent's local objective function subgradients and other complex issues of agents communicate are deeply studied.The main content of this paper is divided into two parts:Firstly,due to the fact that data packet-dropping may happen when agents communication with each other in the multi-agent network,each agent's local objective function usually being non-smooth and the single variable information communication between individuals has some limitations,this paper proposes a distributed Push-sum gradient-free optimization algorithm under data packet-dropping.Then based on state augmentation by adding virtual nodes,a finite inhomogenous Markov chain is obtained,which implies that the weight matrix associated with the multi-agent network is column stochastic and not necessary doubly stochastic,and thus the corresponding network is switched and unbalanced.Furthermore,by combining results of ergodic coefficients,the convergence of the proposed method to an approximate solution is established and the error level of which is characterized by the smoothing parameters of Gaussian approximation function and the Lipschitz constant of the objective function.so it can effectively solve the distributed optimization problem of data packet-dropping and the subgradient of each agent's local objective function is computationally infeasible or not exist.Secondly,This paper studies the problem that the frequent occurrence of information congestion or system collapse caused by each agent in the network interacts information at the same time,so a distributed gossip-based push-sum gradient-free algorithm is proposed to solve the above optimization problem.The process of individuals selecting neighbors obeys the rotation regularity of a Poisson distributed clock,and at each tick of its clock rotation,each time the clock rotates represents with the selected neighbor information to communicate once.Furthermore,the convergence of the proposed algorithm is proved based on the network connectivity and iterative step size reduction.Finally,the chart obtained by MATLAB software analysis verifies the effectiveness of the proposed optimization algorithm.In summary,the convergence of the distributed Push-sum gradient-free optimization algorithm under data packet-dropping and the distributed gossip-based push-sum gradient-free algorithm are proved theoretically in the case of network connectivity and the weight matrix associated with the multi-agent networks is column stochastic,Thus effectively solve the complex problem of data packet-dropping,non-smooth objective function,single variable communication and synchronous information communication.Finally,the results obtained by MATLAB software show that the communication of single(double)variable communication in multi-agent networks does not affect the convergence of the algorithm,but only the convergence rate of double variable information is faster than single variable communication.