Improving simulated annealing through derandomization

DOI10.1007/S10898-016-0461-1zbMATH Open1372.90084arXiv1505.03173OpenAlexW1765974657MaRDI QIDQ2397439FDOQ2397439

Authors: Mathieu Gerber, Luke Bornn 

Publication date: 22 May 2017

Published in: Journal of Global Optimization (Search for Journal in Brave)

Abstract: We propose and study a version of simulated annealing (SA) on continuous state spaces based on $(t,s{)}_R$-sequences. The parameter $$ 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=infty$ 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 $RinmathbbN$. 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.

Full work available at URL: https://arxiv.org/abs/1505.03173

Recommendations

• Simulated annealing for almost sure convergent random sequences
• Sequential Monte Carlo simulated annealing
• Simulated annealing algorithms for continuous global optimization: Convergence conditions
• Simulated annealing type algorithms for multivariate optimization
• Simulated annealing for discrete optimization with estimation

zbMATH Keywords

simulated annealingglobal optimizationquasi-Monte Carlothreshold acceptingrandomized quasi-Monte Carlo

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Nonconvex programming, global optimization (90C26)

Cites Work

• Algorithm 823
• Global optimization of statistical functions with simulated annealing
• Title not available (Why is that?)
• Remarks on a Multivariate Transformation
• Convergence theorems for a class of simulated annealing algorithms on ℝ^d
• Title not available (Why is that?)
• Title not available (Why is that?)
• Modeling nonstationary processes through dimension expansion
• Title not available (Why is that?)
• Very fast simulated re-annealing
• Point sets and sequences with small discrepancy
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
• Stochastic Optimization on Continuous Domains With Finite-Time Guarantees by Markov Chain Monte Carlo Methods
• Sequential Quasi Monte Carlo
• Diffusions for Global Optimization
• The threshold accepting optimisation algorithm in economics and statistics
• Convergence properties of simulated annealing for continuous global optimization
• Localization of Search in Quasi-Monte Carlo Methods for Global Optimization
• On the convergence of ``threshold accepting
• Convergence of a simulated annealing algorithm for continuous global optimization.
• Convergence of simulated annealing using Foster-Lyapunov criteria
• Title not available (Why is that?)
• Adaptive simulated annealing for optimization in signal processing applications
• A modification to the new version of the Price's algorithm for continuous global optimization problems
• Adaptive random search in quasi-Monte Carlo methods for global optimization
• Title not available (Why is that?)
• Fast simulated annealing in \(\mathbb R^d\) with an application to maximum likelihood estimation in state-space models
• Simulated annealing for maximum a posteriori parameter estimation of hidden Markov models
• Metropolis-Type Annealing Algorithms for Global Optimization in $\mathbb{R}^d $
• Title not available (Why is that?)
• Extensible Grids: Uniform Sampling on a Space Filling Curve
• Simulated annealing process in general state space
• Title not available (Why is that?)

Cited In (4)

• An exact D-dimensional Tsallis random number generator for generalized simulated annealing
• The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods
• Sequential Monte Carlo simulated annealing
• On the convergence rate issues of general Markov search for global minimum

Uses Software

• Algorithm 823

This page was built for publication: Improving simulated annealing through derandomization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397439)