JSM 2015 Preliminary Program

Online Program Home
My Program

Abstract Details

Activity Number: 502
Type: Contributed
Date/Time: Wednesday, August 12, 2015 : 8:30 AM to 10:20 AM
Sponsor: Section on Statistical Computing
Abstract #316986
Title: Improving Simulated Annealing Through Derandomization
Author(s): Mathieu Gerber* and Luke Bornn
Companies: Harvard University and Harvard University
Keywords: Global optimization ; Simulated annealing ; Quasi-Monte Carlo
Abstract:

We propose and study a quasi-Monte Carlo (QMC) version of simulated annealing (SA) on continuous state spaces. The convergence of this new deterministic optimization method, which we refer to as QMC-SA, is proved both in the case where the same Markov kernel is used throughout the course of the algorithm and in the case where it shrinks over time to improve local exploration. The theoretical guarantees for QMC-SA are stronger than those for classical SA, for example requiring no objective-dependent conditions on the algorithm's cooling schedule and allowing for convergence results even with time-varying Markov kernels (which, for Monte Carlo SA, only exist for the convergence in probability). 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, and show how randomness can be re-introduced to get a stochastic version of QMC-SA which exhibits (almost surely) the good theoretical properties of the deterministic algorithm. We finally illustrate the superiority of QMC-SA over SA algorithms in a numerical study, notably on a non-different


Authors who are presenting talks have a * after their name.

Back to the full JSM 2015 program





For program information, contact the JSM Registration Department or phone (888) 231-3473.

For Professional Development information, contact the Education Department.

The views expressed here are those of the individual authors and not necessarily those of the JSM sponsors, their officers, or their staff.

2015 JSM Online Program Home