A generalized endogenous grid method for discrete-continuous choice

Preprint OPEN
John Rust ; Bertel Schjerning ; Fedor Iskhakov (2012)

This paper extends Carroll's endogenous grid method (2006 "The method of endogenous gridpoints for solving dynamic stochastic optimization problems", Economic Letters) for models with sequential discrete and continuous choice. Unlike existing generalizations, we propose solution algorithm that inherits both advantages of the original method, namely it avoids all root finding operations, and also efficiently deals with restrictions on the continuous decision variable. To further speed up the solution, we perform the inevitable optimization across discrete decisions as more efficient computation of upper envelope of a set of piece-wise linear functions. We formulate the algorithm relying as little as possible on a particular model specification, and precisely define the class of dynamic stochastic optimal control problems it can be applied to. We illustrate our algorithm using finite horizon discrete sector choice model with consumption-savings decisions and borrowing constraints, and show that in comparison to the traditional approach the proposed method runs at least an order of magnitude faster to deliver the same precision of the solution. To implement the method we develop a generic software package that includes pseudo-language for easy model specification and computational modules which support both shared memory and cluster parallelization. The package is wrapped in a Matlab class and incurs low start-up cost to the user. The software package is accessible in public domain.
  • References (9)

    Andrew Clausen and Carlo Strub. Envelope theorems for non-smooth and non-concave optimization. Preliminary and incomplete, version of February 14, 2011.

    Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry, 4:311-336, 1989. ISSN 0179-5376. URL http://dx.doi.org/10.1007/BF02187733. 10.1007/BF02187733.

    Giulio Fella. A generalized endogenous grid method for non-concave problems. School of Economics and Finance, Queen Mary University of London Working Paper, N. 677, 2011.

    János Pach and Micha Sharir. The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis. Discrete & Computational Geometry, 4:291-309, 1989. ISSN 0179-5376. URL http://dx.doi.org/10.1007/BF02187732. 10.1007/BF02187732.

    George Tauchen. Finite state markov-chain approximations vector autoregressions. Economics Letters, 20(2):177-181, http://ideas.repec.org/a/eee/ecolet/v20y1986i2p177-181.html.

    1. Allow a0 = M . Calculate m(a0). If m(a0) M , set ba = a0, mb = m(a0) and proceed to next step, otherwise let a0 21 (a0 + A0) and repeat this step.

    2. Set i = 0 ai = A0 and calculate m(ai).

    3. Find ai such that the straight line through (ai; m(ai)) and (ba; mb) takes value M at ai.

    4. Divide the interval (ai; ai) into n

  • Metrics
    No metrics available
Share - Bookmark