Optimal Budget Allocation for Sample Average Approximation

Abstract

The sample average approximation approach to solving stochastic programs induces a sampling error, caused by replacing an expectation by a sample average, as well as an optimization error due to approximating the solution of the resulting sample average problem. We obtain estimators of an optimal solution and the optimal value of the original stochastic program after executing a finite number of iterations of an optimization algorithm applied to the sample average problem. We examine the convergence rate of the estimators as the computing budget tends to infinity, and characterize the allocation policies that maximize the convergence rate in the case of sublinear, linear, and superlinear convergence regimes for the optimization algorithm.