EUROPT 2025
Abstract Submission

498. Controlled stochastic processes for simulated annealing

Invited abstract in session MD-12: Applications of optimisation under uncertainty, stream Applications: AI, uncertainty management and sustainability.

Monday, 16:30-18:30
Room: B100/8009

Authors (first author is the speaker)

1. Vincent Molin
Department of Mathematical Sciences, Chalmers University of Technology
2. Axel Ringh
Department of Mathematical Sciences, Chalmers University of Technology and the University of Gothenburg

Abstract

Simulated annealing solves optimization problems by means of a random walk in an energy landscape based on the objective function and a temperature parameter. By slowly decreasing the temperature, the algorithm converges to the global optimal solution, also for nonconvex functions. However, if the temperature is decreased too quickly, this procedure often gets stuck in local minima. To overcome this, we here present a new perspective on simulated annealing. More precisely, we consider the cooling landscape as a curve of probability measures and prove that there exists a minimal norm velocity field which solves the continuity equation. The latter is a differential equation which governs the evolution of the aforementioned curve. The solution is the weak gradient of an integrable function, which is in line with the interpretation of the velocity field as a derivative of optimal transport maps. We also show that controlling stochastic annealing processes by superimposing this velocity field would allow them to follow arbitrarily fast cooling schedules. Based on these findings, we design novel interacting particle based optimization methods, convergent optimal transport based approximations to this control, that accelerate simulated annealing processes. This acceleration behavior is also validated on a number of numerical experiments.

Keywords

Status: accepted

Back to the list of papers