# Finite Differences on Sparse Grids for Continuous-Time Heterogeneous Agent Models
## 3 Sparse Grids
### (Non-)Convergence of Sparse Grid Finite Difference Schemes for Solving the HJB Equation  
The requirements one needs to fulfill to obtain a convergent approximation scheme for HJB equations by means of Barles and Souganidis [11] involve a stable, consistent, and monotone scheme. While it is trivial to show that one needs monotone interpolation, interpolation on sparse grids is not monotone in general, as it is already pointed out in [36]; see also [32]. Since we are approximating value functions arising from economic models, it is of interest if one can achieve monotonicity by restricting ourselves to concave monotonically increasing functions as they arise for the employed models. Ref. [9] notes that the introduced upwind finite difference scheme converges even though the scheme is not monotone. However, Ref. [9] does not give examples or justifications that it is not monotone.  
In just one dimension, the scheme is monotone since it is uses standard linear interpolation. Observe that we only need one-dimensional monotonicity per dimension, that is with respect to the used ghost points.  
Let us give a definition of monotone interpolation.  
**Definition 4** (Monotone interpolation in one dimension).: _Let \(x_{1},\ldots,x_{n}\) be data points with \(x_{1}<\ldots<x_{n}\). A function \(f\) is called monotone if it holds that \(f(x_{1})\leq\ldots\leq f(x_{n})\) or \(f(x_{1})\geq\ldots\geq f(x_{n})\). In case of strict inequalities \(f\) is strictly monotone. The interpolation \(f_{1}\) of \(f\) is monotone, if for every pair of two points \(\tilde{x}_{1}<\tilde{x}_{2},\ \tilde{x}_{1},\tilde{x}_{2}\in[x_{1},x_{n}]\) it holds_  
\[f_{1}(\tilde{x}_{1})\leq f_{1}(\tilde{x}_{2})\text{ for }f(\tilde{x}_{1}) \leq f(\tilde{x}_{2})\]  
_or_  
\[f_{1}(\tilde{x}_{1})\geq f_{1}(\tilde{x}_{2})\text{ for }f(\tilde{x}_{1}) \geq f(\tilde{x}_{2}),\]with strict inequality for strictly monotone interpolation._  
Note that we are interested in higher dimensions and aim for one-dimensional monotone interpolation for the restriction to the different dimensions.  
Non-Monotone Sparse Grid Interpolation for Concave Monotonically Increasing Functions  
We give a counter example to show that sparse grid interpolation for monotonically increasing concave functions is not monotone in general. To achieve this, we give concave monotonically increasing functions for which negative hierarchical coefficients arise. Let us consider the interpolation of the function  
\[f_{1}(x,y)=\frac{-1}{1+10x+10y}+50,\]  
which is similar to functions that arise as value functions for some models. Computing the eigenvalues of the Hessian shows that it is negative semidefinite in \([0,1]^{2}\) and thus the function is concave, but note that it is not strictly concave. Unfortunately, we see in the function plots in Figure 2 and the contour plots in Figure 3 that the interpolation is not monotone. Increasing the factors in front of \(x\) and \(y\) increases this effect. Here, we use a sparse grid level \(l=3\), but corresponding counter examples can be constructed for other levels.  
Note further that the above interpolation is in particular not monotone with respect to the points used for our sparse grid finite differences. In Figure 4, one can see that the value shown in red is higher than the one in green. Thus, even if we restrict ourselves to the ghost points, we do not have the monotonicity we hoped for.  
Figure 3: Contour plots of the function \(f_{1}\) on the left and its sparse grid interpolation of level \(l=3\) on the right.  
Figure 2: Plots of the original function \(f_{1}\) on the left and its sparse grid interpolation of level \(l=3\) on the right.  
Strictly_ concave functions can also yield non-monotone sparse grid interpolation, e.g., \(f_{2}(x,y)=-1/(1+(x+0.01)^{0.2}+(y+0.01)^{0.2})+50\). Here, one can check the concavity by using the leading principal minors criteria. Finally, we point out that one cannot simply set the negative hierarchical coefficients to zero to obtain a monotone approximation.