Improving simulated annealing through derandomization

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.