Alexander Shapiro In this paper we consider optimization problems where the objective function is given in a form of the expectation. A basic difficulty of solving such stochastic optimization problems is that the involved multidimensional integrals (expectations) cannot be computed with high accuracy. The aim of this paper is to compare two computational approaches based on Monte … Read more
We discuss in this paper asymptotics of the sample average approximation (SAA) of the optimal value of a minimax stochastic programming problem. The main tool of our analysis is a specific version of the infinite dimensional Delta Method. As an example, we discuss asymptotics of SAA of risk averse stochastic programs involving the absolute semideviation … Read more
We consider a class of two-stage linear stochastic programming problems, introduced by Shmoys and Swamy (2004), motivated by a relaxation of a stochastic set cover problem. We show that the sample size required to solve this problem by the sample average approximation (SAA) method with a relative accuracy $\kappa>0$ and confidence $1-\alpha$ is polynomial in … Read more
In this paper we discuss computational complexity and risk averse approaches to two and multistage stochastic programming problems. We argue that two stage (say linear) stochastic programming problems can be solved with a reasonable accuracy by Monte Carlo sampling techniques while there are indications that complexity of multistage programs grows fast with increase of the … Read more
We derive a uniform (strong) Law of Large Numbers (LLN) for random set-valued mappings. The result can be viewed as an extension of both, a uniform LLN for random functions and LLN for random sets. We apply the established results to a consistency analysis of stationary points of sample average approximations of nonsmooth stochastic programs. … Read more
We analyze an extension of the classical multi-period, single-item, linear cost inventory problem where the objective function is a coherent risk measure. Properties of coherent risk measures allow us to offer a unifying treatment of risk averse and min-max type formulations. For the single period newsvendor problem, we show that the structure of the optimal … Read more
In this paper, we discuss the sample average approximation (SAA) method applied to a class of stochastic mathematical programs with variational (equilibrium) constraints. To this end, we briefly investigate piecewise structure and directional differentiability of both — the lower level equilibrium solution and objective integrant. We show almost sure convergence of optimal values, optimal solutions … Read more
In this paper we derive estimates of the sample sizes required to solve a multistage stochastic programming problem with a given accuracy by the (conditional sampling) sample average approximation method. The presented analysis is self contained and is based on a, relatively elementary, one dimensional Cramer’s Large Deviations Theorem. Citation Working paper, Georgia Institute of … Read more
We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given (close to one) probability, a system of randomly perturbed convex constraints. Our goal is to build a computationally tractable approximation of this (typically intractable) problem, i.e., an explicitly given convex optimization program with the feasible … Read more
We consider an optimization problem of minimization of a linear function subject to chance constraints. In the multidimensional case this problem is, generically, a problem of minimizing under a nonconvex and difficult to compute constraints and as such is computationally intractable. We investigate the potential of conceptually simple scenario approximation of the chance constraints. The … Read more