Distributed Optimization Algorithms For Multi-Agent Systems With Communication Delays

Multi-agent systems have broad applications on. creature, artificial intelligence and coordination control. The aim of a multi-agent distributed optimization algorithm is to solve a global optimization problem through the cooperation of agents. However, in practice, the influence of communication delays on multi-agent systems cannot be ignored due to delays can slow down the speed of convergence and deteriorate the performance of systems. Therefore, the research for multi-agent systems with communication delays is a topic of significance. Distributed subgradient algorithm with fixed delay is studied in this paper and the effect of fixed delays on algorithm performance is analyzed. The main contents include the following two aspects:1. The distributed subgradient algorithm with communication delays and fixed topology. There are many excellent works about distributed subgradient optimization algorithms for multi-agent systems in literature. The time delay, which is an important factor, is concerned in this paper based on the existed algorithms. Based on the assumption that the communication delays among agents are fixed, the optimization problem with time delay is converted to the optimization problem without delays by virtue of state augmentation technique, then the weight adjacency matrix describing topology of the network is transformed into a time-delay weight adjacency matrix. However, the time-delay weight adjacency matrix is no longer doubly stochastic but only stochastic even the weight adjacency matrix is double stochastic. This difference brings about some difficulties when establishing the convergence result for the algorithm. The double stochastic matrix has excellent convergence properties and each element of it will converge to the mean value of the elements of each row. Because the newly introduced agents after state augmentation only transmit information, then the importance of the agents in the system is no longer same and thus the time-delay weight adjacency matrix is stochastic. The relationship between a stochastic matrix and its stationary distribute is used to carry out the convergence analysis for the distributed subgradient algorithm with communication delays in this paper. Finally, the effectiveness of the algorithm is further verified by a simulation example.2. The distributed subgradient projection algorithm with communication delays and switching topologies. The optimization problem in which each agent’s state subjected to a convex constraint set is considered, and in this case the network topology is not fixed or unchanged but dynamically switching. For the communication delays, the state augmentation technique is still adopted, and the projection operation is adopted to deal with the convex state constraints of agents. Due to the dynamically switching topologies, the time-delay weight adjacency matrix is not only stochastic but also time-varying. Therefore, the convergence properties for the case of fixed topologies can no longer be valid here. Then by using the property that each row of a stochastic transition matrix geometrically converges to a stochastic vector, the convergence result for the proposed distributed subgradient projection algorithm is established.In brief, it is shown that, provided that the corresponding directed network with fixed topology is strongly connected, or the corresponding directed network with switching topology is periodically strongly connected, and the communication delays are bounded, the proposed distributed optimization algorithms always converge, which means that bounded communication delays cannot change the convergence of the algorithms but only influence the convergence performance of the algorithm. According to the theoretic and numerical simulation results, the communication delays can only slow down the convergence speeds of the algorithms and incur larger convergence errors.