Stochastic Programming

A cutting surface algorithm for semi-infinite convex programming with an application to moment robust optimization

  • Sanjay Mehrotra
  • Dávid Papp
    • Categories Robust Optimization, Semi-infinite Programming, Stochastic Programming Tags , , , , , , ,

    We first present and analyze a central cutting surface algorithm for general semi-infinite convex optimization problems, and use it to develop an algorithm for distributionally robust optimization problems in which the uncertainty set consists of probability distributions with given bounds on their moments. The cutting surface algorithm is also applicable to problems with non-differentiable semi-infinite … Read more

    Monte Carlo Sampling-Based Methods for Stochastic Optimization

  • Güzin Bayraksan
  • Tito Homem-de-Mello
    • Categories Optimization of Simulated Systems, Stochastic Programming

    This paper surveys the use of Monte Carlo sampling-based methods for stochastic optimization problems. Such methods are required when—as it often happens in practice—the model involves quantities such as expectations and probabilities that cannot be evaluated exactly. While estimation procedures via sampling are well studied in statistics, the use of such methods in an optimization … Read more

    Kusuoka Representations of Coherent Risk Measures in General Probability Spaces

  • Nilay Noyan
  • Gabor Rudolf
    • Categories Stochastic Programming

    Kusuoka representations provide an important and useful characterization of law invariant coherent risk measures in atomless probability spaces. However, the applicability of these results is limited by the fact that such representations do not always exist in probability spaces with atoms, such as finite probability spaces. We introduce the class of functionally coherent risk measures, … Read more

    Optimal Primal-Dual Methods for a Class of Saddle Point Problems

  • Yunmei Chen
  • Guanghui Lan
  • Yuyuan Ouyang
    • Categories Convex Optimization, Stochastic Programming

    We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPP). The basic idea of this algorithm is to incorporate a multi-step acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence … Read more

    Convergence of trust-region methods based on probabilistic models

  • A. S. Bandeira
  • Katya Scheinberg
  • Luis Nunes Vicente
    • Categories Nonlinear Optimization, Stochastic Programming Tags , , , ,

    In this paper we consider the use of probabilistic or random models within a classical trust-region framework for optimization of deterministic smooth general nonlinear functions. Our method and setting differs from many stochastic optimization approaches in two principal ways. Firstly, we assume that the value of the function itself can be computed without noise, in … Read more

    REDUCTION OF TWO-STAGE PROBABILISTIC OPTIMIZATION PROBLEMS WITH DISCRETE DISTRIBUTION OF RANDOM DATA TO MIXED INTEGER PROGRAMMING PROBLEMS

  • Andrey Kibzun
  • Vladimir I. Norkin
  • Andrey Naumov
    • Categories (Mixed) Integer Nonlinear Programming, Nonsmooth Optimization, Stochastic Programming Tags , , , , ,

    We consider models of two-stage stochastic programming with a quantile second stage criterion and optimization models with a chance constraint on the second stage objective function values. Such models allow to formalize requirements to reliability and safety of the system under consideration, and to optimize the system in extreme conditions. We suggest a method of … Read more

    Tail bounds for stochastic approximation

  • Michael P. Friedlander
  • Gabriel Goh
    • Categories Convex Optimization, Stochastic Programming Tags , , ,

    Stochastic-approximation gradient methods are attractive for large-scale convex optimization because they offer inexpensive iterations. They are especially popular in data-fitting and machine-learning applications where the data arrives in a continuous stream, or it is necessary to minimize large sums of functions. It is known that by appropriately decreasing the variance of the error at each … Read more

    Interdiction Games on Markovian PERT Networks

  • Eli Gutin
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Stochastic Programming Tags , , ,

    In a stochastic interdiction game a proliferator aims to minimize the expected duration of a nuclear weapons development project, while an interdictor endeavors to maximize the project duration by delaying some of the project tasks. We formulate static and dynamic versions of the interdictor’s decision problem where the interdiction plan is either pre-committed or adapts … Read more

    Time (in)consistency of multistage distributionally robust inventory models with moment constraints

  • David A. Goldberg
  • Linwei Xin
    • Categories Stochastic Programming Tags , , , , , , , ,

    Recently, there has been a growing interest in developing inventory control policies which are robust to model misspecification. One approach is to posit that nature selects a worst-case distribution for any relevant stochastic primitives from some pre-specified family. Several communities have observed that a subtle phenomena known as time inconsistency can arise in this framework. … Read more

    On reducing a quantile optimization problem with discrete distribution to a mixed integer programming problem

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

    We suggest a method for equivalent transformation of a quantile optimization problem with discrete distribution of random parameters to mixed integer programming problems. The number of additional integer (in fact boolean) variables in the equivalent problems equals to the number of possible scenarios for random data. The obtained mixed integer problems are solved by standard … Read more