# Improving simulated annealing through derandomization

Mathieu Gerber () and Luke Bornn
Mathieu Gerber: Harvard University
Luke Bornn: Harvard University

Journal of Global Optimization, 2017, vol. 68, issue 1, 189-217

Abstract: Abstract 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.

Keywords: Global optimization; Quasi-Monte Carlo; Randomized quasi-Monte Carlo; Simulated annealing; Threshold accepting (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1) Track citations by RSS feed

Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/10898