Long-time Stability and Convergence of Particle Swarm Optimization
TL;DR
This paper studies a regularized PSO model without memory, with non-degenerate noise by adding a noise floor to the original model, providing new quantitative estimates for the time-discrete algorithm.
Abstract
Particle Swarm Optimization (PSO) is a global optimization algorithm defined by an interacting set of particles evolving over the search space. Heuristically motivated, its theoretical analysis remains limited due to the second-order, stochastic, and highly nonlinear nature of the dynamics. In this paper, we connect classical PSO stability analysis under the stagnation assumption with more recent mean-field methods, providing new quantitative estimates for the time-discrete algorithm. We study in particular a regularized PSO model without memory, with non-degenerate noise by adding a noise floor to the original model. Studying such a surrogate model allows us to identify quantitative conditions under which the dynamics is stable and converges toward a small neighborhood of a global minimizer. We do so by first studying the Schur stability of the linearized dynamics, then analyzing the convergence properties of a nonlinear mean-field system via a Laplace principle, and finally establishing a quantitative error bound for the mean-field approximation of order $N^{-1/2}$.