Events Archive

We consider the single-stage stochastic optimization problem to minimize
the expected cost over a set of decisions. Motivated by the dual
formulation of optimal stopping problems we focus on the following
situation: The set of minimizers is infinite and there is at least one
"surely optimal" decision, i.e., a minimizer whose cost has zero
variance.
  A classical method for solving stochastic optimization problems
numerically is sample average approximation (SAA), a Monte Carlo method
which replaces the expectation by the empirical mean over a simulated
sample and then applies deterministic algorithms to search for a
minimizer of the approximate problem. While SAA is known to converge to
an optimal decision under appropriate assumptions, we illustrate that it
may fail to converge to a surely optimal decision.
  In order to exploit the zero-variance property of surely optimal
decisions we suggest a randomization of the original optimization
problem, which enforces convergence of SAA to surely optimal decisions,
while preserving the structure of the problem (e.g., convexity or linear
programming formulation of the deterministic problem). We state improved
convergence properties of the randomization approach in the framework of
optimal stopping and illustrate the results in some numerical
experiments.