Robust sample average approximation

DOI10.1007/S10107-017-1174-ZMaRDI QIDQ1785199zbMATH OpenOpenAlexFDO

Authors Vishal Gupta, Nathan Kallus, Dimitris Bertsimas

Publication date 28 September 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.4445

zbMATH Keywords

multistage optimization polyhedral approximation robust optimization uncertainty

Mathematics Subject Classification ID

Stochastic programming (90C15) Mathematical programming (90C99)

Abstract: Sample average approximation (SAA) is a widely popular approach to data-driven decision-making under uncertainty. Under mild assumptions, SAA is both tractable and enjoys strong asymptotic performance guarantees. Similar guarantees, however, do not typically hold in finite samples. In this paper, we propose a modification of SAA, which we term Robust SAA, which retains SAA's tractability and asymptotic properties and, additionally, enjoys strong finite-sample performance guarantees. The key to our method is linking SAA, distributionally robust optimization, and hypothesis testing of goodness-of-fit. Beyond Robust SAA, this connection provides a unified perspective enabling us to characterize the finite sample and asymptotic guarantees of various other data-driven procedures that are based upon distributionally robust optimization. This analysis provides insight into the practical performance of these various methods in real applications. We present examples from inventory management and portfolio allocation, and demonstrate numerically that our approach outperforms other data-driven approaches in these applications.

Review text

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.

Recommendations

Cites work

Cited in

(69)

Describes a project that uses

Uses Software

This page was built for publication: Robust sample average approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785199)