Rigorous finite-time guarantees for optimization on continuous domains by simulated annealing

Start Time: 2.15pm, Building 59 (Zepler), Seminar Room 1/p>

Speaker: Andrea Lecchini from the Department of Engineering, University of Leicester

Simulated annealing is a popular method for approaching the solution of a global optimization problem. Existing results on its performance apply to discrete combinatorial optimization where the optimization variables can assume only a finite set of possible values. In this talk I will introduce new results which allow one to guarantee finite-time performance of simulated annealing in the optimization of functions of continuous variables. I will first recall a result of Vidyasagar which introduced rigorous finite-time guarantees for the optimization of expected-value criteria based on independent sampling of the optimization domain. Then, I will show that a similar type of finite-time guarantees can be achieved by the more general family of simulated annealing algorithms. The results hold universally for any optimization problem on a bounded domain and establish a connection between simulated annealing and up-to-date theory of convergence of Markov chain Monte Carlo methods on continuous domains.