SpringerLink
Log in

Variance reduction in sample approximations of stochastic programs

  • Published:
Mathematical Programming Submit manuscript

Abstract.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Spain)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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)

    Article  Google Scholar 

  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)

    Google Scholar 

  3. Attouch, H.: Variational convergence for functions and operators. Pitman (Advanced Publishing Program), Boston, MA, 1984

  4. Billingsley, P.: Convergence of probability measures. John Wiley & Sons Inc., New York, 2nd edn, 1999

  5. Boyle, P., Broadie, M., Glasserman, P.: Monte Carlo methods for security pricing. J. Econ. Dyn. Cont 21, 1267–1321 (1997)

    Article  MathSciNet  Google Scholar 

  6. Bratley, P., Fox, B.L., Schrage, L.E.: A guide to simulation. Springer-Verlag, 2 edn, 1987

  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)

    Google Scholar 

  8. Cranley, R., Patterson, T.N.L.: Randomization of number theoretic methods for multiple integration. SIAM J. Numer. Anal. 13 (6), 904–914 (1976)

    Article  Google Scholar 

  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)

    Google Scholar 

  10. Fox, B.L.: Algorithm 647: Implementation and relative efficiency of quasirandom sequence generators. ACM Transactions on Mathematical Software 12 (4), 362–376 (1986)

    Article  Google Scholar 

  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

  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)

    Article  Google Scholar 

  13. Hammersley, J.M.: Monte Carlo methods for solving multivariable problems. Ann. New York Acad. Sci. 86, 844–874 (1960)

    Google Scholar 

  14. Higle, J.L.: Variance reduction and objective function evaluation in stochastic linear programs. J. Comput. 10, 236–247 (1998)

    MathSciNet  Google Scholar 

  15. Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs. Ann. Oper. Res. 39, 69–95 (1992)

    Google Scholar 

  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)

    Article  Google Scholar 

  18. L’Ecuyer, P., Lemieux, C.: Variance reduction via lattice rules. Management Sci. 46 (2), 1214–1235 (2000)

    Article  Google Scholar 

  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)

    Article  Google Scholar 

  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)

    Google Scholar 

  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)

    Article  Google Scholar 

  24. Niederreiter, H.: Low-discrepancy and low-dispersion sequences. J. Number Th. 30, 51–70 (1988)

    Article  Google Scholar 

  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

  26. Pennanen, T., Koivu, M.: Epi-convergent discretizations of stochastic programs via integration quadratures. Stochastic Programming E-print Series, 2003

  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

  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

  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)

    Article  Google Scholar 

  31. Sloan, I.H., Joe, S.: Lattice methods for multiple integration. Oxford Science Publications. The Clarendon Press Oxford University Press, New York, 1994

  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)

  33. Tuffin, B.: On the use of low discrepancy sequences in Monte Carlo methods. Monte Carlo Methods and Appl. 2 (4), 295–320 (1996)

    Google Scholar 

  34. Wang, X., Fang, K.T.: The effective dimension and quasi-Monte Carlo integration. J. Complexity 19, 101–124 (2002)

    Article  Google Scholar 

  35. Zervos, M.: On the epiconvergence of stochastic optimization problems. Math. Oper. Res. 24 (2), 495–508 (1999)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Management Science, Helsinki School of Economics, PL1210 00101, Helsinki, Finland

    Matti Koivu

Authors
  1. Matti Koivu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matti Koivu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Koivu, M. Variance reduction in sample approximations of stochastic programs. Math. Program. 103, 463–485 (2005). https://doi.org/10.1007/s10107-004-0557-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-004-0557-0

Keywords

Search

Navigation