Improving simulated annealing through derandomization

We propose and study a version of simulated annealing (SA) on continuous state spaces based on $$(t,s)_R$$ ( t , s ) R -sequences. The parameter $$R\in \bar{\mathbb {N}}$$ R ∈ N ¯ regulates the degree of randomness of the input sequence, with the case $$R=0$$ R = 0 corresponding to IID uniform random numbers and the limiting case $$R=\infty $$ 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 $$\varphi $$ φ for any $$R\in \mathbb {N}$$ R ∈ N . When $$\varphi $$ φ 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-dependent conditions 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 $$\varphi $$ φ . 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.