Abstract
We propose and study a version of simulated annealing (SA) on continuous state spaces based on (t,s)R-sequences. The parameter R ∈ Ν regulates the degree of randomness of the input sequence, with the case R=0 corresponding to IID uniform random numbers and the limiting case R=∞ to (t,s)-sequences. Our main result, obtained for rectangular domains, shows that the resulting optimization method, which we refer to as QMC-SA, converges almost surely to the global optimum of the objective function φ for any R ∈ N. When φ is univariate, we are in addition able to show that the completely deterministic version of QMC-SA is convergent. A key property of these results is that they do not require objective-dependentconditions on the cooling schedule. As a corollary of our theoretical analysis, we provide a new almost sure convergence result for SA which shares this property under minimal assumptions on φ. 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. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study.
Original language | English |
---|---|
Pages (from-to) | 189-217 |
Number of pages | 29 |
Journal | Journal of Global Optimization |
Volume | 68 |
Issue number | 1 |
Early online date | 8 Sept 2016 |
DOIs | |
Publication status | Published - May 2017 |
Keywords
- Global optimization
- Quasi-Monte Carlo
- Randomized quasi-Monte Carlo
- Simulated annealing
- Threshold accepting
Fingerprint
Dive into the research topics of 'Improving simulated annealing through derandomization'. Together they form a unique fingerprint.Profiles
-
Dr Mathieu Gerber
- School of Mathematics - Senior Lecturer in Statistical Science
- Statistical Science
Person: Academic , Member