Applying experimental design and regression splines to high-dimensional continuous-state stochastic dynamic programming
成果类型：
Article
署名作者：
Chen, VCP; Ruppert, D; Shoemaker, CA
署名单位：
University System of Georgia; Georgia Institute of Technology; Cornell University
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.47.1.38
发表日期：
1999
页码：
38-53
关键词：
摘要：
In stochastic dynamic programming (SDP) with continuous stare and decision variables, the future value function is computed at discrete points in the state space. Interpolation can be used to approximate the values of the future value function between these discrete points. However, for large dimensional problems the number of discrete points required to obtain a good approximation of the future value function can be prohibitively large. Statistical methods of experimental design and function estimation may be employed to overcome this curse of dimensionality. In this paper, we describe a method for estimating the future value function by multivariate adaptive regression splines (MARS) fit over a discretization scheme based on orthogonal array (OA) experimental designs. Because orthogonal arrays only grow polynomially in the state-space dimension, our OA/MARS method is accurately able to solve higher dimensional SDP problems than previously possible. To our knowledge, the most efficient method published prior to this work employs tenser-product cubic splines to approximate the future value function (Johnson et al. 1993). The computational advantages of OA/MARS are demonstrated in comparisons with the method using tenser-product cubic splines for applications of an inventory forecasting SDP with up to nine state variables computed on a small workstation. In particular, the storage of an adequate tenser-product cubic spline for six dimensions exceeds the memory of our workstation, and the run time for an accurate OA/MARS SDP solution would be at least an order of magnitude faster than using tenser-product cubic splines for higher than six dimensions.