Stochastic Programming

Sampling-based decomposition methods for multistage stochastic programs based on extended polyhedral risk measures

  • Vincent Guigues
  • Werner Romisch
    • Categories Stochastic Programming

    We define a risk averse nonanticipative feasible policy for multistage stochastic programs and propose a methodology to implement it. The approach is based on dynamic programming equations written for a risk averse formulation of the problem. This formulation relies on a new class of multiperiod risk functionals called extended polyhedral risk measures. Dual representations of … Read more

    Robust and Stochastically Weighted Multi-Objective Optimization Models and Reformulations

  • Jian Hu
  • Sanjay Mehrotra
    • Categories Multi-Criteria Optimization, Robust Optimization, Stochastic Programming Tags , , ,

    In this paper we introduce robust and stochastically weighted sum approaches to deterministic and stochastic multi-objective optimization. The robust weighted sum approach minimizes the worst case weighted sum of objectives over a given weight region. We study the reformulations of the robust weighted sum problem under different definitions of deterministic weight regions. We next introduce … Read more

    The value of rolling horizon policies for risk-averse hydro-thermal planning

  • Vincent Guigues
  • Claudia Sagastizábal
    • Categories Applications - OR and Management Sciences, Robust Optimization, Stochastic Programming

    We consider the optimal management of a hydro-thermal power system in the mid and long terms. From the optimization point of view, this amounts to a large-scale multistage stochastic linear program, often solved by combining sampling with decomposition algorithms, like stochastic dual dynamic programming. Such methodologies, however, may entail prohibitive computational time, especially when applied … Read more

    On the Complexity of Non-Overlapping Multivariate Marginal Bounds for Probabilistic Combinatorial Optimization Problems

  • Xuan Vinh Doan
  • Karthik Natarajan
    • Categories Combinatorial Optimization, Stochastic Programming Tags , ,

    Given a combinatorial optimization problem with an arbitrary partition of the set of random objective coefficients, we evaluate the tightest possible bound on the expected optimal value for joint distributions consistent with the given multivariate marginals of the subsets in the partition. For univariate marginals, this bound was first proposed by Meilijson and Nadas (Journal … Read more

    Convex duality in stochastic programming and mathematical finance

  • Teemu Pennanen
    • Categories Convex and Nonsmooth Optimization, Finance and Economics, Stochastic Programming Tags , ,

    This paper proposes a general duality framework for the problem of minimizing a convex integral functional over a space of stochastic processes adapted to a given filtration. The framework unifies many well-known duality frameworks from operations research and mathematical finance. The unification allows the extension of some useful techniques from these two fields to a … Read more

    Inexact Bundle Methods for Two-Stage Stochastic Programming

  • Welington de Oliveira
  • Claudia Sagastizábal
  • Susana Scheimberg
    • Categories Nonlinear Optimization, Stochastic Programming Tags , ,

    Stochastic programming problems arise in many practical situations. In general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness in the subproblem … Read more

    PySP: Modeling and Solving Stochastic Programs in Python

  • William E. Hart
  • Jean-Paul Watson
  • David L. Woodruff
    • Categories Modeling Languages and Systems, Optimization Software Design Principles, Stochastic Programming Tags , , ,

    Although stochastic programming is a powerful tool for modeling decision-making under uncertainty, various impediments have historically prevented its wide-spread use. One key factor involves the ability of non-specialists to easily express stochastic programming problems as extensions of deterministic models, which are often formulated first. A second key factor relates to the difficulty of solving stochastic … Read more

    Information-theoretic lower bounds on the oracle complexity of convex optimization

  • Alekh Agarwal
  • Peter L Bartlett
  • Martin J Wainwright
  • Pradeep Ravikumar
    • Categories Convex Optimization, Stochastic Programming Tags ,

    Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic … Read more

    Scenario decomposition of risk-averse multistage stochastic programming problems

  • Ricardo A. Collado
  • Dávid Papp
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , , ,

    For a risk-averse multistage stochastic optimization problem with a finite scenario tree, we introduce a new scenario decomposition method and we prove its convergence. The method is applied to a risk-averse inventory and assembly problem. In addition, we develop a partially regularized bundle method for nonsmooth optimization. CitationRUTCOR, Rutgers University, Piscataway, NJ 08854ArticleDownload View PDF

    Pattern-Based Modeling and Solution of Probabilistically Constrained Optimization Problems

  • Miguel A. Lejeune
    • Categories Stochastic Programming

    optimization problems in which the random variables are represented by an extremely large number of scenarios. The method involves the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function (pdBf) representing the combination (F,p) of the binarized probability distribution F and the enforced probability level p. We show that … Read more