Stochastic Programming

Importance Sampling in Stochastic Programming: A Markov Chain Monte Carlo Approach

  • Ustun Berk
  • Webster Mort
  • Panos Parpas
  • Quang Kha Tran
    • Categories Stochastic Programming Tags , , , ,

    Stochastic programming models are large-scale optimization problems that are used to facilitate decision-making under uncertainty. Optimization algorithms for such problems need to evaluate the expected future costs of current decisions, often referred to as the recourse function. In practice, this calculation is computationally difficult as it requires the evaluation of a multidimensional integral whose integrand … Read more

    Bounds for nested law invariant coherent risk measures

  • Alexander Shapiro
  • Linwei Xin
    • Categories Dynamic Programming, Stochastic Programming Tags , , , ,

    With every law invariant coherent risk measure is associated its conditional analogue. In this paper we discuss lower and upper bounds for the corresponding nested (composite) formulations of law invariant coherent risk measures. In particular, we consider the Average Value-at-Risk and comonotonic risk measures. ArticleDownload View PDF

    Multi-horizon stochastic programming

  • Marte Fodstad
  • Michal Kaut
  • Lars Hellemo
  • Kjetil T. Midthun
  • Asgeir Tomasgard
  • Adrian S. Werner
    • Categories Stochastic Programming Tags , , ,

    Infrastructure-planning models are challenging because of their combination of different time scales: while planning and building the infrastructure involves strategic decisions with time horizons of many years, one needs an operational time scale to get a proper picture of the infrastructure’s performance and profitability. In addition, both the strategic and operational levels are typically subject … Read more

    Stochastic optimization and sparse statistical recovery: An optimal algorithm for high dimensions

  • Alekh Agarwal
  • Martin J Wainwright
  • Sahand Negahban
    • Categories Convex Optimization, Stochastic Programming Tags , ,

    We develop and analyze stochastic optimization algorithms for problems in which the expected loss is strongly convex, and the optimum is (approximately) sparse. Previous approaches are able to exploit only one of these two structures, yielding an $\order(\pdim/T)$ convergence rate for strongly convex objectives in $\pdim$ dimensions, and an $\order(\sqrt{(\spindex \log \pdim)/T})$ convergence rate when … Read more

    A note on the convergence of the SDDP algorithm

  • Kengy Barty
    • Categories Dynamic Programming, Stochastic Programming Tags ,

    In this paper we are interested in the convergence analysis of the Stochastic Dual Dynamic Algorithm (SDDP) algorithm in a general framework, and regardless of whether the underlying probability space is discrete or not. We consider a convex stochastic control program not necessarily linear and the resulting dynamic programming equation. We prove under mild assumptions … Read more

    Improving the Performance of Stochastic Dual Dynamic Programming

  • Vitor de Matos
  • Erlon Finardi
  • Andrew B. Philpott
    • Categories Scheduling, Stochastic Programming

    This paper is concerned with tuning the Stochastic Dual Dynamic Programming algorithm to make it more computationally efficient. We report the results of some computational experiments on a large-scale hydrothermal scheduling model developed for Brazil. We find that the best improvements in computation time are obtained from an implementation that increases the number of scenarios … Read more

    Robust Decision Making using a General Utility Set

  • Manish Bansal
  • Jian Hu
  • Sanjay Mehrotra
    • Categories Finance and Economics, Robust Optimization, Stochastic Programming Tags , , ,

    We develop the concept of utility robustness to address the problem of ambiguity and inconsistency in utility assessments. A robust decision-making framework is built on a utility set which characterizes a decision maker’s risk attitude described by boundary and auxiliary conditions. This framework is studied using the Sample Average Approximation (SAA) approach. We show the … Read more

    Data-driven Chance Constrained Stochastic Program

  • Yongpei Guan
  • Ruiwei Jiang
    • Categories Semi-definite Programming, Semi-infinite Programming, Stochastic Programming

    Chance constrained programming is an effective and convenient approach to control risk in decision making under uncertainty. However, due to unknown probability distributions of random parameters, the solution obtained from a chance constrained optimization problem can be biased. In practice, instead of knowing the true distribution of a random parameter, only a series of historical … Read more

    Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization, II: Shrinking Procedures and Optimal Algorithms

  • Saeed Ghadimi
  • Guanghui Lan
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    In this paper we study new stochastic approximation (SA) type algorithms, namely, the accelerated SA (AC-SA), for solving strongly convex stochastic composite optimization (SCO) problems. Specifically, by introducing a domain shrinking procedure, we significantly improve the large-deviation results associated with the convergence rate of a nearly optimal AC-SA algorithm presented by the authors. Moreover, we … Read more

    A new Search via Probability Algorithm for solving Engineering Optimization Problems

  • Nguyen Huu Thong
    • Categories Applications - Science and Engineering, Global Optimization, Stochastic Programming Tags , , ,

    The Search Algorithms have been introduced in the paper [3][6] under the name ‘Search via Probability Algorithm’. These optimization techniques converge very fast and are very efficient for solving optimization problems with very large scale feasible domains. But these optimization techniques are not effective in solving the numerical optimization problems with long narrow feasible domains. … Read more