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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
E.M.L. Beale, On minimizing a convex function subject to linear inequalities, J. Roy. Stat. Soc. 17b (1955).
J.F. Benders, Partitioning procedures for solving mixed-variable programming problems, Numer. Math. 4 (1962) 238–252.
J.R. Birge, Decomposition and partitioning methods for multi-stage stochastic linear programming, Oper. Res. 33 (1985) 989–1007.
G.B. Dantzig, Linear programming under uncertainty, Manag. Sci. 1 (1955) 197–206.
G.B. Dantzig and P.W. Glynn, Parallel processors for planning under uncertainty, Ann. Oper. Res. 22 (1990) 1–21.
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).
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.
P.J. Davis and P. Rabinowitz,Methods of Numerical Integration (Academic Press, London, 1984).
Y. Ermoliev, Stochastic quasi-gradient methods and their applications to systems optimization, Stochastics 9 (1983) 1–36.
Y. Ermoliev and R.J. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer, 1988).
K. Frauendorfer, Solving SLP recourse problems with arbitrary multivariate distributions — The dependent case, Math. Oper. Res. 13 (1988) 377–394.
P.W. Glynn and D.L. Iglehart, Importance sampling for stochastics simulation, Manag. Sci. 35 (1989) 1367–1392.
N.H. Hakansson, Optimal myopic portfolio policies, with and without serial correlation of yields, J. Bus. U. of Chicago 44 (1971).
N.H. Hakansson, Convergence to isoelastic utility and policy in multi-period portfolio choice, J. Fin. Econ. 1 (1974) 201.
J.L. Higle and S. Sen, Stochastic decomposition: An algorithm for two stage linear programs with recourse, Math. Oper. Res., to appear.
J.K. Ho and E. Loute, A set of staircase linear programming test problems, Math. Prog. 20 (1981) 245–250.
J.K. Ho and A.S. Manne, Nested decomposition for dynamic models, Math. Progr. 6 (1974) 121–140.
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).
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.
R. Jarrow, Pricing interest rate options, in:Handbooks in Operations Research and Management Science, eds. R. Jarrow, M. Maksimovic and W. Ziemba.
P. Kall, Computational methods for two stage stochastic linear programming problems, Z. angew. Math. Phys. 30 (1979) 261–271.
H. Konno, Piecewise linear risk function and portfolio optimization, J. Oper. Res. Soc. Japan 33, no. 2 (1990).
H. Markowitz,Portfolio Selection: Efficient Diversification of Investments (Wiley, New York, 1959).
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).
J.M. Mulvey, Nonlinear network models in finance, Adv. Math. Progr. Fin. Planning 1 (1987) 253.
J.M. Mulvey and H. Vladimirou, Stochastic network optimization models for investment planning, Ann. Oper. Res. 20 (1989) 187–217.
J.M. Mulvey and H. Vladimirou, Applying the progressive hedging algorithm to stochastic generalized networks, Ann. Oper. Res. 31 (1991) 399–424.
B.A. Murtagh, and M.A. Saunders, MINOS User's Guide, SOL 82-20, Department of Operations Research, Stanford University, Stanford CA 94305 (1983).
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).
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).
A. Perold, Large-scale portfolio optimization, Manag. Sci. 30 (1984) 1143.
R.T. Rockafellar and R.J. Wets, Scenario and policy aggregation in optimization under uncertainty, Math. Oper. Res. (1989), to appear.
A. Ruszczynski, A regularized decomposition method for minimizing a sum of polyhedral functions, Math. Progr. 35 (1986) 309–333.
W.F. Sharpe, Capital asset prices: A theory of market equilibrium under condition of risk, J. Finance 19 (1964) 425–442.
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.
R.J. Wets, Programming under uncertainty: The equivalent convex program, SIAM J. Appl. Math. 14 (1984) 89–105.
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.
Author information
Authors and Affiliations
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
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
Issue Date:
DOI: https://doi.org/10.1007/BF02282041