To develop practical and efficient scenario tree reduction methods, we introduce a new methodology which allows for changing node values, and an easy-to-calculate distance function to measure the difference between two scenario trees. Based on minimizing the new distance, we first construct a primitive scenario tree reduction model which also minimizes the Wasserstein distance between the reduced tree and the initial tree. To make it appropriate for the reduction of general multi-stage scenario trees, we then construct an improved model which not only performs well for the multi-stage scenario tree reduction but also is supported theoretically by the stability results of stochastic programs. Two approximate algorithms are proposed to solve the primitive model. With them, we design a stage-wise scenario tree reduction algorithm which is superior to the simultaneous backward reduction method in terms of computational complexity, the corresponding reduction algorithm especially for fan-liked trees is also presented. We further design a multi-stage scenario tree reduction algorithm with a pre-specified distance by utilizing the stability results of stochastic programs. A series of numerical experiments with real trading data and the application to multi-stage portfolio selection demonstrate the practicality, efficiency and robustness of proposed reduction models and algorithms.
Citation
Research report 3 Department of Computing Science, School of Mathematics and Statistics, Xi'an Jiaotong University, 710049, Xi'an, Shaanxi, P. R. China 3 May, 2016