Distributed Subgradient Random Projection Algorithm Over Switching Topology With Communication Delays

Distributed optimization of the multi-agent system means that in a communication network,multiple agents,which can compute?communicate and perceive,update their states according to a distributed algorithm to minimize the global objective function.A central agent that is responsible for overall scheduling is not required in multi-agent system,and the algorithm for system is mainly designed as distributed algorithm.Studying the distributed optimization of multi-agent systems has great help for us to solve some large-scale and uncertain distributed complex system problems,such as smart grid,wireless sensor networks,logistics deployment,etc.The gradient-based distributed algorithm is one of the key directions of early research in distributed optimization of multi-agent system.With further research,the objective functions in many practical problems are not differentiable,so the subgradient-based distributed algorithm that does not rely on gradient gets lots of attention by scholars,and now it has been widely discussed in the study of multi-agent systems.In recent research,more and more practical factors are taken into account,such as,each agent has a large number of sub-constraint sets? the communication network switches over time,there exists communication delay and communication noise between agents,etc.Therefore,it is of great theoretical and practical significance to study the improvement strategy of the convergence speed of the distributed subgradient algorithm for multi-agent systems under switching networks with actual cases mentioned above as communication delay,random noise and large number of local constraint sets.The research of this paper is divided into three parts:1)Based on the multi-agent system model over switching network with fixed delay,a distributed batch random projection subgradient algorithm is proposed and the convergence analysis is conducted.Batch random projection means that each agent chooses some sub-constraint sets randomly for batch projection during the agent's state is updating.The more sub-constraint set selected,the faster the algorithm converges.For the communication delay in the network,a method for network expansion is proposed,which can replace the delay item in algorithm and simplify the convergence analysis.Finally,a numerical example is given to verify the effectiveness of the algorithm,and the result demonstrates that the convergence of algorithm can be speed up by increasing the number of random projection sets.2)Based on a multi-agent system model over switching network with random delay,a multi-step subgradient batch random projection algorithm is proposed,the convergence analysis and convergence rate of the algorithm are also conducted.The multi-step subgradient of agent is a combination of the subgradient at the current time and all historical subgradient information of agent from the beginning of the algorithm carried out.Agent's state,which updates along the multi-step subgradient direction,can reach the optimal point faster than the state which updates along a simple subgradient direction.For the random delay in the network,we still utilize a method of network expansion to replace the random delay item and simplify the convergence analysis.The numerical simulation result shows that the multi-step subgradient batch random projection algorithm has a faster convergence speed than the batch random projection subgradient algorithm and a traditional subgradient algorithm.3)Based on a multi-agent system model over switching network with random delay and random communication noise,a multi-step approximate subgradient random projection algorithm is proposed,and the convergence analysis of algorithm is conducted.The approximate subgradient of agent is a weighted combination of the subgradient of agent's neighbors and the subgradient of the agent.The algorithm integrates the two algorithm framework about approximate subgradient and multi-step subgradient,which further improves the convergence speed of distributed subgradient algorithm.Numerical simulation shows that even if there exists random noise,the algorithm which combines multi-step approximate subgradient and batch random projection can still further improve the convergence speed of the algorithm.