Comparative Analysis of Two-Stage Distributionally Robust Optimization over 1-Wasserstein and 2-Wasserstein Balls

Geunyeong Byeon · 2025

Read Comparative Analysis of Two-Stage Distributionally Robust Optimization over 1-Wasserstein and 2-Wasserstein Balls by Geunyeong Byeon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05619.txt.

Introduction

Geunyeong Byeon compares two flavors of robust optimization under data uncertainty in a 2025 paper. Planners must decide now and adjust later, the two-stage pattern. Robust versions guard against the worst plausible data shift. The guard zone shape, a Wasserstein ball, comes in two common types.

The type one ball shows a pathological quirk in their tests. Type two balls led to better-informed choices in a newsvendor case. A penalty reading suggests type two wins across wider settings. Closed-form solutions make the contrast crisp. Supply and inventory planners face exactly this choice in practice.

Catalog record

CREATORGeunyeong Byeon
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05619

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Comparative Analysis of Two-Stage Distributionally Robust Optimization over 1-Wasserstein and 2-Wasserstein Balls Geunyeong Byeon Abstract This paper investigates advantages of using 2-Wasserstein ambiguity sets over 1-Wasserstein sets in two-stage distributionally robust optimization with right-hand side uncertainty. We examine the worst-case distributions within 1- and 2-Wasserstein balls under both unrestricted and nonnegative orthant supports, highlighting a pathological behavior arising in 1-Wasserstein balls. Closed-form solutions for a single-scenario newsvendor problem illustrate that 2-Wasserstein balls enable more informed decisions. Additionally, a penalty-based dual interpretation suggests that 2-Wasserstein balls may outperform 1-Wasserstein balls across a broader range of Wasserstein radii, even with general support sets. ∎ MSC 90C15 Stochastic Programming 90C25 Convex Programming 90C47 Minimax Problems 1 Introduction Two-stage distributionally robust optimization (TSDRO) seeks an optimal here-and-now decision x\in\mathbb{R}^{n_{x}} that hedges against the worst-case distribution within an ambiguity set of plausible distributions for uncertain parameters \tilde{\xi}\in\mathbb{R}^{k} supported on \Xi . This paper focuses on TSDRO with right-hand side uncertainty, where the ambiguity set is an r -Wasserstein ball of radius \epsilon centered at an empirical distribution \hat{\mathbb{P}}_{N} constructed from N samples, denoted as \mathcal{P}^{r}_{N,\epsilon} . We compare the performance of resulting here-and-now decisions under \mathcal{P}^{1}_{N,\epsilon} and \mathcal{P}^{2}_{N,\epsilon} . 1.1 Problem statement We focus on a class of TSDRO problems in which the first-stage problem is modeled as a mixed-integer conic-linear programming (coneLP) problem and the second-stage problem is posed as a coneLP problem: \displaystyle\min \displaystyle c^{\top}x+\sup_{\mathbb{P}\in\mathcal{P}^{r}_{N,\epsilon}}\mathbb{E}_{\mathbb{P}}[Z(x,\tilde{\xi})] (1) \displaystyle\mbox{s.t.} \displaystyle x\in\mathcal{X}:=\{x\in\mathcal{K}_{x}:x_{i}\in\mathbb{Z},\ \forall i\in\mathcal{I},\ Ax=b\}, where Z(x,\xi):=\inf_{y\in\mathcal{K}_{y}}\left\{q^{\top}y:Wy\geq Tx+\xi\right\} (2) evaluates the second-stage cost by optimizing a wait-and-see decision y given x and an outcome \xi of the uncertain vector \tilde{\xi} . Positive integers n_{x} , n_{y} , and k respectively denote the dimensions of x , y , and \tilde{\xi} . The sets \mathcal{K}_{x}\subseteq\mathbb{R}^{n_{x}} and \mathcal{K}_{y}\subseteq\mathbb{R}^{n_{y}} represent Cartesian products of some collections of proper cones (e.g., second-order cones, nonnegative orthants, and vectorized positive semidefinite cones). The set \mathcal{X} defines the feasible region of x , where a subvector (x_{i})_{i\in\mathcal{I}} may be integer-valued. The parameters c,b,q,A,W and T are vectors and matrices with suitable dimensions. Given N samples \zeta^{1},\cdots,\zeta^{N}\in\Xi of \tilde{\xi} , we let \hat{\mathbb{P}}_{N} denote the empirical distribution \hat{\mathbb{P}}_{N}:=\frac{1}{N}\sum^{N}_{i=1}{\delta}_{\zeta^{i}} , where {\delta}_{\zeta^{i}} denotes the Dirac measure whose unit mass is concentrated on \{\zeta^{i}\} . The ambiguity set \mathcal{P}^{r}_{N,\epsilon} is given by \mathcal{P}^{r}_{N,\epsilon}:=\{\mathbb{Q}\in\mathcal{P}^{r}(\Xi):W^{r}(\mathbb{Q},\hat{\mathbb{P}}_{N})\leq{\epsilon}\}, where {\mathcal{P}^{r}(\Xi)} denotes the collection of all probability distributions \mathbb{Q} on (\Xi,\mathcal{B}(\Xi)) with a finite r th moment, and \mathcal{B}(\Xi) is the Borel \sigma -algebra of subsets of \Xi . The r -Wasserstein distance W^{r} between distributions \mathbb{Q}_{1},\mathbb{Q}_{2}\in\mathcal{P}^{r}(\Xi) is defined as W^{r}(\mathbb{Q}_{1},\mathbb{Q}_{2}):=\inf_{\gamma\in\Gamma(\mathbb{Q}_{1},\mathbb{Q}_{2})}\left\{\left(\int_{\Xi\times\Xi}\|\xi_{1}-\xi_{2}\|^{r}\,\mathrm{d}\gamma(\xi_{1},\xi_{2})\right)^{1/r}\right\}, where \Gamma(\mathbb{Q}_{1},\mathbb{Q}_{2}) denotes the collection of all probability distributions on the product space (\Xi\times\Xi,\mathcal{B}(\Xi)\otimes\mathcal{B}(\Xi)) with marginals \mathbb{Q}_{1} and \mathbb{Q}_{2} , respectively, and \|\cdot\| is an l_{p} -norm in \mathbb{R}^{k} for some p\in[1,\infty] . TSDRO provides an alternative to sample average approximation (SAA) and robust optimization (RO), determined by the Wasserstein radius \epsilon>0 . Let \tilde{x}^{r}_{N}(\epsilon) denote the random optimal solution of ( 1 ), with randomness arising from sampling for \hat{\mathbb{P}}_{N} . When \epsilon=0 , the Wasserstein ambiguity set reduces to \mathcal{P}^{r}_{N,0}=\{\hat{\mathbb{P}}_{N}\} . In this case, we denote the corresponding solution by \tilde{x}^{\texttt{SAA}}_{N} . Additionally, let \mathcal{X}_{\texttt{RO}}:=\arg\inf_{x\in\mathcal{X}}c^{\top}x+\sup_{\xi\in\Xi}Z(x,\xi) denote the set of robust optimization solutions. We define \tilde{O}^{r}_{N}(\epsilon) as the true expected cost of the solution obtained by TSDRO over \mathcal{P}^{r}_{N,\epsilon} , that is \tilde{O}^{r}_{N}(\epsilon):=c^{\top}\tilde{x}^{r}_{N}(\epsilon)+\mathbb{E}_{\tilde{\xi}\sim\mathbb{P}^{\texttt{true}}}[Z(\tilde{x}^{r}_{N}(\epsilon),\tilde{\xi})] . When \epsilon=0 , this value corresponds to the out-of-sample performance of the SAA solution. If {\mathcal{X}}_{\texttt{RO}}\neq\emptyset , then as \epsilon\rightarrow\infty , \tilde{O}^{r}_{N}(\epsilon) converges to the out-of-sample performance of RO. 1.2 Motivating example (a) p1 (b) p21 (c) p43 (d) Figure 1 : (a)-(c): The median values (line) and the 10th to 90th percentiles (shaded region) of \tilde{O}^{r}_{5}(\epsilon) , where the expectation is estimated using 2,000 testing samples drawn from \mathbb{P}^{\texttt{true}} . (d): \mathbb{P}[\tilde{O}^{2}_{5}(\epsilon)\leq\tilde{O}^{1}_{5}(\epsilon)\times 1.001] . For each choice of \epsilon , \tilde{O}^{r}_{5}(\epsilon) is simulated over 20 runs Figure 1 presents a notable observation from three facility location problem instances—Holmberg instances p1 , p21 , and p43 [ 10 ] —using the experimental setup described in [ 3 ] , where p=2 is used for the r=2 case and p=1 for the r=1 case to ensure comparability on the same scale. The results reveal that \tilde{O}^{2}_{5}(\epsilon) has a lower or equal median across all tested \epsilon values compared to \tilde{O}^{1}_{5}(\epsilon) . As shown in the figure, \tilde{x}^{1}_{5}(\epsilon) provides alternative solutions to both SAA and RO over a narrow range of \epsilon -values. It initially aligns with the SAA solution, then undergoes a sharp decline, and promptly converges to some x^{\texttt{RO}}\in\mathcal{X}_{\texttt{RO}} . In contrast, \tilde{x}^{2}_{5}(\epsilon) exhibits a smoother transition from \tilde{x}^{\texttt{SAA}}_{5} as soon as \epsilon is greater than zero and then converges to a RO solution at larger \epsilon -values than \tilde{x}^{1}_{5}(\epsilon) . Furthermore, \tilde{O}^{2}_{5}(\epsilon) empirically demonstrates zeroth-order dominance over \tilde{O}^{1}_{5}(\epsilon) across a wide range of \epsilon -values. Specifically, this dominance is observed for values of \epsilon where \mathbb{P}[\tilde{O}^{2}_{5}(\epsilon)\leq\tilde{O}^{1}_{5}(\epsilon)\times 1.001]=1 (see Figure 1(d) ). This paper aims to investigate the underlying reasons for this behavior. 1.3 Related Literature TSDRO with right-hand side uncertainty over 1- and 2-Wasserstein ambiguity sets has been extensively studied in the literature [ 9 , 5 , 13 , 6 , 4 , 3 , 11 , 8 ] . However, there is limited research comparing their out-of-sample performances. The most relevant work is [ 7 ] , which provides performance guarantees for r=1 and r=2 . These results, especially for r=2 , however, rely on the differentiability of Z(x,\cdot) , a condition that typically does not hold in our setting. 1.4 Contributions To the best of the author’s knowledge, this is the first paper to demonstrate the potential advantages of 2-Wasserstein balls over 1-Wasserstein balls in the TSDRO context. For \Xi=\mathbb{R}^{k} or \mathbb{R}^{k}_{+} , we derive the worst-case distributions in \mathcal{P}^{1}_{N,\epsilon} and \mathcal{P}^{2}_{N,\epsilon} , highlighting an undesirable property of \mathcal{P}^{1}_{N,\epsilon} that does not appear in \mathcal{P}^{2}_{N,\epsilon} . This characterization provides closed-form solutions to a distributionally robust newsvendor problem with a single scenario aunder both \mathcal{P}^{1}_{N,\epsilon} and \mathcal{P}^{2}_{N,\epsilon} , suggesting that \tilde{x}^{2}_{N}(\epsilon) is better informed than \tilde{x}^{1}_{N}(\epsilon) ; specifically, unlike \tilde{x}^{1}_{N}(\epsilon) , \tilde{x}^{2}_{N}(\epsilon) accounts for both the critical fractile and the Wasserstein radius \epsilon . Through a penalty-based interpretation of the dual worst-case expectation problem, we further reveal the superior out-of-sample performance of 2-Wasserstein balls for general \Xi , which offer a wider range of radii yielding solutions that outperform SAA and RO, aligning with the observation in Figure 1 . 1.5 Notation Throughout this paper, let q be a scalar such that 1/p+1/q=1 , ensuring \|\cdot\|_{q} is the dual norm of \|\cdot\| . For an integer n , define [n]:=\{1,\cdots,n\} and let \mathbb{R}^{n}_{+} represent the n -dimensional nonnegative orthant. For a set \mathcal{K}\subseteq\mathbb{R}^{n} , \mathcal{K}^{*} denotes its dual cone, that is, \mathcal{K}^{*}=\{y\in\mathbb{R}^{n}:y^{T}x\geq 0,\ \forall x\in\mathcal{K}\} , and \mbox{recc}(\mathcal{K}) represents the recession cone of \mathcal{K} , that is \mbox{recc}(\mathcal{K})=\{\vec{u}\in\mathbb{R}^{n}:\forall u\in\mathcal{K},u+\alpha\vec{u}\in\mathcal{K},\ \forall\alpha\in\mathbb{R}_{+}\} . For a proper cone \mathcal{K} , \preceq_{\mathcal{K}} denotes the generalized inequality defined by \mathcal{K} , i.e., x\preceq_{\mathcal{K}}y\Leftrightarrow y-x\in\mathcal{K} . For a vector v\in\mathbb{R}^{k} and a scalar a , v^{a} denotes the componentwise exponentiation of v with exponent a , i.e., v^{a}=(v_{j}^{a})_{j\in[k]} , and |v| denotes the componentwise absolutization of v , that is, |v|=(|v_{j}|)_{j\in[k]} . 2 Preliminaries and assumptions The dual of ( 2 ) is given as \max_{\pi\geq 0}\left\{(Tx+\xi)^{\top}\pi:W^{\top}\pi\preceq_{\mathcal{K}_{y}^{*}}q\right\}. We let \Pi

Read the complete text