| In a simulation a random variable, Y, can often be identified that is likely to be highly correlated with a random variable of interest, X. If muY = E[ Y] is known then Y can be used as a control variate to estimate muX = E[ X] more efficiently than by a direct simulation of X. We propose a method that uses Y to speed up the simulation when muY is unknown. The method is effective when muY can be efficiently estimated in an auxiliary simulation that does not involve X. For a simulation of length t > 0 time units, we invest pt units estimating muY with the auxiliary simulation, yielding an estimator Z¯pt. The remaining q = (1 - p)t units are spent on the main simulation yielding estimates (X˜qt, Y˜ qt) for (muX, mu Y). The two simulations can be interleaved so they are effectively done simultaneously. For each p ∈ (0,1) and alpha ∈ ℜ we have a quasi control variate estimator for muX Q&d1;tp ,a=X&d5; qt+a&parl0;Y&d5;qt -Z&d1;pt&parr0;, t>0. .;We find p and alpha that minimize the asymptotic variance of Q¯t(p, alpha) in terms of statistics that are estimated during the simulations and then describe an easily implemented adaptive procedure that achieves the minimum variance. The adaptive procedure evolves into the optimal quasi control variate scheme if it is more efficient than a direct simulation, X¯t → mu X; otherwise it develops into the direct simulation. This research is motivated by stochastic linear programs where problem data are random; in this setting, we estimate the expected value of the objective function. We illustrate applications involving petroleum refining and power system reliability evaluation. In the former application the constraint matrix is random and a simple approximation can be constructed to generate an effective control variate. For the power system reliability evaluation illustration, a special "dual" approximation to the primal problem is constructed to form an effective control variate. In both cases, a tremendous improvement in efficiency is realized. |
