Stochastic Optimization by Simulation: Convergence Proofs for the GI/G/1 Queue in Steady-State

Pierre L'Ecuyer and Peter W. Glynn
Additional contact information
Pierre L'Ecuyer: Département d'I.R.o., Université de Montréal, C.P. 6128, Montréal, Quebec, Canada, H3C 3J7
Peter W. Glynn: Operations Research Department, Stanford University, Stanford, California 94305

Management Science, 1994, vol. 40, issue 11, 1562-1578

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 system. 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 variant 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. Our analysis exploits the regenerative structure of the system, but our derivative estimation and optimization algorithms do not always take advantage of that regenerative structure. In a companion paper, we report numerical experiments with an M/M/1 queue, which illustrate the basis convergence properties and possible pitfalls of the various techniques.

Keywords: discrete event systems; stochastic approximation; gradient estimation; optimization; steady-state (search for similar items in EconPapers)
Date: 1994
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.40.11.1562 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:40:y:1994:i:11:p:1562-1578

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().