Efficient Algorithms for Distributionally Robust Stochastic Optimization with Discrete Scenario Support

Understand

Recently, there has been a growing interest in distributionally robust optimization (DRO) as a principled approach to data-driven decision making.

• In this paper, we consider a distributionally robust two-stage stochastic optimization problem with discrete scenario support.
• While much research effort has been devoted to tractable reformulations for DRO problems, especially those with continuous scenario support, few efficient numerical algorithms were developed, and most of them can neither handle the non-smooth second-stage cost function nor the large number of scenarios $K$ effectively.
• We fill the gap by reformulating the DRO problem as a trilinear min-max-max saddle point problem and developing novel algorithms that can achieve an $\mathcal{O}(1/\epsilon)$ iteration complexity which only mildly depends on $K$.