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

    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

    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

    Mean-risk objectives in stochastic programming

  • Shabbir Ahmed
    • Categories Nonsmooth Optimization, Stochastic Programming Tags , , ,

    Traditional stochastic programming is risk neutral in the sense that it is concerned with the optimization of an expectation criteria. A common approach to addressing risk in decision making problems is to consider a weighted mean-risk criterion, where some dispersion statistic is used as a measure of risk. We investigate the computational suitability of various … Read more

    Robust Option Modelling

  • Frank Lutgens
  • Jos F. Sturm
    • Categories Finance and Economics, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    This paper considers robust optimization to cope with uncertainty about the stock return process in one period portfolio selection problems involving options. The ro- bust approach relates portfolio choice to uncertainty, making more cautious portfolios when uncertainty is high. We represent uncertainty by a set of plausible expected returns of the underlyings and show that … Read more

    The Sample Average Approximation Method for Stochastic Programs with Integer Recourse

  • Shabbir Ahmed
  • Alexander Shapiro
    • Categories Integer Programming, Stochastic Approaches, Stochastic Programming Tags , , ,

    This paper develops a solution strategy for two-stage stochastic programs with integer recourse. The proposed methodology relies on approximating the underlying stochastic program via sampling, and solving the approximate problem via a specialized optimization algorithm. We show that the proposed scheme will produce an optimal solution to the true problem with probability approaching one exponentially … Read more

    Statistical inference of multistage stochastic programming problems

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

    We discuss in this paper statistical inference of sample average approximations of multistage stochastic programming problems. We show that any random sampling scheme provides a valid statistical lower bound for the optimal value of the true problem. However, in order for such lower bound to be consistent one needs to employ the conditional sampling procedure. … Read more

    The Empirical Behavior of Sampling Methods for Stochastic Programming

  • Jeff Linderoth
  • Alexander Shapiro
  • Stephen Wright
    • Categories Stochastic Programming Tags , ,

    We investigate the quality of solutions obtained from sample-average approximations to two-stage stochastic linear programs with recourse. We use a recently developed software tool executing on a computational grid to solve many large instances of these problems, allowing us to obtain high-quality solutions and to verify optimality and near-optimality of the computed solutions in various … Read more