Skip to main content
SpringerLink
Log in

Multi-stage stochastic linear programs for portfolio optimization

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

The paper demonstrates how multi-period portfolio optimization problems can be efficiently solved as multi-stage stochastic linear programs. A scheme based on a blending of classical Benders decomposition techniques and a special technique, called importance sampling, is used to solve this general class of multi-stochastic linear programs. We discuss the case where stochastic parameters are dependent within a period as well as between periods. Initial computational results are presented.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. E.M.L. Beale, On minimizing a convex function subject to linear inequalities, J. Roy. Stat. Soc. 17b (1955).

  2. J.F. Benders, Partitioning procedures for solving mixed-variable programming problems, Numer. Math. 4 (1962) 238–252.

    Google Scholar 

  3. J.R. Birge, Decomposition and partitioning methods for multi-stage stochastic linear programming, Oper. Res. 33 (1985) 989–1007.

    Google Scholar 

  4. G.B. Dantzig, Linear programming under uncertainty, Manag. Sci. 1 (1955) 197–206.

    Google Scholar 

  5. G.B. Dantzig and P.W. Glynn, Parallel processors for planning under uncertainty, Ann. Oper. Res. 22 (1990) 1–21.

    Google Scholar 

  6. G.B. Dantzig and G. Infanger, Large-scale stochastic linear programs: Importance sampling and Benders decomposition, Technical Report SOL 91-4, Department of Operations Research, Stanford University (1991).

  7. G.B. Dantzig and M. Madansky, On the solution of two-staged linear programs under uncertainty,Proc. 4th Berkeley Symp. on Mathematical Statistics and Probability I, ed. J. Neyman (1961) pp. 165–176.

  8. P.J. Davis and P. Rabinowitz,Methods of Numerical Integration (Academic Press, London, 1984).

    Google Scholar 

  9. Y. Ermoliev, Stochastic quasi-gradient methods and their applications to systems optimization, Stochastics 9 (1983) 1–36.

    Google Scholar 

  10. Y. Ermoliev and R.J. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer, 1988).

  11. K. Frauendorfer, Solving SLP recourse problems with arbitrary multivariate distributions — The dependent case, Math. Oper. Res. 13 (1988) 377–394.

    Google Scholar 

  12. P.W. Glynn and D.L. Iglehart, Importance sampling for stochastics simulation, Manag. Sci. 35 (1989) 1367–1392.

    Google Scholar 

  13. N.H. Hakansson, Optimal myopic portfolio policies, with and without serial correlation of yields, J. Bus. U. of Chicago 44 (1971).

  14. N.H. Hakansson, Convergence to isoelastic utility and policy in multi-period portfolio choice, J. Fin. Econ. 1 (1974) 201.

    Google Scholar 

  15. J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two stage linear programs with recourse, Math. Oper. Res., to appear.

  16. J.K. Ho and E. Loute, A set of staircase linear programming test problems, Math. Prog. 20 (1981) 245–250.

    Google Scholar 

  17. J.K. Ho and A.S. Manne, Nested decomposition for dynamic models, Math. Progr. 6 (1974) 121–140.

    Google Scholar 

  18. G. Infanger, Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs, Technical Report SOL 89-13R, Department of Operations Research, Stanford University (1990).

  19. G. Infanger, Monte Carlo (importance) sampling within a Benders decomposition algorithm for stochastic linear programs, Extended Version: Including large-scale results, Ann. Oper. Res. 39 (1992) 41–67.

    Google Scholar 

  20. R. Jarrow, Pricing interest rate options, in:Handbooks in Operations Research and Management Science, eds. R. Jarrow, M. Maksimovic and W. Ziemba.

  21. P. Kall, Computational methods for two stage stochastic linear programming problems, Z. angew. Math. Phys. 30 (1979) 261–271.

    Google Scholar 

  22. H. Konno, Piecewise linear risk function and portfolio optimization, J. Oper. Res. Soc. Japan 33, no. 2 (1990).

    Google Scholar 

  23. H. Markowitz,Portfolio Selection: Efficient Diversification of Investments (Wiley, New York, 1959).

    Google Scholar 

  24. T.A. Marsh, Term structure of interest rates and the pricing of fixed income claims and bonds, in:Handbooks in Operations Research and Management Science, eds. R. Jarrow, M. Maksimovic and W. Ziemba (1992).

  25. J.M. Mulvey, Nonlinear network models in finance, Adv. Math. Progr. Fin. Planning 1 (1987) 253.

    Google Scholar 

  26. J.M. Mulvey and H. Vladimirou, Stochastic network optimization models for investment planning, Ann. Oper. Res. 20 (1989) 187–217.

    Google Scholar 

  27. J.M. Mulvey and H. Vladimirou, Applying the progressive hedging algorithm to stochastic generalized networks, Ann. Oper. Res. 31 (1991) 399–424.

    Google Scholar 

  28. B.A. Murtagh, and M.A. Saunders, MINOS User's Guide, SOL 82-20, Department of Operations Research, Stanford University, Stanford CA 94305 (1983).

    Google Scholar 

  29. M.V. Pereira, L.M.V.G. Pinto, G.C. Oliveira and S.H.F. Cunha, A technique for solving LP-problems with stochastic right-hand sides, CEPEL, Centro del Pesquisas de Energia Electria, Rio de Janeiro, Brazil (1989).

    Google Scholar 

  30. M.V. Pereira and L.M.V.G. Pinto, Stochastic dual dynamic programming, Technical Note, DEE- PUC/RJ — Catholic University of Rio de Janeiro, Caixa Postal 38063 Gávea, Rio de Janeiro RJ CEP 22452 Brazil (1989).

    Google Scholar 

  31. A. Perold, Large-scale portfolio optimization, Manag. Sci. 30 (1984) 1143.

    Google Scholar 

  32. R.T. Rockafellar and R.J. Wets, Scenario and policy aggregation in optimization under uncertainty, Math. Oper. Res. (1989), to appear.

  33. A. Ruszczynski, A regularized decomposition method for minimizing a sum of polyhedral functions, Math. Progr. 35 (1986) 309–333.

    Google Scholar 

  34. W.F. Sharpe, Capital asset prices: A theory of market equilibrium under condition of risk, J. Finance 19 (1964) 425–442.

    Google Scholar 

  35. J. Van Slyke and R.J. Wets, L-shaped linear programs with applications to optimal control and stochastic programming, SIAM J. Appl. Math. 17 (1969) 638–663.

    Google Scholar 

  36. R.J. Wets, Programming under uncertainty: The equivalent convex program, SIAM J. Appl. Math. 14 (1984) 89–105.

    Google Scholar 

  37. S.A. Zenios, A model for portfolio management with mortgage backed securities, Department of Decision Sciences, The Wharton School, University of Pennsylvania, Philadelphia, PA 19104-6366 (1991), to appear in Ann. Oper. Res.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Operations Research, Stanford University, 94305-4022, Stanford, CA, USA

    George B. Dantzig & Gerd Infanger

Authors
  1. George B. Dantzig
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gerd Infanger
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research and reproduction of this report were partially supported by the Office of Naval Research Contract N00014-89-J-1659; the National Science Foundation Grants ECS-8906260, DMS-8913089, the Electric Power Research Institute Contract RP-8010-09, CSA-4O05335, and the Austrian Science Foundation, “Fonds zur Förderung der wissenschaftlichen Forschung”, Grant J0323-Phy. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do NOT necessarily reflect the views of the above sponsors. The comments of anonymous referees are gratefully acknowledged.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dantzig, G.B., Infanger, G. Multi-stage stochastic linear programs for portfolio optimization. Ann Oper Res 45, 59–76 (1993). https://doi.org/10.1007/BF02282041

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02282041

Keywords

Search

Navigation