×

Variance reduction in sample approximations of stochastic programs. (English) Zbl 1099.90036

Summary: This paper studies the use of randomized quasi-Monte Carlo methods (RQMC) in sample approximations of stochastic programs. In numerical integration, RQMC methods often substantially reduce the variance of sample approximations compared to Monte Carlo (MC). It seems thus natural to use RQMC methods in sample approximations of stochastic programs. It is shown, that RQMC methods produce epi-convergent approximations of the original problem. RQMC and MC methods are compared numerically in five different portfolio management models. In the tests, RQMC methods outperform MC sampling substantially reducing the sample variance and bias of optimal values in all the considered problems.

MSC:

90C15 Stochastic programming
65C05 Monte Carlo methods
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Artstein, Z., Wets, R.J.-B.: Stability results for stochastic programs and sensors, allowing for discontinuous objective functions. SIAM J. Optim. 4 (3), 537–550 (1994) · Zbl 0830.90111 · doi:10.1137/0804030
[2] Artstein, Z., Wets R.J.-B.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal. 2 (1–2), 1–17 (1995) · Zbl 0837.90093
[3] Attouch, H.: Variational convergence for functions and operators. Pitman (Advanced Publishing Program), Boston, MA, 1984 · Zbl 0561.49012
[4] Billingsley, P.: Convergence of probability measures. John Wiley & Sons Inc., New York, 2nd edn, 1999 · Zbl 0944.60003
[5] Boyle, P., Broadie, M., Glasserman, P.: Monte Carlo methods for security pricing. J. Econ. Dyn. Cont 21, 1267–1321 (1997) · Zbl 0901.90007 · doi:10.1016/S0165-1889(97)00028-6
[6] Bratley, P., Fox, B.L., Schrage, L.E.: A guide to simulation. Springer-Verlag, 2 edn, 1987 · Zbl 0515.68070
[7] Caflisch, R., Morokoff, W., Owen, A.: Valuation of mortgage backed securities using brownian bridges to reduce effective dimension. J. Comput. Finance 1, 27–46 (1997)
[8] Cranley, R., Patterson, T.N.L.: Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13 (6), 904–914 (1976) · Zbl 0354.65016 · doi:10.1137/0713071
[9] Faure, H.: Discrépance de suites associées à un système de numération (en dimension s). Acta Arith. 41 (4), 337–351 (1982) · Zbl 0442.10035
[10] Fox, B.L.: Algorithm 647: Implementation and relative efficiency of quasirandom sequence generators. ACM Transactions on Mathematical Software 12 (4), 362–376 (1986) · Zbl 0615.65003 · doi:10.1145/22721.356187
[11] Friedel, I., Keller, A.: Fast generation of randomized low discrepancy point sets. In: K.-T. Fang, F.J. Hickernell, H. Niederreiter (eds) Monte Carlo and Quasi-Monte Carlo Methods 2000, Springer Verlag, 2002, pp. 257–273 · Zbl 1055.11049
[12] Halton, J.H.: On the efficiency of certain quasi-random sequences of points in evaluating multi- dimensional integrals. Numer. Math. 2, 84–90 (1960) · Zbl 0090.34505 · doi:10.1007/BF01386213
[13] Hammersley, J.M.: Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci. 86, 844–874 (1960) · Zbl 0111.12405 · doi:10.1111/j.1749-6632.1960.tb42846.x
[14] Higle, J.L.: Variance reduction and objective function evaluation in stochastic linear programs. J. Comput. 10, 236–247 (1998) · Zbl 1034.90520
[15] Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39, 69–95 (1992) · Zbl 0773.90054 · doi:10.1007/BF02060936
[16] Jäckel, P.: Monte Carlo Methods in Finance. John Wiley & Sons, 2002
[17] Kouwenberg, R.: Scenario generation and stochastic programming models for asset liability management. European J. Oper. Res. 134 (2), 279–292 (2001) · Zbl 1008.91050 · doi:10.1016/S0377-2217(00)00261-7
[18] L’Ecuyer, P., Lemieux, C.: Variance reduction via lattice rules. Management Sci. 46 (2), 1214–1235 (2000) · Zbl 1232.65008 · doi:10.1287/mnsc.46.9.1214.12231
[19] L’Ecuyer, P., Lemieux, C.: Recent advances in randomized quasi-Monte Carlo methods. In: M. Dror, P. L’Ecuyer, F. Szidarovszki (eds). Modeling Uncertainty: An Examination of Stochastic Theory, Methods, and Applications, Kluwer Academic Publishers, 2002, pp. 419–474
[20] Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Optimization technical report 02-01, Computer Sciences Department, University of Wisconsin-Madison, 2002
[21] Lucchetti, R., Salinetti, G., Wets, R.J.-B.: Uniform convergence of probability measures: topological criteria. J. Multivariate Anal. 51 (2), 252–264 (1994) · Zbl 0817.60005 · doi:10.1006/jmva.1994.1061
[22] Lucchetti, R., Wets, R.J.-B.: Convergence of minima of integral functionals, with applications to optimal control and stochastic optimization. Statist. Decisions 11 (1), 69–84 (1993) · Zbl 0779.49030
[23] Matsumoto, M., Nishimura, T.: Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Trans. Modeling Comput. Simulation 8 (1), 3–30 (1998) · Zbl 0917.65005 · doi:10.1145/272991.272995
[24] Niederreiter, H.: Low-discrepancy and low-dispersion sequences. J. Number Th. 30, 51–70 (1988) · Zbl 0651.10034 · doi:10.1016/0022-314X(88)90025-X
[25] Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, volume 63 of CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992 · Zbl 0761.65002
[26] Pennanen, T., Koivu, M.: Epi-convergent discretizations of stochastic programs via integration quadratures. Stochastic Programming E-print Series, 2003 · Zbl 1063.65047
[27] Press, W.H., Teukolsky, S.A., Vetterling, W.T., Flannery, B.P.: Numerical recipes in C. The art of scientific computing. Cambridge University Press, Cambridge, 2nd edn, 1992 · Zbl 0845.65001
[28] Rockafellar, R.T., Wets, R.J.-B.: Variational analysis, volume 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, 1998 · Zbl 0888.49001
[29] Shapiro, A.: Stochastic programming by Monte Carlo simulation methods. Stochastic Programming E-Print Series, 2000
[30] Shapiro, A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Meth. Oper. Res. 58, 57–68 (2003) · Zbl 1116.90384 · doi:10.1007/s001860300280
[31] Sloan, I.H., Joe, S.: Lattice methods for multiple integration. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1994 · Zbl 0855.65013
[32] Sobol’, I.M.: The distribution of points in a cube and the approximate evaluation of integrals. U.S.S.R. Computational Math. And Math. Phys. (4), 86–112 (1967) · Zbl 0185.41103
[33] Tuffin, B.: On the use of low discrepancy sequences in Monte Carlo methods. Monte Carlo Methods and Appl. 2 (4), 295–320 (1996) · Zbl 0868.65010 · doi:10.1515/mcma.1996.2.4.295
[34] Wang, X., Fang, K.T.: The effective dimension and quasi-Monte Carlo integration. J. Complexity 19, 101–124 (2002) · Zbl 1021.65002 · doi:10.1016/S0885-064X(03)00003-7
[35] Zervos, M.: On the epiconvergence of stochastic optimization problems. Math. Oper. Res. 24 (2), 495–508 (1999) · Zbl 1074.90552 · doi:10.1287/moor.24.2.495
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.