Sequential Importance Sampling Algorithms for Dynamic Stochastic Programming
by
Michael A.H. Dempster
Centre for Financial Research, Judge Institute of Management Studies, University of Cambridge, Cambridge, England and Cambridge Systems Associates Limited

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 the expected value of perfect information (EVPI) process and the 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.

Date received: March 24, 1999

Copyright © 1999 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cacq-27.