Sequential importance sampling algorithms for dynamic stochastic programming

M. Dempster

Zapiski Nauchnykh Seminarov POMI, Representation theory, dynamical systems. Part XI, Tome 312 (2004), pp. 94-129

Résumé

This paper gives a comprehensive treatment of EVPI-based sequential importance sampling algorithms for dynamic (multistage) stochastic programming problems. Both theory and computational algorithms are discussed. Under general assumptions it is shown that both an expected value of perfect information (EVPI) process and the corresponding marginal EVPI process (the supremum norm of the conditional expectation of its generalized derivative) are nonanticipative nonnegative supermartingales. These processes are used as importance criteria in the class of sampling algorithms treated in the paper. When their values are negligible at a node of the current sample problem scenario tree, scenarios descending from the node are replaced by a single scenario at the next iteration. High values on the other hand lead to increasing the number of scenarios descending from the node. Both the small sample and asymptotic properties of the sample problem estimates arising from the algorithms are established and the former are evaluated numerically in the context of a financial planning problem. Finally, current and future research is described.

Bibliographie

[1] K. Back, S. R. Pliska, “The shadow price of information in continuous-time decision problems”, Stochastics, 22 (1987), 151–186 | MR | Zbl

[2] B. Bereanu, “On stochastic linear programming. II: Distribution problems. Non-stochastic technology matrix”, Rev. Roumaine Math. Pures Appl., 11 (1966), 713–725 | MR | Zbl

[3] B. Bereanu, “On stochastic linear programming: Distribution problems. Stochastic technology matrix”, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 8 (1967), 148–152 | DOI | MR | Zbl

[4] P. Billingsley, Probability and Measure, 2nd edition, Wiley, New York, 1980

[5] J. R. Birge, M. A. H. Dempster, H. I. Gassmann, E. A. Gunn, A. J. King, S. Wallace, “A standard input format for multiperiod stochastic linear programs. Mathematical Programming Society”, Committee on Algorithms Newsletter, 17 (1987), 1–20

[6] M. J. Brennan, E. S. Schwartz, R. Lagnado, “Strategic asset allocation”, Journal of Economic Dynamics and Control, 21 (1997), 1377–1403 | DOI | MR | Zbl

[7] Z. Chen, G. Consigli, M. A. H. Dempster, N. Hicks Pedrón, “Towards sequential sampling algorithms for dynamic portfolio management”, Operational Tools in the Management of Financial Risks, 1997, 197–211

[8] X. Corvera Poiré, Model Generation and Sampling Algorithms for Dynamic Stochastic Programming, PhD Thesis, Departmentt of Mathematics, University of Essex, UK, 1995

[9] X. Corvera Poiré, STOCHGEN User's Manual. Department of Mathematics, University of Essex, UK, 1995

[10] J. W. Daniel, The Approximate Minimization of Functionals, Prentice-Hall, Englewood Cliffs, NJ, 1971 | MR

[11] G. B. Dantzig, P. W. Glynn, “Parallel processors for planning under uncertainty”, Annals of Operations Research, 22 (1990), 1–21 | DOI | MR | Zbl

[12] G. B. Dantzig, G. Infanger, Large-scale stochastic linear programs: Importance sampling and Benders decomposition, Technical Report SOL 91–4, Department of Operations Research, Stanford University, Stanford, CA, 1991 | MR

[13] G. B. Dantzig, A. Madansky, “On the solution of two-stage linear programs under uncertainty”, Proceedings of the Fourth Symposium on Mathematical Statistics and Probability, Vol. I, Univ. of California, Berkeley, 1961, 165–176

[14] M. H. A. Davis, M. A. H. Dempster, R. J. Elliott, “On the value of information in controlled diffusion processes”, Stochastic Analysis, 1991, 125–138 | MR | Zbl

[15] M. A. H. Dempster (ed.), Stochastic Programming, Academic Press, London, 1980 | MR

[16] M. A. H. Dempster, “The expected value of perfect information in the optimal evolution of stochastic systems”, Stochastic Differential Systems, Lecture Notes in Information and Control, 36, eds. M. Arato, D. Vermes, A. V. Balikrishnan, Springer, Berlin, 1981, 25–40

[17] M. A. H. Dempster, “On stochastic programming. II: Dynamic problems under risk”, Stochastics, 25 (1988), 15–42 | MR | Zbl

[18] M. A. H. Dempster, R. T. Thompson, “EVPI-based importance sampling solution procedures for multistage stochastic linear programmes on parallel MIMD architectures”, Annals of Operations Research, 90 (1999), 161–184 | DOI | MR | Zbl

[19] D. Dentcheva, W. Römisch, Differential stability of two-stage stochastic programs, Preprint No 96-36, Institute of Mathematics, Humboldt University, Berlin, 1996 | Zbl

[20] O. Fiedler, W. Römisch, “Stability in multistage stochastic programming”, Annals of Operations Research, 56 (1995), 79–93 | DOI | MR | Zbl

[21] H. I. Gassmann, “MSLiP: A computer code for the multistage stochastic linear programming problem”, Mathematical Programming, 47 (1990), 407–423 | DOI | MR | Zbl

[22] N. Hicks Pedrón, Model-Based Asset Management: A Comparative Study, PhD Thesis, Judge Institute of Management Studies, University of Cambridge, UK, 1998

[23] J. L. Higle, S. Sen, “Stochastic decomposition: An algorithm for two stage linear programs with recourse”, Mathematics of Operations Research, 16 (1991), 650–669 | DOI | MR | Zbl

[24] J. L. Higle, S. Sen, Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming, Kluwer Academic Publishers, Dordrecht, 1996 | MR | Zbl

[25] G. Infanger, Planning under Uncertainty: Solving Large-Scale Stochastic Linear Programs, Boyd Fraser, Danvers, MA, 1994

[26] A. J. King, Asymptotic Behaviour of Solutions in Stochastic Optimization: Nonsmooth Analysis and the Derivation of Non-normal Limit Distributions, PhD Thesis, Department of Mathematics, University of Washington, 1986

[27] A. J. King, “Generalized delta theorems for multivalued mappings and measurable selections”, Mathematics of Operations Research, 14 (1989), 720–736 | DOI | MR | Zbl

[28] A. J. King, Martingales and duality in contingent claims analysis: The discrete case, Research Report RC21153, IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY, 1998

[29] A. J. King, R. T. Rockafellar, “Asymptotic theory for solutions in statistical estimation and stochastic programming”, Mathematics of Operations Research, 18 (1993), 148–162 | DOI | MR | Zbl

[30] M. Lane, P. Hutchinson, “A model for managing a certificate of deposit portfolio under uncertainty”, Stochastic Programming, 1980, 473–493 | MR

[31] W. K. Mak, D. P. Morton, R. K. Wood, Monte Carlo bounding techniques for determining solution quality in stochastic programs, Research Report, Department of Computer Science, University of Texas at Austin, 1997

[32] H. M. Markowitz, Portfolio Selection, Efficient Diversification of Investments, 2nd edition, Blackwell, Oxford, 1987 | MR | Zbl

[33] E. Mayer-Wolf, E. Merzbach, A. Schwartz, Stochastic Analysis, Academic Press, New York, 1991 | MR | Zbl

[34] V. I. Norkin, G. C. Pflug, A. Ruszcynski, A branch and bound method for stochastic global optimization, Working Paper WP-96-065, International Institute for Applied Systems Analysis, Laxenburg, Austria, 1996

[35] P. Olsen, “Discretizations of multistage stochastic programming problems”, Mathematical Programming Studies, 6 (1976), 111–124 | MR | Zbl

[36] G. Ch. Pflug, Optimization of Stochastic Models: The Interface Between Simulation and Optimization, Kluwer, Boston, 1996 | MR | Zbl

[37] A. Prékopa, “Laws of large numbers for random linear programs”, Math. Systems Theory, 6 (1972), 277–288 | DOI | MR

[38] S. T. Rachev, Probability Metrics and the Stability of Stochastic Models, Wiley, New York | MR

[39] H. Raiffa, Decision Analysis, Addison-Wesley, Reading, MA, 1968 | Zbl

[40] R. T. Rockafellar and R. J.-B. Wets, “Nonanticipativity and $L^1$-martingales in stochastic optimization problems”, Mathematical Programming Studies, 6 (1976), 170–186. | MR

[41] R. T. Rockafellar, R. J.-B.Wets, “A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming”, Mathematical Programming Studies, 28 (1986), 63–93 | MR | Zbl

[42] W. Römisch, Quantitative stability of stochastic programs, Presented at 16th International Symposium on Mathematical Programming, Lausanne, 1997

[43] R. Y. Rubinstein, A. Shapiro, Discrete Event Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Method, Wiley, New York, 1993 | MR | Zbl

[44] G. Salinetti, R. J.-B.Wets, “On the distribution of measurable multifunctions (random sets), normal integrands, stochastic processes and stochastic infima”, Mathematics of Operations Research, 11 (1986), 385–419 | DOI | MR | Zbl

[45] A. Shapiro, “Asymptotic analysis of stochastic programs”, Annals of Operations Research, 30 (1991), 169–186 | DOI | MR | Zbl

[46] A. Shapiro, “Asymptotic behaviour of optimal solutions in stochastic programming”, Mathematics of Operations Research, 18 (1993), 829–845 | DOI | MR | Zbl

[47] A. Shapiro, “Simulation-based optimization: Convergence analysis and statistical inference”, Commun. Statist., Stochastic Models, 12 (1996), 425–454 | DOI | MR | Zbl

[48] R. T. Thompson, MSLiP-OSL 8.3 User's Guide, Judge Institute of Management Studies, University of Cambridge, UK, 1997

[49] C. Zopounidis (ed.), Operational Tools in the Management of Financial Risks, Kluwer, Dordrecht, 1997