×

Are quasi-Monte Carlo algorithms efficient for two-stage stochastic programs? (English) Zbl 1384.90067

Summary: Quasi-Monte Carlo algorithms are studied for designing discrete approximations of two-stage linear stochastic programs with random right-hand side and continuous probability distribution. The latter should allow for a transformation to a distribution with independent marginals. The two-stage integrands are piecewise linear, but neither smooth nor lie in the function spaces considered for QMC error analysis. We show that under some weak geometric condition on the two-stage model all terms of their ANOVA decomposition, except the one of highest order, are continuously differentiable and that first and second order ANOVA terms have mixed first order partial derivatives and belong to \(L_2\). Hence, randomly shifted lattice rules (SLR) may achieve the optimal rate of convergence \(O(n^{-1+\delta})\) with \(\delta\in (0,\frac{1}{2}]\) and a constant not depending on the dimension if the effective superposition dimension is at most two. We discuss effective dimensions and dimension reduction for two-stage integrands. The geometric condition is shown to be satisfied almost everywhere if the underlying probability distribution is normal and principal component analysis (PCA) is used for transforming the covariance matrix. Numerical experiments for a large scale two-stage stochastic production planning model with normal demand show that indeed convergence rates close to the optimal are achieved when using SLR and randomly scrambled Sobol’ point sets accompanied with PCA for dimension reduction.

MSC:

90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Baldeaux, J.: Higher order nets and sequences, PhD Thesis, The University of New South Wales, Sydney (2010) · Zbl 1149.65303
[2] Brockwell, P.J., Davis, R.A.: Introduction to Time Series and Forecasting, 2nd edn. Springer, New York (2002) · Zbl 0994.62085 · doi:10.1007/b97391
[3] Dick, J., Sloan, I.H., Wang, X., Woźniakowski, H.: Liberating the weights. J. Complex. 20, 593-623 (2004) · Zbl 1089.65005 · doi:10.1016/j.jco.2003.06.002
[4] Dick, J.: Walsh spaces containing smooth functions and Quasi-Monte Carlo rules of arbitrary high order. SIAM J. Numer. Anal. 46, 1519-1553 (2008) · Zbl 1189.42012 · doi:10.1137/060666639
[5] Dick, J., Pillichshammer, F.: Digital Nets and Sequences. Cambridge University Press, Cambridge (2010) · Zbl 1282.65012 · doi:10.1017/CBO9780511761188
[6] Dick, J., Kuo, F.Y., Sloan, I.H.: High-dimensional integration—the Quasi-Monte Carlo way. Acta Numerica 22, 133-288 (2013) · Zbl 1296.65004 · doi:10.1017/S0962492913000044
[7] Drew, S.S., Homem-de-Mello, T.: Quasi-Monte Carlo strategies for stochastic optimization. Proceedings of the 2006 Winter Simulation Conference. IEEE, Piscataway (2006) · Zbl 1025.65010
[8] Dudley, R.M.: The speed of mean Glivenko-Cantelli convergence. Ann. Math. Stat. 40, 40-50 (1969) · Zbl 0184.41401 · doi:10.1214/aoms/1177697802
[9] Eichhorn, A., Römisch, W., Wegner, I.: Mean-risk optimization of electricity portfolios using multiperiod polyhedral risk measures. IEEE St. Petersburg Power Tech (2005) · Zbl 1354.91172
[10] Evans, L.C., Gariepy, R.F.: Measure Theory and Fine Properties of Functions. CRC Press, Boca Raton (1992) · Zbl 0804.28001
[11] Glasserman, P.: Monte-Carlo Methods in Financial Engineering. Springer, New York (2003) · Zbl 1038.91045 · doi:10.1007/978-0-387-21617-1
[12] Graf, S., Luschgy, H.: Foundations of Quantization for Probability Distributions. Lecture Notes in Mathematics, vol. 1730. Springer, Berlin (2000) · Zbl 0951.60003
[13] Griebel, M., Holtz, M.: Dimension-wise integration of high-dimensional functions with applications to finance. J. Complex. 26, 455-489 (2010) · Zbl 1203.65056 · doi:10.1016/j.jco.2010.06.001
[14] Griebel, M., Kuo, F.Y., Sloan, I.H.: The smoothing effect of the ANOVA decomposition. J. Complex. 26, 523-551 (2010) · Zbl 1205.65017 · doi:10.1016/j.jco.2010.04.003
[15] Griebel, M., Kuo, F.Y., Sloan, I.H.: The smoothing effect of integration in \[{\mathbb{R}}^d\] Rd and the ANOVA decomposition. Math. Comput. 82, 383-400 (2013) · Zbl 1264.41030 · doi:10.1090/S0025-5718-2012-02578-6
[16] Hickernell, F.J.: A generalized discrepancy and quadrature error bound. Math. Comput. 67, 299-322 (1998) · Zbl 0889.41025 · doi:10.1090/S0025-5718-98-00894-1
[17] Hickernell, FJ; Fang, K-T (ed.); Hickernell, FJ (ed.); Niederreiter, H. (ed.), Obtaining \[O(N^{-2 +\epsilon })O(N-2\]+ϵ) convergence for lattice quadrature rules, 274-289 (2002), Berlin · Zbl 1002.65009 · doi:10.1007/978-3-642-56046-0_18
[18] Hoeffding, W.: A class of statistics with asymptotically normal distribution. Ann. Math. Stat. 19, 293-325 (1948) · Zbl 0032.04101 · doi:10.1214/aoms/1177730196
[19] Homem-de-Mello, T.: On rates of convergence for stochastic optimization problems under non-i.i.d. sampling. SIAM J. Optim. 19, 524-551 (2008) · Zbl 1171.90486 · doi:10.1137/060657418
[20] Hong, H.S., Hickernell, F.J.: Algorithm 823: Implementing scrambled digital sequences. ACM Trans. Math. Softw. 29, 95-109 (2003) · Zbl 1068.11049 · doi:10.1145/779359.779360
[21] Imai, J.; Tan, KS; Niederreiter, H. (ed.), Minimizing effective dimension using linear transformation, 275-292 (2004), Berlin · Zbl 1043.65003
[22] Joe, S., Kuo, F.Y.: Remark on Algorithm 659: Implementing Sobol’s quasirandom sequence generator. ACM Trans. Math. Softw. 29, 49-57 (2003) · Zbl 1070.65501 · doi:10.1145/641876.641879
[23] Koivu, M.: Variance reduction in sample approximations of stochastic programs. Math. Program. 103, 463-485 (2005) · Zbl 1099.90036 · doi:10.1007/s10107-004-0557-0
[24] Kuo, F.Y.: Component-by-component constructions achieve the optimal rate of convergence in weighted Korobov and Sobolev spaces. J. Complex. 19, 301-320 (2003) · Zbl 1027.41031 · doi:10.1016/S0885-064X(03)00006-2
[25] Kuo, F.Y., Schwab, Ch., Sloan, I.H.: Quasi-Monte Carlo methods for high-dimensional integration: the standard (weighted Hilbert space) setting and beyond. ANZIAM J. 53, 1-37 (2011) · Zbl 1248.65001 · doi:10.1017/S1446181112000077
[26] Kuo, F.Y., Sloan, I.H., Wasilkowski, G.W., Waterhouse, B.J.: Randomly shifted lattice rules with the optimal rate of convergence for unbounded integrands. J. Complex. 26, 135-160 (2010) · Zbl 1208.65008 · doi:10.1016/j.jco.2009.07.005
[27] Kuo, F.Y., Sloan, I.H., Wasilkowski, G.W., Woźniakowski, H.: On decomposition of multivariate functions. Math. Comput. 79, 953-966 (2010) · Zbl 1196.41022 · doi:10.1090/S0025-5718-09-02319-9
[28] L’Ecuyer, P.; Lemieux, Ch; Dror, M. (ed.); L’Ecuyer, P. (ed.); Szidarovski, F. (ed.), Recent advances in randomized quasi-Monte Carlo methods, 419-474 (2002), Boston
[29] Lemieux, Ch.: Monte Carlo and Quasi-Monte Carlo Sampling. Springer, New York (2009) · Zbl 1269.65001
[30] Liu, R., Owen, A.B.: Estimating mean dimensionality of analysis of variance decompositions. J. Am. Stat. Assoc. 101, 712-721 (2006) · Zbl 1119.62343 · doi:10.1198/016214505000001410
[31] Matoušek, J.: On the \[L_2\] L2-discrepancy for anchored boxes. J. Complex. 14, 527-556 (1998) · Zbl 0942.65021 · doi:10.1006/jcom.1998.0489
[32] Matsumoto, M., Nishimura, T.: Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator. ACM Trans. Model. Comput. Simul. 8, 3-30 (1998) · Zbl 0917.65005 · doi:10.1145/272991.272995
[33] Niederreiter, H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia (1992) · Zbl 0761.65002 · doi:10.1137/1.9781611970081
[34] Nožička, F., Guddat, J., Hollatz, H., Bank, B.: Theory of Linear Parametric Programming (in German). Akademie-Verlag, Berlin (1974)
[35] Nuyens, D., Cools, R.: Fast algorithms for component-by-component constructions of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces. Math. Comput. 75, 903-922 (2006) · Zbl 1094.65004 · doi:10.1090/S0025-5718-06-01785-6
[36] Owen, AB; Niederreiter, H. (ed.); Shiue, PJ-S (ed.), Randomly permuted \[(t,m,s)\](t,m,s)-nets and \[(t,s)\](t,s)-sequences, No. 106, 299-317 (1995), New York · Zbl 0831.65024 · doi:10.1007/978-1-4612-2552-2_19
[37] Owen, A.B.: Monte Carlo variance of scrambled net quadrature. SIAM J. Numer. Anal. 34, 1884-1910 (1997) · Zbl 0890.65023 · doi:10.1137/S0036142994277468
[38] Owen, A.B.: Scrambled net variance for integrals of smooth functions. Ann. Stat. 25, 1541-1562 (1997) · Zbl 0886.65018 · doi:10.1214/aos/1031594731
[39] Owen, A.B.: The dimension distribution and quadrature test functions. Statistica Sinica 13, 1-17 (2003) · Zbl 1017.62060
[40] Owen, AB; Fan, J. (ed.); Li, G. (ed.), Multidimensional variation for Quasi-Monte Carlo, 49-74 (2005), Singapore · Zbl 1266.26024
[41] Owen, A.B.: Local antithetic sampling with scrambled nets. Ann. Stat. 36, 2319-2343 (2008) · Zbl 1157.65006 · doi:10.1214/07-AOS548
[42] Pagès, G.: A space quantization method for numerical integration. J. Comput. Appl. Math. 89, 1-38 (1997) · Zbl 0908.65012 · doi:10.1016/S0377-0427(97)00190-8
[43] Papageorgiou, A.: Brownian bridge does not offer a consistent advantage in Quasi-Monte Carlo integration. J. Complex. 18, 171-186 (2002) · Zbl 0998.65005 · doi:10.1006/jcom.2001.0631
[44] Pappas, SSp, Ekonomou, L., Karampelas, P., Karamousantas, D.C., Katsikas, S.K., Chatzarakis, G.E., Skafidas, P.D.: Electricity demand load forecasting of the Hellenic power system using an ARMA model. Electr. Power Syst. Res. 80, 256-264 (2010) · doi:10.1016/j.epsr.2009.09.006
[45] Pennanen, T., Koivu, M.: Epi-convergent discretizations of stochastic programs via integration quadratures. Numerische Mathematik 100, 141-163 (2005) · Zbl 1063.65047 · doi:10.1007/s00211-004-0571-4
[46] Pflug, G.Ch., Pichler, A.: Approximations for probability distributions and stochastic optimization problems. In: Bertocchi, M.I., Consigli, G. (eds.) Stochastic Optimization Methods in Finance and Energy, pp. 343-387. Springer, Berlin (2011) · Zbl 1405.90093
[47] Proinov, P.D.: Discrepancy and integration of continuous functions. J. Approx. Theory 52, 121-131 (1998) · Zbl 0644.41018 · doi:10.1016/0021-9045(88)90051-2
[48] Rachev, S.T., Rüschendorf, L.: Mass Transportation Problems, vol. I. Springer, New York (1998) · Zbl 0990.60500
[49] Römisch, W.; Ruszczyński, A. (ed.); Shapiro, A. (ed.), Stability of stochastic programming problems, No. 10, 483-554 (2003), Amsterdam
[50] Römisch, W.; Cochran, JJ (ed.), Scenario generation (2010), New York
[51] Ruszczyński, A., Shapiro, A. (eds.): Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10. Elsevier, Amsterdam (2003) · Zbl 1115.90001
[52] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. MPS-SIAM Series on Optimization, Philadelphia (2009) · Zbl 1183.90005 · doi:10.1137/1.9780898718751
[53] Sloan, IH; Fang, K-T (ed.); Hickernell, FJ (ed.); Niederreiter, H. (ed.), QMC integration—beating intractability by weighting the coordinate directions, 103-123 (2002), Berlin · Zbl 1003.65004 · doi:10.1007/978-3-642-56046-0_7
[54] Sloan, I.H., Woźniakowski, H.: When are Quasi Monte Carlo algorithms efficient for high-dimensional integration. J. Complex. 14, 1-33 (1998) · Zbl 1032.65011 · doi:10.1006/jcom.1997.0463
[55] Sloan, I.H., Kuo, F.Y., Joe, S.: Constructing randomly shifted lattice rules in weighted Sobolev spaces. SIAM J. Numer. Anal. 40, 1650-1665 (2002) · Zbl 1037.65005 · doi:10.1137/S0036142901393942
[56] Sobol’, I.M.: Multidimensional Quadrature Formulas and Haar Functions (in Russian). Nauka, Moscow (1969) · Zbl 0195.16903
[57] Sobol’, I.M.: Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates. Math. Comput. Simul. 55, 271-280 (2001) · Zbl 1005.65004 · doi:10.1016/S0378-4754(00)00270-6
[58] Sobol’, I.M., Kucherenko, S.: Derivative based global sensitivity measures and their link with global sensitivity indices. Math. Comput. Simul. 79, 3009-3017 (2009) · Zbl 1167.62005 · doi:10.1016/j.matcom.2009.01.023
[59] Takemura, A.: Tensor analysis of ANOVA decomposition. J. Am. Stat. Assoc. 78, 894-900 (1983) · Zbl 0535.62061 · doi:10.1080/01621459.1983.10477037
[60] Tezuka, Shu, Faure, Henri: I-binomial scrambling of digital nets and sequences. J. Complex. 19, 744-757 (2003) · Zbl 1073.68033 · doi:10.1016/S0885-064X(03)00035-9
[61] Walkup, D., Wets, R.J.-B.: Lifting projections of convex polyedra. Pac. J. Math. 28, 465-475 (1969) · Zbl 0172.23702 · doi:10.2140/pjm.1969.28.465
[62] Wallace, S.W., Ziemba, W.T. (eds.): Applications of Stochastic Programming. MPS-SIAM Series on Optimization, Philadelphia (2005) · Zbl 1068.90002
[63] Wang, X.: Tractability of multivariate integration using Quasi-Monte Carlo algorithms. Math. Comput. 72, 823-838 (2003) · Zbl 1025.65010 · doi:10.1090/S0025-5718-02-01440-0
[64] Wang, X.: On the effects of dimension reduction techniques on some high-dimensional problems in finance. Oper. Res. 54, 1063-1078 (2006) · Zbl 1167.91376 · doi:10.1287/opre.1060.0334
[65] Wang, X., Fang, K.-T.: The effective dimension and Quasi-Monte Carlo integration. J. Complex. 19, 101-124 (2003) · Zbl 1021.65002 · doi:10.1016/S0885-064X(03)00003-7
[66] Wang, X., Sloan, I.H.: Why are high-dimensional finance problems often of low effective dimension. SIAM J. Sci. Comput. 27, 159-183 (2005) · Zbl 1149.65303 · doi:10.1137/S1064827503429429
[67] Wang, X., Sloan, I.H.: Brownian bridge and principal component analysis: towards removing the curse of dimensionality. IMA J. Numer. Anal. 27, 631-654 (2007) · Zbl 1130.65007 · doi:10.1093/imanum/drl044
[68] Wang, X., Sloan, I.H.: Low discrepancy sequences in high dimensions: how well are their projections distributed? J. Comput. Appl. Math. 213, 366-386 (2008) · Zbl 1144.65003 · doi:10.1016/j.cam.2007.01.005
[69] Wang, X., Sloan, I.H.: Quasi-Monte Carlo methods in financial engineering: An equivalence principle and dimension reduction. Oper. Res. 59, 80-95 (2011) · Zbl 1217.91202 · doi:10.1287/opre.1100.0853
[70] Wets, R.J.-B.: Stochastic programs with fixed recourse: the equivalent deterministic program. SIAM Rev. 16, 309-339 (1974) · Zbl 0311.90056 · doi:10.1137/1016053
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.