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, 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.