Endogenous Gridpoints in Multiple Dimensions: Interpolation on Non-Linear Grids

In dynamic optimization problems with multiple continuous state variables and multiple continuous controls, the method of endogenous gridpoints (ENDG) generates an irregular collection of gridpoints for which standard interpolation techniques do not apply, while alternative interpolation methods are extremely slow. This paper presents an interpolation technique that allows ENDG to be used in multi-dimensional problems in an intuitive and computationally e?cient way. The method translates irregular grid sectors onto the unit square (unit cube, unit hypercube, etc) and then applies standard linear interpolation. This method’s superiority to traditional solution approaches, in terms of speed and accuracy, is demonstrated on a benchmark model. At commonly used grid densities, the method of endogenous gridpoints with non-linear grid interpolation is 7.7 times faster than the traditional solution method, with slightly greater accuracy. This computational acceleration erodes only very slowly as grid density increases, unlike with alternative interpolation methods.