Graph-Theoretic Convergence Guarantees for Decentralized Particle Swarm Optimization on Directed Time-Varying Topologies

Abstract

Particle swarm optimization is a population based stochastic search method in which a set of agents, called particles, move through a search space under the influence of inertial, cognitive, and social terms. Many engineered systems motivate implementations where particles can only exchange information with neighboring agents over a communication network, rather than access a globally shared best solution. In such decentralized settings the communication pattern is often naturally modeled as a directed graph, because information flow can be asymmetric due to sensing constraints, bandwidth limits, or protocol design. Moreover, the graph structure can vary over time as agents move, links fail, or scheduling policies change. These factors raise questions about the convergence and stability of decentralized particle swarm optimization when interactions are described by directed, time varying topologies. This work develops a graph theoretic framework for analyzing the mean dynamics of decentralized particle swarms under such conditions. The approach models information exchange through products of row stochastic matrices associated with the directed communication graphs and decomposes the swarm state into components aligned with consensus and disagreement modes. By linearizing around candidate equilibrium points and separating the contribution of local particle dynamics from the influence of the evolving topology, the analysis identifies structural conditions on the sequence of graphs and parameter conditions on the algorithm that together ensure bounded trajectories, asymptotic agreement of local best estimates, and convergence of particle positions toward a common limit. The discussion also addresses robustness to asynchronous updates and imperfect communication, and it provides qualitative design implications for choosing network structures and parameters in decentralized swarm implementations.