On the global convergence of particle swarm optimization methods

DOI10.1007/S00245-023-09983-3zbMATH Open1515.65037arXiv2201.12460OpenAlexW4378878907MaRDI QIDQ6166343FDOQ6166343

Authors: Hui Huang, Jinniao Qiu, Konstantin Riedl 

Publication date: 6 July 2023

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

Abstract: In this paper we provide a rigorous convergence analysis for the renowned particle swarm optimization method by using tools from stochastic calculus and the analysis of partial differential equations. Based on a time-continuous formulation of the particle dynamics as a system of stochastic differential equations, we establish convergence to a global minimizer of a possibly nonconvex and nonsmooth objective function in two steps. First, we prove consensus formation of an associated mean-field dynamics by analyzing the time-evolution of the variance of the particle distribution. We then show that this consensus is close to a global minimizer by employing the asymptotic Laplace principle and a tractability condition on the energy landscape of the objective function. These results allow for the usage of memory mechanisms, and hold for a rich class of objectives provided certain conditions of well-preparation of the hyperparameters and the initial datum. In a second step, at least for the case without memory effects, we provide a quantitative result about the mean-field approximation of particle swarm optimization, which specifies the convergence of the interacting particle system to the associated mean-field limit. Combining these two results allows for global convergence guarantees of the numerical particle swarm optimization method with provable polynomial complexity. To demonstrate the applicability of the method we propose an efficient and parallelizable implementation, which is tested in particular on a competitive and well-understood high-dimensional benchmark problem in machine learning.

Full work available at URL: https://arxiv.org/abs/2201.12460

Recommendations

• From particle swarm optimization to consensus based optimization: stochastic modeling and mean-field limit
• On convergence analysis of particle swarm optimization algorithm
• Rough Sets and Current Trends in Computing
• Convergence analysis of the particle swarm optimization based on stochastic processes
• Reprint of: On convergence analysis of particle swarm optimization algorithm

zbMATH Keywords

metaheuristicsparticle swarm optimizationmean-field limitVlasov-Fokker-Planck equationsglobal derivative-free optimizationhigh-dimensional nonconvex optimization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Vlasov equations (35Q83) Stochastic particle methods (65C35) Derivative-free methods and methods using generalized derivatives (90C56) PDEs in connection with mathematical programming (35Q90)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A Stochastic Approximation Method
• Stochastic differential equations. An introduction with applications.
• Title not available (Why is that?)
• Stochastic mean-field limit: non-Lipschitz forces and swarming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Applied asymptotic analysis
• An algorithmic introduction to numerical simulation of stochastic differential equations
• A Convergence Proof for the Particle Swarm Optimiser
• Title not available (Why is that?)
• Title not available (Why is that?)
• Metaheuristics for Hard Optimization
• An initiation to logarithmic Sobolev inequalities. Transl. from the French by Donald Babbitt
• More is the same; phase transitions and mean field theories
• Title not available (Why is that?)
• Title not available (Why is that?)
• Particle swarm optimization almost surely finds local optima
• Handbook of swarm intelligence. Concepts, principles and applications
• Analyzing Convergence and Rates of Convergence of Particle Swarm Optimization Algorithms Using Stochastic Approximation Methods
• A consensus-based model for global optimization and its mean-field limit
• Random batch methods (RBM) for interacting particle systems
• An analytical framework for consensus-based global optimization method
• A mean field view of the landscape of two-layer neural networks
• Recuit simulé sur \(\mathbb{R}{}^ n\). Étude de l'évolution de l'énergie libre. (Simulated annealing on \(\mathbb{R}{}^ n\). Study of the evolution of free energy)
• On the mean-field limit for the Vlasov-Poisson-Fokker-Planck system
• A comprehensive survey on particle swarm optimization algorithm and its applications
• Consensus-based optimization on hypersurfaces: Well-posedness and mean-field limit
• Consensus-based global optimization with personal best
• From particle swarm optimization to consensus based optimization: stochastic modeling and mean-field limit
• A consensus-based global optimization method for high dimensional machine learning problems
• Zero-inertia limit: from particle swarm optimization to consensus-based optimization
• Title not available (Why is that?)
• Anisotropic diffusion in consensus-based optimization on the sphere

Cited In (14)

• Zero-inertia limit: from particle swarm optimization to consensus-based optimization
• Convergence analysis of particle swarm optimization in one dimension
• Erratum to ``On convergence of the multi-objective particle swarm optimizers
• A note on the mean-field limit for the particle swarm optimization
• Consensus-based optimization methods converge globally
• Control methods in hyperbolic PDEs. Abstracts from the workshop held November 5--10, 2023
• Binary interaction methods for high dimensional global optimization and machine learning
• Leveraging memory effects and gradient information in consensus-based optimisation: on global convergence in mean-field law
• Swarm-based gradient descent method for non-convex optimization
• Optimization by linear kinetic equations and mean-field Langevin dynamics
• On the convergence of a population-based global optimization algorithm
• A Convergence Proof for the Particle Swarm Optimiser
• Swarm gradient dynamics for global optimization: the mean-field limit case
• An adaptive consensus based method for multi-objective optimization with uniform Pareto front approximation

This page was built for publication: On the global convergence of particle swarm optimization methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6166343)