Solving Dynamic Programming Problems on a Computational Grid

详细信息    查看全文

• 作者：Yongyang Cai ; Kenneth L. Judd ; Greg Thain ; Stephen J. Wright
• 关键词：Numerical dynamic programming ; Parallel computing ; Grid computing ; Value function iteration ; Dynamic portfolio optimization ; Multi ; country optimal growth ; C61 ; C63 ; G11
• 刊名：Computational Economics
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：45
• 期：2
• 页码：261-284
• 全文大小：258 KB
• 参考文献：1. Abdelkhalek, A., Bilas, A., & Michaelides, A. (2001). Parallelization, optimization and performance analysis of portfolio choice models. In / Proceedings of the 2001 international conference on parallel processing (ICPP01) (pp. 277-86).
  2. Aldrich, E. M., Fernandez-Villaverde, J., Gallant, A. R., & Rubio-Ramrez, J. F. (2011). Tapping the supercomputer under your desk: Solving dynamic equilibrium models with graphics processors. / Journal of Economic Dynamics and Control, / 35, 386-93. CrossRef
  3. Bellman, R. (1957). / Dynamic programming. Princeton: Princeton University Press.
  4. Cai, Y. (2010). / Dynamic programming and its application in economics and finance. PhD thesis, Stanford University.
  5. Cai, Y., & Judd, K. L. (2010). Stable and efficient computational methods for dynamic programming. / Journal of the European Economic Association, / 8(2-), 626-34. CrossRef
  6. Cai, Y., & Judd, K. L. (2012a). Dynamic programming with shape-preserving rational spline Hermite interpolation. / Economics Letters, / 117(1), 161-64. CrossRef
  7. Cai, Y., & Judd, K. L. (2012b). Dynamic programming with Hermite approximation. NBER Working Paper No. w18540.
  8. Cai, Y., & Judd, K. L. (2013). Shape-preserving dynamic programming. / Mathematical Methods of Operations Research, / 77(3), 407-21. CrossRef
  9. Cai, Y., Judd, K. L., Lontzek, T. S., Michelangeli, V., & Su, C.-L. (2013a). Nonlinear programming method for dynamic programming. NBER Working Paper No. w19034.
  10. Cai, Y., Judd, K. L., & Xu, R. (2013b). Numerical solutions of dynamic portfolio optimization with transaction costs. NBER Working Paper No. w18709.
  11. Chung, S. L., Hanson, F. B., & Xu, H. H. (1992). Parallel stochastic dynamic programming: Finite element methods. / Linear Algebra and Its Applications, / 172, 197-18. CrossRef
  12. Coleman, W. J. (1992). Solving nonlinear dynamic models on parallel computers. Discussion Paper 66, Institute for Empirical Macroeconomics, Federal Reserve Bank of Minneapolis.
  13. Creel, M. (2005). User-friendly parallel computations with econometric examples. / Computational Economics, / 26(2), 107-28. CrossRef
  14. Creel, M., & Goffe, W. L. (2008). Multi-core CPUs, clusters, and grid computing: A tutorial. / Computational Economics, / 32(4), 353-82. CrossRef
  15. Den Haan, W. J., Judd, K. L., & Juillard, M. (2011). Computational suite of models with heterogeneous agents II: Multi-country real business cycle models. / Journal of Economic Dynamics & Control, / 35, 175-77. CrossRef
  16. Gill, P., Murray, W., Saunders, M. A., & Wright, M. H. (1994). User’s guide for NPSOL 5.0: A Fortran package for nonlinear programming. Technical Report, SOL, Stanford University.
  17. Griebel, M., & Wozniakowski, H. (2006). On the optimal convergence rate of universal and nonuniversal algorithms for multivariate integration and approximation. / Mathematics of Computation, / 75(255), 1259-286. CrossRef
  18. Judd, K. L. (1998). / Numerical methods in economics. Cambridge, MA: The MIT Press.
  19. Juillard, M., & Villemot, S. (2011). Multi-country real business cycle models: Accuracy tests and test bench. / Journal of Economic Dynamics & Control, / 35, 178-85. CrossRef
  20. Morozov, S., & Mathur, S. (2012). Massively parallel computation using graphics processors with application to optimal experimentation in dynamic control. / Computational Economics, / 40(2), 151-82. CrossRef
  21. Pflug, G. C., & Swietanowski, A. (2000). Selected parallel optimization methods for financial management under uncertainty. / Parall
• 作者单位：Yongyang Cai (1) (2)
  Kenneth L. Judd (3)
  Greg Thain (4)
  Stephen J. Wright (4)
  
  1. Hoover Institution, Stanford University, Stanford, CA, USA
  2. Becker Friedman Institute, University of Chicago, Chicago, IL, USA
  3. Hoover Institution, Stanford University & NBER, Stanford, CA, USA
  4. Computer Science Department, University of Wisconsin, Madison, WI?, 53706, USA
  
• 刊物类别：Business and Economics
• 刊物主题：Economics
  Economic Theory
  
• 出版者：Springer Netherlands
• ISSN：1572-9974

文摘

We implement a dynamic programming algorithm on a computational grid consisting of loosely coupled processors, possibly including clusters and individual workstations. The grid changes dynamically during the computation, as processors enter and leave the pool of workstations. The algorithm is implemented using the Master–Worker library running on the HTCondor grid computing platform, which can be deployed on many networks. We implement value function iteration for large dynamic programming problems of two kinds: optimal growth problems and dynamic portfolio problems. We present examples that solve in hours on HTCondor but would take weeks if executed on a single workstation. The cost of using HTCondor is small because it uses CPU resources that otherwise would be idle. The use of HTCondor can increase a researcher’s computational productivity by at least two orders of magnitude.