On the global convergence of particle swarm optimization methods
From MaRDI portal
Publication:6166343
metaheuristicsparticle swarm optimizationmean-field limitVlasov-Fokker-Planck equationsglobal derivative-free optimizationhigh-dimensional nonconvex optimization
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)
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.
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
Cites work
- scientific article; zbMATH DE number 6019552 (Why is no real title available?)
- scientific article; zbMATH DE number 4211245 (Why is no real title available?)
- scientific article; zbMATH DE number 41891 (Why is no real title available?)
- scientific article; zbMATH DE number 53884 (Why is no real title available?)
- scientific article; zbMATH DE number 3497315 (Why is no real title available?)
- scientific article; zbMATH DE number 1245556 (Why is no real title available?)
- scientific article; zbMATH DE number 1310111 (Why is no real title available?)
- scientific article; zbMATH DE number 1158743 (Why is no real title available?)
- scientific article; zbMATH DE number 3438157 (Why is no real title available?)
- scientific article; zbMATH DE number 1972910 (Why is no real title available?)
- scientific article; zbMATH DE number 1405267 (Why is no real title available?)
- scientific article; zbMATH DE number 7626752 (Why is no real title available?)
- A Convergence Proof for the Particle Swarm Optimiser
- A Stochastic Approximation Method
- A comprehensive survey on particle swarm optimization algorithm and its applications
- A consensus-based global optimization method for high dimensional machine learning problems
- A consensus-based model for global optimization and its mean-field limit
- A mean field view of the landscape of two-layer neural networks
- An algorithmic introduction to numerical simulation of stochastic differential equations
- An analytical framework for consensus-based global optimization method
- An initiation to logarithmic Sobolev inequalities. Transl. from the French by Donald Babbitt
- Analyzing Convergence and Rates of Convergence of Particle Swarm Optimization Algorithms Using Stochastic Approximation Methods
- Anisotropic diffusion in consensus-based optimization on the sphere
- Applied asymptotic analysis
- Consensus-based global optimization with personal best
- Consensus-based optimization on hypersurfaces: Well-posedness and mean-field limit
- From particle swarm optimization to consensus based optimization: stochastic modeling and mean-field limit
- Handbook of swarm intelligence. Concepts, principles and applications
- Metaheuristics for Hard Optimization
- More is the same; phase transitions and mean field theories
- On the mean-field limit for the Vlasov-Poisson-Fokker-Planck system
- Particle swarm optimization almost surely finds local optima
- Random batch methods (RBM) for interacting particle systems
- 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)
- Stochastic differential equations. An introduction with applications.
- Stochastic mean-field limit: non-Lipschitz forces and swarming
- Zero-inertia limit: from particle swarm optimization to consensus-based optimization
Cited in
(14)- Optimization by linear kinetic equations and mean-field Langevin dynamics
- Leveraging memory effects and gradient information in consensus-based optimisation: on global convergence in mean-field law
- Erratum to ``On convergence of the multi-objective particle swarm optimizers
- Consensus-based optimization methods converge globally
- On the convergence of a population-based global optimization algorithm
- 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
- A note on the mean-field limit for the particle swarm optimization
- A Convergence Proof for the Particle Swarm Optimiser
- Zero-inertia limit: from particle swarm optimization to consensus-based optimization
- Convergence analysis of particle swarm optimization in one dimension
- 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
- Swarm-based gradient descent method for non-convex optimization
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)
