Abstract
This paper presents new algorithms for the dynamic generation of scenario trees for multistage stochastic optimization. The different methods described are based on random vectors, which are drawn from conditional distributions given the past and on sample trajectories. The structure of the tree is not determined beforehand, but dynamically adapted to meet a distance criterion, which measures the quality of the approximation. The criterion is built on transportation theory, which is extended to stochastic processes.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
The disjoint union \(\biguplus _{i}V_{i}\) symbolizes that the sets are pairwise disjoint, \(V_{i}\cap V_{j}=\emptyset \), whenever \(i\ne j\).
Generating random vectors can be accomplished by rejection sampling in \({\mathbb {R}}^{m}\), e.g., or by a standard procedure as addressed in the Appendix.
The exponent \(s=3/4\) is a compromise between \(s\le 1\) to obtain \(\sum _{k=1}\frac{1}{k^{s}}=\infty \) and \(s>\frac{1}{2}\) for \(\sum _{k=1}\frac{1}{k^{2s}}<\infty \).
References
Bally, V., Pagès, G., Printems, J.: A quantization tree method for pricing and hedging multidimensional american options. Math. Financ. 15(1), 119–168 (2005)
Beiglböck, M., Goldstern, M., Maresch, G., Schachermayer, W.: Optimal and better transport plans. J. Funct. Anal. 256(6), 1907–1927 (2009)
Brenier, Y.: Décomposition polaire et réarrangement monotone des champs de vecteurs. Comptes Rendus de l’Académie des Sci. Paris Sér. I Math 305(19), 805–808 (1987)
Brenier, Y.: Polar factorization and monotone rearrangement of vector-valued functions. Commun. Pure Appl. Math. 44(4), 375–417 (1991)
Dupačová, J., Gröwe-Kuska, N., Römisch, W.: Scenario reduction in stochastic programming. Math. Program. Ser. A 95(3), 493–511 (2003)
Graf, S., Luschgy, H.: Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics, vol. 1730. Springer-Verlag, Berlin Heidelberg (2000)
Heitsch, H., Römisch, W.: Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. Stoch. Program. 24(2–3), 187–206 (2003)
Heitsch, H., Römisch, W.: A note on scenario reduction for two-stage stochastic programs. Oper. Res. Lett. 6, 731–738 (2007)
Heitsch, H., Römisch, W.: Scenario tree modeling for multistage stochastic programs. Math. Program. Ser. A 118, 371–406 (2009)
Heitsch, H., Römisch, W.: Scenario tree reduction for multistage stochastic programs. Comput. Manag. Sci. 2, 117–133 (2009)
Heitsch, H., Römisch, W.: Stochastic Optimization Methods in Financ eand Energy. Scenario Tree Generation for Multistage Stochastic Programs, chapter 14, pp. 313–341. Springer Verlag, New York (2011)
Hilli, P., Pennanen, T.: Numerical study of discretizations of multistage stochastic programs. Kybernetika 44(2), 185–204 (2008)
Høyland, K., Wallace, S.: Generating scenario trees for multistage decision problems. Manag. Sci. 47(2), 295–307 (2001)
Kaut, M., Wallace, S.W.: Shape-based scenario generation using copulas. Comput. Manag. Sci. 8(1–2), 181–199 (2011)
Küchler, Ch.: On stability of multistage stochastic programs. SIAM J. Optim. 19(2), 952–968 (2008)
Kuhn, D.: Generalized Bounds for Convex Multistage Stochastic Programs. Lecture Notes in Economics and Mathematical Systems. Berlin, DE: Springer (2005)
Kuhn, D.: Aggregation and discretization in multistage stochastic programming. Math. Program. 113(1), 61–94 (2008)
MacQueen, J.: Some methods for classification and analysis of multivariate observations. In Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability. Statistics, vol. 1, pp. 281–29. University of California Press, Berkeley (1967)
Mirkov, R., Pflug, G.Ch.: Tree approximations of dynamic stochastic programs. SIAM J. Optim. 18(3), 1082–1105 (2007)
Pagès, G.: A space quantization method for numerical integration. J. Comput. Appl. Math. 89(1), 1–38 (1998)
Pennanen, T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Program. 116(1–2), 461–479 (2009)
Pennanen, T., Koivu, M.: Epi-convergent discretizations of stochastic programs via integration quadratures. Numerische Mathematik 100, 141–163 (2005)
Pflug, G.Ch.: Optimization of Stochastic Models. The Kluwer International Series in Engineering and Computer Science, vol. 373. Kluwer Academic Publishers, New York (1996)
Pflug, G.Ch.: Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. 89, 251–271 (2001)
Pflug, G.Ch.: Version-independence and nested distribution in multistage stochastic optimization. SIAM J. Optim. 20, 1406–1420 (2009)
Pflug, G.Ch., Pichler, A.: A distance for multistage stochastic optimization models. SIAM J. Optim. 22(1), 1–23 (2012)
Pflug, G.Ch., Pichler, A.: Multistage Stochastic Optimization. Springer, Springer Series in Operations Research and Financial Engineering, New York (2014)
Rachev, S.T.: Probability metrics and the stability of stochastic models. Wiley, West Sussex (1991)
Römisch, W.: Stability of stochastic programming problems. In: Ruszczyński, A., Shapiro, A. (eds.) Stochastic Programming, Handbooks in Operations Research and Management Science, volume 10, chapter 8. Elsevier, Amsterdam (2003)
Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58(1), 57–68 (2003)
Shiryaev, A.N.: Probability. Springer, New York (1996)
Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence, RI (2003)
Williams, D.: Probability with Martingales. Cambridge University Press, Cambridge (1991)
Acknowledgments
We would like to thank two independent referees. Based on their careful reading and precise feedback we were able to improve the presentation and content significantly. Parts of this paper are addressed in our Springer book Multistage Stochastic Optimization [27], which summarizes many more topics in multistage stochastic optimization and which had to be completed before final acceptance of this paper. A. Pichler: The author gratefully acknowledges support of the Research Council of Norway (Grant 207690/E20)
Author information
Authors and Affiliations
Corresponding author
Appendix: Conditional method for multivariate distributions
Appendix: Conditional method for multivariate distributions
To generate instances from a multivariate distribution (random vectors) with cdf \(F\left( z_{1},\ldots z_{m}\right) \) one may employ rejection sampling, or the ratio of uniforms method, or generate the vector component by component by proceeding as follows:
-
(i)
Generate \(Z_{1}\) from \(F_{1}\left( z\right) \), where \(F_{1}(z_{1})=F\left( z_{1},\infty ,\ldots \infty \right) \) is the first marginal. This can be accomplished by solving
$$\begin{aligned} U_{1}=F_{1}(Z_{1}) \end{aligned}$$(the probability integral transform, where \(U_{1}\) is a uniformly distributed random variable) or by rejection sampling;
-
(ii)
Given the random vector up to dimension \(i-1\) one may generate \(Z_{i}\) conditionally on \(\left( Z_{1},\ldots Z_{i-1}\right) \) by solving
$$\begin{aligned} U_{i}=F_{i}\left( z_{i}|\,Z_{1},\ldots Z_{i-1}\right) =\frac{F\left( Z_{1}\ldots ,Z_{i-1},x_{i},\infty ,\ldots \infty \right) }{F\left( Z_{1},\ldots Z_{i-1},\infty ,\ldots \infty \right) }, \end{aligned}$$where \(U_{i}\) is uniformly distributed, and independent from \(U_{1},\ldots U_{i-1}\).
Rights and permissions
About this article
Cite this article
Pflug, G.C., Pichler, A. Dynamic generation of scenario trees. Comput Optim Appl 62, 641–668 (2015). https://doi.org/10.1007/s10589-015-9758-0
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-015-9758-0