Introduction
In this paper, we consider a system of coupled first order Hamilton–Jacobi–Bellman equations with recursive utility, recently analyzed in [5, 4]. Such a system of equations arises from the Aiyagari–Bewley–Huggett type heterogeneous agent (HA for brevity) models in macroeconomic theory [22], extended to continuous time in [2]. HA models provide a standard framework for studying consumption–saving decisions, wealth distributions, and equilibrium asset prices in incomplete markets. By incorporating idiosyncratic income risk and borrowing constraints, these models capture the interaction between individual saving behavior and the distribution of wealth in general equilibrium. Their numerical solution involves Hamilton–Jacobi–Bellman (HJB) equations coupled with equations describing the invariant distribution of agents and the equilibrium conditions for asset prices.
The HJB equation for characterizing the agent’s consumption–saving decision involves the Epstein–Zin recursive utility, which is specified through the aggregator (cf. [26])
f ( c , v ) = ρ 1 − ψ − 1 c 1 − ψ − 1 − ( ( 1 − γ ) v ) θ ( ( 1 − γ ) v ) θ − 1 , θ = 1 − ψ − 1 1 − γ . (1) f(c,v)=\frac{\rho}{1-\psi^{-1}}\frac{c^{1-\psi^{-1}}-((1-\gamma)v)^\theta}{((1-\gamma)v)^{\theta-1}},\qquad\theta=\frac{1-\psi^{-1}}{1-\gamma}. \tag*{(1)} f ( c , v ) = 1 − ψ − 1 ρ (( 1 − γ ) v ) θ − 1 c 1 − ψ − 1 − (( 1 − γ ) v ) θ , θ = 1 − γ 1 − ψ − 1 . (1)
In (1) , c c c denotes consumption, v v v is the value function, ρ \rho ρ is the subjective discount rate, ψ \psi ψ is the elasticity of intertemporal substitution (EIS), and γ \gamma γ is the coefficient of relative risk aversion. We focus on the parameter region 0 < ψ < 1 0 < \psi< 1 0 < ψ < 1 and γ > 1 \gamma> 1 γ > 1 . The time-additive constant relative risk aversion (CRRA) specification is recovered when γ = ψ − 1 \gamma= \psi^{-1} γ = ψ − 1 . The parameter θ \theta θ determines the preference for the timing of the resolution of uncertainty: early resolution is preferred when θ < 1 \theta< 1 θ < 1 , while late resolution is preferred when θ > 1 \theta> 1 θ > 1 [19].
The system of HJB equations with recursive utility and a given interest rate r r r is
0 = max c ≥ 0 { f ( c , v j ) + ( r x + y j − c ) D v j ( x ) } + λ j ( v j ˉ ( x ) − v j ( x ) ) , j ∈ { 1 , 2 } , j ˉ = 3 − j . (2) 0 = \max_{c \ge0} \left\{ f(c,v_j) + (rx+y_j-c)D v_j(x) \right\} + \lambda_j\left(v_{\bar{j}}(x)-v_j(x)\right), \qquad j \in\{1,2\},\quad\bar{j}=3-j. \tag*{(2)} 0 = c ≥ 0 max { f ( c , v j ) + ( r x + y j − c ) D v j ( x ) } + λ j ( v j ˉ ( x ) − v j ( x ) ) , j ∈ { 1 , 2 } , j ˉ = 3 − j . (2)
The equations are coupled through the switching terms λ j ( v j ˉ − v j ) \lambda_j(v_{\bar{j}}-v_j) λ j ( v j ˉ − v j ) , encoding the transitions between income states with Poisson rates λ j \lambda_j λ j . The state constraint x ≥ x ‾ x \ge\underline{x} x ≥ x (a borrowing limit) is imposed to prevent negative savings at x ‾ \underline{x} x : r x + y j − c j ( x ) ≥ 0 rx+y_j-c_j(x) \ge0 r x + y j − c j ( x ) ≥ 0 .
As a first theoretical contribution, we prove a comparison principle for solutions of (2) in the case of preference for early resolution of uncertainty, i.e. 0 < θ < 1 0 < \theta< 1 0 < θ < 1 . The uniqueness of solutions to this type of problem in the discrete-time setting has been analyzed in [23, 24, 25]. In the continuous-time setting, the strong comparison principle (between semicontinuous sub- and supersolutions) in the case θ = 1 \theta= 1 θ = 1 has been established in [13] and then extended to θ > 1 \theta> 1 θ > 1 in [5]. The main difficulty in the case 0 < θ < 1 0 < \theta< 1 0 < θ < 1 is that the nonlinear part of the aggregator f ( c , v ) f(c,v) f ( c , v ) in (2) becomes an increasing function for the v v v -argument. The existence of extremal solutions has been addressed in [4] but the uniqueness of solution was not established. In this paper we exploit an ordinal transformation of the recursive utility problem to obtain a more tractable equivalent representation. Because the transformation is invertible, comparison principle in the transformed representation translates into that of the original problem. This yields a self-contained proof of uniqueness to the HJB equation in the parameter regime 0 < θ < 1 0 < \theta< 1 0 < θ < 1 . Similar changes of variables have been used in [6, 18] for second order HJB equation involving recursive utility.
We next address the numerical solution of such HJB systems and related H A HA H A models. The finite difference methods for solving (2) have been considered recently in [4]. Building on the semi-Lagrangian framework for state-constrained heterogeneous agent models with time-additive CRRA utility developed in [13], we extend the HJB discretization to Epstein–Zin recursive utility, whose nonlinear dependence on the value function requires new analytical arguments and iterative algorithms. SL methods discretize the dynamic programming principle by following the controlled dynamics over a discrete time interval and evaluating the value function at the resulting off-grid points through interpolation. We refer to [8, 20] for the theoretical foundations, to [10] for approximation of coupled HJB systems, to [15] for convergence rate analysis and to [16, 7] for SL schemes for Mean Field Games. Concerning iterative algorithms, [14] studied a learning value iteration algorithm and its acceleration by policy iteration for a semi-Lagrangian discretization of Mean Field Games. In the abstract dynamic programming framework, [25, 23] developed monotonicity-based and order-theoretic approaches to establish convergence of iterative algorithms, for solving problems with recursive preferences.
We consider the underlying stochastic control problem associated with the Epstein–Zin utility, cf. [17, 18, 26]:
v ( x , y ) = sup c τ E [ ∫ t ∞ f ( c τ , v τ ) d τ | x t = x , y t = y ] , s.t. { d x τ = ( r x τ + y τ − c τ ) d τ , τ > t , x τ ≥ x ‾ . (3) v(x,y)=\sup_{c_\tau}\mathbb{E}\left[\int_t^\infty f(c_\tau,v_\tau)\,\mathrm{d}\tau\,\middle|\, x_t=x,\ y_t=y\right],\qquad\text{s.t.}\quad\left\{\begin{aligned}
\mathrm{d}x_\tau&= (rx_\tau+y_\tau-c_\tau)\,\mathrm{d}\tau,\quad\tau>t,\\
x_\tau&\ge\underline{x}.
\end{aligned}\right. \tag*{(3)} v ( x , y ) = c τ sup E [ ∫ t ∞ f ( c τ , v τ ) d τ x t = x , y t = y ] , s.t. { d x τ x τ = ( r x τ + y τ − c τ ) d τ , τ > t , ≥ x . (3)
Here, x τ x_\tau x τ and y τ y_\tau y τ respectively stand for the agent’s wealth and labor income at time τ \tau τ . The control variable is the consumption c τ c_\tau c τ and the flow f f f depends also on the continuation value v τ = v ( x τ , y τ ) v_\tau= v(x_\tau, y_\tau) v τ = v ( x τ , y τ ) . It is assumed that y τ y_\tau y τ is a two-state continuous-time Markov chain with Poisson switching rates. We observe that the same ordinal equivalent transformation for the HJB equation can also apply to the SL scheme, which allows us to establish a discrete comparison principle in the case 0 < θ < 1 0 < \theta< 1 0 < θ < 1 . Building on the Howard policy iteration in [13], we develop a Howard–Newton algorithm in which the nonlinear policy evaluation arising from recursive utility is performed using Newton’s method. We prove convergence of the outer policy iteration in both the late- and early-resolution preference regimes. As an alternative, in the early-resolution case 0 < θ < 1 0 < \theta< 1 0 < θ < 1 , we formulate the discrete problem as a fixed point of a monotone and invariant map and develop a corresponding value iteration algorithm.
This paper is organized as follows. In § 2 , we introduce the relevant background and previous results for the HJB equation, building on [5, 4]. In § 3 , we prove the comparison principle and uniqueness of solution to the HJB equation in the case 0 < θ < 1 0 < \theta< 1 0 < θ < 1 (a result which is not available in [5, 4]), based on an ordinal equivalent transformation. In § 4 , we propose an SL scheme. We develop a Howard–Newton algorithm and prove a discrete comparison principle for the solution to the scheme. In the early-resolution case, we propose additionally a monotone value iteration algorithm. For the late-resolution case, the SL scheme has a first-order convergence rate to the unique solution of the HJB equation. In § 5 , we give the solution methods for the Fokker–Planck–Kolmogorov (FPK) equations and a general equilibrium Mean Field Game model. Finally, numerical experiments in § 6 demonstrate the effectiveness of the proposed methods and confirm their agreement with the results obtained using the finite difference methods from [4].
Preliminaries
The assumptions that follow will be made in the whole paper:
γ > 1 , 0 < ψ < 1 , ρ > r > 0 , y 2 > y 1 > 0 , x ≤ 0 , ρ x + y 1 > 0. (4) \gamma> 1,\quad0 < \psi< 1,\quad\rho> r > 0,\quad y_2 > y_1 > 0,\quad x \le0,\quad\rho x + y_1 > 0. \tag*{(4)} γ > 1 , 0 < ψ < 1 , ρ > r > 0 , y 2 > y 1 > 0 , x ≤ 0 , ρ x + y 1 > 0. (4)
It has been proved in [5] that the equilibrium interest rate r ∗ r^* r ∗ is smaller than ρ \rho ρ , if there exists a solution to (5.3) below. This justifies the bounds on r r r in (2.1). With the constant b b b defined in Table 1 below, (2.1) yields r < b < ρ r < b < \rho r < b < ρ , r x + y 2 > r x + y 1 > 0 rx + y_2 > rx + y_1 > 0 r x + y 2 > r x + y 1 > 0 and b ( x + y 1 / r ) > 0 b(x + y_1/r) > 0 b ( x + y 1 / r ) > 0 . Therefore, the functions in (2.10) below are well defined.
We observe that the Epstein–Zin utility can be decomposed as, using ρ / θ = ζ \rho/\theta= \zeta ρ / θ = ζ ,
f ( c , v j ) = F ( c , v j ) − ζ v j , F ( c , v j ) = ρ 1 − ψ − 1 ( ( 1 − γ ) v j ) θ − 1 c 1 − ψ − 1 . (5) f(c,v_j) = \mathcal{F}(c,v_j) - \zeta v_j,\qquad\mathcal{F}(c,v_j) = \frac{\rho}{1-\psi^{-1}((1-\gamma)v_j)^{\theta-1}}c^{1-\psi^{-1}}. \tag*{(5)} f ( c , v j ) = F ( c , v j ) − ζ v j , F ( c , v j ) = 1 − ψ − 1 (( 1 − γ ) v j ) θ − 1 ρ c 1 − ψ − 1 . (5)
We use (2.2) to rewrite the HJB equation (1.2) as
ρ θ v j ( x ) = H ( x , y j , v j , D v j ) + λ j ( v j ˉ ( x ) − v j ( x ) ) , (6) \frac{\rho}{\theta}v_j(x) = H(x,y_j,v_j,Dv_j) + \lambda_j\left(v_{\bar{j}}(x)-v_j(x)\right), \tag*{(6)} θ ρ v j ( x ) = H ( x , y j , v j , D v j ) + λ j ( v j ˉ ( x ) − v j ( x ) ) , (6)
where we use the notation from (2.2) and
H ( x , y j , v j , p ) : = max c ≥ 0 { F ( c , v j ) + ( r x + y j − c ) p } . (7) H(x,y_j,v_j,p) := \max_{c\ge0}\left\{\mathcal{F}(c,v_j) + (rx+y_j-c)p\right\}. \tag*{(7)} H ( x , y j , v j , p ) := c ≥ 0 max { F ( c , v j ) + ( r x + y j − c ) p } . (7)
From the first order necessary optimality condition, the Hamiltonian in (7) is
H ( x , y , v , p ) = { ( r x + y ) p + ρ ψ ψ − 1 p 1 − ψ ( ( 1 − γ ) v ) 1 − γ ψ 1 − γ , if p ≥ 0 , + ∞ , if p < 0. (8) H(x,y,v,p)=\begin{cases}
(rx+y)p+\dfrac{\rho^\psi}{\psi-1}p^{1-\psi}\bigl((1-\gamma)v\bigr)^{\frac{1-\gamma\psi}{1-\gamma}}, & \text{if } p\ge0,\\
+\infty, & \text{if } p<0.
\end{cases} \tag*{(8)} H ( x , y , v , p ) = ⎩ ⎨ ⎧ ( r x + y ) p + ψ − 1 ρ ψ p 1 − ψ ( ( 1 − γ ) v ) 1 − γ 1 − γ ψ , + ∞ , if p ≥ 0 , if p < 0. (8)
We observe that H ( x , y , v , p ) H(x,y,v,p) H ( x , y , v , p ) defined in (8) is strictly convex in p p p for fixed ( x , y , v ) (x,y,v) ( x , y , v ) with p > 0 p>0 p > 0 . The optimal consumption (away from the borrowing limit) is given by the first order necessary optimality condition, whenever D v j > 0 Dv_j>0 D v j > 0 ,
c j = arg max c ≥ 0 { F ( c , v j ) − c D v j } = ρ ψ ( D v j ) − ψ ( ( 1 − γ ) v j ) 1 − γ ψ 1 − γ . (9) c_j=\underset{c\ge0}{\arg\max}\left\{\mathcal{F}(c,v_j)-cDv_j\right\}=\rho^\psi(Dv_j)^{-\psi}\bigl((1-\gamma)v_j\bigr)^{\frac{1-\gamma\psi}{1-\gamma}}. \tag*{(9)} c j = c ≥ 0 arg max { F ( c , v j ) − cD v j } = ρ ψ ( D v j ) − ψ ( ( 1 − γ ) v j ) 1 − γ 1 − γ ψ . (9)
We summarize the notation in Table 1 .
Table 1. Symbols
For any c > 0 c>0 c > 0 , if θ > 1 \theta>1 θ > 1 (resp. 0 < θ < 1 0<\theta<1 0 < θ < 1 ) then F ( c , v ) \mathcal{F}(c,v) F ( c , v ) is decreasing (resp. increasing) in v v v , i.e.
F v ( c , v ) < 0 ( resp. F v ( c , v ) > 0 ) . (10) \mathcal{F}_v(c,v)<0\quad(\text{resp. }\mathcal{F}_v(c,v)>0). \tag*{(10)} F v ( c , v ) < 0 ( resp. F v ( c , v ) > 0 ) . (10)
If θ > 1 \theta>1 θ > 1 , then f ( c , v ) f(c,v) f ( c , v ) and F ( c , v ) \mathcal{F}(c,v) F ( c , v ) are jointly concave in ( c , v ) ∈ ( 0 , + ∞ ) × ( − ∞ , 0 ) (c,v)\in(0,+\infty)\times(-\infty,0) ( c , v ) ∈ ( 0 , + ∞ ) × ( − ∞ , 0 ) .
Definition 2.1.
An upper semicontinuous (u.s.c.) function v = ( v 1 , v 2 ) v=(v_1,v_2) v = ( v 1 , v 2 ) is said to be a viscosity subsolution of (6) at x x x , if whenever φ \varphi φ is a smooth function and v j − φ v_j-\varphi v j − φ has a local maximum at x x x , then
ρ θ v j ( x ) ≤ H ( x , y j , v j ( x ) , D φ ( x ) ) + λ j ( v j ˉ ( x ) − v j ( x ) ) . (11) \dfrac{\rho}{\theta}v_j(x)\le H(x,y_j,v_j(x),D\varphi(x))+\lambda_j(v_{\bar j}(x)-v_j(x)). \tag*{(11)} θ ρ v j ( x ) ≤ H ( x , y j , v j ( x ) , D φ ( x )) + λ j ( v j ˉ ( x ) − v j ( x )) . (11) A lower semicontinuous (l.s.c.) function v = ( v 1 , v 2 ) v=(v_1,v_2) v = ( v 1 , v 2 ) is said to be a viscosity supersolution of (6) at x x x , if whenever φ \varphi φ is a smooth function and v j − φ v_j-\varphi v j − φ has a local minimum at x x x , then
ρ θ v j ( x ) ≥ H ( x , y j , v j ( x ) , D φ ( x ) ) + λ j ( v j ˉ ( x ) − v j ( x ) ) . (12) \dfrac{\rho}{\theta}v_j(x)\ge H(x,y_j,v_j(x),D\varphi(x))+\lambda_j(v_{\bar j}(x)-v_j(x)). \tag*{(12)} θ ρ v j ( x ) ≥ H ( x , y j , v j ( x ) , D φ ( x )) + λ j ( v j ˉ ( x ) − v j ( x )) . (12) A continuous function v v v is said to be a constrained viscosity solution to system (6) if v v v is a viscosity supersolution in ( x ‾ , ∞ ) (\underline{x},\infty) ( x , ∞ ) and a viscosity subsolution in [ x ‾ , ∞ ) [\underline{x},\infty) [ x , ∞ ) .
The sub- and supersolutions proposed below will play an important role in what follows.
Proposition 2.2. With the constant b b b defined in Table 1 , let y ˉ > y 2 \bar{y}>y_2 y ˉ > y 2 and consider the functions
u ˇ 1 ( x ) = u ˇ 2 ( x ) = ( r x + y 1 ) 1 − γ 1 − γ , v ˇ 1 ( x ) = v ˇ 2 ( x ) = ( b ( x + y ˉ / r ) ) 1 − γ 1 − γ . (13) \check{u}_1(x)=\check{u}_2(x)=\frac{(rx+y_1)^{1-\gamma}}{1-\gamma},\qquad\check{v}_1(x)=\check{v}_2(x)=\frac{\left(b(x+\bar{y}/r)\right)^{1-\gamma}}{1-\gamma}. \tag*{(13)} u ˇ 1 ( x ) = u ˇ 2 ( x ) = 1 − γ ( r x + y 1 ) 1 − γ , v ˇ 1 ( x ) = v ˇ 2 ( x ) = 1 − γ ( b ( x + y ˉ / r ) ) 1 − γ . (13) The pairs ( u ˇ 1 , u ˇ 2 ) (\check{u}_1,\check{u}_2) ( u ˇ 1 , u ˇ 2 ) and ( v ˇ 1 , v ˇ 2 ) (\check{v}_1,\check{v}_2) ( v ˇ 1 , v ˇ 2 ) are respectively a subsolution of (6) in [ x ‾ , + ∞ ) [\underline{x},+\infty) [ x , + ∞ ) and a supersolution of (6) in ( x ‾ , + ∞ ) (\underline{x},+\infty) ( x , + ∞ ) .
Proof. For the subsolution property, we refer to [5, Proposition 3.5] for the case θ ≥ 1 \theta\geq1 θ ≥ 1 , noting that the same argument extends directly to the case 0 < θ < 1 0<\theta<1 0 < θ < 1 . We now prove that ( v ˇ 1 , v ˇ 2 ) (\check{v}_1,\check{v}_2) ( v ˇ 1 , v ˇ 2 ) satisfies (12) with j = 2 j=2 j = 2 . Observe that v ˇ 2 ∈ C 1 \check{v}_2\in C^1 v ˇ 2 ∈ C 1 , hence for all x > x ‾ x>\underline{x} x > x , we know D v ˇ 2 ( x ) = D φ ( x ) D\check{v}_2(x)=D\varphi(x) D v ˇ 2 ( x ) = D φ ( x ) if v ˇ 2 − φ \check{v}_2-\varphi v ˇ 2 − φ has a local minimum at x x x ,
H ( x , y 2 , v ˇ 2 ( x ) , D v ˇ 2 ( x ) ) + λ 2 ( v ˇ 1 ( x ) − v ˇ 2 ( x ) ) = max c ≥ 0 { F ( c , v ˇ 2 ( x ) ) + ( r x + y ˉ − c ) D v ˇ 2 ( x ) } + ( y 2 − y ˉ ) D v ˇ 2 ( x ) ≤ ρ θ v ˇ 2 ( x ) . H(x,y_2,\check{v}_2(x),D\check{v}_2(x))+\lambda_2(\check{v}_1(x)-\check{v}_2(x))
=\max_{c\geq0}\left\{\mathcal{F}(c,\check{v}_2(x))+(rx+\bar{y}-c)D\check{v}_2(x)\right\}+(y_2-\bar{y})D\check{v}_2(x)\leq\frac{\rho}{\theta}\check{v}_2(x). H ( x , y 2 , v ˇ 2 ( x ) , D v ˇ 2 ( x )) + λ 2 ( v ˇ 1 ( x ) − v ˇ 2 ( x )) = c ≥ 0 max { F ( c , v ˇ 2 ( x )) + ( r x + y ˉ − c ) D v ˇ 2 ( x ) } + ( y 2 − y ˉ ) D v ˇ 2 ( x ) ≤ θ ρ v ˇ 2 ( x ) .
Similarly, we can derive (12) with j = 1 j=1 j = 1 . Therefore, ( v ˇ 1 , v ˇ 2 ) (\check{v}_1,\check{v}_2) ( v ˇ 1 , v ˇ 2 ) is a supersolution.
The strong comparison principle for viscosity sub- and supersolutions of (6) has been shown in [13, Theorem 2.3] with θ = 1 \theta=1 θ = 1 and [5, Proposition 3.1] with θ > 1 \theta>1 θ > 1 . Such results yield the uniqueness of the viscosity solution when θ ≥ 1 \theta\geq1 θ ≥ 1 . Reference [5] contains a complete study of continuous-time H A HA H A models in the case θ ≥ 1 \theta\geq1 θ ≥ 1 . The following proposition summarizes results from [5, Proposition 3.5, Proposition 3.10, Proposition 3.11].
Proposition 2.4. Assume θ ≥ 1 \theta\geq1 θ ≥ 1 . There exists a unique viscosity solution ( v 1 , v 2 ) (v_1,v_2) ( v 1 , v 2 ) which is C 1 C^1 C 1 and strictly concave. Moreover, v j ∈ W l o c 2 , ∞ ( x ‾ , + ∞ ) v_j\in W_{\mathrm{loc}}^{2,\infty}(\underline{x},+\infty) v j ∈ W loc 2 , ∞ ( x , + ∞ ) and v 2 ≥ v 1 v_2\geq v_1 v 2 ≥ v 1 .
Next we give some results concerning the saving policies s j s_j s j . The following proposition summarizes results from [5, Proposition 3.12, Corollary 3.2].
Proposition 2.5. Assume θ ≥ 1 \theta\geq1 θ ≥ 1 . The optimal saving policy s 1 s_1 s 1 has the following properties: s 1 ( x ) < 0 s_1(x)<0 s 1 ( x ) < 0 for all x > x ‾ x>\underline{x} x > x and s 1 ( x ‾ ) = 0 s_1(\underline{x})=0 s 1 ( x ) = 0 . If furthermore
( ρ − r ) ( r x + y 2 ) − γ + λ 2 ( ( r x + y 2 ) − γ − ( r x + y 1 ) − γ ) < 0 , (14) (\rho-r)(rx+y_2)^{-\gamma}+\lambda_2\left((rx+y_2)^{-\gamma}-(rx+y_1)^{-\gamma}\right)<0, \tag*{(14)} ( ρ − r ) ( r x + y 2 ) − γ + λ 2 ( ( r x + y 2 ) − γ − ( r x + y 1 ) − γ ) < 0 , (14) then s 2 ( x ) > 0 s_2(x)>0 s 2 ( x ) > 0 . Moreover, D v 1 ( x ) > D v 2 ( x ) Dv_1(x)>Dv_2(x) D v 1 ( x ) > D v 2 ( x ) .
The next result deals with the behavior of s 2 s_2 s 2 as x → + ∞ x\to+\infty x → + ∞ . It justifies solving the HJB equation numerically on a bounded domain [ x ‾ , x ˉ ] [\underline{x},\bar{x}] [ x , x ˉ ] .
Proposition 2.6 ([5], Proposition 3.15). Assume θ ≥ 1 \theta\geq1 θ ≥ 1 and s 2 ( x ‾ ) > 0 s_2(\underline{x})>0 s 2 ( x ) > 0 . There exists x ^ > x ‾ \hat{x}>\underline{x} x ^ > x such that s 2 ( x ^ ) = 0 s_2(\hat{x})=0 s 2 ( x ^ ) = 0 and s 2 ( x ) < 0 s_2(x)<0 s 2 ( x ) < 0 for all x > x ^ x>\hat{x} x > x ^ .
It has been shown in [5, Corollary 3.3] that, under the same assumptions as Proposition 2.5, lim x → x ‾ D 2 v 1 ( x ) = − ∞ \lim_{x \to\underline{x}}D^{2}v_{1}(x)=-\infty lim x → x D 2 v 1 ( x ) = − ∞ . The next result, from [5, Appendix C], is about the asymptotic analysis of s 1 s_{1} s 1 , D 2 v 1 D^{2}v_{1} D 2 v 1 and D v 1 Dv_{1} D v 1 near x = x ‾ x=\underline{x} x = x .
Proposition 2.8. Assume θ ≥ 1 \theta\ge1 θ ≥ 1 . We define
ϰ : = ( ρ θ − r ) D v 1 ( x ) + λ 1 ( D v 1 ( x ) − D v 2 ( x ) ) − H v ( x , y 1 , v 1 ( x ) , D v 1 ( x ) ) D v 1 ( x ) . (15) \varkappa:=\left(\frac{\rho}{\theta}-r\right)Dv_{1}(x)+\lambda_{1}\left(Dv_{1}(x)-Dv_{2}(x)\right)-H_{v}\left(x,y_{1},v_{1}(x),Dv_{1}(x)\right)Dv_{1}(x). \tag*{(15)} ϰ := ( θ ρ − r ) D v 1 ( x ) + λ 1 ( D v 1 ( x ) − D v 2 ( x ) ) − H v ( x , y 1 , v 1 ( x ) , D v 1 ( x ) ) D v 1 ( x ) . (15) Near x = x ‾ x=\underline{x} x = x , the functions s 1 s_{1} s 1 , D 2 v 1 D^{2}v_{1} D 2 v 1 and D v 1 Dv_{1} D v 1 have the following behavior:
s 1 ( x ) D 2 v 1 ( x ) = ϰ + o ( 1 ) , (16) s_{1}(x)D^{2}v_{1}(x)=\varkappa+o(1), \tag*{(16)} s 1 ( x ) D 2 v 1 ( x ) = ϰ + o ( 1 ) , (16) s 1 ( x ) = − 2 ϰ ψ ρ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ‾ ) ) ψ − 1 − γ γ − 1 ( x − x ‾ ) + o ( x − x ‾ ) , (17) s_{1}(x)=-\sqrt{\frac{2\varkappa\psi}{\rho}(rx+y_{1})^{1+\psi^{-1}}\left((1-\gamma)v_{1}(\underline{x})\right)^{\frac{\psi^{-1}-\gamma}{\gamma-1}}(x-\underline{x})}+o\left(\sqrt{x-\underline{x}}\right), \tag*{(17)} s 1 ( x ) = − ρ 2 ϰ ψ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) γ − 1 ψ − 1 − γ ( x − x ) + o ( x − x ) , (17) D 2 v 1 ( x ) = − ϰ ( 2 ϰ ψ ρ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ‾ ) ) ψ − 1 − γ γ − 1 ( x − x ‾ ) ) − 1 / 2 ( 1 + o ( 1 ) ) , (18) D^{2}v_{1}(x)=-\varkappa\left(\frac{2\varkappa\psi}{\rho}(rx+y_{1})^{1+\psi^{-1}}\left((1-\gamma)v_{1}(\underline{x})\right)^{\frac{\psi^{-1}-\gamma}{\gamma-1}}(x-\underline{x})\right)^{-1/2}(1+o(1)), \tag*{(18)} D 2 v 1 ( x ) = − ϰ ( ρ 2 ϰ ψ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) γ − 1 ψ − 1 − γ ( x − x ) ) − 1/2 ( 1 + o ( 1 )) , (18) D v 1 ( x ) = ρ ( ( 1 − γ ) v 1 ( x ‾ ) ) ψ − 1 − γ 1 − γ ( r x + y 1 ) ψ − 1 − 2 ρ ϰ ( x − x ‾ ) ψ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ‾ ) ) ψ − 1 − 1 − γ 1 − γ + o ( x − x ‾ ) . (19) Dv_{1}(x)=\rho\frac{\left((1-\gamma)v_{1}(\underline{x})\right)^{\frac{\psi^{-1}-\gamma}{1-\gamma}}}{(rx+y_{1})^{\psi^{-1}}}-\sqrt{\frac{2\rho\varkappa(x-\underline{x})}{\psi(rx+y_{1})^{1+\psi^{-1}}\left((1-\gamma)v_{1}(\underline{x})\right)^{\frac{\psi^{-1}-1-\gamma}{1-\gamma}}}}+o\left(\sqrt{x-\underline{x}}\right). \tag*{(19)} D v 1 ( x ) = ρ ( r x + y 1 ) ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) 1 − γ ψ − 1 − γ − ψ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) 1 − γ ψ − 1 − 1 − γ 2 ρ ϰ ( x − x ) + o ( x − x ) . (19)
Finally, we observe that the existence of a viscosity solution to (1.2) has been proved in [4, Proposition 2.15] with a fixed point method.
Proposition 2.9. Assume 0 < θ < 1 0<\theta<1 0 < θ < 1 . There exists a viscosity solution ( v 1 , v 2 ) (v_{1},v_{2}) ( v 1 , v 2 ) to the system (1.2).
Comparison principle and uniqueness of solution in the case 0 < θ < 1 0<\theta<1 0 < θ < 1
We perform the change of variable
( 1 − γ ) v j = ( − w j ) 1 / θ , j = 1 , 2 , (20) (1-\gamma)v_{j}=(-w_{j})^{1/\theta},\qquad j=1,2, \tag*{(20)} ( 1 − γ ) v j = ( − w j ) 1/ θ , j = 1 , 2 , (20)
equivalently
w j : = − ( ( 1 − γ ) v j ) θ . (21) w_{j}:=-\left((1-\gamma)v_{j}\right)^{\theta}. \tag*{(21)} w j := − ( ( 1 − γ ) v j ) θ . (21)
Since 1 − γ < 0 1-\gamma<0 1 − γ < 0 , θ > 0 \theta>0 θ > 0 , and v j < 0 v_{j}<0 v j < 0 , we have w j < 0 w_{j}<0 w j < 0 . Moreover u ↦ − ( ( 1 − γ ) u ) θ u\mapsto-\left((1-\gamma)u\right)^{\theta} u ↦ − ( ( 1 − γ ) u ) θ is an increasing transformation of u u u , so w j w_{j} w j inherits monotonicity in x x x from v j v_{j} v j .
The following elementary function is important for the analysis of the HJB equation in the case 0 < θ < 1 0<\theta<1 0 < θ < 1 . For a , b > 0 a,b>0 a , b > 0 we define
Φ ( a , b ) : = a 1 − 1 / θ b 1 / θ . (22) \Phi(a,b):=a^{1-1/\theta}b^{1/\theta}. \tag*{(22)} Φ ( a , b ) := a 1 − 1/ θ b 1/ θ . (22)
This will play the role of the switching/coupling nonlinearity between the two income states.
Lemma 3.1. Assume 0 < θ < 1 0<\theta<1 0 < θ < 1 , then Φ ( a , b ) = a 1 − 1 / θ b 1 / θ \Phi(a,b)=a^{1-1/\theta}b^{1/\theta} Φ ( a , b ) = a 1 − 1/ θ b 1/ θ is jointly convex on ( 0 , ∞ ) 2 (0,\infty)^{2} ( 0 , ∞ ) 2 .
Lemma 3.2. For a , b > 0 a,b>0 a , b > 0 and δ ≥ 0 \delta\ge0 δ ≥ 0 ,
Φ ( a + δ , b + δ ) − Φ ( a , b ) ≤ δ . (23) \Phi(a+\delta,b+\delta)-\Phi(a,b)\le\delta. \tag*{(23)} Φ ( a + δ , b + δ ) − Φ ( a , b ) ≤ δ . (23)
Proof. We first observe that joint convexity together with positive homogeneity of degree 1 (i.e. Φ ( t a , t b ) = t Φ ( a , b ) \Phi(ta,tb)=t\Phi(a,b) Φ ( t a , t b ) = t Φ ( a , b ) for t > 0 t>0 t > 0 ), 1 2 Φ ( a + δ , b + δ ) = Φ ( a + δ 2 , b + δ 2 ) ≤ 1 2 Φ ( a , b ) + 1 2 Φ ( δ , δ ) \frac{1}{2}\Phi(a+\delta,b+\delta)=\Phi\left(\frac{a+\delta}{2},\frac{b+\delta}{2}\right)\le\frac{1}{2}\Phi(a,b)+\frac{1}{2}\Phi(\delta,\delta) 2 1 Φ ( a + δ , b + δ ) = Φ ( 2 a + δ , 2 b + δ ) ≤ 2 1 Φ ( a , b ) + 2 1 Φ ( δ , δ ) . By (3.3) and ( 1 − 1 θ ) + 1 θ = 1 (1-\frac{1}{\theta})+\frac{1}{\theta}=1 ( 1 − θ 1 ) + θ 1 = 1 , Φ ( δ , δ ) = δ 1 − 1 / θ δ 1 / θ = δ \Phi(\delta,\delta)=\delta^{1-1/\theta}\delta^{1/\theta}=\delta Φ ( δ , δ ) = δ 1 − 1/ θ δ 1/ θ = δ , which yields (3.4).
Since the transformation is smooth and strictly monotone increasing, we observe that if ( v 1 , v 2 ) (v_1,v_2) ( v 1 , v 2 ) is a viscosity solution to (1.2), then ( w 1 , w 2 ) (w_1,w_2) ( w 1 , w 2 ) is a viscosity solution to the following system of HJB equations:
ρ w j ( x ) = sup c ≥ 0 { ( r x + y j − c ) D w j ( x ) − ρ c 1 − ψ − 1 } − θ λ j [ w j ( x ) + Φ ( − w j ( x ) , − w j ˉ ( x ) ) ] = H ( x , y j , D w j ( x ) ) − θ λ j [ w j ( x ) + Φ ( − w j ( x ) , − w j ˉ ( x ) ) ] , j = 1 , 2 , j ˉ = 3 − j , (24) \begin{aligned}
\rho w_j(x)=\sup_{c\ge0}\left\{(rx+y_j-c)Dw_j(x)-\rho c^{1-\psi^{-1}}\right\}-\theta\lambda_j\left[w_j(x)+\Phi\left(-w_j(x),-w_{\bar{j}}(x)\right)\right] \\
&=\mathcal{H}(x,y_j,Dw_j(x))-\theta\lambda_j\left[w_j(x)+\Phi\left(-w_j(x),-w_{\bar{j}}(x)\right)\right],\qquad j=1,2,\quad\bar{j}=3-j, \tag*{(24)}
\end{aligned} ρ w j ( x ) = c ≥ 0 sup { ( r x + y j − c ) D w j ( x ) − ρ c 1 − ψ − 1 } − θ λ j [ w j ( x ) + Φ ( − w j ( x ) , − w j ˉ ( x ) ) ] = H ( x , y j , D w j ( x )) − θ λ j [ w j ( x ) + Φ ( − w j ( x ) , − w j ˉ ( x ) ) ] , j = 1 , 2 , j ˉ = 3 − j , (24)
subject to the state constraint x ≥ x ‾ x\ge\underline{x} x ≥ x and r x + y j − c j ( x ) ≥ 0 rx+y_j-c_j(x)\ge0 r x + y j − c j ( x ) ≥ 0 . The first-order condition for the maximization in (24) gives the optimal consumption
c j ( x ) = ( D w j ( x ) ρ ( ψ − 1 − 1 ) ) − ψ . (25) c_j(x)=\left(\frac{Dw_j(x)}{\rho(\psi^{-1}-1)}\right)^{-\psi}. \tag*{(25)} c j ( x ) = ( ρ ( ψ − 1 − 1 ) D w j ( x ) ) − ψ . (25)
It is to be replaced by the constrained value c j ( x ) = r x + y j c_j(x)=rx+y_j c j ( x ) = r x + y j whenever the unconstrained rule would violate the state constraint. The Hamiltonian in (24) is given by
H ( x , y , p ) = { ( r x + y ) p − 1 1 − ψ ( ρ ( 1 − ψ ) ψ ) ψ p 1 − ψ , if p ≥ 0 , + ∞ , if p < 0. (26) \mathcal{H}(x,y,p)=
\begin{cases}
(rx+y)p-\frac{1}{1-\psi}\left(\frac{\rho(1-\psi)}{\psi}\right)^\psi p^{1-\psi}, & \text{if }p\ge0,\\
+\infty, & \text{if }p<0.
\end{cases} \tag*{(26)} H ( x , y , p ) = ⎩ ⎨ ⎧ ( r x + y ) p − 1 − ψ 1 ( ψ ρ ( 1 − ψ ) ) ψ p 1 − ψ , + ∞ , if p ≥ 0 , if p < 0. (26)
The new Hamiltonian H ( x , y , p ) \mathcal{H}(x,y,p) H ( x , y , p ) is convex w.r.t. p p p , and for fixed ( x , y ) (x,y) ( x , y ) attains its minimum at p min ( x , y ) = ρ ( 1 − ψ ) ψ ( r x + y ) − 1 / ψ p_{\min}(x,y)=\frac{\rho(1-\psi)}{\psi}(rx+y)^{-1/\psi} p m i n ( x , y ) = ψ ρ ( 1 − ψ ) ( r x + y ) − 1/ ψ .
Remark 3.3. When θ = 1 \theta=1 θ = 1 (i.e. γ = ψ − 1 \gamma=\psi^{-1} γ = ψ − 1 ), Φ ( − w j , − w j ˉ ) = − w j ˉ \Phi(-w_j,-w_{\bar{j}})=-w_{\bar{j}} Φ ( − w j , − w j ˉ ) = − w j ˉ , so the switching term reduces to λ j ( w j ˉ − w j ) \lambda_j(w_{\bar{j}}-w_j) λ j ( w j ˉ − w j ) , recovering the HJB equations with CRRA utility in [13].
We define sub- and supersolutions of the (24) similarly as in Definition 2.1 and then prove the subsolution lies below the supersolution. We give only the first steps of the proof, as the only significant difference from the setting of [13, Theorem 2.3] is the presence of the nonlinear switching terms.
Theorem 3.4 (Comparison principle). Assume 0 < θ < 1 0<\theta<1 0 < θ < 1 , if u = ( u 1 , u 2 ) u=(u_1,u_2) u = ( u 1 , u 2 ) and w = ( w 1 , w 2 ) w=(w_1,w_2) w = ( w 1 , w 2 ) are sub- and supersolutions then u j ( x ) ≤ w j ( x ) u_j(x)\le w_j(x) u j ( x ) ≤ w j ( x ) for all x ≥ x ‾ x\ge\underline{x} x ≥ x , j = 1 , 2 j=1,2 j = 1 , 2 .
Proof. Suppose, for contradiction, that δ : = sup j ∈ { 1 , 2 } , x ≥ x ‾ ( u j ( x ) − w j ( x ) ) > 0 \delta:=\sup_{j\in\{1,2\},\,x\ge\underline{x}}(u_j(x)-w_j(x))>0 δ := sup j ∈ { 1 , 2 } , x ≥ x ( u j ( x ) − w j ( x )) > 0 , attained at some ( j ∗ , x ∗ ) (j^*,x^*) ( j ∗ , x ∗ ) with x ∗ ≥ x ‾ x^*\ge\underline{x} x ∗ ≥ x . By the maximality of δ \delta δ (over both j j j and x x x ):
u j ∗ ( x ∗ ) − w j ∗ ( x ∗ ) = δ , u j ˉ ∗ ( x ∗ ) − w j ˉ ∗ ( x ∗ ) ≤ δ . (27) u_{j^*}(x^*)-w_{j^*}(x^*)=\delta,\qquad u_{\bar{j}^*}(x^*)-w_{\bar{j}^*}(x^*)\le\delta. \tag*{(27)} u j ∗ ( x ∗ ) − w j ∗ ( x ∗ ) = δ , u j ˉ ∗ ( x ∗ ) − w j ˉ ∗ ( x ∗ ) ≤ δ . (27)
From (27) and since Φ \Phi Φ is increasing in its second argument, we infer
[ w j ∗ ( x ∗ ) + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) ] − [ u j ∗ ( x ∗ ) + Φ ( − u j ∗ ( x ∗ ) , − u j ˉ ∗ ( x ∗ ) ) ] = − δ + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) − Φ ( − w j ∗ ( x ∗ ) − δ , − u j ˉ ∗ ( x ∗ ) ) ≤ − δ + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) − Φ ( − w j ∗ ( x ∗ ) − δ , − w j ˉ ∗ ( x ∗ ) − δ ) ≤ 0 , (28) \begin{aligned}
&\left[w_{j^*}(x^*)+\Phi\left(-w_{j^*}(x^*),-w_{\bar{j}^*}(x^*)\right)\right]
-\left[u_{j^*}(x^*)+\Phi\left(-u_{j^*}(x^*),-u_{\bar{j}^*}(x^*)\right)\right]\\
&=-\delta+\Phi\left(-w_{j^*}(x^*),-w_{\bar{j}^*}(x^*)\right)
-\Phi\left(-w_{j^*}(x^*)-\delta,-u_{\bar{j}^*}(x^*)\right)\\
&\le-\delta+\Phi\left(-w_{j^*}(x^*),-w_{\bar{j}^*}(x^*)\right)
-\Phi\left(-w_{j^*}(x^*)-\delta,-w_{\bar{j}^*}(x^*)-\delta\right)\le0, \tag*{(28)}
\end{aligned} [ w j ∗ ( x ∗ ) + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) ] − [ u j ∗ ( x ∗ ) + Φ ( − u j ∗ ( x ∗ ) , − u j ˉ ∗ ( x ∗ ) ) ] = − δ + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) − Φ ( − w j ∗ ( x ∗ ) − δ , − u j ˉ ∗ ( x ∗ ) ) ≤ − δ + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) − Φ ( − w j ∗ ( x ∗ ) − δ , − w j ˉ ∗ ( x ∗ ) − δ ) ≤ 0 , (28)
where the last inequality is yielded by (23) . Multiplying (28) by θ λ j ∗ \theta\lambda_{j^*} θ λ j ∗ yields the relationship between the switching terms of the HJB equations:
− θ λ j ∗ [ u j ∗ ( x ∗ ) + Φ ( − u j ∗ ( x ∗ ) , − u j ˉ ∗ ( x ∗ ) ) ] ≤ − θ λ j ∗ [ w j ∗ ( x ∗ ) + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) ] . -\theta\lambda_{j^*}\left[u_{j^*}(x^*)+\Phi\left(-u_{j^*}(x^*),-u_{\bar{j}^*}(x^*)\right)\right]\leq-\theta\lambda_{j^*}\left[w_{j^*}(x^*)+\Phi\left(-w_{j^*}(x^*),-w_{\bar{j}^*}(x^*)\right)\right]. − θ λ j ∗ [ u j ∗ ( x ∗ ) + Φ ( − u j ∗ ( x ∗ ) , − u j ˉ ∗ ( x ∗ ) ) ] ≤ − θ λ j ∗ [ w j ∗ ( x ∗ ) + Φ ( − w j ∗ ( x ∗ ) , − w j ˉ ∗ ( x ∗ ) ) ] .
The rest of the proof proceeds similarly as [13, Theorem 2.3] and we omit the details.
Theorem 3.5. There exists a unique viscosity solution v = ( v 1 , v 2 ) v=(v_1,v_2) v = ( v 1 , v 2 ) to the HJB system (2) .
Proof. We know from Proposition 2.9 , or by using Perron’s method, that there exists v = ( v 1 , v 2 ) v=(v_1,v_2) v = ( v 1 , v 2 ) which is a viscosity solution of (2) . We infer there exists a viscosity solution w w w of (24) given by the change of variables (20) , since this mapping is monotone increasing and differentiable. We know from Theorem 3.4 that w w w is the unique solution of (24) , hence v v v is the unique solution of (2) .
The semi-Lagrangian method
The SL scheme and first elements of analysis
Given a step size Δ x = ( x ˉ − x ) / I \Delta x=(\bar{x}-x)/I Δ x = ( x ˉ − x ) / I , I ∈ N I\in\mathbb{N} I ∈ N , let x i = x + i Δ x x_i=x+i\Delta x x i = x + i Δ x , i = 0 , … , I i=0,\ldots,I i = 0 , … , I , be the points of the space grid G Δ x = { x i } i = 0 I \mathcal{G}^{\Delta x}=\{x_i\}_{i=0}^{I} G Δ x = { x i } i = 0 I . We denote Δ = ( h , Δ x ) \Delta=(h,\Delta x) Δ = ( h , Δ x ) where h h h is the time step. We denote by I [ ⋅ ] \mathbb{I}[\cdot] I [ ⋅ ] the standard piecewise-linear interpolation operator that maps a grid function φ = ( φ i ) i = 0 I ∈ B ( G Δ x ) \varphi=(\varphi_i)_{i=0}^{I}\in B(\mathcal{G}^{\Delta x}) φ = ( φ i ) i = 0 I ∈ B ( G Δ x ) to a function on [ x , x ˉ ] [x,\bar{x}] [ x , x ˉ ] . Specifically, I [ φ ] ( x ) = ∑ i = 0 I φ i β i ( x ) \mathbb{I}[\varphi](x)=\sum_{i=0}^{I}\varphi_i\beta_i(x) I [ φ ] ( x ) = ∑ i = 0 I φ i β i ( x ) , where ( β i ) i = 0 I (\beta_i)_{i=0}^{I} ( β i ) i = 0 I denotes the standard piecewise-linear Q 1 \mathbb{Q}_1 Q 1 nodal basis associated with the grid. We recall that I \mathbb{I} I is order preserving, i.e.,
φ ≤ ϕ on G Δ x ⟹ I [ φ ] ( z ) ≤ I [ ϕ ] ( z ) ∀ z ∈ [ x , x ˉ ] . (29) \varphi\leq\phi\text{ on }\mathcal{G}^{\Delta x}\quad\Longrightarrow\quad\mathbb{I}[\varphi](z)\leq\mathbb{I}[\phi](z)\quad\forall z\in[x,\bar{x}]. \tag*{(29)} φ ≤ ϕ on G Δ x ⟹ I [ φ ] ( z ) ≤ I [ ϕ ] ( z ) ∀ z ∈ [ x , x ˉ ] . (29)
We define the admissible set at a grid point x i x_i x i
C j Δ ( x i ) = [ 0 , + ∞ ) ∩ [ x i − x ˉ h + r x i + y j , x i − x h + r x i + y j ] . (30) \mathcal{C}^{\Delta}_j(x_i)=[0,+\infty)\cap\left[\frac{x_i-\bar{x}}{h}+rx_i+y_j,\frac{x_i-x}{h}+rx_i+y_j\right]. \tag*{(30)} C j Δ ( x i ) = [ 0 , + ∞ ) ∩ [ h x i − x ˉ + r x i + y j , h x i − x + r x i + y j ] . (30)
which enforces both the borrowing constraint at x x x and the upper limit x ˉ \bar{x} x ˉ . Throughout the paper, we impose the standing assumption 0 < h < min { θ β , 1 λ 1 , 1 λ 2 } 0<h<\min\left\{\frac{\theta}{\beta},\frac{1}{\lambda_1},\frac{1}{\lambda_2}\right\} 0 < h < min { β θ , λ 1 1 , λ 2 1 } . We now consider the semi-Lagrangian (SL) scheme obtained by a first order (in h h h ) time discretization of the dynamic programming equation: the transport term is treated by evaluating the interpolated value I [ V j ] \mathbb{I}[V_j] I [ V j ] at the point reached after one time step along the discrete characteristic, while the aggregator f ( c , v j ) f(c,v_j) f ( c , v j ) is kept at the grid point itself. By using a Bernoulli process to approximate the Poisson process with rate λ j \lambda_j λ j , we construct the scheme as in [13], with j ∈ { 1 , 2 } j\in\{1,2\} j ∈ { 1 , 2 } and j ˉ = 3 − j \bar{j}=3-j j ˉ = 3 − j :
V i , j Δ = sup c ∈ C j Δ ( x i ) { h f ( c , V i , j Δ ) + [ λ j h V i , j ˉ Δ + ( 1 − λ j h ) I [ V j Δ ] ( x i + h s i , j ( c ) ) ] } , V_{i,j}^{\Delta}=\sup_{c\in\mathcal{C}^{\Delta}_j(x_i)}\left\{hf(c,V_{i,j}^{\Delta})+\left[\lambda_jhV_{i,\bar{j}}^{\Delta}+(1-\lambda_jh)\mathbb{I}[V_j^{\Delta}]\left(x_i+hs_{i,j}(c)\right)\right]\right\}, V i , j Δ = c ∈ C j Δ ( x i ) sup { h f ( c , V i , j Δ ) + [ λ j h V i , j ˉ Δ + ( 1 − λ j h ) I [ V j Δ ] ( x i + h s i , j ( c ) ) ] } ,
s i , j ( c ) = r x i + y j − c , s_{i,j}(c)=rx_i+y_j-c, s i , j ( c ) = r x i + y j − c ,
where V k , j Δ V_{k,j}^{\Delta} V k , j Δ denotes the approximation of v j ( x k ) v_j(x_k) v j ( x k ) . We observe that with (5) and ( 1 + h ζ ) − 1 = 1 − ζ h + o ( h ) (1+h\zeta)^{-1}=1-\zeta h+o(h) ( 1 + h ζ ) − 1 = 1 − ζ h + o ( h ) , the above scheme is equivalent (up to first order in h h h ) to
V i , j Δ = sup c ∈ C j Δ ( x i ) { h F ( c , V i , j Δ ) + ( 1 − ζ h ) [ λ j h V i , j ˉ Δ + ( 1 − λ j h ) I [ V j Δ ] ( x i + h s i , j ( c ) ) ] } . (31) V_{i,j}^{\Delta}=\sup_{c\in\mathcal{C}^{\Delta}_j(x_i)}\left\{h\mathcal{F}(c,V_{i,j}^{\Delta})+(1-\zeta h)\left[\lambda_jhV_{i,\bar{j}}^{\Delta}+(1-\lambda_jh)\mathbb{I}[V_j^{\Delta}]\left(x_i+hs_{i,j}(c)\right)\right]\right\}. \tag*{(31)} V i , j Δ = c ∈ C j Δ ( x i ) sup { h F ( c , V i , j Δ ) + ( 1 − ζ h ) [ λ j h V i , j ˉ Δ + ( 1 − λ j h ) I [ V j Δ ] ( x i + h s i , j ( c ) ) ] } . (31)
We observe that if θ = 1 \theta= 1 θ = 1 then ρ = ζ \rho= \zeta ρ = ζ and F \mathcal{F} F does not depend on V V V : we recover the SL scheme from [13]. We use the notation U ⪯ V U \preceq V U ⪯ V (resp. U ⪰ V U \succeq V U ⪰ V ) introduced in (29) , U i , j ≤ V i , j U_{i,j} \leq V_{i,j} U i , j ≤ V i , j (resp. U i , j ≥ V i , j U_{i,j} \geq V_{i,j} U i , j ≥ V i , j ) for all i , j i,j i , j .
We now introduce the discrete sub- and supersolutions of (31) , analogous to Definition 2.1 at the continuous level.
Definition 4.1. A grid function pair U Δ = ( U 1 Δ , U 2 Δ ) U^\Delta= (U_1^\Delta,U_2^\Delta) U Δ = ( U 1 Δ , U 2 Δ ) , U j Δ = ( U i , j Δ ) i = 0 I U_j^\Delta= (U_{i,j}^\Delta)_{i=0}^{I} U j Δ = ( U i , j Δ ) i = 0 I , is a subsolution (resp. a supersolution) of (31) if for every i , j i,j i , j ,
U i , j Δ ≤ ( resp. ≥ ) sup c ∈ C j Δ ( x i ) { h F ( c , U i , j Δ ) + ( 1 − ζ h ) [ λ j h U i , j ˉ Δ + ( 1 − λ j h ) I [ U j Δ ] ( x i + h s i , j ( c ) ) ] } . (32) U_{i,j}^\Delta\leq\ (\operatorname{resp.}\ \geq)\ \sup_{c \in C_j^\Delta(x_i)} \left\{ h\mathcal{F}(c,U_{i,j}^\Delta) + (1-\zeta h)\left[\lambda_j h U_{i,\bar{j}}^\Delta+ (1-\lambda_j h)\mathbb{I}[U_j^\Delta](x_i+h s_{i,j}(c))\right]\right\}. \tag*{(32)} U i , j Δ ≤ ( resp. ≥ ) c ∈ C j Δ ( x i ) sup { h F ( c , U i , j Δ ) + ( 1 − ζ h ) [ λ j h U i , j ˉ Δ + ( 1 − λ j h ) I [ U j Δ ] ( x i + h s i , j ( c )) ] } . (32)
We next give a discrete counterpart of Proposition 2.2, providing barriers for the numerical solution.
Proposition 4.2. Let us define u ˇ , v ˇ \check{u},\check{v} u ˇ , v ˇ as in (13) . We set U ˇ i , j Δ = u ˇ j ( x i ) \check{U}_{i,j}^\Delta=\check{u}_j(x_i) U ˇ i , j Δ = u ˇ j ( x i ) and V ˇ i , j Δ = v ˇ j ( x i ) \check{V}_{i,j}^\Delta=\check{v}_j(x_i) V ˇ i , j Δ = v ˇ j ( x i ) . Then, the grid function pair ( U ˇ 1 Δ , U ˇ 2 Δ ) (\check{U}_1^\Delta,\check{U}_2^\Delta) ( U ˇ 1 Δ , U ˇ 2 Δ ) is a subsolution of (31) . Moreover, for sufficiently small h > 0 h>0 h > 0 , the grid function pair ( V ˇ 1 Δ , V ˇ 2 Δ ) (\check{V}_1^\Delta,\check{V}_2^\Delta) ( V ˇ 1 Δ , V ˇ 2 Δ ) is a supersolution of (31) .
Proof. Subsolution. Let us fix a grid index i i i and denote the null-saving consumption c ˉ 1 ( x i ) = r x i + y 1 \bar{c}_1(x_i)=rx_i+y_1 c ˉ 1 ( x i ) = r x i + y 1 , which yields s i , 1 ( c ˉ 1 ( x i ) ) = 0 s_{i,1}(\bar{c}_1(x_i))=0 s i , 1 ( c ˉ 1 ( x i )) = 0 . We can infer from (13) and the scheme (31) that at j = 1 j=1 j = 1 ,
sup c ∈ C 1 Δ ( x i ) { h F ( c , U ˇ i , 1 Δ ) + ( 1 − ζ h ) [ λ 1 h U ˇ i , 2 Δ + ( 1 − λ 1 h ) I [ U ˇ 1 Δ ] ( x i + h s i , 1 ( c ) ) ] } − U ˇ i , 1 Δ ≥ h F ( c ˉ 1 ( x i ) , U ˇ i , 1 Δ ) − ρ h θ U ˇ i , 1 Δ = 0 \sup_{c\in C_1^\Delta(x_i)}\left\{h\mathcal{F}(c,\check{U}_{i,1}^\Delta)+(1-\zeta h)\left[\lambda_1h\check{U}_{i,2}^\Delta+(1-\lambda_1h)\mathbb{I}[\check{U}_1^\Delta](x_i+hs_{i,1}(c))\right]\right\}-\check{U}_{i,1}^\Delta
\geq h\mathcal{F}(\bar{c}_1(x_i),\check{U}_{i,1}^\Delta)-\frac{\rho h}{\theta}\check{U}_{i,1}^\Delta=0 c ∈ C 1 Δ ( x i ) sup { h F ( c , U ˇ i , 1 Δ ) + ( 1 − ζ h ) [ λ 1 h U ˇ i , 2 Δ + ( 1 − λ 1 h ) I [ U ˇ 1 Δ ] ( x i + h s i , 1 ( c )) ] } − U ˇ i , 1 Δ ≥ h F ( c ˉ 1 ( x i ) , U ˇ i , 1 Δ ) − θ ρ h U ˇ i , 1 Δ = 0
where for the last equality we used the algebraic identity F ( c ˉ 1 ( x ) , u ˇ 1 ( x ) ) = ρ θ u ˇ 1 ( x ) \mathcal{F}(\bar{c}_1(x),\check{u}_1(x))=\frac{\rho}{\theta}\check{u}_1(x) F ( c ˉ 1 ( x ) , u ˇ 1 ( x )) = θ ρ u ˇ 1 ( x ) . Therefore (32) holds at j = 1 j=1 j = 1 . The same argument, with c ˉ 2 ( x i ) = r x i + y 2 \bar{c}_2(x_i)=rx_i+y_2 c ˉ 2 ( x i ) = r x i + y 2 and using y 2 > y 1 y_2>y_1 y 2 > y 1 , F ( c ˉ 2 ( x i ) , U ˇ i , 2 Δ ) ≥ F ( c ˉ 1 ( x i ) , U ˇ i , 2 Δ ) \mathcal{F}(\bar{c}_2(x_i),\check{U}_{i,2}^\Delta)\geq\mathcal{F}(\bar{c}_1(x_i),\check{U}_{i,2}^\Delta) F ( c ˉ 2 ( x i ) , U ˇ i , 2 Δ ) ≥ F ( c ˉ 1 ( x i ) , U ˇ i , 2 Δ ) ((5) being increasing in c c c ), yields (32) at j = 2 j=2 j = 2 .
Supersolution. Since v ˇ 2 \check{v}_2 v ˇ 2 is concave, we know that for every c ∈ C 2 Δ ( x i ) c\in C_2^\Delta(x_i) c ∈ C 2 Δ ( x i ) ,
I [ V ˇ 2 Δ ] ( x i + h s i , 2 ( c ) ) ≤ v ˇ 2 ( x i + h s i , 2 ( c ) ) ≤ V ˇ i , 2 Δ + h s i , 2 ( c ) D v ˇ 2 ( x i ) . \mathbb{I}[\check{V}_2^\Delta](x_i+hs_{i,2}(c))\leq\check{v}_2(x_i+hs_{i,2}(c))\leq\check{V}_{i,2}^\Delta+hs_{i,2}(c)D\check{v}_2(x_i). I [ V ˇ 2 Δ ] ( x i + h s i , 2 ( c )) ≤ v ˇ 2 ( x i + h s i , 2 ( c )) ≤ V ˇ i , 2 Δ + h s i , 2 ( c ) D v ˇ 2 ( x i ) .
Since F ( c , V ˇ i , 2 Δ ) < 0 \mathcal{F}(c,\check{V}_{i,2}^\Delta)<0 F ( c , V ˇ i , 2 Δ ) < 0 , F ( c , V ˇ i , 2 Δ ) ≤ ( 1 − λ 2 h ) ( 1 − ζ h ) F ( c , V ˇ i , 2 Δ ) \mathcal{F}(c,\check{V}_{i,2}^\Delta)\leq(1-\lambda_2h)(1-\zeta h)\mathcal{F}(c,\check{V}_{i,2}^\Delta) F ( c , V ˇ i , 2 Δ ) ≤ ( 1 − λ 2 h ) ( 1 − ζ h ) F ( c , V ˇ i , 2 Δ ) .
sup c ∈ C 2 Δ ( x i ) { h F ( c , V ˇ i , 2 Δ ) + ( 1 − ζ h ) [ λ 2 h V ˇ i , 1 Δ + ( 1 − λ 2 h ) I [ V ˇ 2 Δ ] ( x i + h s i , 2 ( c ) ) ] } − V ˇ i , 2 Δ ≤ h ( 1 − λ 2 h ) ( 1 − ζ h ) ( sup c ≥ 0 { F ( c , v ˇ 2 ( x i ) ) + ( r x i + y ˉ − c ) D v ˇ 2 ( x i ) − ζ v ˇ 2 ( x i ) } ) + h [ ζ ( 1 − ( 1 − λ 2 h ) ( 1 − ζ h ) ) ( − v ˇ 2 ( x i ) ) + ( 1 − λ 2 h ) ( 1 − ζ h ) ( y 2 − y ˉ ) D v ˇ 2 ( x i ) ] ≤ 0. \begin{aligned}
&\sup_{c\in C_2^\Delta(x_i)}\left\{h\mathcal{F}(c,\check{V}_{i,2}^\Delta)+(1-\zeta h)\left[\lambda_2h\check{V}_{i,1}^\Delta+(1-\lambda_2h)\mathbb{I}[\check{V}_2^\Delta](x_i+hs_{i,2}(c))\right]\right\}-\check{V}_{i,2}^\Delta\\
&\leq h(1-\lambda_2h)(1-\zeta h)\left(\sup_{c\geq0}\left\{\mathcal{F}(c,\check{v}_2(x_i))+(rx_i+\bar{y}-c)D\check{v}_2(x_i)-\zeta\check{v}_2(x_i)\right\}\right) \\
&\quad+h\left[\zeta\left(1-(1-\lambda_2h)(1-\zeta h)\right)(-\check{v}_2(x_i))+(1-\lambda_2h)(1-\zeta h)(y_2-\bar{y})D\check{v}_2(x_i)\right] \\
&\leq0.
\end{aligned} c ∈ C 2 Δ ( x i ) sup { h F ( c , V ˇ i , 2 Δ ) + ( 1 − ζ h ) [ λ 2 h V ˇ i , 1 Δ + ( 1 − λ 2 h ) I [ V ˇ 2 Δ ] ( x i + h s i , 2 ( c )) ] } − V ˇ i , 2 Δ ≤ h ( 1 − λ 2 h ) ( 1 − ζ h ) ( c ≥ 0 sup { F ( c , v ˇ 2 ( x i )) + ( r x i + y ˉ − c ) D v ˇ 2 ( x i ) − ζ v ˇ 2 ( x i ) } ) + h [ ζ ( 1 − ( 1 − λ 2 h ) ( 1 − ζ h ) ) ( − v ˇ 2 ( x i )) + ( 1 − λ 2 h ) ( 1 − ζ h ) ( y 2 − y ˉ ) D v ˇ 2 ( x i ) ] ≤ 0.
For the last inequality, we used y 2 − y ˉ < 0 y_2-\bar{y}<0 y 2 − y ˉ < 0 and h h h sufficiently small. We have therefore obtained the ≥ \geq ≥ inequality in (32) with j = 2 j=2 j = 2 . The proof for j = 1 j=1 j = 1 is similar hence we omit it.
A discrete comparison principle
We now derive the comparison principle satisfied by the scheme (31) . For the case θ = 1 \theta=1 θ = 1 , a proof has been given in [13, Proposition 4.6]. For the case θ > 1 \theta>1 θ > 1 , we only need a straightforward extension of the same method. We mainly focus on discussing the case 0 < θ < 1 0<\theta<1 0 < θ < 1 . As in (20) , we perform the change of variable for the solution V V V to (31) :
( 1 − γ ) V j = ( − W j ) 1 / θ , j = 1 , 2 , (33) (1-\gamma)V_j=(-W_j)^{1/\theta},\qquad j=1,2, \tag*{(33)} ( 1 − γ ) V j = ( − W j ) 1/ θ , j = 1 , 2 , (33)
A direct computation yields
W i , j = sup c ∈ C j Δ ( x i ) { − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j h ) ( − W i , j ) 1 − 1 / θ × I [ ( − W j ) 1 / θ ] ( x i + h s i , j ( c ) ) } − ( 1 − ζ h ) λ j h Φ ( − W i , j , − W i , ȷ ˉ ) . (34) \begin{aligned}
W_{i,j}
={}&\sup_{c\in C_j^\Delta(x_i)}
\Bigl\{-h\zeta c^{1-\psi^{-1}}-(1-\zeta h)(1-\lambda_jh)(-W_{i,j})^{1-1/\theta}\\
&\qquad\qquad\qquad\qquad\qquad\qquad{}\times\mathbb{I}\bigl[(-W_j)^{1/\theta}\bigr](x_i+hs_{i,j}(c))\Bigr\}\\
&\quad-(1-\zeta h)\lambda_jh\Phi(-W_{i,j},-W_{i,\bar{\jmath}}). \tag*{(34)}
\end{aligned} W i , j = c ∈ C j Δ ( x i ) sup { − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j h ) ( − W i , j ) 1 − 1/ θ × I [ ( − W j ) 1/ θ ] ( x i + h s i , j ( c )) } − ( 1 − ζ h ) λ j h Φ ( − W i , j , − W i , ˉ ) . (34)
The scheme (34) in fact corresponds to the system of HJB equations (24) .
Proposition 4.3. Let us assume 0 < θ < 1 0<\theta<1 0 < θ < 1 . If U U U and W W W are respectively a sub- and a supersolution of (4.6), then U ⪯ W U\preceq W U ⪯ W .
Proof. Suppose, arguing by contradiction, that
U i ∗ , j ∗ − W i ∗ , j ∗ = max i , j { U i , j − W i , j } = δ > 0. (35) U_{i^*,j^*}-W_{i^*,j^*}=\max_{i,j}\{U_{i,j}-W_{i,j}\}=\delta>0. \tag*{(35)} U i ∗ , j ∗ − W i ∗ , j ∗ = i , j max { U i , j − W i , j } = δ > 0. (35)
Since C j ∗ Δ ( x i ∗ ) C_{j^*}^\Delta(x_{i^*}) C j ∗ Δ ( x i ∗ ) is compact and
c ⟼ − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( − U i ∗ , j ∗ ) 1 − 1 / θ I [ ( − U j ∗ ) 1 / θ ] ( x i ∗ + h s i ∗ , j ∗ ( c ) ) c\longmapsto-h\zeta c^{1-\psi^{-1}}-(1-\zeta h)(1-\lambda_{j^*}h)(-U_{i^*,j^*})^{1-1/\theta}\mathbb{I}\bigl[(-U_{j^*})^{1/\theta}\bigr](x_{i^*}+hs_{i^*,j^*}(c)) c ⟼ − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( − U i ∗ , j ∗ ) 1 − 1/ θ I [ ( − U j ∗ ) 1/ θ ] ( x i ∗ + h s i ∗ , j ∗ ( c ))
is continuous, the supremum defining the subsolution property of U U U at ( i ∗ , j ∗ ) (i^*,j^*) ( i ∗ , j ∗ ) is attained at some c ^ ∈ C j ∗ Δ ( x i ∗ ) \widehat{c}\in C_{j^*}^\Delta(x_{i^*}) c ∈ C j ∗ Δ ( x i ∗ ) . Moreover, there exist two grids x k x_k x k and x k + 1 x_{k+1} x k + 1 such that x k ≤ x i ∗ + h s i ∗ , j ∗ ( c ^ ) ≤ x k + 1 x_k\leq x_{i^*}+hs_{i^*,j^*}(\widehat{c})\leq x_{k+1} x k ≤ x i ∗ + h s i ∗ , j ∗ ( c ) ≤ x k + 1 . We denote by β : = x k + 1 − x i ∗ − h s i ∗ , j ∗ ( c ^ ) Δ x \beta:=\frac{x_{k+1}-x_{i^*}-hs_{i^*,j^*}(\widehat{c})}{\Delta x} β := Δ x x k + 1 − x i ∗ − h s i ∗ , j ∗ ( c ) . We obtain
I [ ( − U j ∗ ) 1 / θ ] ( x i ∗ + h s i ∗ , j ∗ ( c ^ ) ) = β ( − U k , j ∗ ) 1 / θ + ( 1 − β ) ( − U k + 1 , j ∗ ) 1 / θ , \mathbb{I}\bigl[(-U_{j^*})^{1/\theta}\bigr](x_{i^*}+hs_{i^*,j^*}(\widehat{c}))=\beta(-U_{k,j^*})^{1/\theta}+(1-\beta)(-U_{k+1,j^*})^{1/\theta}, I [ ( − U j ∗ ) 1/ θ ] ( x i ∗ + h s i ∗ , j ∗ ( c )) = β ( − U k , j ∗ ) 1/ θ + ( 1 − β ) ( − U k + 1 , j ∗ ) 1/ θ ,
which yields
U i ∗ , j ∗ ≤ − h ζ c ^ 1 − ψ − 1 − ( 1 − ζ h ) λ j ∗ h Φ ( − U i ∗ , j ∗ , − U i ∗ , ȷ ˉ ∗ ) − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( β Φ ( − U i ∗ , j ∗ , − U k , j ∗ ) + ( 1 − β ) Φ ( − U i ∗ , j ∗ , − U k + 1 , j ∗ ) ) . (36) \begin{aligned}
U_{i^*,j^*}\leq{}&-h\zeta\widehat{c}^{1-\psi^{-1}}-(1-\zeta h)\lambda_{j^*}h\Phi(-U_{i^*,j^*},-U_{i^*,\bar{\jmath}^*})\\
&-(1-\zeta h)(1-\lambda_{j^*}h)\bigl(\beta\Phi(-U_{i^*,j^*},-U_{k,j^*})\\
&\qquad\qquad\qquad\qquad{}+(1-\beta)\Phi(-U_{i^*,j^*},-U_{k+1,j^*})\bigr). \tag*{(36)}
\end{aligned} U i ∗ , j ∗ ≤ − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) λ j ∗ h Φ ( − U i ∗ , j ∗ , − U i ∗ , ˉ ∗ ) − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( β Φ ( − U i ∗ , j ∗ , − U k , j ∗ ) + ( 1 − β ) Φ ( − U i ∗ , j ∗ , − U k + 1 , j ∗ ) ) . (36)
Since W W W is a supersolution of (34) and c ^ \widehat{c} c is an admissible control for
sup c ∈ C j ∗ Δ ( x i ∗ ) { − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( − W i ∗ , j ∗ ) 1 − 1 / θ I [ ( − W j ∗ ) 1 / θ ] ( x i ∗ + h s i ∗ , j ∗ ( c ) ) } , \sup_{c\in C_{j^*}^\Delta(x_{i^*})}\Bigl\{-h\zeta c^{1-\psi^{-1}}-(1-\zeta h)(1-\lambda_{j^*}h)(-W_{i^*,j^*})^{1-1/\theta}\mathbb{I}\bigl[(-W_{j^*})^{1/\theta}\bigr](x_{i^*}+hs_{i^*,j^*}(c))\Bigr\}, c ∈ C j ∗ Δ ( x i ∗ ) sup { − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( − W i ∗ , j ∗ ) 1 − 1/ θ I [ ( − W j ∗ ) 1/ θ ] ( x i ∗ + h s i ∗ , j ∗ ( c )) } ,
we can infer
W i ∗ , j ∗ ≥ − h ζ c ^ 1 − ψ − 1 − ( 1 − ζ h ) λ j ∗ h Φ ( − W i ∗ , j ∗ , − W i ∗ , ȷ ˉ ∗ ) − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( β Φ ( − W i ∗ , j ∗ , − W k , j ∗ ) + ( 1 − β ) Φ ( − W i ∗ , j ∗ , − W k + 1 , j ∗ ) ) . (37) \begin{aligned}
W_{i^*,j^*}\geq{}&-h\zeta\widehat{c}^{1-\psi^{-1}}-(1-\zeta h)\lambda_{j^*}h\Phi(-W_{i^*,j^*},-W_{i^*,\bar{\jmath}^*})\\
&-(1-\zeta h)(1-\lambda_{j^*}h)\bigl(\beta\Phi(-W_{i^*,j^*},-W_{k,j^*})\\
&\qquad\qquad\qquad\qquad{}+(1-\beta)\Phi(-W_{i^*,j^*},-W_{k+1,j^*})\bigr). \tag*{(37)}
\end{aligned} W i ∗ , j ∗ ≥ − h ζ c 1 − ψ − 1 − ( 1 − ζ h ) λ j ∗ h Φ ( − W i ∗ , j ∗ , − W i ∗ , ˉ ∗ ) − ( 1 − ζ h ) ( 1 − λ j ∗ h ) ( β Φ ( − W i ∗ , j ∗ , − W k , j ∗ ) + ( 1 − β ) Φ ( − W i ∗ , j ∗ , − W k + 1 , j ∗ ) ) . (37)
We observe that (35) yields
U k , j ∗ ≤ W k , j ∗ + δ , U k + 1 , j ∗ ≤ W k + 1 , j ∗ + δ , U i ∗ , j ˉ ∗ ≤ W i ∗ , j ˉ ∗ + δ , U_{k,j^*} \le W_{k,j^*}+\delta,\quad U_{k+1,j^*} \le W_{k+1,j^*}+\delta,\quad U_{i^*,\bar{j}^*} \le W_{i^*,\bar{j}^*}+\delta, U k , j ∗ ≤ W k , j ∗ + δ , U k + 1 , j ∗ ≤ W k + 1 , j ∗ + δ , U i ∗ , j ˉ ∗ ≤ W i ∗ , j ˉ ∗ + δ ,
hence we can deduce from (23) that
Φ ( − W i ∗ , j ∗ , − W i ∗ , j ˉ ∗ ) − Φ ( − U i ∗ , j ∗ , − U i ∗ , j ˉ ∗ ) ≤ δ , Φ ( − W i ∗ , j ∗ , − W k , j ∗ ) − Φ ( − U i ∗ , j ∗ , − U k , j ∗ ) ≤ δ , Φ ( − W i ∗ , j ∗ , − W k + 1 , j ∗ ) − Φ ( − U i ∗ , j ∗ , − U k + 1 , j ∗ ) ≤ δ . (38) \begin{aligned}
\Phi\left(-W_{i^*,j^*},-W_{i^*,\bar{j}^*}\right)-\Phi\left(-U_{i^*,j^*},-U_{i^*,\bar{j}^*}\right)&\le\delta,\\
\Phi\left(-W_{i^*,j^*},-W_{k,j^*}\right)-\Phi\left(-U_{i^*,j^*},-U_{k,j^*}\right)&\le\delta,\\
\Phi\left(-W_{i^*,j^*},-W_{k+1,j^*}\right)-\Phi\left(-U_{i^*,j^*},-U_{k+1,j^*}\right)&\le\delta. \tag*{(38)}
\end{aligned} Φ ( − W i ∗ , j ∗ , − W i ∗ , j ˉ ∗ ) − Φ ( − U i ∗ , j ∗ , − U i ∗ , j ˉ ∗ ) Φ ( − W i ∗ , j ∗ , − W k , j ∗ ) − Φ ( − U i ∗ , j ∗ , − U k , j ∗ ) Φ ( − W i ∗ , j ∗ , − W k + 1 , j ∗ ) − Φ ( − U i ∗ , j ∗ , − U k + 1 , j ∗ ) ≤ δ , ≤ δ , ≤ δ . (38)
By comparing the two inequalities (36) and (37) , while using (38) , we deduce δ ≤ ( 1 − ζ h ) δ \delta\le(1-\zeta h)\delta δ ≤ ( 1 − ζ h ) δ which is a contradiction. □
Proposition 4.4. If U U U and V V V are respectively a sub- and a supersolution of (31) (Definition 4.1 ), then U ⪯ V U \preceq V U ⪯ V .
Proof. The proof in the case θ = 1 \theta=1 θ = 1 is the same as [13, Proposition 4.6]. We now consider the other two cases.
Case 1: θ > 1 \theta>1 θ > 1 . Suppose, arguing by contradiction, that
U i ∗ , j ∗ − V i ∗ , j ∗ = max i , j { U i , j − V i , j } = δ > 0. U_{i^*,j^*}-V_{i^*,j^*}=\max_{i,j}\{U_{i,j}-V_{i,j}\}=\delta>0. U i ∗ , j ∗ − V i ∗ , j ∗ = i , j max { U i , j − V i , j } = δ > 0.
Since C j ∗ ∗ ( x i ∗ ) C^*_{j^*}(x_{i^*}) C j ∗ ∗ ( x i ∗ ) is compact and c ↦ h F ( c , U i ∗ , j ∗ ) + ( 1 − ζ h ) ( 1 − λ j ∗ h ) I [ U j ∗ ] ( x i ∗ + h s i ∗ , j ∗ ( c ) ) c\mapsto h\mathcal{F}(c,U_{i^*,j^*})+(1-\zeta h)(1-\lambda_{j^*}h)\mathbb{I}[U_{j^*}](x_{i^*}+hs_{i^*,j^*}(c)) c ↦ h F ( c , U i ∗ , j ∗ ) + ( 1 − ζ h ) ( 1 − λ j ∗ h ) I [ U j ∗ ] ( x i ∗ + h s i ∗ , j ∗ ( c )) is continuous, the supremum defining the subsolution property of U U U at ( i ∗ , j ∗ ) (i^*,j^*) ( i ∗ , j ∗ ) is attained at some c ^ ∈ C j ∗ Δ ( x i ∗ ) \hat{c}\in C^\Delta_{j^*}(x_{i^*}) c ^ ∈ C j ∗ Δ ( x i ∗ ) , and, since V V V is a supersolution, the same control c ^ \hat{c} c ^ is admissible in the corresponding inequality for V V V . Hence, with s ^ = s i ∗ , j ∗ ( c ^ ) \hat{s}=s_{i^*,j^*}(\hat{c}) s ^ = s i ∗ , j ∗ ( c ^ ) ,
U i ∗ , j ∗ ≤ h F ( c ^ , U i ∗ , j ∗ ) + ( 1 − ζ h ) [ λ j ∗ h U i ∗ , j ˉ ∗ + ( 1 − λ j ∗ h ) I [ U j ∗ ] ( x i ∗ + h s ^ ) ] , U_{i^*,j^*}\le h\mathcal{F}(\hat{c},U_{i^*,j^*})+(1-\zeta h)\left[\lambda_{j^*}hU_{i^*,\bar{j}^*}+(1-\lambda_{j^*}h)\mathbb{I}[U_{j^*}](x_{i^*}+h\hat{s})\right], U i ∗ , j ∗ ≤ h F ( c ^ , U i ∗ , j ∗ ) + ( 1 − ζ h ) [ λ j ∗ h U i ∗ , j ˉ ∗ + ( 1 − λ j ∗ h ) I [ U j ∗ ] ( x i ∗ + h s ^ ) ] ,
V i ∗ , j ∗ ≥ h F ( c ^ , V i ∗ , j ∗ ) + ( 1 − ζ h ) [ λ j ∗ h V i ∗ , j ˉ ∗ + ( 1 − λ j ∗ h ) I [ V j ∗ ] ( x i ∗ + h s ^ ) ] . V_{i^*,j^*}\ge h\mathcal{F}(\hat{c},V_{i^*,j^*})+(1-\zeta h)\left[\lambda_{j^*}hV_{i^*,\bar{j}^*}+(1-\lambda_{j^*}h)\mathbb{I}[V_{j^*}](x_{i^*}+h\hat{s})\right]. V i ∗ , j ∗ ≥ h F ( c ^ , V i ∗ , j ∗ ) + ( 1 − ζ h ) [ λ j ∗ h V i ∗ , j ˉ ∗ + ( 1 − λ j ∗ h ) I [ V j ∗ ] ( x i ∗ + h s ^ ) ] .
Since U i ∗ , j ∗ > V i ∗ , j ∗ U_{i^*,j^*}>V_{i^*,j^*} U i ∗ , j ∗ > V i ∗ , j ∗ , we know from θ > 1 \theta>1 θ > 1 and (10) that
F ( c ^ , U i ∗ , j ∗ ) − F ( c ^ , V i ∗ , j ∗ ) < 0. \mathcal{F}(\hat{c},U_{i^*,j^*})-\mathcal{F}(\hat{c},V_{i^*,j^*})<0. F ( c ^ , U i ∗ , j ∗ ) − F ( c ^ , V i ∗ , j ∗ ) < 0.
Since U i ∗ , j ˉ ∗ − V i ∗ , j ˉ ∗ ≤ δ U_{i^*,\bar{j}^*}-V_{i^*,\bar{j}^*}\le\delta U i ∗ , j ˉ ∗ − V i ∗ , j ˉ ∗ ≤ δ and, by (29) together with U j ∗ − V j ∗ ≤ δ U_{j^*}-V_{j^*}\le\delta U j ∗ − V j ∗ ≤ δ on the grid,
I [ U j ∗ ] ( x i ∗ + h s ^ ) − I [ V j ∗ ] ( x i ∗ + h s ^ ) ≤ δ . \mathbb{I}[U_{j^*}](x_{i^*}+h\hat{s})-\mathbb{I}[V_{j^*}](x_{i^*}+h\hat{s})\le\delta. I [ U j ∗ ] ( x i ∗ + h s ^ ) − I [ V j ∗ ] ( x i ∗ + h s ^ ) ≤ δ .
Subtracting the two inequalities above and combining with these two bounds, we obtain
δ = U i ∗ , j ∗ − V i ∗ , j ∗ ≤ ( 1 − ζ h ) [ λ j ∗ h δ + ( 1 − λ j ∗ h ) δ ] = ( 1 − ζ h ) δ , \delta=U_{i^*,j^*}-V_{i^*,j^*}\le(1-\zeta h)\left[\lambda_{j^*}h\delta+(1-\lambda_{j^*}h)\delta\right]=(1-\zeta h)\delta, δ = U i ∗ , j ∗ − V i ∗ , j ∗ ≤ ( 1 − ζ h ) [ λ j ∗ h δ + ( 1 − λ j ∗ h ) δ ] = ( 1 − ζ h ) δ ,
i.e. ζ h δ ≤ 0 \zeta h\delta\le0 ζ h δ ≤ 0 , yielding a contradiction.
Case 2: 0 < θ < 1 0<\theta<1 0 < θ < 1 . Let us denote
( 1 − γ ) U = ( − U ~ ) 1 / θ , ( 1 − γ ) V = ( − V ~ ) 1 / θ , (1-\gamma)U=(-\widetilde{U})^{1/\theta},\qquad(1-\gamma)V=(-\widetilde{V})^{1/\theta}, ( 1 − γ ) U = ( − U ) 1/ θ , ( 1 − γ ) V = ( − V ) 1/ θ ,
then U ~ \widetilde{U} U and V ~ \widetilde{V} V are respectively sub- and supersolution of (34) . From Proposition 4.3, we know U ~ ⪯ V ~ \widetilde{U}\preceq\widetilde{V} U ⪯ V , hence U ⪯ V U\preceq V U ⪯ V . □
By Proposition 4.2, ( U ~ 1 , U ~ 2 ) (\widetilde{U}_1,\widetilde{U}_2) ( U 1 , U 2 ) and ( V ~ 1 , V ~ 2 ) (\widetilde{V}_1,\widetilde{V}_2) ( V 1 , V 2 ) are respectively a subsolution and a supersolution of (31) , so that Proposition 4.4 yields the following discrete barrier property.
Proposition 4.5. The solution V V V to (31) , if it exists, is unique and satisfies U ~ ⪯ V ⪯ V ~ \widetilde{U}\preceq V\preceq\widetilde{V} U ⪯ V ⪯ V .
A Howard–Newton algorithm
Following a similar design as in the finite-difference case (cf. [4, Algorithm 4.1]), (31) can be solved by the following Howard–Newton algorithm, in which the policy evaluation step requires an inner loop of Newton iterations because the aggregator F ( c , V i , j ) \mathcal{F}(c,V_{i,j}) F ( c , V i , j ) depends nonlinearly on V i , j V_{i,j} V i , j if θ ≠ 1 \theta\ne1 θ = 1 .
Algorithm 4.1 Howard–Newton algorithm
Initialize c i , j ( 0 ) = r x i + y j c_{i,j}^{(0)}=rx_i+y_j c i , j ( 0 ) = r x i + y j , and set n = 0 n=0 n = 0
repeat ▷ Outer loop
Saving policy: s i , j ( n ) = r x i + y j − c i , j ( n ) s_{i,j}^{(n)}=rx_i+y_j-c_{i,j}^{(n)} s i , j ( n ) = r x i + y j − c i , j ( n )
Policy evaluation: solve for V i , j ( n ) V_{i,j}^{(n)} V i , j ( n ) , j = 1 , 2 j=1,2 j = 1 , 2 , i = 0 , … , I i=0,\ldots,I i = 0 , … , I ,
V i , j ( n ) = h F ( c i , j ( n ) , V i , j ( n ) ) + ( 1 − ζ h ) [ λ j h V i , ȷ ˉ ( n ) + ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( n ) ) ] . (39) V_{i,j}^{(n)}=h\mathcal{F}\left(c_{i,j}^{(n)},V_{i,j}^{(n)}\right)+(1-\zeta h)\left[\lambda_jhV_{i,\bar{\jmath}}^{(n)}+(1-\lambda_jh)\mathbb{I}\left[V_j^{(n)}\right]\left(x_i+hs_{i,j}^{(n)}\right)\right]. \tag*{(39)} V i , j ( n ) = h F ( c i , j ( n ) , V i , j ( n ) ) + ( 1 − ζ h ) [ λ j h V i , ˉ ( n ) + ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( n ) ) ] . (39) by Newton’s method (the map V i , j ↦ h F ( c i , j ( n ) , V i , j ) V_{i,j}\mapsto h\mathcal{F}(c_{i,j}^{(n)},V_{i,j}) V i , j ↦ h F ( c i , j ( n ) , V i , j ) being smooth in V i , j V_{i,j} V i , j )
▷ Inner loop
Consumption policy update:
c i , j ( n + 1 ) = arg max c ∈ C j Δ ( x i ) { h F ( c , V i , j ( n ) ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( c ) ) } (40) c_{i,j}^{(n+1)}=\arg\max_{c\in C_j^\Delta(x_i)}\left\{h\mathcal{F}\left(c,V_{i,j}^{(n)}\right)+(1-\zeta h)(1-\lambda_jh)\mathbb{I}\left[V_j^{(n)}\right]\left(x_i+hs_{i,j}(c)\right)\right\} \tag*{(40)} c i , j ( n + 1 ) = arg c ∈ C j Δ ( x i ) max { h F ( c , V i , j ( n ) ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( c ) ) } (40) n ← n + 1 n\leftarrow n+1 n ← n + 1
until ∑ j max i ∣ c i , j ( n ) − c i , j ( n − 1 ) ∣ < T o l c \sum_j\max_i\left|c_{i,j}^{(n)}-c_{i,j}^{(n-1)}\right|<\mathrm{Tol}_c ∑ j max i c i , j ( n ) − c i , j ( n − 1 ) < Tol c
Proposition 4.6. We make the same assumption as Proposition 4.2. The sequence V ( n ) V^{(n)} V ( n ) generated by Algorithm 4.1 converges to a bounded grid function V V V , which is the unique solution to (31) .
Proof. From (39) , we observe that V ( n + 1 ) V^{(n+1)} V ( n + 1 ) is the solution to the discrete system
V i , j = h F ( c i , j ( n + 1 ) , V i , j ) + ( 1 − ζ h ) [ λ j h V i , ȷ ˉ + ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( n + 1 ) ) ] . (41) V_{i,j}=h\mathcal{F}\left(c_{i,j}^{(n+1)},V_{i,j}\right)+(1-\zeta h)\left[\lambda_jhV_{i,\bar{\jmath}}+(1-\lambda_jh)\mathbb{I}\left[V_j\right]\left(x_i+hs_{i,j}^{(n+1)}\right)\right]. \tag*{(41)} V i , j = h F ( c i , j ( n + 1 ) , V i , j ) + ( 1 − ζ h ) [ λ j h V i , ˉ + ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( n + 1 ) ) ] . (41)
From (39) and (40) at step n n n ,
V i , j ( n ) ≤ h F ( c i , j ( n + 1 ) , V i , j ( n ) ) + ( 1 − ζ h ) [ λ j h V i , ȷ ˉ ( n ) + ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( n + 1 ) ) ] . V_{i,j}^{(n)}\le h\mathcal{F}\left(c_{i,j}^{(n+1)},V_{i,j}^{(n)}\right)+(1-\zeta h)\left[\lambda_jhV_{i,\bar{\jmath}}^{(n)}+(1-\lambda_jh)\mathbb{I}\left[V_j^{(n)}\right]\left(x_i+hs_{i,j}^{(n+1)}\right)\right]. V i , j ( n ) ≤ h F ( c i , j ( n + 1 ) , V i , j ( n ) ) + ( 1 − ζ h ) [ λ j h V i , ˉ ( n ) + ( 1 − λ j h ) I [ V j ( n ) ] ( x i + h s i , j ( n + 1 ) ) ] .
i.e. V ( n ) V^{(n)} V ( n ) is a subsolution to (41) . We can then use a similar discrete comparison principle as Proposition 4.4 to show V ( n ) ⪯ V ( n + 1 ) V^{(n)}\preceq V^{(n+1)} V ( n ) ⪯ V ( n + 1 ) . Since V ( n ) V^{(n)} V ( n ) is a subsolution to (31) , we infer from Proposition 4.4 that for all n n n , V ( n ) ⪯ V ˘ Δ V^{(n)}\preceq\breve{V}^{\Delta} V ( n ) ⪯ V ˘ Δ . Therefore V ( n ) V^{(n)} V ( n ) converges to a limit V V V , and it is the unique solution of (31) from Proposition 4.5. □
We now discuss the implementation of the consumption policy update (40) . For a generic pair of grid functions V = ( V 1 , V 2 ) V=(V_1,V_2) V = ( V 1 , V 2 ) we define the finite-difference operator
D + ( V i , j ) = V i + 1 , j − V i , j Δ x , 0 ≤ i ≤ I − 1 and D − ( V i , j ) = V i , j − V i − 1 , j Δ x , 1 ≤ i ≤ I , \mathbf{D}^{+}(V_{i,j})=\frac{V_{i+1,j}-V_{i,j}}{\Delta x},\quad0\le i\le I-1\quad\text{and}\quad\mathbf{D}^{-}(V_{i,j})=\frac{V_{i,j}-V_{i-1,j}}{\Delta x},\quad1\le i\le I, D + ( V i , j ) = Δ x V i + 1 , j − V i , j , 0 ≤ i ≤ I − 1 and D − ( V i , j ) = Δ x V i , j − V i − 1 , j , 1 ≤ i ≤ I ,
D ( V i , j ) = { D + ( V 0 , j ) , i = 0 , V i + 1 , j − V i − 1 , j 2 Δ x , 0 < i < I , D − ( V I , j ) , i = I . (42) \mathbf{D}(V_{i,j})=
\begin{cases}
\mathbf{D}^{+}(V_{0,j}), & i=0,\\
\frac{V_{i+1,j}-V_{i-1,j}}{2\Delta x}, & 0<i<I,\\
\mathbf{D}^{-}(V_{I,j}), & i=I.
\end{cases} \tag*{(42)} D ( V i , j ) = ⎩ ⎨ ⎧ D + ( V 0 , j ) , 2Δ x V i + 1 , j − V i − 1 , j , D − ( V I , j ) , i = 0 , 0 < i < I , i = I . (42)
We observe that D + ( V k , j ) \mathbf{D}^{+}(V_{k,j}) D + ( V k , j ) is the slope of the interpolant I [ V j ] \mathbb{I}[V_j] I [ V j ] on the cell [ x k , x k + 1 ] [x_k,x_{k+1}] [ x k , x k + 1 ] . For a grid point ( x i , y j ) (x_i,y_j) ( x i , y j ) and an arrival point z z z , let
χ i , j ( z ) = r x i + y j + x i − z h (43) \chi_{i,j}(z)=r x_i+y_j+\frac{x_i-z}{h} \tag*{(43)} χ i , j ( z ) = r x i + y j + h x i − z (43)
be the consumption at ( x i , y j ) (x_i,y_j) ( x i , y j ) that leads to z = x i + h s i , j ( c ) z=x_i+h s_{i,j}(c) z = x i + h s i , j ( c ) . We consider the problem to solve for the policy update step (40) in Algorithm 4.1:
c ^ i , j : = arg max c ∈ C j Δ ( x i ) { h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) } (44) \widehat{c}_{i,j}:=\underset{c\in C_j^{\Delta}(x_i)}{\arg\max}\left\{h\mathcal{F}(c,V_{i,j})+(1-\zeta h)(1-\lambda_jh)\mathbb{I}[V_j]\left(x_i+h s_{i,j}(c)\right)\right\} \tag*{(44)} c i , j := c ∈ C j Δ ( x i ) arg max { h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) } (44)
with V = V ( n ) V=V^{(n)} V = V ( n ) in the policy update. For each cell 0 ≤ k ≤ I − 1 0\le k\le I-1 0 ≤ k ≤ I − 1 let
C j k ( x i ) : = { c > 0 : x i + h s i , j ( c ) ∈ [ x k , x k + 1 ] } = { c > 0 : χ i , j ( x k + 1 ) ≤ c ≤ χ i , j ( x k ) } , (45) C_j^k(x_i):=\{c>0:x_i+h s_{i,j}(c)\in[x_k,x_{k+1}]\}=\{c>0:\chi_{i,j}(x_{k+1})\le c\le\chi_{i,j}(x_k)\}, \tag*{(45)} C j k ( x i ) := { c > 0 : x i + h s i , j ( c ) ∈ [ x k , x k + 1 ]} = { c > 0 : χ i , j ( x k + 1 ) ≤ c ≤ χ i , j ( x k )} , (45)
and
c ^ i , j k : = arg max c ∈ C j k ( x i ) { h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) ⏟ Φ i , j ( c ) } . (46) \widehat{c}_{i,j}^k:=\underset{c\in C_j^k(x_i)}{\arg\max}\left\{\underbrace{h\mathcal{F}(c,V_{i,j})+(1-\zeta h)(1-\lambda_jh)\mathbb{I}[V_j]\left(x_i+h s_{i,j}(c)\right)}_{\Phi_{i,j}(c)}\right\}. \tag*{(46)} c i , j k := c ∈ C j k ( x i ) arg max ⎩ ⎨ ⎧ Φ i , j ( c ) h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) ⎭ ⎬ ⎫ . (46)
Since the cells cover [ x 0 , x I ] [x_0,x_I] [ x 0 , x I ] , we have C j Δ ( x i ) = ⋃ k C j k ( x i ) C_j^{\Delta}(x_i)=\bigcup_k C_j^k(x_i) C j Δ ( x i ) = ⋃ k C j k ( x i ) .
Lemma 4.7. Fix ( i , j ) (i,j) ( i , j ) and a cell k k k with χ i , j ( x k ) > 0 \chi_{i,j}(x_k)>0 χ i , j ( x k ) > 0 (otherwise C j k ( x i ) = ∅ C_j^{k}(x_i)=\varnothing C j k ( x i ) = ∅ ). If D + V k , j > 0 \mathbf{D}^{+}V_{k,j}>0 D + V k , j > 0 , let
c i , j k = ( ρ ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j ) ψ 1 − γ ψ ( ( 1 − γ ) V i , j ) 1 − γ ψ 1 − γ . (47) c_{i,j}^k=\left(\frac{\rho}{(1-\zeta h)(1-\lambda_jh)\mathbf{D}^{+}V_{k,j}}\right)^{\frac{\psi}{1-\gamma\psi}}\left((1-\gamma)V_{i,j}\right)^{\frac{1-\gamma\psi}{1-\gamma}}. \tag*{(47)} c i , j k = ( ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j ρ ) 1 − γ ψ ψ ( ( 1 − γ ) V i , j ) 1 − γ 1 − γ ψ . (47) Then the maximizer c ^ i , j k \widehat{c}_{i,j}^k c i , j k in (46) exists, is unique, and is given by
c ^ i , j k = { max { min { c i , j k , χ i , j ( x k ) } , χ i , j ( x k + 1 ) } , if D + V k , j > 0 , χ i , j ( x k ) , if D + V k , j ≤ 0. (48) \widehat{c}_{i,j}^k=
\begin{cases}
\max\left\{\min\left\{c_{i,j}^k,\chi_{i,j}(x_k)\right\},\chi_{i,j}(x_{k+1})\right\}, & \text{if }\mathbf{D}^{+}V_{k,j}>0,\\
\chi_{i,j}(x_k), & \text{if }\mathbf{D}^{+}V_{k,j}\le0.
\end{cases} \tag*{(48)} c i , j k = { max { min { c i , j k , χ i , j ( x k ) } , χ i , j ( x k + 1 ) } , χ i , j ( x k ) , if D + V k , j > 0 , if D + V k , j ≤ 0. (48)
Proof. For c ∈ C j k ( x i ) c\in C_j^k(x_i) c ∈ C j k ( x i ) the arrival point x i + h s i , j ( c ) = x i + h ( r x i + y j − c ) x_i+h s_{i,j}(c)=x_i+h(r x_i+y_j-c) x i + h s i , j ( c ) = x i + h ( r x i + y j − c ) lies in [ x k , x k + 1 ] [x_k,x_{k+1}] [ x k , x k + 1 ] , where I [ V j ] ( z ) = V k , j + D + V k , j ( z − x k ) \mathbb{I}[V_j](z)=V_{k,j}+\mathbf{D}^{+}V_{k,j}(z-x_k) I [ V j ] ( z ) = V k , j + D + V k , j ( z − x k ) . The objective Φ i , j ( c ) \Phi_{i,j}(c) Φ i , j ( c ) in (46) is strictly concave in c c c , with derivative h [ F c ( c , V i , j ) − ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j ] h\left[\mathcal{F}_c(c,V_{i,j})-(1-\zeta h)(1-\lambda_jh)\mathbf{D}^{+}V_{k,j}\right] h [ F c ( c , V i , j ) − ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j ] . If D + V k , j > 0 \mathbf{D}^{+}V_{k,j}>0 D + V k , j > 0 , the maximizer on the interval [ χ i , j ( x k + 1 ) , χ i , j ( x k ) ] ∩ ( 0 , ∞ ) [\chi_{i,j}(x_{k+1}),\chi_{i,j}(x_k)]\cap(0,\infty) [ χ i , j ( x k + 1 ) , χ i , j ( x k )] ∩ ( 0 , ∞ ) is c i , j k c_{i,j}^k c i , j k projected onto it. Since c i , j k > 0 c_{i,j}^k>0 c i , j k > 0 and χ i , j ( x k ) > 0 \chi_{i,j}(x_k)>0 χ i , j ( x k ) > 0 , the projection is given by the first line of (48) . If D + V k , j ≤ 0 \mathbf{D}^{+}V_{k,j}\le0 D + V k , j ≤ 0 , then F c ( c , V i , j ) − ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j > 0 \mathcal{F}_c(c,V_{i,j})-(1-\zeta h)(1-\lambda_jh)\mathbf{D}^{+}V_{k,j}>0 F c ( c , V i , j ) − ( 1 − ζ h ) ( 1 − λ j h ) D + V k , j > 0 , hence the objective Φ i , j ( c ) \Phi_{i,j}(c) Φ i , j ( c ) is increasing in c c c and the maximizer is the largest admissible consumption χ i , j ( x k ) \chi_{i,j}(x_k) χ i , j ( x k ) .
By Lemma 4.7 and C j ( x i ) = ⋃ k C j k ( x i ) C_j(x_i)=\bigcup_k C_j^k(x_i) C j ( x i ) = ⋃ k C j k ( x i ) , the global maximizer in (44) is obtained by comparing the cell-wise maximizers:
c ^ i , j = c ^ i , j k ∗ , k ∗ ∈ arg max k ∈ K i , j { h F ( c ^ i , j k , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ^ i , j k ) ) } . (49) \widehat{c}_{i,j}=\widehat{c}_{i,j}^{k^*},\qquad k^*\in\arg\max_{k\in K_{i,j}}\left\{h\mathcal{F}\left(\widehat{c}_{i,j}^k,V_{i,j}\right)+(1-\zeta h)(1-\lambda_jh)\mathbb{I}[V_j]\left(x_i+hs_{i,j}\left(\widehat{c}_{i,j}^k\right)\right)\right\}. \tag*{(49)} c i , j = c i , j k ∗ , k ∗ ∈ arg k ∈ K i , j max { h F ( c i , j k , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c i , j k ) ) } . (49)
where K i , j = { k : χ i , j ( x k ) > 0 } K_{i,j}=\{k:\chi_{i,j}(x_k)>0\} K i , j = { k : χ i , j ( x k ) > 0 } is the set of cells with admissible consumption, and ties are broken in favor of the smallest k k k . Computing (49) for all ( i , j ) (i,j) ( i , j ) solves (44) exactly, but requires O ( I ) O(I) O ( I ) operations per grid point and hence O ( I 2 ) O(I^2) O ( I 2 ) per policy update. In Section A we give an accelerated exact method that exploits the concavity of V j V_j V j on groups of cells, and in Section B an approximate alternative based on the first-order condition.
A monotone value iteration algorithm in the case 0 < θ < 1 0<\theta<1 0 < θ < 1
Throughout this section we assume 0 < θ < 1 0<\theta<1 0 < θ < 1 . To solve the scheme (31) in this case, we employ a direct value iteration algorithm, in which the value function is updated successively through an order preserving mapping.
We define the map V = ( V 1 , V 2 ) = Γ ( V ~ 1 , V ~ 2 ) V=(V_1,V_2)=\Gamma(\widetilde{V}_1,\widetilde{V}_2) V = ( V 1 , V 2 ) = Γ ( V 1 , V 2 ) :
V i , j = sup c ∈ C j Δ ( x i ) { h F ( c , V ~ i , j ) + ( 1 − ζ h ) [ λ j h V ~ i , ȷ ˉ + ( 1 − λ j h ) I [ V ~ j ] ( x i + h s i , j ( c ) ) ] } , (50) V_{i,j}=\sup_{c\in C_j^\Delta(x_i)}\left\{h\mathcal{F}(c,\widetilde{V}_{i,j})+(1-\zeta h)\left[\lambda_jh\widetilde{V}_{i,\bar{\jmath}}+(1-\lambda_jh)\mathbb{I}[\widetilde{V}_j]\left(x_i+hs_{i,j}(c)\right)\right]\right\}, \tag*{(50)} V i , j = c ∈ C j Δ ( x i ) sup { h F ( c , V i , j ) + ( 1 − ζ h ) [ λ j h V i , ˉ + ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) ] } , (50)
for j = 1 , 2 j=1,2 j = 1 , 2 and i = 0 , … , I i=0,\ldots,I i = 0 , … , I .
Proposition 4.2 yields directly the following result.
Lemma 4.8. For sufficiently small h > 0 h>0 h > 0 as in Proposition 4.2 , we have the barrier properties
(i). If U = Γ ( U ~ 1 , U ~ 2 ) U=\Gamma(\widetilde{U}_1,\widetilde{U}_2) U = Γ ( U 1 , U 2 ) , then U ⪰ U ~ U\succeq\widetilde{U} U ⪰ U .
(ii). If V = Γ ( V ~ 1 , V ~ 2 ) V=\Gamma(\widetilde{V}_1,\widetilde{V}_2) V = Γ ( V 1 , V 2 ) , then V ⪯ V ~ V\preceq\widetilde{V} V ⪯ V .
Proposition 4.9. Assume 0 < θ < 1 0<\theta<1 0 < θ < 1 . We have the following properties of Γ \Gamma Γ .
Monotonicity. If U = Γ ( U ~ 1 , U ~ 2 ) U=\Gamma(\widetilde{U}_1,\widetilde{U}_2) U = Γ ( U 1 , U 2 ) , V = Γ ( V ~ 1 , V ~ 2 ) V=\Gamma(\widetilde{V}_1,\widetilde{V}_2) V = Γ ( V 1 , V 2 ) and U ~ ⪯ V ~ \widetilde{U}\preceq\widetilde{V} U ⪯ V , then U ⪯ V U\preceq V U ⪯ V .
Invariance. If U ~ ⪯ V ~ ⪯ V ~ \widetilde{U}\preceq\widetilde{V}\preceq\widetilde{V} U ⪯ V ⪯ V and V = Γ ( V ~ 1 , V ~ 2 ) V=\Gamma(\widetilde{V}_1,\widetilde{V}_2) V = Γ ( V 1 , V 2 ) , then U ~ ⪯ V ⪯ V ~ \widetilde{U}\preceq V\preceq\widetilde{V} U ⪯ V ⪯ V .
Proof. From 0 < θ < 1 0<\theta<1 0 < θ < 1 and (10) , we know that U ~ ⪯ V ~ \widetilde{U}\preceq\widetilde{V} U ⪯ V yields F ( c , U ~ i , j ) ≤ F ( c , V ~ i , j ) \mathcal{F}(c,\widetilde{U}_{i,j})\le\mathcal{F}(c,\widetilde{V}_{i,j}) F ( c , U i , j ) ≤ F ( c , V i , j ) for all ( i , j ) (i,j) ( i , j ) and c ∈ C j Δ ( x i ) c\in C_j^\Delta(x_i) c ∈ C j Δ ( x i ) . Therefore,
sup c ∈ C j Δ ( x i ) { h F ( c , U ~ i , j ) + ( 1 − ζ h ) [ λ j h U ~ i , ȷ ˉ + ( 1 − λ j h ) I [ U ~ j ] ( x i + h s i , j ( c ) ) ] } ≤ sup c ∈ C j Δ ( x i ) { h F ( c , V ~ i , j ) + ( 1 − ζ h ) [ λ j h V ~ i , ȷ ˉ + ( 1 − λ j h ) I [ V ~ j ] ( x i + h s i , j ( c ) ) ] } . \begin{aligned}
\sup_{c\in C_j^\Delta(x_i)}\left\{h\mathcal{F}(c,\widetilde{U}_{i,j})+(1-\zeta h)\left[\lambda_jh\widetilde{U}_{i,\bar{\jmath}}+(1-\lambda_jh)\mathbb{I}[\widetilde{U}_j](x_i+hs_{i,j}(c))\right]\right\} \\
&\le\sup_{c\in C_j^\Delta(x_i)}\left\{h\mathcal{F}(c,\widetilde{V}_{i,j})+(1-\zeta h)\left[\lambda_jh\widetilde{V}_{i,\bar{\jmath}}+(1-\lambda_jh)\mathbb{I}[\widetilde{V}_j](x_i+hs_{i,j}(c))\right]\right\}.
\end{aligned} c ∈ C j Δ ( x i ) sup { h F ( c , U i , j ) + ( 1 − ζ h ) [ λ j h U i , ˉ + ( 1 − λ j h ) I [ U j ] ( x i + h s i , j ( c )) ] } ≤ c ∈ C j Δ ( x i ) sup { h F ( c , V i , j ) + ( 1 − ζ h ) [ λ j h V i , ˉ + ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c )) ] } .
Invariance follows from monotonicity and Lemma 4.8 . □
Taking advantage of the monotonicity and invariance properties of Γ \Gamma Γ established in Proposition 4.9 , we propose Algorithm 4.2, initialized at the discrete counterpart of the subsolution u ˘ \breve{u} u ˘ , namely U ~ i , j = u ˘ j ( x i ) \widetilde{U}_{i,j}=\breve{u}_j(x_i) U i , j = u ˘ j ( x i ) .
Algorithm 4.2 Monotone value iteration algorithm
Initialize V i , j ( 0 ) = U ˘ i , j V_{i,j}^{(0)}=\breve{U}_{i,j} V i , j ( 0 ) = U ˘ i , j , and set k = 0 k=0 k = 0
repeat
V ( k + 1 ) = Γ ( V 1 ( k ) , V 2 ( k ) ) V^{(k+1)}=\Gamma\left(V_1^{(k)},V_2^{(k)}\right) V ( k + 1 ) = Γ ( V 1 ( k ) , V 2 ( k ) )
k ← k + 1 k\leftarrow k+1 k ← k + 1
until ∑ j max i ∣ V i , j ( k ) − V i , j ( k − 1 ) ∣ 1 + ∣ V i , j ( k − 1 ) ∣ < T o l V \sum_j\max_i\frac{\left|V_{i,j}^{(k)}-V_{i,j}^{(k-1)}\right|}{1+\left|V_{i,j}^{(k-1)}\right|}<\mathrm{Tol}_V ∑ j max i 1 + V i , j ( k − 1 ) V i , j ( k ) − V i , j ( k − 1 ) < Tol V
Theorem 4.10. The sequence V ( k ) V^{(k)} V ( k ) generated by Algorithm 4.2 converges to a bounded grid function V V V , which is the unique solution to (31) .
Proof. We know from Lemma 4.8 that V ( 0 ) ⪯ V ( 1 ) V^{(0)}\preceq V^{(1)} V ( 0 ) ⪯ V ( 1 ) . From Proposition 4.9 and induction we deduce V ( k ) ⪯ V ( k + 1 ) V^{(k)}\preceq V^{(k+1)} V ( k ) ⪯ V ( k + 1 ) . Moreover, Proposition 4.9 shows that V ( k ) ⪯ V ˘ V^{(k)}\preceq\breve{V} V ( k ) ⪯ V ˘ . Therefore, V ( k ) V^{(k)} V ( k ) converges to a grid function V V V such that V = Γ ( V ) V=\Gamma(V) V = Γ ( V ) . From Proposition 4.5, V V V is the unique solution to (31) .
Remark 4.11. Algorithm 4.2 involves a maximization problem. In practice, we use Algorithm A.1 to solve (44) with V i , j = V i , j ( k ) V_{i,j}=V_{i,j}^{(k)} V i , j = V i , j ( k ) . This yields an optimal consumption c i , j ( k + 1 ) c_{i,j}^{(k+1)} c i , j ( k + 1 ) and Γ ( V 1 ( k ) , V 2 ( k ) ) \Gamma\left(V_1^{(k)},V_2^{(k)}\right) Γ ( V 1 ( k ) , V 2 ( k ) ) is given by V i , j ( k + 1 ) = h F ( c i , j ( k + 1 ) , V i , j ( k ) ) + ( 1 − ζ h ) [ λ j h V i , j ( k ) + ( 1 − λ j h ) I [ V j ( k ) ] ( x i + h s i , j ( k + 1 ) ) ] V_{i,j}^{(k+1)}=hF\left(c_{i,j}^{(k+1)},V_{i,j}^{(k)}\right)+(1-\zeta h)\left[\lambda_jhV_{i,j}^{(k)}+(1-\lambda_jh)\mathbb{I}[V_j^{(k)}]\left(x_i+hs_{i,j}^{(k+1)}\right)\right] V i , j ( k + 1 ) = h F ( c i , j ( k + 1 ) , V i , j ( k ) ) + ( 1 − ζ h ) [ λ j h V i , j ( k ) + ( 1 − λ j h ) I [ V j ( k ) ] ( x i + h s i , j ( k + 1 ) ) ] .
First order rate of convergence
Next, we analyze the convergence rate of the solution to the scheme (on the grid) towards the solution of the HJB equation. Such result for general HJB equations has been considered in e.g. [15]. The key ingredients in our analysis are the local regularity v j ∈ W l o c 2 , ∞ ( x ‾ , + ∞ ) v_j\in W_{\mathrm{loc}}^{2,\infty}(\underline{x},+\infty) v j ∈ W loc 2 , ∞ ( x , + ∞ ) (cf. Proposition 2.4) and a delicate expansion of s 1 s_1 s 1 and D v 1 Dv_1 D v 1 near the boundary x ‾ \underline{x} x established in Proposition 2.8. These estimates allow us to control the local interpolation error near x ‾ \underline{x} x and establish a first-order convergence rate. An analogous result for the finite difference scheme was established in [4, Theorem 4.10]. We start with preliminary results.
Lemma 4.12. We make the same assumptions as Proposition 2.5, and x ˉ ∈ G Δ x \bar{x}\in\mathcal{G}^{\Delta x} x ˉ ∈ G Δ x is sufficiently large such that s 2 ( x ˉ ) < 0 s_2(\bar{x})<0 s 2 ( x ˉ ) < 0 . Let v j v_j v j be the solution to the HJB equation (6) and s j s_j s j denotes the optimal saving policy. For any x ∈ G Δ x x\in\mathcal{G}^{\Delta x} x ∈ G Δ x , if h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) then there exists a constant C > 0 C>0 C > 0 such that
− C Δ x ≤ I [ v j ] ( x + h s j ( x ) ) − v j ( x + h s j ( x ) ) h ≤ 0 , (51) -C\Delta x\leq\frac{\mathbb{I}[v_j]\left(x+hs_j(x)\right)-v_j\left(x+hs_j(x)\right)}{h}\leq0, \tag*{(51)} − C Δ x ≤ h I [ v j ] ( x + h s j ( x ) ) − v j ( x + h s j ( x ) ) ≤ 0 , (51)
and
I [ v j ] ( x + h s j ( x ) ) − v j ( x ) h − s j ( x ) D v j ( x ) = O ( Δ x ) . (52) \frac{\mathbb{I}[v_j]\left(x+hs_j(x)\right)-v_j(x)}{h}-s_j(x)Dv_j(x)=O(\Delta x). \tag*{(52)} h I [ v j ] ( x + h s j ( x ) ) − v j ( x ) − s j ( x ) D v j ( x ) = O ( Δ x ) . (52)
Proof. From Proposition 2.4, v j v_j v j is concave, hence I [ v j ] ( x + h s j ( x ) ) − v j ( x + h s j ( x ) ) ≤ 0 \mathbb{I}[v_j]\left(x+hs_j(x)\right)-v_j\left(x+hs_j(x)\right)\leq0 I [ v j ] ( x + h s j ( x ) ) − v j ( x + h s j ( x ) ) ≤ 0 . Now we consider the lower bound in (51) in two steps.
Step 1. We consider the case j = 2 j=2 j = 2 , which is the easier one. From Proposition 2.5, we know s 2 ( x ) > 0 s_2(x)>0 s 2 ( x ) > 0 . Hence by differentiating (6) with j = 2 j=2 j = 2 , we infer D 2 v 2 ( x ) D^2v_2(x) D 2 v 2 ( x ) is bounded. Therefore, with v 2 ∈ W l o c 2 , ∞ v_2 \in W^{2,\infty}_{\mathrm{loc}} v 2 ∈ W loc 2 , ∞ we obtain v 2 ∈ W 2 , ∞ v_2 \in W^{2,\infty} v 2 ∈ W 2 , ∞ . Let us denote z 2 = x + h s 2 ( x ) z_2=x+hs_2(x) z 2 = x + h s 2 ( x ) for x ∈ G Δ x x\in G^{\Delta x} x ∈ G Δ x , then there exists x k , x k + 1 ∈ G Δ x x_k,x_{k+1}\in G^{\Delta x} x k , x k + 1 ∈ G Δ x such that x k ≤ z 2 ≤ x k + 1 x_k\le z_2\le x_{k+1} x k ≤ z 2 ≤ x k + 1 . We obtain
0 ≤ ( x k + 1 − z 2 ) ( z 2 − x k ) ≤ Δ x min { z 2 − x k , x k + 1 − z 2 } ≤ h ∣ s 2 ( x ) ∣ Δ x . 0\le(x_{k+1}-z_2)(z_2-x_k)\le\Delta x\min\{z_2-x_k,x_{k+1}-z_2\}\le h|s_2(x)|\Delta x. 0 ≤ ( x k + 1 − z 2 ) ( z 2 − x k ) ≤ Δ x min { z 2 − x k , x k + 1 − z 2 } ≤ h ∣ s 2 ( x ) ∣Δ x .
hence
∣ I [ v 2 ] ( z 2 ) − v 2 ( z 2 ) ∣ ≤ 1 2 ∥ D 2 v 2 ∥ L ∞ ( x k + 1 − z 2 ) ( z 2 − x k ) ≤ 1 2 ∥ D 2 v 2 ∥ L ∞ ∥ s 2 ∥ L ∞ h Δ x , \begin{aligned}
|I[v_2](z_2)-v_2(z_2)|\le\frac{1}{2}\|D^2v_2\|_{L^\infty}(x_{k+1}-z_2)(z_2-x_k) \\
&\le\frac{1}{2}\|D^2v_2\|_{L^\infty}\|s_2\|_{L^\infty}h\Delta x,
\end{aligned} ∣ I [ v 2 ] ( z 2 ) − v 2 ( z 2 ) ∣ ≤ 2 1 ∥ D 2 v 2 ∥ L ∞ ( x k + 1 − z 2 ) ( z 2 − x k ) ≤ 2 1 ∥ D 2 v 2 ∥ L ∞ ∥ s 2 ∥ L ∞ h Δ x ,
and this yields
sup x ∈ G Δ x ∣ I [ v 2 ] ( x + h s 2 ( x ) ) − v 2 ( x + h s 2 ( x ) ) ∣ ≤ C h Δ x . \sup_{x\in G^{\Delta x}}|I[v_2](x+hs_2(x))-v_2(x+hs_2(x))|\le Ch\Delta x. x ∈ G Δ x sup ∣ I [ v 2 ] ( x + h s 2 ( x )) − v 2 ( x + h s 2 ( x )) ∣ ≤ C h Δ x .
Step 2. We consider the case j = 1 j=1 j = 1 , which is the more difficult case since D 2 v 1 ( x ) D^2v_1(x) D 2 v 1 ( x ) blows up as x → x ‾ x\to\underline{x} x → x . From Proposition 2.8, there exists a sufficiently small constant η > 0 \eta>0 η > 0 such that
D 2 v 1 ( x ) ≥ − C x − x ‾ , 0 ≤ − s 1 ( x ) ≤ C x − x ‾ , − h s 1 ( x ) ≤ Δ x ∀ x ∈ ( x ‾ , η ) , (53) D^2v_1(x)\ge-\frac{C}{\sqrt{x-\underline{x}}},\qquad0\le-s_1(x)\le C\sqrt{x-\underline{x}},\qquad-hs_1(x)\le\Delta x\quad\forall x\in(\underline{x},\eta), \tag*{(53)} D 2 v 1 ( x ) ≥ − x − x C , 0 ≤ − s 1 ( x ) ≤ C x − x , − h s 1 ( x ) ≤ Δ x ∀ x ∈ ( x , η ) , (53)
where C C C is a positive constant which does not depend on x x x , h h h or Δ x \Delta x Δ x . The CFL condition − h s 1 ( x ) ≤ Δ x -hs_1(x)\le\Delta x − h s 1 ( x ) ≤ Δ x in (4.25) is deduced from − s 1 ( x ) ≤ C x − x ‾ -s_1(x)\le C\sqrt{x-\underline{x}} − s 1 ( x ) ≤ C x − x and h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) .
Since s 1 ( x ) ≤ 0 s_1(x)\le0 s 1 ( x ) ≤ 0 for all x ∈ [ x ‾ , x ˉ ] x\in[\underline{x},\bar{x}] x ∈ [ x , x ˉ ] , we know x + h s 1 ( x ) x+hs_1(x) x + h s 1 ( x ) is bracketed by two grids x k , x k + 1 ∈ G Δ x x_k,x_{k+1}\in G^{\Delta x} x k , x k + 1 ∈ G Δ x such that
z = x + h s 1 ( x ) < x , x k ≤ z < x k + 1 ≤ x . (54) z=x+hs_1(x)<x,\qquad x_k\le z<x_{k+1}\le x. \tag*{(54)} z = x + h s 1 ( x ) < x , x k ≤ z < x k + 1 ≤ x . (54)
It follows from v 1 ∈ W l o c 2 , ∞ v_1\in W^{2,\infty}_{\mathrm{loc}} v 1 ∈ W loc 2 , ∞ that v 1 ∈ W 2 , ∞ v_1\in W^{2,\infty} v 1 ∈ W 2 , ∞ on the compact domain [ η ′ , x ˉ ] [\eta',\bar{x}] [ η ′ , x ˉ ] where η ′ = x ‾ + ( η − x ‾ ) / 2 \eta'=\underline{x}+(\eta-\underline{x})/2 η ′ = x + ( η − x ) /2 . From h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) and the boundedness of s 1 s_1 s 1 on [ x ‾ , x ˉ ] [\underline{x},\bar{x}] [ x , x ˉ ] , we know that x k ≥ z − Δ x > η ′ x_k\ge z-\Delta x>\eta' x k ≥ z − Δ x > η ′ if Δ x \Delta x Δ x is sufficiently small. Similarly as in Step 1 , we can deduce
sup x ∈ G Δ x ∩ [ η , x ˉ ] ∣ I [ v 1 ] ( x + h s 1 ( x ) ) − v 1 ( x + h s 1 ( x ) ) ∣ ≤ 1 2 ∥ D 2 v 1 ∥ L ∞ [ η ′ , x ˉ ] ∥ s 1 ∥ L ∞ h Δ x . \sup_{x\in G^{\Delta x}\cap[\eta,\bar{x}]}|I[v_1](x+hs_1(x))-v_1(x+hs_1(x))|\le\frac{1}{2}\|D^2v_1\|_{L^\infty[\eta',\bar{x}]}\|s_1\|_{L^\infty}h\Delta x. x ∈ G Δ x ∩ [ η , x ˉ ] sup ∣ I [ v 1 ] ( x + h s 1 ( x )) − v 1 ( x + h s 1 ( x )) ∣ ≤ 2 1 ∥ D 2 v 1 ∥ L ∞ [ η ′ , x ˉ ] ∥ s 1 ∥ L ∞ h Δ x .
We now focus on the case x ‾ < x ≤ η \underline{x}<x\le\eta x < x ≤ η . From s 1 ( x ) < 0 s_1(x)<0 s 1 ( x ) < 0 , (4.25) and (4.26) we infer that in this regime
x ‾ − Δ x = x k ≤ z < x k + 1 = x ≤ η . \underline{x}-\Delta x=x_k\le z<x_{k+1}=x\le\eta. x − Δ x = x k ≤ z < x k + 1 = x ≤ η .
The interpolation error can be decomposed as
I [ v 1 ] ( z ) − v 1 ( z ) = x − z Δ x ∫ x k z ( τ − x k ) D 2 v 1 ( τ ) d τ ⏟ ( I ) + z − x k Δ x ∫ z x ( x − τ ) D 2 v 1 ( τ ) d τ ⏟ ( I I ) . (55) I[v_1](z)-v_1(z)=\underbrace{\frac{x-z}{\Delta x}\int_{x_k}^{z}(\tau-x_k)D^2v_1(\tau)\,\mathrm{d}\tau}_{(I)}+\underbrace{\frac{z-x_k}{\Delta x}\int_{z}^{x}(x-\tau)D^2v_1(\tau)\,\mathrm{d}\tau}_{(II)}. \tag*{(55)} I [ v 1 ] ( z ) − v 1 ( z ) = ( I ) Δ x x − z ∫ x k z ( τ − x k ) D 2 v 1 ( τ ) d τ + ( I I ) Δ x z − x k ∫ z x ( x − τ ) D 2 v 1 ( τ ) d τ . (55)
Since τ − x k ≤ z − x k ≤ Δ x \tau-x_k\le z-x_k\le\Delta x τ − x k ≤ z − x k ≤ Δ x , x − z = − h s 1 ( x ) x-z=-hs_1(x) x − z = − h s 1 ( x ) and D 2 v 1 ( τ ) < 0 D^2v_1(\tau)<0 D 2 v 1 ( τ ) < 0 in ( I ) (I) ( I ) , we infer
( I ) ≥ − h s 1 ( x ) ∫ x k z D 2 v 1 ( τ ) d τ . (I)\ge-hs_1(x)\int_{x_k}^{z}D^2v_1(\tau)\,\mathrm{d}\tau. ( I ) ≥ − h s 1 ( x ) ∫ x k z D 2 v 1 ( τ ) d τ .
Similarly x − τ ≤ x − z = − h s 1 ( x ) x-\tau\le x-z=-hs_1(x) x − τ ≤ x − z = − h s 1 ( x ) in ( I I ) (II) ( I I ) , and we deduce
( I I ) ≥ − h s 1 ( x ) ∫ z x D 2 v 1 ( τ ) d τ . (II)\ge-hs_1(x)\int_{z}^{x}D^2v_1(\tau)\,\mathrm{d}\tau. ( I I ) ≥ − h s 1 ( x ) ∫ z x D 2 v 1 ( τ ) d τ .
Therefore, we infer from (53) and (55) that there exists C > 0 C>0 C > 0 such that
I [ v 1 ] ( z ) − v 1 ( z ) ≥ − h s 1 ( x ) ∫ x k x D 2 v 1 ( τ ) d τ ≥ C h x − x ‾ ∫ x k x − C τ − x ‾ d τ ≥ − 2 C 2 h x − x ‾ ( x − x ‾ − x k − x ‾ ) ≥ − 2 C 2 h x − x ‾ Δ x x − x ‾ + x k − x ‾ ≥ − 2 C 2 h Δ x . (56) \begin{aligned}
\mathbb{I}[v_1](z)-v_1(z) &\geq-hs_1(x)\int_{x_k}^{x}D^2v_1(\tau)\,\mathrm{d}\tau\\
&\geq Ch\sqrt{x-\underline{x}}\int_{x_k}^{x}\frac{-C}{\sqrt{\tau-\underline{x}}}\,\mathrm{d}\tau\\
&\geq-2C^2h\sqrt{x-\underline{x}}\left(\sqrt{x-\underline{x}}-\sqrt{x_k-\underline{x}}\right)\\
&\geq-2C^2h\sqrt{x-\underline{x}}\frac{\Delta x}{\sqrt{x-\underline{x}}+\sqrt{x_k-\underline{x}}}\geq-2C^2h\Delta x. \tag*{(56)}
\end{aligned} I [ v 1 ] ( z ) − v 1 ( z ) ≥ − h s 1 ( x ) ∫ x k x D 2 v 1 ( τ ) d τ ≥ C h x − x ∫ x k x τ − x − C d τ ≥ − 2 C 2 h x − x ( x − x − x k − x ) ≥ − 2 C 2 h x − x x − x + x k − x Δ x ≥ − 2 C 2 h Δ x . (56)
Finally, we observe that I [ v 1 ] ( x ‾ ) − v 1 ( x ‾ ) = 0 \mathbb{I}[v_1](\underline{x})-v_1(\underline{x})=0 I [ v 1 ] ( x ) − v 1 ( x ) = 0 since s 1 ( x ‾ ) = 0 s_1(\underline{x})=0 s 1 ( x ) = 0 . We have therefore completed the proof of (51) with Step 1 and Step 2 . From Proposition 2.4, Proposition 2.8 and the uniform boundedness of s j s_j s j , we infer
v j ( x + h s j ( x ) ) − v j ( x ) h = s j ( x ) D v j ( x ) + O ( h ) , ∀ x ∈ [ x ‾ , x ‾ ] . \frac{v_j(x+hs_j(x))-v_j(x)}{h}=s_j(x)Dv_j(x)+O(h),\qquad\forall x\in[\underline{x},\overline{x}]. h v j ( x + h s j ( x )) − v j ( x ) = s j ( x ) D v j ( x ) + O ( h ) , ∀ x ∈ [ x , x ] .
We can then deduce (52) from (51) , h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) and
I [ v j ] ( x + h s j ( x ) ) − v j ( x ) h = I [ v j ] ( x + h s j ( x ) ) − v j ( x + h s j ( x ) ) h + v j ( x + h s j ( x ) ) − v j ( x ) h . \frac{\mathbb{I}[v_j](x+hs_j(x))-v_j(x)}{h}
=
\frac{\mathbb{I}[v_j](x+hs_j(x))-v_j(x+hs_j(x))}{h}
+
\frac{v_j(x+hs_j(x))-v_j(x)}{h}. h I [ v j ] ( x + h s j ( x )) − v j ( x ) = h I [ v j ] ( x + h s j ( x )) − v j ( x + h s j ( x )) + h v j ( x + h s j ( x )) − v j ( x ) .
Lemma 4.13. We make the same assumptions as in Lemma 4.12. Let ( v 1 , v 2 ) (v_1,v_2) ( v 1 , v 2 ) be the solution to (6) and c ^ j ( x ) \widehat{c}_j(x) c j ( x ) be the optimal control such that, for all x i ∈ G Δ x x_i\in G^{\Delta x} x i ∈ G Δ x ,
H ( x i , y j , v j ( x i ) , D v j ( x i ) ) = F ( c ^ j ( x i ) , v j ( x i ) ) + ( r x i + y j − c ^ j ( x i ) ) D v j ( x i ) , j ∈ { 1 , 2 } . (57) H(x_i,y_j,v_j(x_i),Dv_j(x_i))=F(\widehat{c}_j(x_i),v_j(x_i))+(rx_i+y_j-\widehat{c}_j(x_i))Dv_j(x_i),\qquad j\in\{1,2\}. \tag*{(57)} H ( x i , y j , v j ( x i ) , D v j ( x i )) = F ( c j ( x i ) , v j ( x i )) + ( r x i + y j − c j ( x i )) D v j ( x i ) , j ∈ { 1 , 2 } . (57) Suppose h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) , then with sufficiently small Δ x \Delta x Δ x we have c ^ j ( x i ) ∈ C j Δ x ( x i ) \widehat{c}_j(x_i)\in C_j^{\Delta x}(x_i) c j ( x i ) ∈ C j Δ x ( x i ) .
Proof. We first prove the case j = 1 j=1 j = 1 . First we observe from Proposition 2.5 that s 1 ( x ‾ ) = 0 s_1(\underline{x})=0 s 1 ( x ) = 0 , hence c ^ 1 ( x ‾ ) ∈ C 1 Δ x ( x ‾ ) \widehat{c}_1(\underline{x})\in C_1^{\Delta x}(\underline{x}) c 1 ( x ) ∈ C 1 Δ x ( x ) . We now consider the case x i > x ‾ x_i>\underline{x} x i > x , hence x i − x ‾ ≥ Δ x x_i-\underline{x}\geq\Delta x x i − x ≥ Δ x and Δ x ≤ Δ x x i − x ‾ \Delta x\leq\sqrt{\Delta x}\sqrt{x_i-\underline{x}} Δ x ≤ Δ x x i − x . From (17) , there exists a constant η > x ‾ \eta>\underline{x} η > x such that ∣ s 1 ( x i ) ∣ = O ( x i − x ‾ ) |s_1(x_i)|=O(\sqrt{x_i-\underline{x}}) ∣ s 1 ( x i ) ∣ = O ( x i − x ) for all x i ∈ ( x ‾ , η ] x_i\in(\underline{x},\eta] x i ∈ ( x , η ] . Therefore for all x i ∈ ( x ‾ , η ] x_i\in(\underline{x},\eta] x i ∈ ( x , η ] , h ∣ s 1 ( x i ) ∣ = O ( h x i − x ‾ ) = O ( Δ x x i − x ‾ ) = O ( Δ x ( x i − x ‾ ) ) h|s_1(x_i)|=O(h\sqrt{x_i-\underline{x}})=O(\Delta x\sqrt{x_i-\underline{x}})=O\left(\sqrt{\Delta x(x_i-\underline{x})}\right) h ∣ s 1 ( x i ) ∣ = O ( h x i − x ) = O ( Δ x x i − x ) = O ( Δ x ( x i − x ) ) . Moreover, with sufficiently small Δ x \Delta x Δ x and h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) , we can infer from the boundedness of s 1 s_1 s 1 that
sup x i ∈ G Δ x , η < x i ≤ x ‾ h ∣ s 1 ( x i ) ∣ ≤ η − x ‾ ≤ x i − x ‾ . \sup_{x_i\in G^{\Delta x},\,\eta<x_i\leq\overline{x}}h|s_1(x_i)|\leq\eta-\underline{x}\leq x_i-\underline{x}. x i ∈ G Δ x , η < x i ≤ x sup h ∣ s 1 ( x i ) ∣ ≤ η − x ≤ x i − x .
This implies x i + h s 1 ( x i ) ≥ x ‾ x_i+hs_1(x_i)\geq\underline{x} x i + h s 1 ( x i ) ≥ x holds for all x i ∈ G Δ x x_i\in G^{\Delta x} x i ∈ G Δ x if Δ x \Delta x Δ x is sufficiently small. The fact x i + h s 1 ( x i ) ≤ x ‾ x_i+hs_1(x_i)\leq\overline{x} x i + h s 1 ( x i ) ≤ x is trivial since s 1 ( x i ) < 0 s_1(x_i)<0 s 1 ( x i ) < 0 for all x > x ‾ x>\underline{x} x > x . We conclude c ^ 1 ( x i ) ∈ C 1 Δ x ( x i ) \widehat{c}_1(x_i)\in C_1^{\Delta x}(x_i) c 1 ( x i ) ∈ C 1 Δ x ( x i ) .
The case with j = 2 j=2 j = 2 is simpler, since there exists z ≤ x ‾ z\leq\overline{x} z ≤ x such that s 2 ≥ 0 s_2\geq0 s 2 ≥ 0 on [ x ‾ , z ] [\underline{x},z] [ x , z ] and s 2 ≤ 0 s_2\leq0 s 2 ≤ 0 on [ x ‾ , x ‾ ] [\overline{x},\overline{x}] [ x , x ] . Therefore we omit the details.
Theorem 4.14. We make the same assumptions as in Proposition 2.5, and x ‾ ∈ G Δ x \overline{x}\in G^{\Delta x} x ∈ G Δ x is sufficiently large such that s 2 ( x ‾ ) < 0 s_2(\overline{x})<0 s 2 ( x ) < 0 . Then for sufficiently small Δ x \Delta x Δ x and h = O ( Δ x ) h=O(\Delta x) h = O ( Δ x ) , there exists a constant C > 0 C>0 C > 0 , independent of Δ x \Delta x Δ x , such that
max j , x ∈ G Δ x ∣ v j ( x ) − V j Δ x ( x ) ∣ ≤ C Δ x . (58) \max_{j,\,x\in G^{\Delta x}}\left|v_j(x)-V_j^{\Delta x}(x)\right|\leq C\Delta x. \tag*{(58)} j , x ∈ G Δ x max v j ( x ) − V j Δ x ( x ) ≤ C Δ x . (58)
Proof. In this proof, C C C denotes a generic positive constant that may change from line to line.
Step 1. Let us define
σ = max j , x ∈ G Δ x { v j ( x ) − V j Δ ( x ) } = v j ∗ ( x ∗ ) − V j ∗ Δ ( x ∗ ) , (59) \sigma=\max_{j,x\in G^{\Delta x}}\{v_j(x)-V_j^{\Delta}(x)\}=v_{j^*}(x^*)-V_{j^*}^{\Delta}(x^*), \tag*{(59)} σ = j , x ∈ G Δ x max { v j ( x ) − V j Δ ( x )} = v j ∗ ( x ∗ ) − V j ∗ Δ ( x ∗ ) , (59)
and suppose σ > 0 \sigma>0 σ > 0 . Since v j ∈ C 1 ( x ‾ , + ∞ ) v_j\in C^1(\underline{x},+\infty) v j ∈ C 1 ( x , + ∞ ) , we know that if x ∗ > x ‾ x^*>\underline{x} x ∗ > x then
ρ θ v j ∗ ( x ∗ ) = H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ ) ) + λ j ∗ ( v j ∗ ‾ ( x ∗ ) − v j ∗ ( x ∗ ) ) . (60) \frac{\rho}{\theta}v_{j^*}(x^*)=H(x^*,y_{j^*},v_{j^*}(x^*),Dv_{j^*}(x^*))+\lambda_{j^*}(v_{\overline{j^*}}(x^*)-v_{j^*}(x^*)). \tag*{(60)} θ ρ v j ∗ ( x ∗ ) = H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ )) + λ j ∗ ( v j ∗ ( x ∗ ) − v j ∗ ( x ∗ )) . (60)
Since D v j Dv_j D v j is uniformly continuous in [ x ‾ , + ∞ ) [\underline{x},+\infty) [ x , + ∞ ) , (4.32) holds if x ∗ = x ‾ x^*=\underline{x} x ∗ = x .
We denote by c ^ j ∗ ( x ∗ ) \widehat{c}_{j^*}(x^*) c j ∗ ( x ∗ ) the optimal control given by (4.29), and s ^ j ∗ ( x ∗ ) = r x ∗ + y j ∗ − c ^ j ∗ ( x ∗ ) \widehat{s}_{j^*}(x^*)=rx^*+y_{j^*}-\widehat{c}_{j^*}(x^*) s j ∗ ( x ∗ ) = r x ∗ + y j ∗ − c j ∗ ( x ∗ ) . We know from (4.31) that for all j j j and x ∈ G Δ x x\in G^{\Delta x} x ∈ G Δ x , V j Δ ( x ) ≥ v j ( x ) − σ V_j^{\Delta}(x)\geq v_j(x)-\sigma V j Δ ( x ) ≥ v j ( x ) − σ , hence
V j ∗ Δ ( x ∗ ) ≥ v j ∗ ( x ∗ ) − σ , I [ V j ∗ Δ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) ≥ I [ v j ∗ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) − σ . V_{j^*}^{\Delta}(x^*)\geq v_{j^*}(x^*)-\sigma,\qquad\mathbb{I}[V_{j^*}^{\Delta}](x^*+h\widehat{s}_{j^*}(x^*))\geq\mathbb{I}[v_{j^*}](x^*+h\widehat{s}_{j^*}(x^*))-\sigma. V j ∗ Δ ( x ∗ ) ≥ v j ∗ ( x ∗ ) − σ , I [ V j ∗ Δ ] ( x ∗ + h s j ∗ ( x ∗ )) ≥ I [ v j ∗ ] ( x ∗ + h s j ∗ ( x ∗ )) − σ .
From v j ∗ ( x ∗ ) − σ = V j ∗ Δ ( x ∗ ) v_{j^*}(x^*)-\sigma=V_{j^*}^{\Delta}(x^*) v j ∗ ( x ∗ ) − σ = V j ∗ Δ ( x ∗ ) and the SL scheme (4.3), we infer
v j ∗ ( x ∗ ) − σ ≥ sup c ∈ C j ∗ Δ ( x ∗ ) { h F ( c , v j ∗ ( x ∗ ) ) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ‾ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) ) } − ( 1 − ζ h ) σ ≥ h F ( c ^ j ∗ ( x ∗ ) , v j ∗ ( x ∗ ) ) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ‾ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) ) − ( 1 − ζ h ) σ . \begin{aligned}
v_{j^*}(x^*)-\sigma
&\geq\sup_{c\in C_{j^*}^{\Delta}(x^*)}\{h\mathcal{F}(c,v_{j^*}(x^*))+(1-\zeta h)(\lambda_{j^*}hv_{\overline{j^*}}(x^*)\\
&\qquad+(1-\lambda_{j^*}h)\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c)))\}-(1-\zeta h)\sigma\\
&\geq h\mathcal{F}(\widehat{c}_{j^*}(x^*),v_{j^*}(x^*))+(1-\zeta h)(\lambda_{j^*}hv_{\overline{j^*}}(x^*)\\
&\qquad+(1-\lambda_{j^*}h)\mathbb{I}[v_{j^*}](x^*+h\widehat{s}_{j^*}(x^*)))-(1-\zeta h)\sigma.
\end{aligned} v j ∗ ( x ∗ ) − σ ≥ c ∈ C j ∗ Δ ( x ∗ ) sup { h F ( c , v j ∗ ( x ∗ )) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )))} − ( 1 − ζ h ) σ ≥ h F ( c j ∗ ( x ∗ ) , v j ∗ ( x ∗ )) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h s j ∗ ( x ∗ ))) − ( 1 − ζ h ) σ .
For the last inequality above, we used c ^ j ∗ ( x ∗ ) ∈ C j ∗ Δ ( x ∗ ) \widehat{c}_{j^*}(x^*)\in C_{j^*}^{\Delta}(x^*) c j ∗ ( x ∗ ) ∈ C j ∗ Δ ( x ∗ ) which follows from Lemma 4.13. This yields
ρ θ ( v j ∗ ( x ∗ ) − σ ) ≥ F ( c ^ j ∗ ( x ∗ ) , v j ∗ ( x ∗ ) ) + I [ v j ∗ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) − v j ∗ ( x ∗ ) h + λ j ∗ ( v j ∗ ‾ ( x ∗ ) − v j ∗ ( x ∗ ) ) + O ( h ) ≥ F ( c ^ j ∗ ( x ∗ ) , v j ∗ ( x ∗ ) ) + s ^ j ∗ ( x ∗ ) D v j ∗ ( x ∗ ) + λ j ∗ ( v j ∗ ‾ ( x ∗ ) − v j ∗ ( x ∗ ) ) + O ( Δ x ) . (61) \begin{aligned}
\frac{\rho}{\theta}(v_{j^*}(x^*)-\sigma)
&\geq\mathcal{F}(\widehat{c}_{j^*}(x^*),v_{j^*}(x^*))+\frac{\mathbb{I}[v_{j^*}](x^*+h\widehat{s}_{j^*}(x^*))-v_{j^*}(x^*)}{h}\\
&\qquad+\lambda_{j^*}(v_{\overline{j^*}}(x^*)-v_{j^*}(x^*))+O(h)\\
&\geq\mathcal{F}(\widehat{c}_{j^*}(x^*),v_{j^*}(x^*))+\widehat{s}_{j^*}(x^*)Dv_{j^*}(x^*)\\
&\qquad+\lambda_{j^*}(v_{\overline{j^*}}(x^*)-v_{j^*}(x^*))+O(\Delta x). \tag*{(61)}
\end{aligned} θ ρ ( v j ∗ ( x ∗ ) − σ ) ≥ F ( c j ∗ ( x ∗ ) , v j ∗ ( x ∗ )) + h I [ v j ∗ ] ( x ∗ + h s j ∗ ( x ∗ )) − v j ∗ ( x ∗ ) + λ j ∗ ( v j ∗ ( x ∗ ) − v j ∗ ( x ∗ )) + O ( h ) ≥ F ( c j ∗ ( x ∗ ) , v j ∗ ( x ∗ )) + s j ∗ ( x ∗ ) D v j ∗ ( x ∗ ) + λ j ∗ ( v j ∗ ( x ∗ ) − v j ∗ ( x ∗ )) + O ( Δ x ) . (61)
For the last inequality of (4.33) we used Lemma 4.12. From (4.32) and (4.33), we then deduce ζ σ ≤ O ( Δ x ) \zeta\sigma\leq O(\Delta x) ζ σ ≤ O ( Δ x ) .
Step 2. Now let us define
σ 2 = max j , x ∈ G Δ x { V j Δ ( x ) − v j ( x ) } = V j ∗ Δ ( x ∗ ) − v j ∗ ( x ∗ ) , x ∗ ∈ G Δ x , (62) \sigma_2=\max_{j,x\in G^{\Delta x}}\{V_j^{\Delta}(x)-v_j(x)\}=V_{j^*}^{\Delta}(x^*)-v_{j^*}(x^*),\qquad x^*\in G^{\Delta x}, \tag*{(62)} σ 2 = j , x ∈ G Δ x max { V j Δ ( x ) − v j ( x )} = V j ∗ Δ ( x ∗ ) − v j ∗ ( x ∗ ) , x ∗ ∈ G Δ x , (62)
and suppose σ 2 > 0 \sigma_2>0 σ 2 > 0 . We know from (4.34) that for all j j j and x ∈ G Δ x x\in G^{\Delta x} x ∈ G Δ x , V j Δ ( x ) ≤ v j ( x ) + σ 2 V_j^{\Delta}(x)\leq v_j(x)+\sigma_2 V j Δ ( x ) ≤ v j ( x ) + σ 2 , hence
V j ∗ Δ ( x ∗ ) ≤ v j ∗ ( x ∗ ) + σ 2 , I [ V j ∗ Δ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) ≤ I [ v j ∗ ] ( x ∗ + h s ^ j ∗ ( x ∗ ) ) + σ 2 , V_{j^*}^{\Delta}(x^*)\leq v_{j^*}(x^*)+\sigma_2,\qquad\mathbb{I}[V_{j^*}^{\Delta}](x^*+h\widehat{s}_{j^*}(x^*))\leq\mathbb{I}[v_{j^*}](x^*+h\widehat{s}_{j^*}(x^*))+\sigma_2, V j ∗ Δ ( x ∗ ) ≤ v j ∗ ( x ∗ ) + σ 2 , I [ V j ∗ Δ ] ( x ∗ + h s j ∗ ( x ∗ )) ≤ I [ v j ∗ ] ( x ∗ + h s j ∗ ( x ∗ )) + σ 2 ,
and we infer from the SL scheme (4.3) that
v j ∗ ( x ∗ ) + σ 2 ≤ sup c ∈ C j ∗ Δ ( x ∗ ) { h F ( c , v j ∗ ( x ∗ ) ) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ‾ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) ) } + ( 1 − ζ h ) σ 2 . \begin{aligned}
v_{j^*}(x^*)+\sigma_2
&\leq\sup_{c\in C_{j^*}^{\Delta}(x^*)}\{h\mathcal{F}(c,v_{j^*}(x^*))+(1-\zeta h)(\lambda_{j^*}hv_{\overline{j^*}}(x^*)\\
&\qquad+(1-\lambda_{j^*}h)\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c)))\}+(1-\zeta h)\sigma_2.
\end{aligned} v j ∗ ( x ∗ ) + σ 2 ≤ c ∈ C j ∗ Δ ( x ∗ ) sup { h F ( c , v j ∗ ( x ∗ )) + ( 1 − ζ h ) ( λ j ∗ h v j ∗ ( x ∗ ) + ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )))} + ( 1 − ζ h ) σ 2 .
It follows from direct calculation that
ρ θ ( v j ∗ ( x ∗ ) + σ 2 ) ≤ sup c ∈ C j ∗ Δ ( x ∗ ) { F ( c , v j ∗ ( x ∗ ) ) + ( 1 − ζ h ) ( 1 − λ j ∗ h ) I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) − v j ∗ ( x ∗ ) h } + ( 1 − ζ h ) λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ ) ) ≤ ( 1 − ζ h ) ( 1 − λ j ∗ h ) sup c ∈ C j ∗ Δ ( x ∗ ) { F ( c , v j ∗ ( x ∗ ) ) + I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) − v j ∗ ( x ∗ ) h } + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ ) ) + O ( h ) . (63) \begin{aligned}
\frac{\rho}{\theta}(v_{j^*}(x^*)+\sigma_2)
\le\sup_{c\in C_{j^*}^{\Delta}(x^*)}\left\{\mathcal{F}(c,v_{j^*}(x^*))+(1-\zeta h)(1-\lambda_{j^*}h)\frac{\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c))-v_{j^*}(x^*)}{h}\right\}
+(1-\zeta h)\lambda_{j^*}(v_{\bar{j}^*}(x^*)-v_{j^*}(x^*)) \\
&\le(1-\zeta h)(1-\lambda_{j^*}h)\sup_{c\in C_{j^*}^{\Delta}(x^*)}\left\{\mathcal{F}(c,v_{j^*}(x^*))+\frac{\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c))-v_{j^*}(x^*)}{h}\right\}
+\lambda_{j^*}(v_{\bar{j}^*}(x^*)-v_{j^*}(x^*))+O(h). \tag*{(63)}
\end{aligned} θ ρ ( v j ∗ ( x ∗ ) + σ 2 ) ≤ c ∈ C j ∗ Δ ( x ∗ ) sup { F ( c , v j ∗ ( x ∗ )) + ( 1 − ζ h ) ( 1 − λ j ∗ h ) h I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )) − v j ∗ ( x ∗ ) } + ( 1 − ζ h ) λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ )) ≤ ( 1 − ζ h ) ( 1 − λ j ∗ h ) c ∈ C j ∗ Δ ( x ∗ ) sup { F ( c , v j ∗ ( x ∗ )) + h I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )) − v j ∗ ( x ∗ ) } + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ )) + O ( h ) . (63)
For the last inequality, we used the fact that F ( c , v j ∗ ( x ∗ ) ) < 0 \mathcal{F}(c,v_{j^*}(x^*))<0 F ( c , v j ∗ ( x ∗ )) < 0 for all c ∈ C j ∗ Δ ( x ∗ ) c\in C_{j^*}^{\Delta}(x^*) c ∈ C j ∗ Δ ( x ∗ ) , hence F ( c , v j ∗ ( x ∗ ) ) < ( 1 − ζ h ) ( 1 − λ j ∗ h ) F ( c , v j ∗ ( x ∗ ) ) \mathcal{F}(c,v_{j^*}(x^*))<(1-\zeta h)(1-\lambda_{j^*}h)\mathcal{F}(c,v_{j^*}(x^*)) F ( c , v j ∗ ( x ∗ )) < ( 1 − ζ h ) ( 1 − λ j ∗ h ) F ( c , v j ∗ ( x ∗ )) .
Next, we observe that since v j ∗ v_{j^*} v j ∗ is concave, for all c ∈ C j ∗ Δ ( x ∗ ) c\in C_{j^*}^{\Delta}(x^*) c ∈ C j ∗ Δ ( x ∗ ) ,
I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) − v j ∗ ( x ∗ ) h ≤ v j ∗ ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) − v j ∗ ( x ∗ ) h ≤ ( r x ∗ + y j ∗ − c ) D v j ∗ ( x ∗ ) . \frac{\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c))-v_{j^*}(x^*)}{h}
\le\frac{v_{j^*}(x^*+h(rx^*+y_{j^*}-c))-v_{j^*}(x^*)}{h}
\le(rx^*+y_{j^*}-c)Dv_{j^*}(x^*). h I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )) − v j ∗ ( x ∗ ) ≤ h v j ∗ ( x ∗ + h ( r x ∗ + y j ∗ − c )) − v j ∗ ( x ∗ ) ≤ ( r x ∗ + y j ∗ − c ) D v j ∗ ( x ∗ ) .
It follows then
sup c ∈ C j ∗ Δ ( x ∗ ) { F ( c , v j ∗ ( x ∗ ) ) + I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c ) ) − v j ∗ ( x ∗ ) h } ≤ sup c ∈ C j ∗ Δ ( x ∗ ) { F ( c , v j ∗ ( x ∗ ) ) + ( r x ∗ + y j ∗ − c ) D v j ∗ ( x ∗ ) } ≤ H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ ) ) . (64) \sup_{c\in C_{j^*}^{\Delta}(x^*)}\left\{\mathcal{F}(c,v_{j^*}(x^*))+\frac{\mathbb{I}[v_{j^*}](x^*+h(rx^*+y_{j^*}-c))-v_{j^*}(x^*)}{h}\right\}
\le\sup_{c\in C_{j^*}^{\Delta}(x^*)}\left\{\mathcal{F}(c,v_{j^*}(x^*))+(rx^*+y_{j^*}-c)Dv_{j^*}(x^*)\right\}
\le H(x^*,y_{j^*},v_{j^*}(x^*),Dv_{j^*}(x^*)). \tag*{(64)} c ∈ C j ∗ Δ ( x ∗ ) sup { F ( c , v j ∗ ( x ∗ )) + h I [ v j ∗ ] ( x ∗ + h ( r x ∗ + y j ∗ − c )) − v j ∗ ( x ∗ ) } ≤ c ∈ C j ∗ Δ ( x ∗ ) sup { F ( c , v j ∗ ( x ∗ )) + ( r x ∗ + y j ∗ − c ) D v j ∗ ( x ∗ ) } ≤ H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ )) . (64)
We infer from (63) and (64) that
ρ θ ( v j ∗ ( x ∗ ) + σ 2 ) ≤ ( 1 − ζ h ) ( 1 − λ j ∗ h ) H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ ) ) + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ ) ) + O ( h ) = H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ ) ) + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ ) ) + O ( h ) . \frac{\rho}{\theta}(v_{j^*}(x^*)+\sigma_2)
\le(1-\zeta h)(1-\lambda_{j^*}h)H(x^*,y_{j^*},v_{j^*}(x^*),Dv_{j^*}(x^*))+\lambda_{j^*}(v_{\bar{j}^*}(x^*)-v_{j^*}(x^*))+O(h)
=H(x^*,y_{j^*},v_{j^*}(x^*),Dv_{j^*}(x^*))+\lambda_{j^*}(v_{\bar{j}^*}(x^*)-v_{j^*}(x^*))+O(h). θ ρ ( v j ∗ ( x ∗ ) + σ 2 ) ≤ ( 1 − ζ h ) ( 1 − λ j ∗ h ) H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ )) + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ )) + O ( h ) = H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ )) + λ j ∗ ( v j ˉ ∗ ( x ∗ ) − v j ∗ ( x ∗ )) + O ( h ) .
For the last equality, we used the boundedness of H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ ) ) H(x^*,y_{j^*},v_{j^*}(x^*),Dv_{j^*}(x^*)) H ( x ∗ , y j ∗ , v j ∗ ( x ∗ ) , D v j ∗ ( x ∗ )) . We observe that (4.32) holds here with j ∗ , x ∗ j^*,x^* j ∗ , x ∗ defined by (4.34), yielding σ 2 ≤ C Δ x \sigma_2\le C\Delta x σ 2 ≤ C Δ x .
Solution method for an Aiyagari model with recursive utility
The wealth-income distribution of agents is given by a measure m m m on [ x ‾ , ∞ ) × { y 1 , y 2 } [\underline{x},\infty)\times\{y_1,y_2\} [ x , ∞ ) × { y 1 , y 2 } of the form d m = ∑ j ∈ { 1 , 2 } d m j ( x ) ⊗ δ y j ( y ) dm=\sum_{j\in\{1,2\}}dm_j(x)\otimes\delta_{y_j}(y) d m = ∑ j ∈ { 1 , 2 } d m j ( x ) ⊗ δ y j ( y ) , where m j m_j m j denotes the distribution of wealth conditional on the income state y j y_j y j . It is shown in [5] that m j m_j m j has a density g j g_j g j and possibly a Dirac mass at x = x ‾ x=\underline{x} x = x weighted by μ j \mu_j μ j . The pair of densities ( g 1 , g 2 ) (g_1,g_2) ( g 1 , g 2 ) is described by the solution to a system of two stationary Fokker–Planck–Kolmogorov (FPK) equations in the sense of distributions:
− d d x [ s j ( x ) g j ( x ) ] + λ j ˉ g j ˉ ( x ) − λ j g j ( x ) = 0 , ∑ j ∫ x ≥ x ‾ g j ( x ) d x + ∑ j μ j = 1. (65) -\frac{d}{dx}[s_j(x)g_j(x)]+\lambda_{\bar{j}}g_{\bar{j}}(x)-\lambda_jg_j(x)=0,\qquad\sum_j\int_{x\ge\underline{x}}g_j(x)\,dx+\sum_j\mu_j=1. \tag*{(65)} − d x d [ s j ( x ) g j ( x )] + λ j ˉ g j ˉ ( x ) − λ j g j ( x ) = 0 , j ∑ ∫ x ≥ x g j ( x ) d x + j ∑ μ j = 1. (65)
In (65) , s j s_j s j is the optimal saving policy, the transport term accounts for movements in wealth while the two switching terms account for transitions between income states. To solve (65) , we follow [13] and employ the dual SL scheme
G i , j Δ = ( 1 − λ j h ) ∑ k β i ( x k + h s k , j ) G k , j Δ + λ j ˉ h G i , j ˉ Δ , ∑ i G i , 1 Δ + ∑ i G i , 2 Δ = 1 / Δ x , (66) G_{i,j}^{\Delta}=(1-\lambda_jh)\sum_k\beta_i(x_k+hs_{k,j})G_{k,j}^{\Delta}+\lambda_{\bar{j}}hG_{i,\bar{j}}^{\Delta},\qquad\sum_iG_{i,1}^{\Delta}+\sum_iG_{i,2}^{\Delta}=1/\Delta x, \tag*{(66)} G i , j Δ = ( 1 − λ j h ) k ∑ β i ( x k + h s k , j ) G k , j Δ + λ j ˉ h G i , j ˉ Δ , i ∑ G i , 1 Δ + i ∑ G i , 2 Δ = 1/Δ x , (66)
where ( β i ) i = 0 I (\beta_i)_{i=0}^{I} ( β i ) i = 0 I denotes the piecewise-linear Q 1 \mathbb{Q}_1 Q 1 nodal basis. This discretization depends only on the saving policy and the income-state transition probabilities, and is therefore independent of the particular discretization used for the HJB equation. Consequently, the scheme (66) applies to both approaches developed in this paper. We summarize the solution method for (66) in Algorithm 5.1.
Algorithm 5.1 Dual semi-Lagrangian scheme for the stationary FPK equation
Require: optimal saving policies s i , j s_{i,j} s i , j , j = 1 , 2 j=1,2 j = 1 , 2 , i = 0 , … , I i=0,\ldots,I i = 0 , … , I
Assemble transport matrices: for j = 1 , 2 j=1,2 j = 1 , 2 , build the sparse matrix M ( s j ) ∈ R ( I + 1 ) × ( I + 1 ) M(s_j)\in\mathbb{R}^{(I+1)\times(I+1)} M ( s j ) ∈ R ( I + 1 ) × ( I + 1 )
Assemble the dual (transposed) operator:
Q = ( ( 1 − λ 1 h ) M T ( s 1 ) − I λ 2 h I λ 1 h I ( 1 − λ 2 h ) M T ( s 2 ) − I ) Q=\begin{pmatrix}
(1-\lambda_1h)M^{T}(s_1)-I & \lambda_2hI\\
\lambda_1hI & (1-\lambda_2h)M^{T}(s_2)-I
\end{pmatrix} Q = ( ( 1 − λ 1 h ) M T ( s 1 ) − I λ 1 h I λ 2 h I ( 1 − λ 2 h ) M T ( s 2 ) − I )
Normalization: replace one row of Q Q Q (e.g. the first) by 1 T \mathbf{1}^{T} 1 T and set the corresponding right-hand side entry to 1 / Δ x 1/\Delta x 1/Δ x ; call the resulting system Q ~ G = b \widetilde{Q}G=b Q G = b
Solve the sparse linear system Q ~ G = b \widetilde{Q}G=b Q G = b for G = ( G 1 , G 2 ) T G=(G_1,G_2)^T G = ( G 1 , G 2 ) T
Project: G ← max ( G , 0 ) G\leftarrow\max(G,0) G ← max ( G , 0 ) , then renormalize G ← G / ( Δ x ∑ i ( G i , 1 + G i , 2 ) ) G\leftarrow G/(\Delta x\sum_i(G_{i,1}+G_{i,2})) G ← G / ( Δ x ∑ i ( G i , 1 + G i , 2 ))
return G 1 , G 2 G_1,G_2 G 1 , G 2
In (66) , the discrete density G i , j Δ G_{i,j}^{\Delta} G i , j Δ approximates g j ( x i ) g_j(x_i) g j ( x i ) for x i > x x_i>x x i > x , while G 0 , j Δ Δ x G_{0,j}^{\Delta}\Delta x G 0 , j Δ Δ x approximates the mass μ j \mu_j μ j at the borrowing constraint. For the implementation of the coupled HJB and FPK equations, it is useful to express the interpolation operator in matrix form. We define the matrix M ( s j ) ∈ R ( I + 1 ) × ( I + 1 ) M(s_j)\in\mathbb{R}^{(I+1)\times(I+1)} M ( s j ) ∈ R ( I + 1 ) × ( I + 1 ) by M ( s j ) i , k = β k ( x i + h s i , j ) M(s_j)_{i,k}=\beta_k(x_i+hs_{i,j}) M ( s j ) i , k = β k ( x i + h s i , j ) . For a grid function ϕ \phi ϕ , the matrix M ( s j ) M(s_j) M ( s j ) represents the composition of the interpolation operator with the shift x i ↦ x i + h s i , j x_i\mapsto x_i+hs_{i,j} x i ↦ x i + h s i , j : ( M ( s j ) ϕ ) i = I [ ϕ ] ( x i + h s i , j ) (M(s_j)\phi)_i=I[\phi](x_i+hs_{i,j}) ( M ( s j ) ϕ ) i = I [ ϕ ] ( x i + h s i , j ) . Its transpose satisfies ( M ( s j ) T ) i , k = β i ( x k + h s k , j ) (M(s_j)^T)_{i,k}=\beta_i(x_k+hs_{k,j}) ( M ( s j ) T ) i , k = β i ( x k + h s k , j ) , so that ( M ( s j ) T G j ) i = ∑ k β i ( x k + h s k , j ) G k , j Δ (M(s_j)^TG_j)_i=\sum_k\beta_i(x_k+hs_{k,j})G_{k,j}^{\Delta} ( M ( s j ) T G j ) i = ∑ k β i ( x k + h s k , j ) G k , j Δ . Consequently, the transport term in (66) is represented by the transpose M ( s j ) T M(s_j)^T M ( s j ) T .
For each r r r , solving the HJB equation yields the saving policy s j [ r ] s_j[r] s j [ r ] , which then gives the measure m j [ r ] m_j[r] m j [ r ] . We consider the aggregate wealth K [ r ] = ∑ j ∫ x ≥ x x d m j [ r ] \mathcal{K}[r]=\sum_j\int_{x\geq x}x\,dm_j[r] K [ r ] = ∑ j ∫ x ≥ x x d m j [ r ] . The Mean Field Game system for an Aiyagari model with the recursive utility (1.1) is (cf. [5, (1.7)]):
{ (i) 0 = max c ≥ 0 { f ( c , v j ) + ( r ∗ x + y j − c ) D v j ( x ) } + λ j ( v j ˉ ( x ) − v j ( x ) ) , c j ∗ ( x ) = arg max c ≥ 0 { f ( c , v j ) + ( r ∗ x + y j − c ) D v j ( x ) } , (ii) − ∂ ∂ x [ ( r ∗ x + y j − c j ∗ ( x ) ) g j ( x ) ] + λ j ˉ g j ˉ ( x ) − λ j g j ( x ) = 0 , ∫ x ≥ x g 1 ( x ) d x + ∫ x ≥ x g 2 ( x ) d x + ∑ j ∈ { 1 , 2 } μ j = 1. (67) \left\{
\begin{aligned}
\text{(i)}\quad&0=\max_{c\geq0}\{f(c,v_j)+(r^*x+y_j-c)Dv_j(x)\}+\lambda_j(v_{\bar{j}}(x)-v_j(x)),\\
&c_j^*(x)=\arg\max_{c\geq0}\{f(c,v_j)+(r^*x+y_j-c)Dv_j(x)\},\\
\text{(ii)}\quad&-\frac{\partial}{\partial x}\left[(r^*x+y_j-c_j^*(x))g_j(x)\right]+\lambda_{\bar{j}}g_{\bar{j}}(x)-\lambda_jg_j(x)=0,\\
&\int_{x\geq x}g_1(x)\,dx+\int_{x\geq x}g_2(x)\,dx+\sum_{j\in\{1,2\}}\mu_j=1.
\end{aligned}
\right. \tag*{(67)} ⎩ ⎨ ⎧ (i) (ii) 0 = c ≥ 0 max { f ( c , v j ) + ( r ∗ x + y j − c ) D v j ( x )} + λ j ( v j ˉ ( x ) − v j ( x )) , c j ∗ ( x ) = arg c ≥ 0 max { f ( c , v j ) + ( r ∗ x + y j − c ) D v j ( x )} , − ∂ x ∂ [ ( r ∗ x + y j − c j ∗ ( x )) g j ( x ) ] + λ j ˉ g j ˉ ( x ) − λ j g j ( x ) = 0 , ∫ x ≥ x g 1 ( x ) d x + ∫ x ≥ x g 2 ( x ) d x + j ∈ { 1 , 2 } ∑ μ j = 1. (67)
with r ∗ r^* r ∗ determined by the coupling condition
r ∗ = A α ( K [ r ∗ ] N ) α − 1 − δ = A α ( K [ m ( r ∗ ) ] N ) α − 1 − δ , N = λ 2 y 1 + λ 1 y 2 λ 1 + λ 2 . (68) r^* = A\alpha\left(\frac{K[r^*]}{N}\right)^{\alpha-1}-\delta= A\alpha\left(\frac{K[m(r^*)]}{N}\right)^{\alpha-1}-\delta,\qquad N=\frac{\lambda_2y_1+\lambda_1y_2}{\lambda_1+\lambda_2}. \tag*{(68)} r ∗ = A α ( N K [ r ∗ ] ) α − 1 − δ = A α ( N K [ m ( r ∗ )] ) α − 1 − δ , N = λ 1 + λ 2 λ 2 y 1 + λ 1 y 2 . (68)
Here, A A A , α \alpha α , and δ \delta δ denote, respectively, total factor productivity, the capital share in production, and the depreciation rate of capital. The equilibrium interest rate r ∗ r^* r ∗ clears the capital market if K [ r ∗ ] = K d ( r ∗ ) K[r^*]=K_d(r^*) K [ r ∗ ] = K d ( r ∗ ) , where K ( r ) K(r) K ( r ) is the household capital supply obtained from the invariant distribution and K d ( r ) = N ( A α r + δ ) 1 / ( 1 − α ) K_d(r)=N\left(\frac{A\alpha}{r+\delta}\right)^{1/(1-\alpha)} K d ( r ) = N ( r + δ A α ) 1/ ( 1 − α ) is the firm’s capital demand, with aggregate labor N N N .
For each given r r r , we use an HJB equation solver to obtain an approximation of the saving policy s j ( r ) s_j(r) s j ( r ) , which gives us G i , j Δ G_{i,j}^{\Delta} G i , j Δ from solving (66) . The supply of capital is approximated by K [ r ] = ∑ i x i ( G i , 1 ( r ) + G i , 2 ( r ) ) Δ x K[r]=\sum_i x_i\left(G_{i,1}(r)+G_{i,2}(r)\right)\Delta x K [ r ] = ∑ i x i ( G i , 1 ( r ) + G i , 2 ( r ) ) Δ x . For solving (67) , we define the excess capital supply E ( r ) : = K [ r ] − N ( A α r + δ ) 1 / ( 1 − α ) E(r):=K[r]-N\left(\frac{A\alpha}{r+\delta}\right)^{1/(1-\alpha)} E ( r ) := K [ r ] − N ( r + δ A α ) 1/ ( 1 − α ) and solve E ( r ) = 0 E(r)=0 E ( r ) = 0 by bisection.
Numerical examples
We consider the examples from [4] and fix the following parameters:
ρ = 0.05 , y 1 = 0.5 , y 2 = 1.5 , λ 1 = 0.2 , λ 2 = 0.2 , x = − 0.15 , x ˉ = 60 , \rho=0.05,\quad y_1=0.5,\quad y_2=1.5,\quad\lambda_1=0.2,\quad\lambda_2=0.2,\quad x=-0.15,\quad\bar{x}=60, ρ = 0.05 , y 1 = 0.5 , y 2 = 1.5 , λ 1 = 0.2 , λ 2 = 0.2 , x = − 0.15 , x ˉ = 60 ,
A = 0.95 , α = 0.35 , δ = 0.1. (69) A=0.95,\quad\alpha=0.35,\quad\delta=0.1. \tag*{(69)} A = 0.95 , α = 0.35 , δ = 0.1. (69)
The parameters in the first line of (6.1) are used to solve the HJB equations, while those in the second line determine the equilibrium condition (5.3) ( i i i A ) (iii_A) ( ii i A ) . Unless otherwise specified, we use the baseline discretization parameters Δ x = 0.01 \Delta x=0.01 Δ x = 0.01 and h / Δ x = 0.2 h/\Delta x=0.2 h /Δ x = 0.2 . We consider the following three tests for the Aiyagari model (or, equivalently, the corresponding Mean Field Game), varying the risk-aversion coefficient γ \gamma γ and the EIS coefficient ψ \psi ψ . The resulting equilibrium interest rates are reported below. For each test, we solve the HJB equation using Algorithm 4.1 and solve the full model using the methods described in Section 5.
Test 1 MFG: γ = 2 \gamma=2 γ = 2 , ψ = 0.4 \psi=0.4 ψ = 0.4 , r ∗ = 0.0288 r^*=0.0288 r ∗ = 0.0288 .
Test 2 MFG: γ = 4 \gamma=4 γ = 4 , ψ = 0.5 \psi=0.5 ψ = 0.5 , r ∗ = 0.0266 r^*=0.0266 r ∗ = 0.0266 .
Test 3 MFG: γ = 20 \gamma=20 γ = 20 , ψ = 0.5 \psi=0.5 ψ = 0.5 , r ∗ = 0.0086 r^*=0.0086 r ∗ = 0.0086 .
For comparison, the finite difference method in [4] with the same parameters and grid size Δ x = 0.01 \Delta x=0.01 Δ x = 0.01 yields equilibrium interest rates that agree with those reported above to four decimal places.
Next, we focus on the analysis of the HJB solver. To isolate these aspects from the equilibrium computation, we fix the interest rates at their corresponding equilibrium values. We refer to these experiments as Test 1 HJB , Test 2 HJB , and Test 3 HJB , respectively. Figure 1 illustrates that for Test 1 and 2 HJB , the sequences produced by Algorithm 4.1 are non decreasing as stated in Proposition 4.6 , i.e. V ( n ) ⪯ V ( n + 1 ) V^{(n)}\preceq V^{(n+1)} V ( n ) ⪯ V ( n + 1 ) . Figure 2 illustrates the fact, stated in Theorem 4.10, that Algorithm 4.2 produces a non decreasing sequence of discrete functions for Test 2 HJB . We also observe from Figure 1 and Figure 2 that both algorithms yield the same solution V V V in Test 2 HJB .
Figure 1. Algorithm 4.1 sequences of grid functions in Test 1 HJB (left) and Test 2 HJB (right)
Figure 2. Algorithm 4.2 constructs a non decreasing sequence of grid functions
Figure 3 below plots the error e n = ∥ V ( n ) − V ∗ ∥ ∞ = sup i , j ∣ V i , j ( n ) − V i , j ∗ ∣ e_n=\lVert V^{(n)}-V^*\rVert_\infty=\sup_{i,j}\lvert V_{i,j}^{(n)}-V_{i,j}^*\rvert e n = ∥ V ( n ) − V ∗ ∥ ∞ = sup i , j ∣ V i , j ( n ) − V i , j ∗ ∣ of the Howard–Newton iterates against the outer iteration n n n (log scale), with V ∗ V^* V ∗ the last iterate. The convergence is superlinear, and numerically consistent with quadratic convergence in the last iterations. The quadratic convergence of the Howard algorithm for viscous HJB equations has been established in [11, 12]. The analysis of the convergence rate of Algorithm 4.1 for the models of this paper, which have state constraints and use recursive utility, will be addressed in future work.
Figure 3. Convergence rate of Algorithm 4.1
The numerical results show that the Howard–Newton algorithm converges significantly faster than value iteration (VI). The slow convergence of VI is mainly due to the small coefficient ζ h \zeta_h ζ h . Although the SL scheme is not subject to the CFL condition and only requires h = O ( Δ x ) h = O(\Delta x) h = O ( Δ x ) (cf. Theorem 4.14), the state constraint and accuracy considerations limit the practical choice of h h h . Compared with the baseline h / Δ x = 0.2 h/\Delta x = 0.2 h /Δ x = 0.2 , one may take h / Δ x = 2 h/\Delta x = 2 h /Δ x = 2 when Δ x = 0.001 \Delta x = 0.001 Δ x = 0.001 while obtaining comparable numerical results, but h h h remains small. Therefore, the Howard–Newton algorithm is particularly advantageous for the models considered in this paper.
We supplement a numerical estimation of the convergence rate. The results are obtained with Algorithm 4.1. We compute a reference solution ( V 1 r e f , V 2 r e f ) (V_1^{\mathrm{ref}}, V_2^{\mathrm{ref}}) ( V 1 ref , V 2 ref ) on a fine grid with Δ x r e f = 0.0005 \Delta x_{\mathrm{ref}} = 0.0005 Δ x ref = 0.0005 . We then solve the scheme on a sequence of ten coarser grids, with Δ x \Delta x Δ x ranging from 0.005 0.005 0.005 to 0.05 0.05 0.05 , spaced geometrically. For each coarse grid spacing Δ x > Δ x r e f \Delta x > \Delta x_{\mathrm{ref}} Δ x > Δ x ref , the reference solution is interpolated onto the coarse grid G Δ x G^{\Delta x} G Δ x via the piecewise linear interpolation. We use e j Δ x = max x ∈ G Δ x ∣ [ V j r e f ] ( x ) − V j ( x ) ∣ e_j^{\Delta x} = \max_{x\in G^{\Delta x}}\left|[V_j^{\mathrm{ref}}](x)-V_j(x)\right| e j Δ x = max x ∈ G Δ x [ V j ref ] ( x ) − V j ( x ) to substitute max x ∈ G Δ x ∣ v j ( x ) − V j ( x ) ∣ \max_{x\in G^{\Delta x}}|v_j(x)-V_j(x)| max x ∈ G Δ x ∣ v j ( x ) − V j ( x ) ∣ . Figure 4 shows an approximately first-order convergence rate for both Test 1 HJB (left) and Test 2 HJB (right). For Test 1 HJB , where θ > 1 \theta> 1 θ > 1 , the observed rate is consistent with the theoretical error bound established in Theorem 4.14 . For Test 2 HJB , where 0 < θ < 1 0 < \theta< 1 0 < θ < 1 , this provides numerical evidence that the same convergence-rate bound holds.
Figure 4. Convergence rate in Test 1 HJB (left) and Test 2 HJB (right)
Finally, we numerically investigate the asymptotic behavior of s 1 s_1 s 1 near the borrowing constraint x ‾ \underline{x} x , as described in Proposition 2.8 . Let b ( x ) \mathbf{b}(x) b ( x ) denote the leading-order term in (2.14), namely,
b ( x ) = − 2 x ψ ϰ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) ψ − 1 − γ γ − 1 ( x − x ‾ ) , \mathbf{b}(x)=-\sqrt{\frac{2x^{\psi}}{\varkappa}}(rx+y_1)^{1+\psi^{-1}}\left((1-\gamma)v_1(x)\right)^{\frac{\psi-1-\gamma}{\gamma-1}}(x-\underline{x}), b ( x ) = − ϰ 2 x ψ ( r x + y 1 ) 1 + ψ − 1 ( ( 1 − γ ) v 1 ( x ) ) γ − 1 ψ − 1 − γ ( x − x ) ,
where ϰ \varkappa ϰ is given by (2.12). To evaluate ϰ \varkappa ϰ numerically, we approximate D v j ( x ‾ ) Dv_j(\underline{x}) D v j ( x ) by the forward difference D + ( V 0 , j ) \mathbf{D}^{+}(V_{0,j}) D + ( V 0 , j ) . In Figure 5 , we compare the numerical saving policy s 1 ( x ) s_1(x) s 1 ( x ) with the asymptotic approximation b ( x ) \mathbf{b}(x) b ( x ) near x ‾ \underline{x} x . For the numerical comparisons in Figure 5 , we solve both tests with h = Δ x = 0.001 h=\Delta x=0.001 h = Δ x = 0.001 to improve the accuracy near the borrowing constraint.
Figure 5. Asymptotic behavior of s 1 s_1 s 1 near x x x , in Test 1 HJB (left) and Test 2 HJB (right)
Concluding remarks
An important direction of our ongoing research is to extend the semi-Lagrangian methods to continuous-time heterogeneous agent models with aggregate risk. In such models, the equilibrium can be characterized by a master equation, in which the value function depends not only on the individual state variables but also on the distribution of agents and the aggregate state. The resulting high-dimensional problem poses substantial analytical and computational challenges. Recent numerical approaches include finite difference methods combined with neural operators [1 ] , semi-Lagrangian methods combined with neural networks [3], perturbation methods [9], global solution methods based on neural networks [21] and reinforcement learning methods [27]. We plan to investigate how the methods developed in this paper can be extended to solving master equations, which may provide a framework for studying the interaction between aggregate shocks, wealth heterogeneity, and preferences for the timing of uncertainty resolution.
Accelerated exact solution of the policy-update problem
Evaluating (4.21) requires a search over all indices k k k at each grid point, at a cost of O ( I ) O(I) O ( I ) . This cost can be reduced by exploiting the concavity of the value function. The exact value function is concave, but the iterate V j ( n ) V_j^{(n)} V j ( n ) need not be concave on the grid, although it typically is on large parts of it. We therefore partition the grid into regions on which V j ( n ) V_j^{(n)} V j ( n ) is concave.
Concave runs. For z ∈ [ x k , x k + 1 ] z \in[x_k,x_{k+1}] z ∈ [ x k , x k + 1 ] , I [ V j ] ( z ) \mathbb{I}[V_j](z) I [ V j ] ( z ) is affine in z z z with slope D + V k , j \mathbf{D}^{+}V_{k,j} D + V k , j . A run is a maximal set of consecutive indices k k k for which D + V k , j \mathbf{D}^{+}V_{k,j} D + V k , j is non-increasing in k k k ; a new run starts at index k k k whenever D + V k , j − D + V k − 1 , j > ε \mathbf{D}^{+}V_{k,j}-\mathbf{D}^{+}V_{k-1,j} > \varepsilon D + V k , j − D + V k − 1 , j > ε , with ε = 10 − 12 max { 1 , max k ∣ D + V k , j ∣ } \varepsilon= 10^{-12}\max\{1,\max_k|\mathbf{D}^{+}V_{k,j}|\} ε = 1 0 − 12 max { 1 , max k ∣ D + V k , j ∣ } . This splits { 0 , … , I − 1 } \{0,\ldots,I-1\} { 0 , … , I − 1 } into runs R 1 , … , R Q R_1,\ldots,R_Q R 1 , … , R Q , with Q = 1 Q=1 Q = 1 if V j V_j V j is concave on the grid and Q Q Q small if it fails to be concave only locally. On the union of the intervals [ x k , x k + 1 ] [x_k,x_{k+1}] [ x k , x k + 1 ] , k ∈ R q k \in R_q k ∈ R q , Φ i , j \Phi_{i,j} Φ i , j is concave in c c c on the corresponding consumptions ⋃ k ∈ R q [ χ i , j ( x k + 1 ) , χ i , j ( x k ) ] \bigcup_{k\in R_q}[\chi_{i,j}(x_{k+1}),\chi_{i,j}(x_k)] ⋃ k ∈ R q [ χ i , j ( x k + 1 ) , χ i , j ( x k )] .
Maximization on one run. On a run R q R_q R q , let k q ∈ R q ∩ K i , j k_q \in R_q \cap K_{i,j} k q ∈ R q ∩ K i , j be an index such that
max c ∈ C j k q ( x i ) Φ i , j ( c ) = max c ∈ ⋃ k ∈ R q C j k ( x i ) { h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c ) ) } . (70) \max_{c\in C_{j}^{k_q}(x_i)} \Phi_{i,j}(c)
=
\max_{c\in\bigcup_{k\in R_q} C_j^k(x_i)}
\left\{h\mathcal{F}(c,V_{i,j})+(1-\zeta h)(1-\lambda_jh)\mathbb{I}[V_j](x_i+hs_{i,j}(c))\right\}. \tag*{(70)} c ∈ C j k q ( x i ) max Φ i , j ( c ) = c ∈ ⋃ k ∈ R q C j k ( x i ) max { h F ( c , V i , j ) + ( 1 − ζ h ) ( 1 − λ j h ) I [ V j ] ( x i + h s i , j ( c )) } . (70)
that is, the consumptions C j k q ( x i ) C_j^{k_q}(x_i) C j k q ( x i ) contain a maximizer of Φ i , j \Phi_{i,j} Φ i , j over the run. Because Φ i , j \Phi_{i,j} Φ i , j is concave in c c c on the run, the sign of its derivative at the endpoints of the sets C j k ( x i ) C_j^k(x_i) C j k ( x i ) changes monotonically with k k k . Hence k q k_q k q can be found by bisection, using only the slopes D + V k , j \mathbf{D}^{+}V_{k,j} D + V k , j . The maximizer on the run is then c ^ i , j k q \widehat{c}_{i,j}^{k_q} c i , j k q from (4.20), which is computed only once per run.
Global argmax. We compare Φ i , j ( c ^ i , j k q ) \Phi_{i,j}(\widehat{c}_{i,j}^{k_q}) Φ i , j ( c i , j k q ) over q = 1 , … , Q q=1,\ldots,Q q = 1 , … , Q and take the largest (the smallest q q q in case of ties). Since the runs cover all indices k k k , this gives the same c ^ i , j \widehat{c}_{i,j} c i , j as (4.21), up to the tolerance ε \varepsilon ε and rounding. Algorithm A.1 summarizes the procedure.
Algorithm A.1 Exact argmax for the consumption policy update (4.12)
Require: V j = V j ( n ) V_j = V_j^{(n)} V j = V j ( n ) on the grid, j = 1 , 2 j = 1, 2 j = 1 , 2 ; tolerance ε \varepsilon ε
for j = 1 , 2 j = 1, 2 j = 1 , 2 do
Split the indices { 0 , … , I − 1 } \{0,\ldots,I-1\} { 0 , … , I − 1 } into runs R 1 , … , R Q \mathcal{R}_1,\ldots,\mathcal{R}_Q R 1 , … , R Q : a new run starts at index k k k whenever D + V k , j − D + V k − 1 , j > ε \mathbf{D}^{+}V_{k,j} - \mathbf{D}^{+}V_{k-1,j} > \varepsilon D + V k , j − D + V k − 1 , j > ε
for i = 0 , … , I i = 0,\ldots,I i = 0 , … , I do
for q = 1 , … , Q q = 1,\ldots,Q q = 1 , … , Q do
k q ← k_q \leftarrow k q ← an index in R q ∩ K i , j \mathcal{R}_q \cap K_{i,j} R q ∩ K i , j satisfying (A.1), found by bisection ▹ \triangleright ▹ concavity of Φ i , j \Phi_{i,j} Φ i , j on R q \mathcal{R}_q R q
Compute c ^ i , j k q \widehat{c}_{i,j}^{k_q} c i , j k q from (4.20)
end for
q ∗ ← q^* \leftarrow q ∗ ← smallest q q q maximizing Φ i , j ( c ^ i , j k q ) \Phi_{i,j}\left(\widehat{c}_{i,j}^{k_q}\right) Φ i , j ( c i , j k q ) ; c i , j ( n + 1 ) ← c ^ i , j k q ∗ c_{i,j}^{(n+1)} \leftarrow\widehat{c}_{i,j}^{k_{q^*}} c i , j ( n + 1 ) ← c i , j k q ∗
end for
end for
FOC-based approximate solution of the policy-update problem
If the grid Δ = ( h , Δ x ) \Delta= (h,\Delta x) Δ = ( h , Δ x ) is sufficiently fine, we expect the maximizer of the discrete problem to be well approximated by the control obtained from the continuous first-order condition (2.6), with the derivative D v j ( x i ) Dv_j(x_i) D v j ( x i ) replaced by D ( V i , j Δ ) . \mathbf{D}(V_{i,j}^{\Delta}). D ( V i , j Δ ) . This yields an approximate policy update method.
Algorithm B.1 uses the first-order-condition (FOC) as a locator to identify a candidate bracket [ x k 0 , x k 0 + 1 ) [x_{k_0},x_{k_0+1}) [ x k 0 , x k 0 + 1 ) ; if the raw gradient is nonpositive, no such guess is reliable, so we anchor the search at the household’s own grid index instead. We then recompute consumption c ^ i , j k \widehat{c}_{i,j}^{k} c i , j k exactly on this bracket using its own secant slope as in (4.20), and verify self-consistency by checking if indeed x k ≤ x i + h ( r x i + y j − c ^ i , j k ) ≤ x k + 1 x_k \leq x_i + h(rx_i+y_j-\widehat{c}_{i,j}^{k}) \leq x_{k+1} x k ≤ x i + h ( r x i + y j − c i , j k ) ≤ x k + 1 is satisfied. If it does not, we repeat the same closed-form calculation on a small number of neighboring brackets — since in practice the correct bracket is almost always adjacent to the FOC’s initial guess. Only when none of these candidates is self-consistent do we fall back to a brute-force search over the entire admissible grid, directly maximizing the right-hand side of the Bellman equation. The result may fail to be a global maximizer for (4.16), we therefore accept the candidate only where it does not decrease the one-step value.
Acknowledgments
The author thanks Yves Achdou for helpful discussions and valuable suggestions for improving the paper.
Claude (Anthropic) and ChatGPT (OpenAI) assisted with some derivations, numerical checks of the formulas, and Python code that generates the quantitative illustrations. The author assumes responsibility for all content.
Algorithm B.1 FOC-based policy update with safeguard (approximate solution of (40) )
Require: V j = V j ( n ) V_j=V_j^{(n)} V j = V j ( n ) and c j ( n ) c_j^{(n)} c j ( n ) on the grid x 0 < ⋯ < x I x_0<\cdots<x_I x 0 < ⋯ < x I , j = 1 , 2 j=1,2 j = 1 , 2 ; search radius L L L
for each grid point ( x i , y j ) (x_i,y_j) ( x i , y j ) do
if D ( V i , j ) > 0 \mathrm{D}(V_{i,j})>0 D ( V i , j ) > 0 then
Set
c ~ i , j ← max { min { ρ ψ [ D ( V i , j ) ] − ψ ∣ ( 1 − γ ) V i , j ∣ 1 − γ ψ 1 − γ ψ , x i − x h + r x i + y j } , x i − x ˉ h + r x i + y j } \widetilde{c}_{i,j}\leftarrow\max\left\{\min\left\{\rho^\psi[\mathrm{D}(V_{i,j})]^{-\psi}\left|(1-\gamma)V_{i,j}\right|^{\frac{1-\gamma\psi}{1-\gamma\psi}},\frac{x_i-x}{h}+rx_i+y_j\right\},\frac{x_i-\bar{x}}{h}+rx_i+y_j\right\} c i , j ← max { min { ρ ψ [ D ( V i , j ) ] − ψ ∣ ( 1 − γ ) V i , j ∣ 1 − γ ψ 1 − γ ψ , h x i − x + r x i + y j } , h x i − x ˉ + r x i + y j } k 0 ← k_0\leftarrow k 0 ← the index with x k 0 ≤ x i + h ( r x i + y j − c ~ i , j ) < x k 0 + 1 x_{k_0}\leq x_i+h(rx_i+y_j-\widetilde{c}_{i,j})<x_{k_0+1} x k 0 ≤ x i + h ( r x i + y j − c i , j ) < x k 0 + 1 , clipped to { 0 , … , I − 1 } \{0,\ldots,I-1\} { 0 , … , I − 1 }
else
k 0 ← min { i , I − 1 } k_0\leftarrow\min\{i,I-1\} k 0 ← min { i , I − 1 } ▷ anchor the search at the household’s own grid index
end if
k ∗ ← N U L L k^*\leftarrow\mathrm{NULL} k ∗ ← NULL ; l ← 0 l\leftarrow0 l ← 0
while k ∗ = N U L L k^*=\mathrm{NULL} k ∗ = NULL and l ≤ L l\leq L l ≤ L do ▷ search cells in order of distance from k 0 k_0 k 0
for k ∈ { k 0 − l , k 0 + l } k\in\{k_0-l,k_0+l\} k ∈ { k 0 − l , k 0 + l } with 0 ≤ k ≤ I − 1 0\leq k\leq I-1 0 ≤ k ≤ I − 1 and k ∗ = N U L L k^*=\mathrm{NULL} k ∗ = NULL do
if D + ( V k , j ) > 0 \mathrm{D}^{+}(V_{k,j})>0 D + ( V k , j ) > 0 then
Compute c ^ i , j k \widehat{c}_{i,j}^{k} c i , j k using (4.20)
if c ^ i , j k > 0 \widehat{c}_{i,j}^{k}>0 c i , j k > 0 and x k ≤ x i + h ( r x i + y j − c ^ i , j k ) ≤ x k + 1 x_k\leq x_i+h(rx_i+y_j-\widehat{c}_{i,j}^{k})\leq x_{k+1} x k ≤ x i + h ( r x i + y j − c i , j k ) ≤ x k + 1 then
k ∗ ← k k^*\leftarrow k k ∗ ← k
end if
end if
end for
l ← l + 1 l\leftarrow l+1 l ← l + 1
end while
if k ∗ ≠ N U L L k^*\ne\mathrm{NULL} k ∗ = NULL then
c ^ i , j ← c ^ i , j k ∗ \widehat{c}_{i,j}\leftarrow\widehat{c}_{i,j}^{k^*} c i , j ← c i , j k ∗ ▷ stationary point in cell [ x k ∗ , x k ∗ + 1 ] [x_{k^*},x_{k^*+1}] [ x k ∗ , x k ∗ + 1 ]
else ▷ fallback: maximize over grid nodes
For each node x q x_q x q with χ i , j ( x q ) = x i − x q h + r x i + y j > 0 \chi_{i,j}(x_q)=\frac{x_i-x_q}{h}+rx_i+y_j>0 χ i , j ( x q ) = h x i − x q + r x i + y j > 0 , q = 0 , … , I q=0,\ldots,I q = 0 , … , I , set
q ∗ ← arg max q Φ i , j ( χ i , j ( x q ) ) , c ^ i , j ← χ i , j ( x q ∗ ) q^*\leftarrow\underset{q}{\operatorname{arg\,max}}\ \Phi_{i,j}(\chi_{i,j}(x_q)),\qquad\widehat{c}_{i,j}\leftarrow\chi_{i,j}(x_{q^*}) q ∗ ← q arg max Φ i , j ( χ i , j ( x q )) , c i , j ← χ i , j ( x q ∗ ) end if
Safeguard: V i , j + ← h F ( c ^ i , j , V i , j ) + ( 1 − ζ h ) [ λ j h V i , j + ( 1 − λ j h ) [ V j ] ( x i + h ( r x i + y j − c ^ i , j ) ) ] V_{i,j}^{+}\leftarrow hF(\widehat{c}_{i,j},V_{i,j})+(1-\zeta h)\left[\lambda_jhV_{i,j}+(1-\lambda_jh)[V_j]\left(x_i+h(rx_i+y_j-\widehat{c}_{i,j})\right)\right] V i , j + ← h F ( c i , j , V i , j ) + ( 1 − ζ h ) [ λ j h V i , j + ( 1 − λ j h ) [ V j ] ( x i + h ( r x i + y j − c i , j ) ) ]
if V i , j + ≥ V i , j V_{i,j}^{+}\geq V_{i,j} V i , j + ≥ V i , j then c i , j ( n + 1 ) ← c ^ i , j c_{i,j}^{(n+1)}\leftarrow\widehat{c}_{i,j} c i , j ( n + 1 ) ← c i , j else c i , j ( n + 1 ) ← c i , j ( n ) c_{i,j}^{(n+1)}\leftarrow c_{i,j}^{(n)} c i , j ( n + 1 ) ← c i , j ( n )
end if
end for