Mean-field theory for consensus-based optimization and extensions to constrained and multi-objective problems

Abstract

Stochastic particle methods in optimization constitute a popular class of heuristic techniques where a set of possible solutions is iteratively updated according to deterministic and stochastic mechanisms. These algorithms are oftentimes inspired by natural phenomena such as the collective motion of birds in a swarm or the reproduction of genes in biology. Recent works apply kinetic tools developed for modeling such phenomena to the analysis of particle-based optimization methods to develop a full mathematical understanding of their convergence properties. In this thesis, we follow this line of research and propose a semi-discrete mean-field model for the analysis of Consensus-Based Optimization (CBO) methods. In the literature, CBO methods are typically analyzed after a twofold approximation: first, the algorithm dynamics are approximated by a system of time-continuous processes, then, the system is approximated by a mono-particle process of McKean type. Here, we directly consider a mean-field approximation of the algorithm’s update and derive a mono-particle difference equation. We also adapt the convergence results for the time-continuous mean-field model to these semi-discrete settings, claiming that this modeling procedure avoids the introduction of an unnecessary additional approximation error. The second part of the thesis extends the class of CBO methods to solve constrained and multi-objective optimization problems. For constrained optimization, we couple the CBO update rule with an exact penalization technique. By adding a penalty term, we reformulate the constrained problem as an unconstrained one and further propose an algorithmic technique to tune, during the computation, the penalization strength to its optimal value. For multi-objective problems, we modify the CBO dynamics so that every particle aims to optimize a different, parameterized scalar sub-problem. In this way, we are able to compute an approximation of the entire Pareto front with a single run of the algorithm. The parameters of the scalarized sub-problems are further adapted following binary repulsive dynamics to improve the diversity of the computed front. Via mean-field approximation, we show that the proposed algorithms are able to converge into a neighborhood of the solutions under mild assumptions, both in the case of constrained and multi-objective optimization problems. Numerical experiments over benchmark problems illustrate the algorithms’ performance in different settings and for different problem types.