two-stage stochastic programming

Convergence Analysis of a Weighted Barrier Decomposition Algorithm for Two Stage Stochastic Programming

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Linear, Cone and Semidefinite Programming, Stochastic Programming Tags , ,

    Mehrotra and Ozevin computationally found that a weighted primal barrier decomposition algorithm significantly outperforms the barrier decomposition proposed and analyzed in Zhao, and Mehrotra and Ozevin. This paper provides a theoretical foundation for the weighted barrier decomposition algorithm (WBDA). Although the worst case analysis of the WBDA achieves a first-stage iteration complexity bound that is … Read more

    On complexity of Shmoys – Swamy class of two-stage linear stochastic programming problems

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Approximation Algorithms, Stochastic Programming Tags , ,

    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

    Stochastic Programming with Equilibrium Constraints

  • Alexander Shapiro
    • Categories Complementarity and Variational Inequalities, Stochastic Programming Tags , , , , , ,

    In this paper we discuss here-and-now type stochastic programs with equilibrium constraints. We give a general formulation of such problems and study their basic properties such as measurability and continuity of the corresponding integrand functions. We also discuss consistency and rates of convergence of sample average approximations of such stochastic problems. CitationSchool of Industrial and … Read more