2000-01-31Buch DOI: 10.18452/2844
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.
Dateien zu dieser Publikation