Stochastic Programming

Two-Stage Stochastic Semidefinite Programming and Decomposition Based Interior Point Methods

  • Sanjay Mehrotra
  • M. Gokhan Ozevin
    • Categories Semi-definite Programming, Stochastic Programming Tags , , ,

    We introduce two-stage stochastic semidefinite programs with recourse and present a Benders decomposition based linearly convergent interior point algorithms to solve them. This extends the results of Zhao, who showed that the logarithmic barrier associated with the recourse function of two-stage stochastic linear programs with recourse behaves as a strongly self-concordant barrier on the first … Read more

    Convex Approximations of Chance Constrained Programs

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    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

    Re-Solving Stochastic Programming Models for Airline Revenue Management

  • Lijian Chen
  • Tito Homem-de-Mello
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , ,

    We study some mathematical programming formulations for the origin-destination model in airline revenue management. In particular, we focus on the traditional probabilistic model proposed in the literature. The approach we study consists of solving a sequence of two-stage stochastic programs with simple recourse, which can be viewed as an approximation to a multi- stage stochastic … Read more

    Scenario Approximations of Chance Constraints

  • Arkadi Nemirovski
  • Alexander Shapiro
    • Categories Optimization of Simulated Systems, Stochastic Programming Tags , , , ,

    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

    On complexity of stochastic programming problems

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

    The main focus of this paper is discussion of complexity of stochastic programming problems. We argue that two-stage (linear) stochastic programming problems with recourse can be solved with a reasonable accuracy by using Monte Carlo sampling techniques, while multi-stage stochastic programs, in general, are intractable. We also discuss complexity of chance constrained problems and multi-stage … Read more

    Worst-case distribution analysis of stochastic programs

  • Alexander Shapiro
    • Categories Stochastic Programming

    We show that for even quasi-concave objective functions the worst-case distribution, with respect to a family of unimodal distributions, of a stochastic programming problem is a uniform distribution. This extends the so-called “Uniformity Principle” of Barmish and Lagoa (1997) where the objective function is the indicator function of a convex symmetric set. Article Download View … Read more

    A Branch-Reduce-Cut Algorithm for the Global Optimization of Probabilistically Constrained Linear Programs

  • Shabbir Ahmed
  • Faiz Al-Khayyal
  • Myun-Seok Cheon
    • Categories Global Optimization, Stochastic Programming

    We consider probabilistic constrained linear programs with general distributions for the uncertain parameters. These problems generally involve non-convex feasible sets. We develop a branch and bound algorithm that searches for a global solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partitions. … 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. Citation School of Industrial … Read more

    Solving Multistage Asset Investment Problems by the Sample Average Approximation Method

  • Jorgen Blomvall
  • Alexander Shapiro
    • Categories Finance and Economics, Stochastic Programming

    The vast size of real world stochastic programming instances requires sampling to make them practically solvable. In this paper we extend the understanding of how sampling affects the solution quality of multistage stochastic programming problems. We present a new heuristic for determining good feasible solutions for a multistage decision problem. For power and log-utility functions … Read more

    Portfolio Investment with the Exact Tax Basis via Nonlinear Programming

  • Victor DeMiguel
  • Raman Uppal
    • Categories Finance and Economics, Stochastic Programming Tags , ,

    Computing the optimal portfolio policy of an investor facing capital gains tax is a challenging problem: because the tax to be paid depends on the price at which the security was purchased (the tax basis), the optimal policy is path dependent and the size of the problem grows exponentially with the number of time periods. … Read more