Robust Optimization

On Distributionally Robust Multistage Convex Optimization: New Algorithms and Complexity Analysis

  • Xu Andy Sun
  • Shixuan Zhang
    • Categories Dynamic Programming, Robust Optimization, Stochastic Programming

    This paper presents a novel algorithmic study and complexity analysis of distributionally robust multistage convex optimization (DR-MCO). We propose a new class of algorithms for solving DR-MCO, namely a sequential dual dynamic programming (Seq-DDP) algorithm and its nonsequential version (NDDP). The new algorithms generalize and strengthen existing DDP-type algorithms by introducing the technique of regularization … Read more

    A General Framework for Optimal Data-Driven Optimization

  • Daniel Kuhn
  • Tobias Sutter
  • Bart Paul Gerard Van Parys
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    We propose a statistically optimal approach to construct data-driven decisions for stochastic optimization problems. Fundamentally, a data-driven decision is simply a function that maps the available training data to a feasible action. It can always be expressed as the minimizer of a surrogate optimization model constructed from the data. The quality of a data-driven decision … Read more

    Distributionally Robust Two-Stage Stochastic Programming

  • Daniel Duque
  • Sanjay Mehrotra
  • David P. Morton
    • Categories Robust Optimization, Stochastic Programming Tags , , ,

    Distributionally robust optimization is a popular modeling paradigm in which the underlying distribution of the random parameters in a stochastic optimization model is unknown. Therefore, hedging against a range of distributions, properly characterized in an ambiguity set, is of interest. We study two-stage stochastic programs with linear recourse in the context of distributional ambiguity, and … Read more

    Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality

  • Rui Gao
    • Categories Robust Optimization, Statistics, Stochastic Programming Tags , , , ,

    Wasserstein distributionally robust optimization (DRO) aims to find robust and generalizable solutions by hedging against data perturbations in Wasserstein distance. Despite its recent empirical success in operations research and machine learning, existing performance guarantees for generic loss functions are either overly conservative due to the curse of dimensionality, or plausible only in large sample asymptotics. … Read more

    Randomized Assortment Optimization

  • Zhengchao Wang
  • Heikki Peura
  • Wolfram Wiesemann
    • Categories Robust Optimization, Yield Management

    When a firm selects an assortment of products to offer to customers, it uses a choice model to anticipate their probability of purchasing each product. In practice, the estimation of these models is subject to statistical errors, which may lead to significantly suboptimal assortment decisions. Recent work has addressed this issue using robust optimization, where … Read more

    Robust Convex Optimization: A New Perspective That Unifies And Extends

  • Dimitris Bertsimas
  • Dick den Hertog
  • Jean Pauphilet
  • Jianzhe Zhen
    • Categories Convex Optimization, Robust Optimization Tags , , ,

    Robust convex constraints are difficult to handle, since finding the worst-case scenario is equivalent to maximizing a convex function. In this paper, we propose a new approach to deal with such constraints that unifies approaches known in the literature and extends them in a significant way. The extension is either obtaining better solutions than the … Read more

    Global Optimization for the Multilevel European Gas Market System with Nonlinear Flow Models on Trees

  • Lars Schewe
  • Martin Schmidt
  • Johannes Thürauf
    • Categories Applications - OR and Management Sciences, Global Optimization, Robust Optimization Tags , , , ,

    The European gas market is implemented as an entry-exit system, which aims to decouple transport and trading of gas. It has been modeled in the literature as a multilevel problem, which contains a nonlinear flow model of gas physics. Besides the multilevel structure and the nonlinear flow model, the computation of so-called technical capacities is … Read more

    Affinely Adjustable Robust Linear Complementarity Problems

  • Christian Biefel
  • Frauke Liers
  • Martin Schmidt
  • Jan Hendrik Rolfes
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Robust Optimization Tags , , , ,

    Linear complementarity problems are a powerful tool for modeling many practically relevant situations such as market equilibria. They also connect many sub-areas of mathematics like game theory, optimization, and matrix theory. Despite their close relation to optimization, the protection of LCPs against uncertainties – especially in the sense of robust optimization – is still in … Read more

    Statistical Robustness in Utility Preference Robust Optimization Models

  • Shaoyan Guo
  • Huifu Xu
    • Categories Robust Optimization Tags , , ,

    Utility preference robust optimization (PRO) concerns decision making problems where information on decision maker’s utility preference is incomplete and has to be elicited through partial information and the optimal decision is based on the worst case utility function elicited. A key assumption in the PRO models is that the true probability distribution is either known … Read more

    Strong Formulations for Distributionally Robust Chance-Constrained Programs with Left-Hand Side Uncertainty under Wasserstein Ambiguity

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
  • Simge Küçükyavuz
  • Dabeen Lee
    • Categories Robust Optimization, Stochastic Programming Tags , , , ,

    Distributionally robust chance-constrained programs (DR-CCP) over Wasserstein ambiguity sets exhibit attractive out-of-sample performance and admit big-$M$-based mixed-integer programming (MIP) reformulations with conic constraints. However, the resulting formulations often suffer from scalability issues as sample size increases. To address this shortcoming, we derive stronger formulations that scale well with respect to the sample size. Our focus … Read more