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.
Description
Operations Research, Vol. 61, pp. 762-776.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Reliability-based design optimization using buffered failure probability
Basova, Habib Gurkan (Monterey, California. Naval Postgraduate School, 2010-06);Reliability-based design optimization (RBDO) seeks the best design for a structural system under uncertainty. Typically, uncertainty arises from random loads such as wind pressure and random material properties such as ... -
Efficient Sample Sizes in Stochastic Nonlinear Programming
Polak, E.; Royset, J.O. (2008);We consider a class of stochastic nonlinear programs for which an approximation to a locally optimal solution is speci_ed in terms of a fractional reduction of the initial cost error. We show that such an approximate ... -
ONLINE LEARNING OF MARKOVIAN SYSTEMS WITH CENSORED POISSON ARRIVALS
Gibbons Mac-Lean, Cedric G. (Monterey, CA; Naval Postgraduate School, 2021-06);This thesis deals with online optimization of discrete performance measures in Markovian models with incomplete information. We consider a setting where a physical realization of the model is sequentially obtained over a ...