Adaptive Simulated Annealing through Alternating Rényi Divergence Minimization

Simulated annealing is a popular approach to solve non-convex and black-box optimization problems. It consists in running a non-homogeneous Markov chain to sample from a sequence of Boltzman probability distributions. This sequence is controlled by a cooling schedule, which governs the concentration of the mass of the Boltzman distributions around the global minimizers. However, convergence is often slow, difficult to assess, and requires a fixed cooling schedule. We propose here a new simulated annealing algorithm with adaptive cooling schedule, which draws samples from variational approximations of the Boltzman distributions. Our approach is theoretically sound and relies on an alternating Bregman proximal-gradient scheme minimizing a regularized Rényi divergence. Numerical experiments illustrate the performance of the method.