A fast upper envelope scan method for discrete-continuous dynamic programming

Loretti I. Dobrescu and Akshay Shanker

Abstract: We introduce a fast upper envelope scan (FUES) method to solve and estimate dynamic programming problems with discrete and continuous choices. FUES builds on the standard endogenous grid method (EGM). EGM applied to problems with continuous and discrete choices, however, does not by itself generate the optimal solution, as the first order conditions used to retrieve the endogenous grid are necessary but not sufficient. FUES sequentially checks the secant lines between EGM candidate solution points and eliminates those not on the upper envelope of the value correspondence by only allowing discontinuities in the policy function at non-concave regions of the value correspondence. Unlike previous methods used to perform EGM in discrete-continuous dynamic models, FUES does not require the monotonicity of the policy functions or analytical information of the value function gradient. It is also computationally efficient, straightforward to implement, and for sufficiently large EGM grid sizes, guaranteed to recover the optimal solution.

Key Words: discrete and continuous choices, non-convex optimization, Euler equation, computational methods, dynamic programming