Improving simulated annealing through derandomization

Mathieu Gerber () and Luke Bornn
Additional contact information
Mathieu Gerber: Harvard University
Luke Bornn: Harvard University

Journal of Global Optimization, 2017, vol. 68, issue 1, No 9, 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 (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10898-016-0461-1 Abstract (text/html)
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

Persistent link: https://EconPapers.repec.org/RePEc:spr:jglopt:v:68:y:2017:i:1:d:10.1007_s10898-016-0461-1

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

DOI: 10.1007/s10898-016-0461-1

Access Statistics for this article

Journal of Global Optimization is currently edited by Sergiy Butenko

More articles in Journal of Global Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().