Daniel Kuhn

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

  • Grani A. Hanasusanto
  • Daniel Kuhn
    • Categories Robust Optimization Tags , , ,

    Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust and distributionally robust linear programs can often be reformulated exactly as conic programs that scale polynomially with the problem dimensions. Specifically, … Read more

    Dice-sion Making under Uncertainty: When Can a Random Decision Reduce Risk?

  • Erick Delage
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming

    Stochastic programming and distributionally robust optimization seek deterministic decisions that optimize a risk measure, possibly in view of the most adverse distribution in an ambiguity set. We investigate under which circumstances such deterministic decisions are strictly outperformed by random decisions which depend on a randomization device producing uniformly distributed samples that are independent of all … Read more

    Chebyshev Inequalities for Products of Random Variables

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Wolfram Wiesemann
    • Categories Convex Optimization, Semi-definite Programming Tags , , ,

    We derive sharp probability bounds on the tails of a product of symmetric non-negative random variables using only information about their first two moments. If the covariance matrix of the random variables is known exactly, these bounds can be computed numerically using semidefinite programming. If only an upper bound on the covariance matrix is available, … Read more

    Data-Driven Inverse Optimization with Imperfect Information

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Soroosh Shafieezadeh-Abadeh
    • Categories Linear, Cone and Semidefinite Programming, Robust Optimization, Stochastic Programming Tags , ,

    In data-driven inverse optimization an observer aims to learn the preferences of an agent who solves a parametric optimization problem depending on an exogenous signal. Thus, the observer seeks the agent’s objective function that best explains a historical sequence of signals and corresponding optimal actions. We focus here on situations where the observer has imperfect … Read more

    Ambiguous Joint Chance Constraints under Mean and Dispersion Information

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Vladimir Roitch
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    We study joint chance constraints where the distribution of the uncertain parameters is only known to belong to an ambiguity set characterized by the mean and support of the uncertainties and by an upper bound on their dispersion. This setting gives rise to pessimistic (optimistic) ambiguous chance constraints, which require the corresponding classical chance constraints … Read more

    Distributionally Robust Logistic Regression

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
  • Soroosh Shafieezadeh-Abadeh
    • Categories Robust Optimization, Stochastic Programming Tags , ,

    This paper proposes a distributionally robust approach to logistic regression. We use the Wasserstein distance to construct a ball in the space of probability distributions centered at the uniform distribution on the training samples. If the radius of this ball is chosen judiciously, we can guarantee that it contains the unknown data-generating distribution with high … Read more

    Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations

  • Daniel Kuhn
  • Peyman Mohajerin Esfahani
    • Categories Robust Optimization, Stochastic Programming Tags ,

    We consider stochastic programs where the distribution of the uncertain parameters is only observable through a finite training dataset. Using the Wasserstein metric, we construct a ball in the space of (multivariate and non-discrete) probability distributions centered at the uniform distribution on the training samples, and we seek decisions that perform best in view of … Read more

    K-Adaptability in Two-Stage Distributionally Robust Binary Programming

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Integer Programming, Robust Optimization

    We propose to approximate two-stage distributionally robust programs with binary recourse decisions by their associated K-adaptability problems, which pre-select K candidate second-stage policies here-and-now and implement the best of these policies once the uncertain parameters have been observed. We analyze the approximation quality and the computational complexity of the K-adaptability problem, and we derive explicit … Read more

    A Comment on “Computational Complexity of Stochastic Programming Problems”

  • Grani A. Hanasusanto
  • Daniel Kuhn
  • Wolfram Wiesemann
    • Categories Stochastic Programming

    Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 2006). Amongst others, that paper argues that linear two-stage stochastic programs with fixed recourse are #P-hard even if the random problem data is … Read more

    Robust Growth-Optimal Portfolios

  • Daniel Kuhn
  • Napat Rujeerapaiboon
  • Wolfram Wiesemann
    • Categories Robust Optimization, Stochastic Programming Tags ,

    The growth-optimal portfolio is designed to have maximum expected log-return over the next rebalancing period. Thus, it can be computed with relative ease by solving a static optimization problem. The growth-optimal portfolio has sparked fascination among finance professionals and researchers because it can be shown to outperform any other portfolio with probability 1 in the … Read more