Format:
1 Online-Ressource (36 Seiten)
Series Statement:
Stochastic Programming E-Print Series 2000,2000,4
Content:
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.
Language:
English
URN:
urn:nbn:de:kobv:11-10046200
URL:
Volltext
(kostenfrei)
Bookmarklink
