Stochastic optimization by simulation: Convergence proofs for the GI/G/1 queue in steady-state

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, the authors 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, they 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 the present convergence proofs, the authors obtain some properties of the derivative estimators that could be of independent interest. The analysis exploits the regenerative structure of the system, but the present derivative estimation and optimization algorithms do not always take advantage of that regenerative structure. In a companion paper, the authors report numerical experiments with an M/M/1 queue, which illustrate the basic convergence properties and possible pitfalls of the various techniques.