Optimization Online


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

Grani A. Hanasusanto (grani.hanasusanto***at***utexas.edu)
Daniel Kuhn (daniel.kuhn***at***epfl.ch)

Abstract: 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, when the ambiguity set constitutes a 2-Wasserstein ball centered at a discrete distribution, then the distributionally robust linear program is equivalent to a copositive program (if the problem has complete recourse) or can be approximated arbitrarily closely by a sequence of copositive programs (if the problem has sufficiently expensive recourse). These results directly extend to the classical robust setting and motivate strong tractable approximations of two-stage problems based on semidefinite approximations of the copositive cone. We also demonstrate that the two-stage distributionally robust optimization problem is equivalent to a tractable linear program when the ambiguity set constitutes a 1-Wasserstein ball centered at a discrete distribution and there are no support constraints.

Keywords: two-stage problems, robust optimization, distributionally robust optimization, copositive programming

Category 1: Robust Optimization


Download: [PDF]

Entry Submitted: 09/23/2016
Entry Accepted: 09/23/2016
Entry Last Modified: 07/14/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society