Stochastic Programming

On Safe Tractable Approximations of Chance Constrained Linear Matrix Inequalities

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , ,

    In the paper, we consider the chance constrained version $$ \Prob\{A_0[x]+\sum_{i=1}^d\zeta_i A_i[x]\succeq0\}\geq1-\epsilon, $$ of an affinely perturbed Linear Matrix Inequality constraint; here $A_i[x]$ are symmetric matrices affinely depending on the decision vector $x$, and $\zeta_1,…,\zeta_d$ are independent of each other random perturbations with light tail distributions (e.g., bounded or Gaussian). Constraints of this type, playing … Read more

    Asymptotics of minimax stochastic programs

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

    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

    A Q-Learning Algorithm with Continuous State Space

  • Kengy Barty
  • Pierre Girardeau
  • Jean-Sebastien Roy
  • Cyrille Strugarek
    • Categories Dynamic Programming, Stochastic Programming Tags , ,

    We study in this paper a Markov Decision Problem (MDP) with continuous state space and discrete decision variables. We propose an extension of the Q-learning algorithm introduced to solve this problem by Watkins in 1989 for completely discrete MDPs. Our algorithm relies on stochastic approximation and functional estimation, and uses kernels to locally update the … Read more

    Cutting planes for multi-stage stochastic integer programs

  • Shabbir Ahmed
  • Yongpei Guan
  • George L. Nemhauser
    • Categories Cutting Plane Approaches, Stochastic Programming Tags , , ,

    This paper addresses the problem of finding cutting planes for multi-stage stochastic integer programs. We give a general method for generating cutting planes for multi-stage stochastic integer programs based on combining inequalities that are valid for the individual scenarios. We apply the method to generate cuts for a stochastic version of a dynamic knapsack problem … Read more

    Selected Topics in Robust Convex Optimization

  • Aharon Ben-Tal
  • Arkadi Nemirovski
    • Categories Control Applications, Robust Optimization, Stochastic Programming Tags , , ,

    Robust Optimization is a rapidly developing methodology for handling optimization problems affected by non-stochastic “uncertain-but-bounded” data perturbations. In this paper, we overview several selected topics in this popular area, specifically, (1) recent extensions of the basic concept of {\sl robust counterpart} of an optimization problem with uncertain data, (2) tractability of robust counterparts, (3) links … Read more

    A Warm-Start Approach for Large-Scale Stochastic Linear Programs

  • Marco Colombo
  • Jacek Gondzio
  • Andreas Grothey
    • Categories Linear Programming, Stochastic Programming Tags , ,

    We describe a method of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree … Read more

    A New Stochastic Algorithm for Engineering Optimization Problems

  • Tran Van Hao
  • Nguyen Huu Thong
    • Categories Constrained Nonlinear Optimization, Robust Optimization, Stochastic Programming Tags ,

    This paper proposes a new stochastic algorithm, Search via Probability (SP) algorithm, for single-objective optimization problems. The SP algorithm uses probabilities to control the process of searching for optimal solutions. We calculate probabilities of the appearance of a better solution than the current one on each iteration, and on the performance of SP algorithm we … Read more

    Step decision rules for multistage stochastic programming: a heuristic approach

  • Julien Thénié
  • Jean-Philippe Vial
    • Categories Stochastic Programming, Supply Chain Management Tags , , ,

    Stochastic programming with step decision rules, SPSDR, is an attempt to overcome the curse of computational complexity of multistage stochastic programming problems. SPSDR combines several techniques. The first idea is to work with independent experts. Each expert is confronted with a sample of scenarios drawn at random from the original stochastic process. The second idea … 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

    Goal Driven Optimization

  • Wenqing Chen
  • Melvyn Sim
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Achieving a targeted objective, goal or aspiration level are relevant aspects of decision making under uncertainties. We develop a goal driven stochastic optimization model that takes into account an aspiration level. Our model maximizes the shortfall aspiration level criterion}, which encompasses the probability of success in achieving the goal and an expected level of under-performance … Read more