Stochastic Programming

Necessary Optimality Conditions for two-stage Stochastic Programs with Equilibrium Constraints

  • Huifu Xu
  • Jane J. Ye
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    Developing first order optimality conditions for a two-stage stochastic mathematical program with equilibrium constraints (SMPEC) whose second stage problem has multiple equilibria/solutions is a challenging undone work. In this paper we take this challenge by considering a general class of two-stage whose equilibrium constraints are represented by a parametric variational inequality (where the first stage … Read more

    On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems

  • Dimitris Bertsimas
  • Vineet Goyal
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    We consider a two-stage mixed integer stochastic optimization problem and show that a static robust solution is a good approximation to the fully-adaptable two-stage solution for the stochastic problem under fairly general assumptions on the uncertainty set and the probability distribution. In particular, we show that if the right hand side of the constraints is … Read more

    Risk-Averse Two-Stage Stochastic Linear Programming: Modeling and Decomposition

  • Naomi Miller
  • Andrzej Ruszczyński
    • Categories Stochastic Programming Tags , ,

    We formulate a risk-averse two-stage stochastic linear programming problem in which unresolved uncertainty remains after the second stage. The objective function is formulated as a composition of conditional risk measures. We analyze properties of the problem and derive necessary and sufficient optimality conditions. Next, we construct two decomposition methods for solving the problem. The first … Read more

    Mixed Zero-one Linear Programs Under Objective Uncertainty: A Completely Positive Representation

  • Karthik Natarajan
  • Chung-Piaw Teo
  • Zhichao Zheng
    • Categories (Mixed) Integer Linear Programming, Semi-definite Programming, Stochastic Programming

    In this paper, we analyze mixed 0-1 linear programs under objective uncertainty. The mean vector and the second moment matrix of the nonnegative objective coefficients is assumed to be known, but the exact form of the distribution is unknown. Our main result shows that computing a tight upper bound on the expected value of a … Read more

    Sample Average Approximation for Stochastic Dominance Constrained Programs

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

    In this paper we study optimization problems with second-order stochastic dominance constraints. This class of problems has been receiving increasing attention in the literature as it allows for the modeling of optimization problems where a risk-averse decision maker wants to ensure that the solution produced by the model dominates certain benchmarks. Here we deal with … Read more

    Convergence and Convergence Rate of Stochastic Gradient Search in the Case of Multiple and Non-Isolated Extrema

  • Vladislav B. Tadic
    • Categories Control Applications, Stochastic Programming Tags , , , , ,

    The asymptotic behavior of stochastic gradient algorithms is studied. Relying on some results of differential geometry (Lojasiewicz gradient inequality), the almost sure point-convergence is demonstrated and relatively tight almost sure bounds on the convergence rate are derived. In sharp contrast to all existing result of this kind, the asymptotic results obtained here do not require … Read more

    A Hierarchy of Bounds for Stochastic Mixed-Integer Programs

  • Nan Kong
  • Burhaneddin Sandikçi
  • Andrew J. Schaefer
    • Categories Stochastic Programming

    Strong relaxations are critical for solving deterministic mixed-integer programs. As solving stochastic mixed-integer programs (SMIPs) is even harder, it is likely that strong relaxations will also prove essential for SMIPs. We consider general two-stage SMIPs with recourse, where integer variables are allowed in both stages of the problem and randomness is allowed in the objective … Read more

    A VaR Black-Litterman Model for the Construction of Absolute Return Fund-of-Funds

  • Miguel A. Lejeune
    • Categories Finance and Economics, Stochastic Programming Tags , , , , , ,

    The objective of this study is to construct fund-of-funds (FoF) that follow an absolute return strategy and meet the requirements imposed by the Value-at-Risk (VaR) market risk measure. We propose the VaR-Black Litterman model which accounts for the VaR and trading (diversification, buy-in threshold, liquidity, currency) requirements. The model takes the form of a probabilistic … Read more

    Stochastic Nash Equilibrium Problems: Sample Average Approximation and Applications

  • Huifu Xu
  • Dali Zhang
    • Categories Game Theory, Nonsmooth Optimization, Stochastic Programming Tags , , ,

    This paper presents a Nash equilibrium model where the underlying objective functions involve uncertainty and nonsmoothness. The well known sample average approximation method is applied to solve the problem and the first order equilibrium conditions are characterized in terms of Clarke generalized gradients. Under some moderate conditions, it is shown that with probability one, a … Read more

    Convergence Rate of Stochastic Gradient Search in the Case of Multiple and Non-Isolated Minima

  • Vladislav B. Tadic
    • Categories Control Applications, Statistics, Stochastic Programming Tags , , , , , , , ,

    The convergence rate of stochastic gradient search is analyzed in this paper. Using arguments based on differential geometry and Lojasiewicz inequalities, tight bounds on the convergence rate of general stochastic gradient algorithms are derived. As opposed to the existing results, the results presented in this paper allow the objective function to have multiple, non-isolated minima, … Read more