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 an estimator of 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 estimator 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 regime for the optimization algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2011
- Accession Number
- ADA551784
Entities
People
- Johannes Ø. Røyset
- Roberto Szechtman
Organizations
- Naval Postgraduate School