Improving simulated annealing through derandomization

DOI10.1007/S10898-016-0461-1MaRDI QIDQ2397439zbMATHOpenAlexFDO

Authors Mathieu Gerber, Luke Bornn

Publication date 22 May 2017

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3837278 (Why is no real title available?)
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 2051229 (Why is no real title available?)
• scientific article; zbMATH DE number 1790423 (Why is no real title available?)
• scientific article; zbMATH DE number 1857675 (Why is no real title available?)
• scientific article; zbMATH DE number 2117879 (Why is no real title available?)
• scientific article; zbMATH DE number 822320 (Why is no real title available?)
• 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
• Adaptive simulated annealing for optimization in signal processing applications
• Algorithm 823
• Convergence of a simulated annealing algorithm for continuous global optimization.
• Convergence of simulated annealing using Foster-Lyapunov criteria
• Convergence properties of simulated annealing for continuous global optimization
• Convergence theorems for a class of simulated annealing algorithms on ℝ^d
• Diffusions for Global Optimization
• Extensible Grids: Uniform Sampling on a Space Filling Curve
• Fast simulated annealing in \(\mathbb R^d\) with an application to maximum likelihood estimation in state-space models
• Global optimization of statistical functions with simulated annealing
• Localization of Search in Quasi-Monte Carlo Methods for Global Optimization
• Metropolis-Type Annealing Algorithms for Global Optimization in $\mathbb{R}^d $
• Modeling nonstationary processes through dimension expansion
• On the convergence of ``threshold accepting
• Point sets and sequences with small discrepancy
• Recursive Stochastic Algorithms for Global Optimization in $\mathbb{R}^d $
• Remarks on a Multivariate Transformation
• Sequential quasi Monte Carlo. With discussion and authors' reply
• Simulated annealing for maximum a posteriori parameter estimation of hidden Markov models
• Simulated annealing process in general state space
• Stochastic Optimization on Continuous Domains With Finite-Time Guarantees by Markov Chain Monte Carlo Methods
• The threshold accepting optimisation algorithm in economics and statistics
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• Very fast simulated re-annealing

Cited in

(4)

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

Describes a project that uses

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)