Robust Optimization

Piecewise constant decision rules via branch-and-bound based scenario detection for integer adjustable robust optimization

  • Krzysztof Postek
  • Ward Romeijnders
    • Categories Integer Programming, Robust Optimization

    Multi-stage problems with uncertain parameters and integer decisions variables are among the most difficult applications of robust optimization (RO). The challenge in these problems is to find optimal here-and-now decisions, taking into account that the wait-and-see decisions have to adapt to the revealed values of the uncertain parameters. Postek and den Hertog (2016) and Bertsimas … Read more

    Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimator

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Viet Anh Nguyen
    • Categories Convex Optimization, Robust Optimization Tags , ,

    We introduce a distributionally robust maximum likelihood estimation model with a Wasserstein ambiguity set to infer the inverse covariance matrix of a p-dimensional Gaussian random vector from n independent samples. The proposed model minimizes the worst case (maximum) of Stein’s loss across all normal reference distributions within a prescribed Wasserstein distance from the normal distribution … Read more

    Distributionally robust optimization with polynomial densities: theory, models and algorithms

  • Etienne de Klerk
  • Daniel Kuhn
  • Krzysztof Postek
    • Categories Robust Optimization, Semi-definite Programming Tags , , ,

    In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distribution that give nature too much … Read more

    Robust-to-Dynamics Optimization

  • Amir Ali Ahmadi
  • Oktay Gunluk
    • Categories Convex Optimization, Robust Optimization, Semi-infinite Programming Tags , , ,

    A robust-to-dynamics optimization (RDO) problem} is an optimization problem specified by two pieces of input: (i) a mathematical program (an objective function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ and a feasible set $\Omega\subseteq\mathbb{R}^n$), and (ii) a dynamical system (a map $g:\mathbb{R}^n\rightarrow\mathbb{R}^n$). Its goal is to minimize $f$ over the set $\mathcal{S}\subseteq\Omega$ of initial conditions that forever remain in $\Omega$ under … Read more

    Shortfall Risk Models When Information of Loss Function Is Incomplete

  • Erick Delage
  • Shaoyan Guo
  • Huifu Xu
    • Categories Linear Programming, Robust Optimization, Stochastic Programming Tags , , , , , ,

    Utility-based shortfall risk measure (SR) has received increasing attentions over the past few years for its potential to quantify more effectively the risk of large losses than conditional value at risk. In this paper we consider the case that the true loss function is unavailable either because it is difficult to be identified or the … Read more

    Trust your data or not – StQP remains StQP: Community Detection via Robust Standard Quadratic Optimization

  • Immanuel M. Bomze
  • Michael Kahr
  • Markus Leitner
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Robust Optimization Tags , , , ,

    We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more

    Monitoring With Limited Information

  • Dan Iancu
  • Nikolaos Trichakis
  • Do Young Yoon
    • Categories Applications - OR and Management Sciences, Dynamic Programming, Robust Optimization Tags , , ,

    We consider a system with an evolving state that can be stopped at any time by a decision maker (DM), yielding a state-dependent reward. The DM does not observe the state except for a limited number of monitoring times, which he must choose, in conjunction with a suitable stopping policy, to maximize his reward. Dealing … Read more

    An Active Set Algorithm for Robust Combinatorial Optimization Based on Separation Oracles

  • Christoph Buchheim
  • Marianna De Santis
    • Categories Combinatorial Optimization, Global Optimization, Robust Optimization Tags , ,

    We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the … Read more

    Robust Principal Component Analysis using Facial Reduction

  • Shiqian Ma
  • Linchuan Wei
  • Henry Wolkowicz
  • Fei Wang
    • Categories Data-Mining, Linear, Cone and Semidefinite Programming, Robust Optimization Tags , , ,

    We study algorithms for robust principal component analysis (RPCA) for a partially observed data matrix. The aim is to recover the data matrix as a sum of a low-rank matrix and a sparse matrix so as to eliminate erratic noise (outliers). This problem is known to be NP-hard in general. A classical way to solve … Read more

    Data-DrivenWater Allocation under Climate Uncertainty: A Distributionally Robust Approach

  • Güzin Bayraksan
  • David Love
  • Jangho Park
    • Categories Civil and Environmental Engineering, Robust Optimization, Stochastic Programming Tags , , , ,

    This paper investigates the application of techniques from distributionally robust optimization (DRO) to water allocation under future uncertainty. Specifically, we look at a rapidly-developing area of Tucson, Arizona. Tucson, like many arid and semi-arid regions around the world, faces considerable uncertainty in its ability to provide water for its citizens in the future. The main … Read more