NUMERICAL-SOLUTION OF CONTINUOUS-STATE DYNAMIC PROGRAMS USING LINEAR AND SPLINE INTERPOLATION

This paper demonstrates that the computational effort required to deve lop numerical solutions to continuous-state dynamic programs can be re duced significantly when cubic piecewise polynomial functions, rather than tensor product linear interpolants, are used to approximate the v alue function. Tensor product cubic splines, represented in either pie cewise polynomial or B-spline form, and multivariate Hermite polynomia ls are considered. Computational savings are possible because of the i mproved accuracy of higher-order functions and because the smoothness of higher-order functions allows efficient quasi-Newton methods to be used to compute optimal decisions. The use of the more efficient piece wise polynomial form of the spline was slightly superior to the use of Hermite polynomials for the test problem and easier to program. In co mparison to linear interpolation, use of splines in piecewise polynomi al form reduced the CPU time to obtain results of equivalent accuracy by a factor of 250-330 for a stochastic 4-dimensional water supply res ervoir problem with a smooth objective function, and factors ranging f rom 25-400 for a sequence of 2-, 3-, 4-, and 5-dimensional problems. A s a result, a problem that required two hours to solve with linear int erpolation was solved in a less than a minute with spline interpolatio n with no loss of accuracy.