2000-01-31Buch DOI: 10.18452/8227
Variable-sample methods and simulated annealing for discrete stochastic optimization
In this paper we study a modifcation of the well-known simulated annealing method, adapting it to discrete stochastic optimization problems. Our algorithm is based on a variable-sample Monte Carlo technique, in which the objective function is replaced, at each iteration, by a sample average approximation. The idea is to obtain independent estimates of the objective function, to avoid getting "trapped" in a single sample-path. We first provide general results under which variable-sample methods yield consistent estimators as well as bounds on the estimation error. Then, we concentrate on the simulated annealing algorithm, and derive a proper schedule of sample sizes that guarantees convergence of the overall algorithm w.p.1. Because the convergence analysis is done sample-path wise (by means of the law of the iterated logarithm), we are able to obtain our results in a exible setting, which includes the possibility of using different neighborhood structures and different sampling distributions along the algorithm, without making strong assumptions on the underlying distributions.
Files in this item
No license information