Optimization Online


Tractable Reformulations of Distributionally Robust Two-stage Stochastic Programs with $\infty-$Wasserstein Distance

Weijun Xie (wxie***at***vt.edu)

Abstract: In the optimization under uncertainty, decision-makers first select a wait-and-see policy before any realization of uncertainty and then place a here-and-now decision after the uncertainty has been observed. Two-stage stochastic programming is a popular modeling paradigm for the optimization under uncertainty that the decision-makers first specifies a probability distribution, and then seek the best decisions to jointly optimize the deterministic wait-and-see and expected here-and-now costs. In practice, such a probability distribution may not be fully available but is probably observable through an empirical dataset. Therefore, this paper studies distributionally robust two-stage stochastic program (DRTSP) which jointly optimizes the deterministic wait-and-see and worst-case expected here-and-now costs, and the probability distribution comes from a family of distributions which are centered at the empirical distribution using $\infty-$Wasserstein metric. There have been successful developments on deriving tractable approximations of the worst-case expected here-and-now cost in DRTSP. Unfortunately, limited results on exact tractable reformulations of DRTSP. This paper fills this gap by providing sufficient conditions under which the worst-case expected here-and-now cost in DRTSP can be efficiently computed via a tractable convex program. By exploring the properties of binary variables, the developed reformulation techniques are extended to DRTSP with binary random parameters. The main tractable reformulations in this paper are projected into the original decision space and thus can be interpreted as conventional two-stage stochastic programs under discrete support with extra penalty terms enforcing the robustness. These tractable results are further demonstrated to be sharp through complexity analysis.

Keywords: Distributionally Robust, Two-stage, Stochastic Program, Tractable, Reformulation.

Category 1: Stochastic Programming


Download: [PDF]

Entry Submitted: 08/20/2019
Entry Accepted: 08/21/2019
Entry Last Modified: 07/18/2020

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