sample average approximation method

Epi-convergence of Sample Averages of a Random Lower Semi-continuous Functional Generated by a Markov Chain and Application to Stochastic Optimization

  • John Birge
  • Arnab Sur
    • Categories Stochastic Programming Tags , , , , , ,

    The purpose of this article is to establish epigraphical convergence of the sample averages of a random lower semi-continuous functional associated with a Harris recurrent Markov chain with stationary distribution $\pi$. Sample averages associated with an ergodic Markov chain with stationary probability distribution will epigraphically converge from $\pi$-almost all starting points. The property of Harris … Read more

    STOCHASTIC OPTIMIZATION OVER A PARETO SET ASSOCIATED WITH A STOCHASTIC MULTI-OBJECTIVE OPTIMIZATION PROBLEM

  • Henri Bonnel
  • Julien Collonge
    • Categories Multi-Criteria Optimization, Stochastic Approaches Tags , , , ,

    We deal with the problem of minimizing the expectation of a real valued random function over the weakly Pareto or Pareto set associated with a Stochastic Multi-Objective Optimization Problem (SMOP) whose objectives are expectations of random functions. Assuming that the closed form of these expectations is difficult to obtain, we apply the Sample Average Approximation … Read more

    Analysis of Stochastic Dual Dynamic Programming Method

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , ,

    In this paper we discuss statistical properties and rates of convergence of the Stochastic Dual Dynamic Programming (SDDP) method applied to multistage linear stochastic programming problems. We assume that the underline data process is stagewise independent and consider the framework where at first a random sample from the original (true) distribution is generated and consequently … Read more

    Validation Analysis of Robust Stochastic Approximation Method

  • Guanghui Lan
  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , , , , ,

    The main goal of this paper is to develop accuracy estimates for stochastic programming problems by employing robust stochastic approximation (SA) type algorithms. To this end we show that while running a Robust Mirror Descent Stochastic Approximation procedure one can compute, with a small additional effort, lower and upper statistical bounds for the optimal objective … Read more

    Stochastic Approximation approach to Stochastic Programming

  • Anatoli Juditsky
  • Guanghui Lan
  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Convex and Nonsmooth Optimization, Stochastic Programming Tags , , , , , , ,

    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

    Stochastic Programming Approach to Optimization under Uncertainty

  • Alexander Shapiro
    • Categories Stochastic Programming Tags , , , , , ,

    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