| In this paper we discuss the issue of solving stochastic optimization problems by
means of sample average approximations. Our focus is on rates of convergence of estimators of optimal solutions and optimal values with respect to the sample size. This
is a well studied problem in case the samples are independent and identically distributed (i.e., when standard Monte Carlo is used); here, we study the case where that
assumption is dropped. Broadly speaking, our results show that, under appropriate assumptions, the rates of convergence for pointwise estimators under a sampling scheme
carry over to the optimization case, in the sense that convergence of approximating
optimal solutions and optimal values to their true counterparts has the same rates as
in pointwise estimation.
Our motivation for the study arises from two types of sampling methods that have
been widely used in the Statistics literature. One is Latin Hypercube Sampling (LHS),
a stratified sampling method originally proposed in the seventies by McKay, Beckman,
and Conover (1979). The other is the class of quasi-Monte Carlo (QMC) methods,
which have become popular especially after the work of Niederreiter (1992). The
advantage of such methods is that they typically yield pointwise estimators which not
only have lower variance than standard Monte Carlo but also possess better rates of
convergence. Thus, it is important to study the use of these techniques in sampling-based optimization. The novelty of our work arises from the fact that, while there
has been some work on the use of variance reduction techniques and QMC methods in
stochastic optimization, none of the existing work — to the best of our knowledge — has
provided a theoretical study on the effect of these techniques on rates of convergence for
the optimization problem. We present numerical results for some two-stage stochastic
programs from the literature to illustrate the discussed ideas.
|
To export the complete metadata set as Endote or Bibtex format please click to the appropriate link.
