Abstract:
|
We propose and study a quasi-Monte Carlo (QMC) version of simulated annealing (SA) on continuous state spaces. The convergence of this new deterministic optimization method, which we refer to as QMC-SA, is proved both in the case where the same Markov kernel is used throughout the course of the algorithm and in the case where it shrinks over time to improve local exploration. The theoretical guarantees for QMC-SA are stronger than those for classical SA, for example requiring no objective-dependent conditions on the algorithm's cooling schedule and allowing for convergence results even with time-varying Markov kernels (which, for Monte Carlo SA, only exist for the convergence in probability). We further explain how our results in fact apply to a broader class of optimization methods including for example threshold accepting, for which to our knowledge no convergence results currently exist, and show how randomness can be re-introduced to get a stochastic version of QMC-SA which exhibits (almost surely) the good theoretical properties of the deterministic algorithm. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study, notably on a non-different
|
ASA Meetings Department
732 North Washington Street, Alexandria, VA 22314
(703) 684-1221 • meetings@amstat.org
Copyright © American Statistical Association.