Abstract
In this paper, we are concerned with the global minimization of a possibly nonsmooth and nonconvex objective function constrained on the unit hypersphere by means of a multi-agent derivative-free method. The proposed algorithm falls into the class of the recently introduced consensus-based optimization. In fact, agents move on the sphere driven by a drift towards an instantaneous consensus point, which is computed as a convex combination of agent locations, weighted by the cost function according to Laplace's principle, and it represents an approximation to a global minimizer. The dynamics is further perturbed by an anisotropic random vector field to favor exploration. The main results of this paper are about the proof of convergence of the numerical scheme to global minimizers provided conditions of well-preparation of the initial datum. The proof of convergence combines a mean-field limit result with a novel asymptotic analysis and classical convergence results of numerical methods for stochastic differential equations. The main innovation with respect to previous work is the introduction of an anisotropic stochastic term, which allows us to ensure the independence of the parameters of the algorithm from the dimension and to scale the method to work in very high dimension. We present several numerical experiments, which show that the algorithm proposed in the present paper is extremely versatile and outperforms previous formulations with isotropic stochastic noise.
Original language | English |
---|---|
Pages (from-to) | 1984-2012 |
Number of pages | 29 |
Journal | SIAM Journal on Optimization |
Volume | 32 |
Issue number | 3 |
Early online date | 16 Aug 2022 |
DOIs | |
Publication status | Published - Sept 2022 |
Keywords
- anisotropic stochastic Kuramoto-Vicsek model
- consensus-based optimization
- derivative-free optimization
- Fokker-Planck equations
- geometric optimization
- high-dimensional optimization
- machine learning
- signal processing
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Applied Mathematics