A Distance For Multistage Stochastic Optimization Models
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.
SIAM J. Optim.