Technical Note-Two-Stage Sample Robust Optimization

• 成果类型: Article
• 署名作者: Bertsimas, Dimitris; Shtern, Shimrit; Sturt, Bradley
• 署名单位: Massachusetts Institute of Technology (MIT); Technion Israel Institute of Technology; University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2020.2096
• 发表日期: 2022
• 页码: 624-640
• 关键词: stochastic programming; distributionally robust optimization; sample average approximation

摘要

We investigate a simple approximation scheme, based on overlapping linear decision rules, for solving data-driven two-stage distributionally robust optimization problems with the type-infinity Wasserstein ambiguity set. Our main result establishes that this approximation scheme is asymptotically optimal for two-stage stochastic linear optimization problems; that is, under mild assumptions, the optimal cost and optimal first-stage decisions obtained by approximating the robust optimization problem converge to those of the underlying stochastic problem as the number of data points grows to infinity. These guarantees notably apply to two-stage stochastic problems that do not have relatively complete recourse, which arise frequently in applications. In this context, we show through numerical experiments that the approximation scheme is practically tractable and produces decisions that significantly outperform those obtained from state-of-the-art data driven alternatives.