Convergence rate of a simulated annealing algorithm with noisy observations

Clément Bouttier (1, 2, 3) , Ioana Gavra (2)

1 ENAC - Ecole Nationale de l'Aviation Civile
2 IMT - Institut de Mathématiques de Toulouse UMR5219
3 Airbus Operation S.A.S.

In this paper we propose a modified version of the simulated annealing algorithm for solving a stochastic global optimization problem. More precisely, we address the problem of finding a global minimizer of a function with noisy evaluations. We provide a rate of convergence and its optimized parametrization to ensure a minimal number of evaluations for a given accuracy and a confidence level close to 1. This work is completed with a set of numerical experimentations and assesses the practical performance both on benchmark test cases and on real world examples.

Mots clés: Simulated Annealing; Stochastic Optimization; Markov Process; Convergence Rate; Aircraft Trajectory Optimization

Domaines: Machine Learning [stat.ML]; Optimisation et contrôle [math.OC]; Statistiques [math.ST]

Clément Bouttier, Ioana Gavra. Convergence rate of a simulated annealing algorithm with noisy observations. 2016. ⟨hal-01477930⟩