Hostname: page-component-8448b6f56d-xtgtn Total loading time: 0 Render date: 2024-04-19T19:40:02.542Z Has data issue: false hasContentIssue false
  • English
  • Français

A NONLINEAR PROGRAMMING METHOD FOR DYNAMIC PROGRAMMING

Published online by Cambridge University Press:  18 January 2016

Yongyang Cai ,
Kenneth L. Judd ,
Thomas S. Lontzek ,
Valentina Michelangeli  and
Che-Lin Su
Yongyang Cai*
Affiliation:
Hoover Institution and Becker Friedman Institute, University of Chicago
Kenneth L. Judd
Affiliation:
Hoover Institution
Thomas S. Lontzek
Affiliation:
University of Zurich
Valentina Michelangeli
Affiliation:
Bank of Italy
Che-Lin Su
Affiliation:
The University of Chicago Booth School of Business
*
Address correspondence to: Yongyang Cai, Hoover Institution, Stanford, CA 94305, USA; e-mail: yycai@stanford.edu.
Get access Rights & Permissions [Opens in a new window]

Abstract

A nonlinear programming formulation is introduced to solve infinite-horizon dynamic programming problems. This extends the linear approach to dynamic programming by using ideas from approximation theory to approximate value functions. Our numerical results show that this nonlinear programming is efficient and accurate, and avoids inefficient discretization.

Keywords

Dynamic ProgrammingOptimal ControlNonlinear ProgrammingInfinite-Horizon Decision Making Problem
Type
Articles
Information
Macroeconomic Dynamics , Volume 21 , Issue 2 , March 2017 , pp. 336 - 361
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

Cai, Judd, Lontzek, and Michelangeli note with great sadness the passing of Che-Lin Su this past July. We thank him for his contributions. We are grateful to the editors and anonymous reviewers for their insightful comments and suggestions. We particularly thank Philipp Renner for his many helpful comments. Cai and Judd gratefully acknowledge NSF support (SES-0951576). The views expressed herein are those of the authors and do not necessarily reflect the views of the Bank of Italy.

References

REFERENCES

Bellman, R. (1957) Dynamic Programming. Princeton, NJ: Princeton University Press.Google Scholar
Blackwell, D. (1965) Discounted dynamic programming. Annals of Mathematical Statistics 36 (1), 226–235.Google Scholar
Bojanic, R. and Cheng, F. (1989) Rate of convergence of Bernstein polynomials for functions with derivatives of bounded variation. Journal of Mathematical Analysis and Applications 141, 136–151.Google Scholar
Cai, Y. (2010) Dynamic Programming and Its Application in Economics and Finance. Ph.D. thesis, Stanford University.Google Scholar
Cai, Y. and Judd, K.L. (2010) Stable and efficient computational methods for dynamic programming. Journal of the European Economic Association 8 (2–3), 626–634.Google Scholar
Cai, Y. and Judd, K.L. (2012) Dynamic programming with shape-preserving rational spline Hermite interpolation. Economics Letters 117 (1), 161–164.Google Scholar
Cai, Y. and Judd, K.L. (2013) Shape-preserving dynamic programming. Mathematical Methods of Operations Research 77 (3), 407–421.Google Scholar
Cai, Y. and Judd, K.L. (2014) Advances in numerical dynamic programming and new applications. In Schmedders, Karl and Judd, Kenneth L. (eds.), Handbook of Computational Economics, Vol. 3, Chap. 8. Elsevier.Google Scholar
Cai, Y. and Judd, K.L. (2015) Dynamic programming with Hermite approximation. Mathematical Methods of Operations Research 81, 245–267.Google Scholar
Carnicer, J.M. and Pena, J.M. (1993) Shape preserving representations and optimality of the Bernstein basis. Advances in Computational Mathematics 1 173–196.Google Scholar
De Farias, D.P. and Van Roy, B. (2003) The linear programming approach to approximate dynamic programming. Operations Research 51 (6), 850–865.Google Scholar
Den Haan, W.J., Judd, K.L., and Juillard, M. (2011) Computational suite of models with heterogeneous agents: II. Multi-country real business cycle models. Journal of Economic Dynamics and Control 35, 175–177.Google Scholar
Farouki, R.T. (2012) The Bernstein polynomial basis: A centennial retrospective. Computer Aided Geometric Design 29, 379–419.Google Scholar
Goodman, T.N.T. (1989) Shape preserving representations. In Lyche, T. and Schumaker, L.L. (eds.), Mathematical Methods in Computer Aided Geometric Design, pp. 333–351. Boston: Academic Press.Google Scholar
Judd, K.L. (1998) Numerical Methods in Economics. Cambridge, MA: MIT Press.Google Scholar
Juillard, M. and Villemot, S. (2011) Multi-country real business cycle models: Accuracy tests and test bench. Journal of Economic Dynamics and Control 35, 178–185.Google Scholar
Maliar, L. and Maliar, S. (2004) Endogenous growth and endogenous business cycles. Macroeconomic Dynamics 8 (5), 559–581.Google Scholar
McCarl, B., Meeraus, A., van der Eijk, P., Bussieck, M., Dirkse, S., Steacy, P., and Nelissen, F. (2015) McCarl GAMS User Guide. GAMS Development Corporation. http://www.gams.com/help/index.jsp?topic=%2Fgams.doc%2Fuserguides%2Fmccarl%2Findex.html.Google Scholar
Michelangeli, V. (2009) Economics of the Life-Cycle: Reverse Mortgage, Mortgage and Marriage. Ph.D. thesis, Boston University.Google Scholar
Polak, E. (1997) Optimization: Algorithms and Consistent Approximations. New York: Springer.Google Scholar
Rust, J. (1996) Numerical dynamic programming in economics. In Amman, H., Kendrick, D., and Rust, J. (eds.), Handbook of Computational Economics, Vol. 1, Chap. 14. Elsevier North Holland.Google Scholar
Rust, J. (2008) Dynamic programming. In Durlauf, S.N. and Blume, L.E. (eds.), New Palgrave Dictionary of Economics, 2nd ed. Palgrave Macmillan.Google Scholar
Su, C.H. and Judd, K.L. (2012) Constrained optimization approaches to estimation of structural models. Econometrica 80 (5), 2213–2230.Google Scholar
Trick, M.A. and Zin, S.E. (1997) Spline approximations to value functions—Linear programming approach. Macroeconomic Dynamics 1, 255–277.Google Scholar