Robust sample average approximation (Q1785199)

Considered is the following stochastic optimization problem \[ z_{\text{stoch}}=\min_{x\in X}\mathbb{E}_{F}\left[ c\left( x;\xi \right) \right],\tag{1} \] where \(c\left( x;\xi \right) \) is a given cost function depending on a random vector \(\xi \) following distribution \(F\) and a decision variable \( x\in X\subseteq \mathbb{R}^{d_{x}}\). In real-world applications, the distribution \(F\) is unknown. Rather are given data \(\xi ^{1},\dots,\xi ^{N}\), which are typically assumed to be drawn IID from \(F\). The most common approach in these settings is the sample average approximation (SAA). SAA approximates the true, unknown distribution \(F\) by the empirical distribution \(\hat{F}_{N}\), which places \(1/N\) mass at each of the data points. In this paper, the authors propose a modification of SAA, termed robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key idea of robust SAA is to approximate (1) by a particular data-driven distributionally robust optimization (DRO) problem using ideas from statistical hypothesis testing. The authors develop new connections between the SAA, DRO problem and statistically hypothesis testing. They prove that robust SAA yields tractable optimization problems that are solvable in polynomial time for a wide class of cost functions. They present examples from inventory management and portfolio allocation, and demonstrate numerically that their approach outperforms other data driven approaches in these applications. Finally, they show how robust SAA can be used to obtain approximations to the ``price of data'' -- the price one would be willing to pay in a data-driven setting for additional data.