2015/05/12 by Gerber, Mathieu, Bornn, Luke
#Computation (stat.CO) #FOS: Computer and information sciences #FOS: Mathematics #Numerical Analysis (math.NA) #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1505.03173
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∈ℕ. 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-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 φ. 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.