Numerical Solution of Continuous-State Dynamic Programs Using Linear and Spline Interpolation

Sharon A. Johnson, Jery R. Stedinger, Christine A. Shoemaker, Ying Li and José Alberto Tejada-Guibert
Additional contact information
Sharon A. Johnson: Worcester Polytechnic Institute, Worcester, Massachusetts
Jery R. Stedinger: Cornell University, Ithaca, New York
Christine A. Shoemaker: Cornell University, Ithaca, New York
Ying Li: Beijing Economic Research Institute of Water Resources and Electric Power, Beijing, Peoples Republic of China
José Alberto Tejada-Guibert: United Nations, New York, New York

Operations Research, 1993, vol. 41, issue 3, 484-500

Abstract: This paper demonstrates that the computational effort required to develop numerical solutions to continuous-state dynamic programs can be reduced significantly when cubic piecewise polynomial functions, rather than tensor product linear interpolants, are used to approximate the value function. Tensor product cubic splines, represented in either piecewise polynomial or B-spline form, and multivariate Hermite polynomials are considered. Computational savings are possible because of the improved 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 piecewise polynomial form of the spline was slightly superior to the use of Hermite polynomials for the test problem and easier to program. In comparison to linear interpolation, use of splines in piecewise polynomial form reduced the CPU time to obtain results of equivalent accuracy by a factor of 250–330 for a stochastic 4-dimensional water supply reservoir problem with a smooth objective function, and factors ranging from 25–400 for a sequence of 2-, 3-, 4-, and 5-dimensional problems. As a result, a problem that required two hours to solve with linear interpolation was solved in a less than a minute with spline interpolation with no loss of accuracy.

Keywords: dynamic programming; applications: numerical solution of continuous-state dynamic programs; dynamic programming; Markov; infinite state: higher-order approximation of the value function (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations: View citations in EconPapers (39)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.41.3.484 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:41:y:1993:i:3:p:484-500

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().