Groupe d’études et de recherche en analyse des décisions

Central Limit Theorems for Stochastic Optimization Algorithms using Infinitesimal Perturbation Analysis

Qian-Yu Tang, Pierre L'Ecuyer et Han-Fu Chen

Central limit theorems are obtained for the perturbation analysis Robbins-Monro single run'' (PARMSR) optimization algorithm, with updates either after every L customers or after every busy period, in the context of the optimization of a GI/GI/1 queue. The PARMSR algorithm is a stochastic approximation (SA) method for the optimization of infinite-horizon models. It is shown that the convergence rate and the asymptotic variance constant of the optimization algorithm, as a function of the total computing budget (i.e., total number of customers), are the same for both updating methods, and independent of L, provided that the step sizes of SA are chosen in the (asymptotically) optimal way for each method.

, 30 pages