STOCHASTIC OPTIMIZATION BY SIMULATION - CONVERGENCE PROOFS FOR THE GIG/1 QUEUE IN STEADY-STATE/

Approaches like finite differences with common random numbers, infinit esinal perturbation analysis, and the likelihood ratio method have dra wn a great deal of attention recently as ways of estimating the gradie nt of a performance measure with respect to continuous parameters in a dynamic stochastic system. In this paper, we study the use of such es timators in stochastic approximation algorithms, to perform so-called ''single-run optimizations'' of steady-state systems. Under mild condi tions, for an objective function that involves the mean system time in a GI/G/1 queue, we prove that many variants of these algorithms conve rge to the minimizer. In most cases, however, the simulation length mu st be increased from iteration to iteration; otherwise the algorithm m ay converge to the wrong value. One exception is a particular implemen tation of infinitesimal perturbation analysis, for which the single-ru n optimization converges to the optimum even with a fixed (and small) number of ends of service per iteration. As a by-product of our conver gence proofs, we obtain some properties of the derivative estimators t hat could be of independent interest. Our analysis exploits the regene rative structure of the system, but our derivative estimation and opti mization 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 basic convergence properties and possible pitfalls of the various techniques.