Kinetic variable-sample methods for stochastic optimization problems

Communications on Pure &amp Applied Analysis, vol. 31, pp. 122–145

Abstract

We discuss kinetic-based particle optimization methods and variable-sample strategies for problems where the cost function represents the expected value of a random mapping. Kinetic-based optimization methods rely on a consensus mechanism targeting the global minimizer, and they exploit tools of kinetic theory to establish a rigorous framework for proving convergence to that minimizer. Variable-sample strategies replace the expected value by an approximation at each iteration of the optimization algorithm. We combine these approaches and introduce a novel algorithm based on instantaneous collisions governed by a linear Boltzmann-type equation. After proving the convergence of the resulting kinetic method under appropriate parameter constraints, we establish a connection to a recently introduced consensus-based method for solving the random problem in a suitable scaling. Finally, we showcase its enhanced computational efficiency compared to the aforementioned algorithm and validate the consistency of the proposed modeling approaches through several numerical experiments.

Authors 2

1. Sabrina Bonandin corresponding Aachen Institute for Geometry and Practical Mathematics

   RWTH Aachen University

   Affiliation as printed

   Institute for Geometry and Practical Mathematics , RWTH Aachen University , Templergraben 55 , 52062 Aachen , Germany

2. Michaël Herty Aachen Institute for Geometry and Practical Mathematics

   RWTH Aachen University

   Affiliation as printed

   Institute for Geometry and Practical Mathematics, RWTH Aachen University, Templergraben 55, 52062 Aachen, Germany