Data-driven Multistage Distributionally Robust Linear Optimization with Nested Distance
This work addresses a complex optimization problem for researchers and practitioners in operations research and decision-making under uncertainty, offering incremental improvements by reformulating existing frameworks to enhance tractability.
The paper tackles the challenge of solving multistage distributionally robust linear optimization problems with nested distance uncertainty, which are non-convex and difficult to handle. It shows that under mild conditions, robust risk evaluation can be expressed recursively, and with stagewise independence, dynamic programming reformulations yield time-consistent optimal policies, reconciling different modeling frameworks and identifying tractable cases for efficient computation.
We study multistage distributionally robust linear optimization, where the uncertainty set is defined as a ball of distribution centered at a scenario tree using the nested distance. The resulting minimax problem is notoriously difficult to solve due to its inherent non-convexity. In this paper, we demonstrate that, under mild conditions, the robust risk evaluation of a given policy can be expressed in an equivalent recursive form. Furthermore, assuming stagewise independence, we derive equivalent dynamic programming reformulations to find an optimal robust policy that is time-consistent and well-defined on unseen sample paths. Our reformulations reconcile two modeling frameworks: the multistage-static formulation (with nested distance) and the multistage-dynamic formulation (with one-period Wasserstein distance). Moreover, we identify tractable cases when the value functions can be computed efficiently using convex optimization techniques.