stochastic programming

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

    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

    Generalized Decision Rule Approximations for Stochastic Programming via Liftings

  • Angelos Georghiou
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Robust Optimization Tags , , ,

    Stochastic programming provides a versatile framework for decision-making under uncertainty, but the resulting optimization problems can be computationally demanding. It has recently been shown that, primal and dual linear decision rule approximations can yield tractable upper and lower bounds on the optimal value of a stochastic program. Unfortunately, linear decision rules often provide crude approximations … Read more

    Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: a Generic Algorithmic Framework

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Data-Mining, Stochastic Programming Tags , , , , ,

    In this paper we present a generic algorithmic framework, namely, the accelerated stochastic approximation (AC-SA) algorithm, for solving strongly convex stochastic composite optimization (SCO) problems. While the classical stochastic approximation (SA) algorithms are asymptotically optimal for solving differentiable and strongly convex problems, the AC-SA algorithm, when employed with proper stepsize policies, can achieve optimal or … Read more

    Multistage Stochastic Portfolio Optimisation in Deregulated Electricity Markets Using Linear Decision Rules

  • Daniel Kuhn
  • Paula Rocha
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , , ,

    The deregulation of electricity markets increases the financial risk faced by retailers who procure electric energy on the spot market to meet their customers’ electricity demand. To hedge against this exposure, retailers often hold a portfolio of electricity derivative contracts. In this paper, we propose a multistage stochastic mean-variance optimisation model for the management of … Read more

    On mixed integer reformulations of monotonic probabilistic programming problems with discrete distributions

  • Vladimir I. Norkin
    • Categories (Mixed) Integer Nonlinear Programming, Finance and Economics, Stochastic Programming Tags , , , , ,

    The paper studies large scale mixed integer reformulation approach to stochastic programming problems containing probability and quantile functions, under assumption of discreteness of the probability distribution involved. Jointly with general sample approximation technique and contemporary mixed integer programming solvers the approach gives a regular framework to solution of practical probabilistic programming problems. In the literature … Read more

    Models and Formulations for Multivariate Dominance Constrained Stochastic Programs

  • Benjamin Armbruster
  • James R. Luedtke
    • Categories Stochastic Programming Tags ,

    Dentcheva and Ruszczynski recently proposed using a stochastic dominance constraint to specify risk preferences in a stochastic program. Such a constraint requires the random outcome resulting from one’s decision to stochastically dominate a given random comparator. These ideas have been extended to problems with multiple random outcomes, using the notion of positive linear stochastic dominance. … Read more

    Risk Adjusted Budget Allocation Models with Application in Homeland Security

  • Tito Homem-de-Mello
  • Jian Hu
  • Sanjay Mehrotra
    • Categories Multi-Criteria Optimization, Robust Optimization, Stochastic Programming Tags , , , , ,

    This paper presents and studies several models for multi-criterion budget allocation problems under uncertainty. We start by introducing a robust weighted objective model, which is developed further using the concept of stochastic dominance to incorporate risk averseness of the decision maker. A budget minimization variant of this model is also presented. We use a Sample … Read more

    A decomposition-based warm-start method for stochastic programming

  • Marco Colombo
  • Andreas Grothey
    • Categories Stochastic Programming Tags , ,

    In this paper we propose a warm-start technique for interior point methods applicable to multi-stage stochastic programming problems. The main idea is to generate an initial point for the interior point solver by decomposing the barrier problem associated with the deterministic equivalent at the sec- ond stage and using a concatenation of the solutions of … Read more