Discrete Approximation and Quantification in Distributionally Robust Optimization

Discrete approximation of probability distributions is an important topic in stochastic programming. In this paper, we extend the research on this topic to distributionally robust optimization (DRO), where discretization is driven by either limited availability of empirical data (samples) or a computational need for improving numerical tractability. We start with a one-stage DRO where the ambiguity set is defined by generalized prior moment conditions and quantify the discrepancy between the discretized ambiguity set and the original one by employing the Kantorovich/Wasserstein metric. The quantification is achieved by establishing a new form of Hoffman’s lemma for moment problems under a general class of metrics—namely, ζ -structures. We then investigate how the discrepancy propagates to the optimal value in one-stage DRO and discuss further the multistage DRO under nested distance. The technical results lay down a theoretical foundation for various discrete approximation schemes to be applied to solve one-stage and multistage distributionally robust optimization problems.