IDEAS home Printed from https://ideas.repec.org/a/kap/compec/v55y2020i3d10.1007_s10614-019-09921-y.html
   My bibliography  Save this article

Solving Stochastic Dynamic Programming Problems: A Mixed Complementarity Approach

Author

Listed:
  • Wonjun Chang

    (CRA International)

  • Michael C. Ferris

    (University of Wisconsin-Madison
    Optimization Group, Wisconsin Institutes for Discovery)

  • Youngdae Kim

    (Mathematics and Computer Science Division, Argonne National Laboratory)

  • Thomas F. Rutherford

    (University of Wisconsin-Madison
    Optimization Group, Wisconsin Institutes for Discovery)

Abstract

We present a mixed complementarity problem (MCP) formulation of continuous state dynamic programming problems (DP-MCP). We write the solution to projection methods in value function iteration (VFI) as a joint set of optimality conditions that characterize maximization of the Bellman equation; and approximation of the value function. The MCP approach replaces the iterative component of projection based VFI with a one-shot solution to a square system of complementary conditions. We provide three numerical examples to illustrate our approach.

Suggested Citation

  • Wonjun Chang & Michael C. Ferris & Youngdae Kim & Thomas F. Rutherford, 2020. "Solving Stochastic Dynamic Programming Problems: A Mixed Complementarity Approach," Computational Economics, Springer;Society for Computational Economics, vol. 55(3), pages 925-955, March.
    • Handle: RePEc:kap:compec:v:55:y:2020:i:3:d:10.1007_s10614-019-09921-y
    DOI: 10.1007/s10614-019-09921-y
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10614-019-09921-y
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10614-019-09921-y?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Jean‐Pierre Dubé & Jeremy T. Fox & Che‐Lin Su, 2012. "Improving the Numerical Performance of Static and Dynamic Aggregate Discrete Choice Random Coefficients Demand Estimation," Econometrica, Econometric Society, vol. 80(5), pages 2231-2267, September.
    2. Yongyang Cai & Kenneth Judd & Greg Thain & Stephen Wright, 2015. "Solving Dynamic Programming Problems on a Computational Grid," Computational Economics, Springer;Society for Computational Economics, vol. 45(2), pages 261-284, February.
    3. Christian Traeger, 2014. "Why uncertainty matters: discounting under intertemporal risk aversion and ambiguity," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(3), pages 627-664, August.
    4. Che‐Lin Su & Kenneth L. Judd, 2012. "Constrained Optimization Approaches to Estimation of Structural Models," Econometrica, Econometric Society, vol. 80(5), pages 2213-2230, September.
    5. Tauchen, George, 1986. "Finite state markov-chain approximations to univariate and vector autoregressions," Economics Letters, Elsevier, vol. 20(2), pages 177-181.
    6. Yongyang Cai & Kenneth Judd & Jevgenijs Steinbuks, 2017. "A nonlinear certainty equivalent approximation method for dynamic stochastic problems," Quantitative Economics, Econometric Society, vol. 8(1), pages 117-147, March.
    7. Derek Lemoine & Christian P. Traeger, 2016. "Economics of tipping the climate dominoes," Nature Climate Change, Nature, vol. 6(5), pages 514-519, May.
    8. Derek Lemoine & Christian Traeger, 2014. "Watch Your Step: Optimal Policy in a Tipping Climate," American Economic Journal: Economic Policy, American Economic Association, vol. 6(1), pages 137-166, February.
    9. Judd, Kenneth L. & Maliar, Lilia & Maliar, Serguei & Valero, Rafael, 2014. "Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain," Journal of Economic Dynamics and Control, Elsevier, vol. 44(C), pages 92-123.
    10. Ferris, Michael C. & Munson, Todd S., 2000. "Complementarity problems in GAMS and the PATH solver," Journal of Economic Dynamics and Control, Elsevier, vol. 24(2), pages 165-188, February.
    11. Rutherford, Thomas F., 1995. "Extension of GAMS for complementarity problems arising in applied economic analysis," Journal of Economic Dynamics and Control, Elsevier, vol. 19(8), pages 1299-1324, November.
    12. Aruoba, S. Boragan & Fernandez-Villaverde, Jesus & Rubio-Ramirez, Juan F., 2006. "Comparing solution methods for dynamic equilibrium economies," Journal of Economic Dynamics and Control, Elsevier, vol. 30(12), pages 2477-2508, December.
    13. Christian Traeger, 2014. "A 4-Stated DICE: Quantitatively Addressing Uncertainty Effects in Climate Change," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 59(1), pages 1-37, September.
    14. Lau, Morten I. & Pahlke, Andreas & Rutherford, Thomas F., 2002. "Approximating infinite-horizon models in a complementarity format: A primer in dynamic general equilibrium analysis," Journal of Economic Dynamics and Control, Elsevier, vol. 26(4), pages 577-609, April.
    15. Yongyang Cai & Kenneth Judd, 2015. "Dynamic programming with Hermite approximation," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 81(3), pages 245-267, June.
    16. Fernández-Villaverde, Jesús & Gordon, Grey & Guerrón-Quintana, Pablo & Rubio-Ramírez, Juan F., 2015. "Nonlinear adventures at the zero lower bound," Journal of Economic Dynamics and Control, Elsevier, vol. 57(C), pages 182-204.
    17. Kenneth L. Judd, 1998. "Numerical Methods in Economics," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262100711, December.
    18. Krueger, Dirk & Kubler, Felix, 2004. "Computing equilibrium in OLG models with stochastic production," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1411-1436, April.
    19. Derek Lemoine & Ivan Rudik, 2017. "Managing Climate Change Under Uncertainty: Recursive Integrated Assessment at an Inflection Point," Annual Review of Resource Economics, Annual Reviews, vol. 9(1), pages 117-142, October.
    20. Rasmussen, Tobias N. & Rutherford, Thomas F., 2004. "Modeling overlapping generations in a complementarity format," Journal of Economic Dynamics and Control, Elsevier, vol. 28(7), pages 1383-1409, April.
    21. Rudik, Ivan, 2016. "Optimal Climate Policy When Damages are Unknown," ISU General Staff Papers 201611130800001011, Iowa State University, Department of Economics.
    22. Mario J. Miranda & Paul L. Fackler, 2004. "Applied Computational Economics and Finance," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633094, December.
    23. Unknown, 1986. "Letters," Choices: The Magazine of Food, Farm, and Resource Issues, Agricultural and Applied Economics Association, vol. 1(4), pages 1-9.
    24. Rust, John, 1996. "Numerical dynamic programming in economics," Handbook of Computational Economics, in: H. M. Amman & D. A. Kendrick & J. Rust (ed.), Handbook of Computational Economics, edition 1, volume 1, chapter 14, pages 619-729, Elsevier.
    25. Derek Lemoine & Ivan Rudik, 2017. "Managing Climate Change Under Uncertainty: Recursive Integrated Assessment at an Inflection Point," Annual Review of Economics, Annual Reviews, vol. 9(1), pages 117-142, October.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Guo, Peijun, 2022. "Dynamic focus programming: A new approach to sequential decision problems under uncertainty," European Journal of Operational Research, Elsevier, vol. 303(1), pages 328-336.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Fernández-Villaverde, J. & Rubio-Ramírez, J.F. & Schorfheide, F., 2016. "Solution and Estimation Methods for DSGE Models," Handbook of Macroeconomics, in: J. B. Taylor & Harald Uhlig (ed.), Handbook of Macroeconomics, edition 1, volume 2, chapter 0, pages 527-724, Elsevier.
    2. Kenneth L. Judd & Lilia Maliar & Serguei Maliar & Inna Tsener, 2017. "How to solve dynamic stochastic models computing expectations just once," Quantitative Economics, Econometric Society, vol. 8(3), pages 851-893, November.
    3. Barillas, Francisco & Fernandez-Villaverde, Jesus, 2007. "A generalization of the endogenous grid method," Journal of Economic Dynamics and Control, Elsevier, vol. 31(8), pages 2698-2712, August.
    4. Yongyang Cai & Kenneth L. Judd, 2023. "A simple but powerful simulated certainty equivalent approximation method for dynamic stochastic problems," Quantitative Economics, Econometric Society, vol. 14(2), pages 651-687, May.
    5. Arellano, Cristina & Maliar, Lilia & Maliar, Serguei & Tsyrennikov, Viktor, 2016. "Envelope condition method with an application to default risk models," Journal of Economic Dynamics and Control, Elsevier, vol. 69(C), pages 436-459.
    6. Yongyang Cai & Kenneth Judd & Jevgenijs Steinbuks, 2017. "A nonlinear certainty equivalent approximation method for dynamic stochastic problems," Quantitative Economics, Econometric Society, vol. 8(1), pages 117-147, March.
    7. Yongyang Cai, 2020. "The Role of Uncertainty in Controlling Climate Change," Papers 2003.01615, arXiv.org, revised Oct 2020.
    8. Ivan Rudik & Derek Lemoine & Maxwell Rosenthal, 2018. "General Bayesian Learning in Dynamic Stochastic Models: Estimating the Value of Science Policy," 2018 Meeting Papers 369, Society for Economic Dynamics.
    9. Aruoba, S. Boragan & Fernandez-Villaverde, Jesus & Rubio-Ramirez, Juan F., 2006. "Comparing solution methods for dynamic equilibrium economies," Journal of Economic Dynamics and Control, Elsevier, vol. 30(12), pages 2477-2508, December.
    10. Serguei Maliar & John Taylor & Lilia Maliar, 2016. "The Impact of Alternative Transitions to Normalized Monetary Policy," 2016 Meeting Papers 794, Society for Economic Dynamics.
    11. Marlon Azinovic & Luca Gaegauf & Simon Scheidegger, 2022. "Deep Equilibrium Nets," International Economic Review, Department of Economics, University of Pennsylvania and Osaka University Institute of Social and Economic Research Association, vol. 63(4), pages 1471-1525, November.
    12. Yasuo Hirose & Takeki Sunakawa, 2019. "Review of Solution and Estimation Methods for Nonlinear Dynamic Stochastic General Equilibrium Models with the Zero Lower Bound," The Japanese Economic Review, Springer, vol. 70(1), pages 51-104, March.
    13. van der Ploeg, Frederick & ,, 2018. "Pricing Carbon Under Economic and Climactic Risks: Leading-Order Results from Asymptotic Analysis," CEPR Discussion Papers 12642, C.E.P.R. Discussion Papers.
    14. Aldrich Eric Mark & Kung Howard, 2021. "Computational Methods for Production-Based Asset Pricing Models with Recursive Utility," Studies in Nonlinear Dynamics & Econometrics, De Gruyter, vol. 25(1), pages 1-26, February.
    15. Lilia Maliar & Serguei Maliar & John B. Taylor & Inna Tsener, 2020. "A tractable framework for analyzing a class of nonstationary Markov models," Quantitative Economics, Econometric Society, vol. 11(4), pages 1289-1323, November.
    16. Yongyang Cai & Thomas S. Lontzek, 2019. "The Social Cost of Carbon with Economic and Climate Risks," Journal of Political Economy, University of Chicago Press, vol. 127(6), pages 2684-2734.
    17. Svenn Jensen & Christian P. Traeger & Christian Träger, 2021. "Pricing Climate Risk," CESifo Working Paper Series 9196, CESifo.
    18. Dominika Czyz & Karolina Safarzynska, 2023. "Catastrophic Damages and the Optimal Carbon Tax Under Loss Aversion," Environmental & Resource Economics, Springer;European Association of Environmental and Resource Economists, vol. 85(2), pages 303-340, June.
    19. Andrew Foerster & Juan F. Rubio‐Ramírez & Daniel F. Waggoner & Tao Zha, 2016. "Perturbation methods for Markov‐switching dynamic stochastic general equilibrium models," Quantitative Economics, Econometric Society, vol. 7(2), pages 637-669, July.
    20. Sandra Gschnaller, 2020. "The albedo loss from the melting of the Greenland ice sheet and the social cost of carbon," Climatic Change, Springer, vol. 163(4), pages 2201-2231, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:kap:compec:v:55:y:2020:i:3:d:10.1007_s10614-019-09921-y. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.