A distance for multistage stochastic optimization models

Pflug, G.C. ORCID: https://orcid.org/0000-0001-8215-3550 & Pichler, A. (2012). A distance for multistage stochastic optimization models. SIAM Journal on Optimization 22 (1) 1-23. 10.1137/110825054.

Full text not available from this repository.


We describe multistage stochastic programs in a purely in-distribution setting, i.e., without any reference to a concrete probability space. The concept is based on the notion of nested distributions, which encompass in one mathematical object the scenario values as well as the information structure under which decisions have to be made. The nested distance between these distributions is introduced and turns out to be a generalization of the Wasserstein distance for stochastic two-stage problems. We give characterizations of this distance and show its usefulness in examples. The main result states that the difference of the optimal values of two multistage stochastic programs, which are Lipschitz and differ only in the nested distribution of the stochastic parameters, can be bounded by the nested distance of these distributions. This theorem generalizes the well-known Kantorovich-Rubinstein theorem, which is applicable only in two-stage situations, to multistage. Moreover, a dual characterization for the nested distance is established. The setup is applicable both for general stochastic processes and for finite scenario trees. In particular, the nested distance between general processes and scenario trees is well defined and becomes the important tool for judging the quality of the scenario tree generation. Minimizing - at least heuristically - this distance is what good scenario tree generation is all about.

Item Type: Article
Uncontrolled Keywords: Stochastic optimization; Quantitative stability; Transportation distance; Scenario approximation
Research Programs: Risk & Resilience (RISK)
Risk, Policy and Vulnerability (RPV)
Bibliographic Reference: SIAM Journal on Optimization; 22(1):1-23 (Published online 5 January 2012)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 08:46
Last Modified: 27 Aug 2021 17:22
URI: https://pure.iiasa.ac.at/9970

Actions (login required)

View Item View Item