Stochastic Optimization by Simulation: Convergence Proofs for the GI/G/1 Queue in Steady-State
Abstract
Approaches like finite differences with common random numbers, infinitesimal perturbation analysis, and the likelihood ratio method, have drawn a great deal of attention recently, as ways of estimating the gradient of a performance measure with respect to continuous parameters in a dynamic stochastic systems. In this paper, we study the use of such estimators in stochastic approximation algorithms, to perform so-called 'single-run optimizations' of steady-state systems. Under mild conditions, for an objective function that involves the mean system time in a GI/G/1 queue, we prove that many variants of these algorithms converge to the minimizer. In most cases, however, the simulation length must be increased from iteration to iteration; otherwise the algorithm may converge to the wrong value. One exception is a particular implementation of infinitesimal perturbation analysis, for which the single-run optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. As a by-product of our convergence proofs, we obtain some properties of the derivative estimators that could be of independent interest.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 20, 1993
- Accession Number
- ADA271141
Entities
People
- Peter W. Glynn
- Pierre L'ecuyer
Organizations
- Stanford University