Abstract
Stochastic optimal principle leads to the resolution of a partial differential equation (PDE), namely the Hamilton–Jacobi–Bellman (HJB) equation. In general, this equation cannot be solved analytically, thus numerical algorithms are the only tools to provide accurate approximations. The aims of this paper is to introduce a novel fitted finite volume method to solve high dimensional degenerated HJB equation from stochastic optimal control problems in high dimension (\( n\ge 3\)). The challenge here is due to the nature of our HJB equation which is a degenerated second-order partial differential equation coupled with an optimization problem. For such problems, standard scheme such as finite difference method losses its monotonicity and therefore the convergence toward the viscosity solution may not be guarantee. We discretize the HJB equation using the fitted finite volume method, well known to tackle degenerated PDEs, while the time discretisation is performed using the Implicit Euler scheme.. We show that matrices resulting from spatial discretization and temporal discretization are M-matrices. Numerical results in finance demonstrating the accuracy of the proposed numerical method comparing to the standard finite difference method are provided.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1 Introduction
The theory of optimal control for stochastic differential equations is mathematically challenging and it has been considered in many fields such as economics, engineering, biology and finance (Fleming and Soner 2006; Pham 2000). Stochastic optimal control problems have been studied by many researches (Krylov 2000; Jakobsen 2003; Peyrl et al. 2005). In some cases, the well posedness of such problems have been studied using methods such as viscosity and minimax techniques (see Crandall and Lions 1983; Crandall et al. 1984, 1992). In general, most of them do not have an explicit solution, therefore there have been many attempts to develop novel methods for their approximations. Numerical approximation of stochastic optimal control problem is therefore an active research area and has attracted a lot of attentions (Huang et al. 2004; Krylov 1999, 2005, 2000; Jakobsen 2003; Peyrl et al. 2005). The keys challenge for solving HJB equation are the low regularity of the solution and the lack of appropriate numerical methods to tackle the degeneracy of the differential operator in HJB equation. Indeed adding to the standard issue that we usually have when solving degenerated PDE, we need to couple with an optimization problem at each point of the grid and for each time step. A standard approach is based on Markov chain approximation, which suffers from time step limitations due to stability issues (Forsyth and Labahn 2007) as the method is indeed based on finite difference approach. Many stochastic optimal control problems such as Merton optimal problems have degenerated linear operator when the spatial variables approach the region near to zero. This degeneracy has an adverse impact on the accuracy when the finite difference method is used to solve such optimal problems (Dleuna Nyoumbi and Tambue 2021; Wilmott 2005) as the monotonicity of the scheme is usually lost. However, when solving HJB equation, the monotonicity also plays a key role to ensure the convergence of the numerical scheme toward the viscosity solution. Indeed in high dimensional Merton’s control problem, the matrix in the diffusion part is lower rank near the origin and it has been found in Bénézet et al. (2005) for optimization problem at every time step. The merit of the method is that it is absolutely stable in time because of the implicit nature of the time discretisation and yields a linear system with a positive-definite M-matrix, this is in contrast of the standard finite difference scheme.
The novel contribution of our paper over the existing literature can be summarized as
-
We have upgraded the fitted finite volume technique to discretize a more generalized HJB equation coupled with the implicit time-step** method for temporal discretization method and the iterative method for the optimization problem at every time step. To best of our knowledge such combination has not yet proposed so far to solve stochastic optimal control problems in high dimensional domain (\(n\ge 3\)).
-
We have proved that the corresponding matrices after spatial and temporal discretization are positive-definite M-matrices. We have demonstrated by numerical experiments that the proposed scheme can be more accurate than the standard finite difference scheme.
The rest of the paper is organized as follows. The stochastic optimal control problems is introduced in Sect. 2. In Sect. 3, we introduce the fitted finite volume in high dimensional domain and show that the system matrix of the resulting discrete equations is an M-matrix. Section 5 provides temporal discretization and optimization algorithm for spatial diiscretized HJB equation. In Sect. 6, we present some numerical examples illustrating the accuracy of the proposed method comparing to the standard finite difference. Finally, in Sect. 7, we summarise our finding.
2 Preliminaries and Formulation
Let \(\left( \varOmega , {\mathcal {F}}, {\mathbb {F}}=({\mathcal {F}}_t)_{t \ge 0}, {\mathbb {P}}\right) \) be a filtrated probability space. We consider the numerical approximation of the following controlled stochastic differential equation (SDE) defined in \({\mathbb {R}}^{ n}\) by
where
is the drift term and
the d-dimensional diffusion coefficients. Note that \( \omega _t \) are d-dimensional independent Brownian motion on \( \left( \varOmega , {\mathcal {F}}, ({\mathcal {F}}_t)_{t \ge 0}, {\mathbb {P}} \right) \), the control \( \alpha =(\alpha _t)_{t \ge 0}\) is an \( {\mathbb {F}} \)-adapted process, valued in \( {\mathcal {A}} \) compact convex subset of \( {\mathbb {R}}^m \, (m \ge 1)\) and satisfying some integrability conditions and/or state constraints. Precise assumptions on b and \( \sigma \) to ensure the existence of the unique solution \( x_t \) of (1) can be found in Pham (2000).
Given a function f from \([0, T] \times {\mathbb {R}}^n\times {\mathcal {A}} \) into \( {\mathbb {R}}\) and g from \({\mathbb {R}}^n \) into \( {\mathbb {R}}\), the performance functional is defined as
We assume that
The model problem consists to solve the following optimization
By dynamic programming, the resulting Hamilton–Jacobi–Bellamn (HJB) equation (Krylov 2000) is given by
where
and \( a^\alpha (t,x) = \dfrac{1}{2}\bigg (\sigma (t,x,\alpha )(\sigma (t,x,\alpha ))^T\bigg ) \). The resulting Hamilton–Jacobi–Bellman equation is typically a second order nonlinear partial differential equation, which can degenerate and therefore should to solve accurately.
3 Fitted Finite Volume Method in Three Dimension HJB
As we have already mentioned, even for Black–Scholes PDEs for options pricing, fitted technique for three dimensional space has be lacked in the literature to the best of our knowledge. The goal here is to update the technique in Dleuna Nyoumbi and Tambue (2021) and Wang (2004) to three dimensional HJB equation.
Consider the more generalized HJB Eq. (7) in dimension 3 which can be written in the form by setting \( \tau = T-t \)
where \(k(v(\tau ,x,y,z)) = A(\tau ,x,y,z,\alpha )\cdot \nabla v(\tau ,x,y,z)+ b(\tau ,x,y,z,\alpha )\,v(\tau ,x,y,z)\) with
Indeed this divergence form is not a restriction as the differentiation is respect to x, y and z and not respect to the control \(\alpha \), which may be discontinuous in some applications. We will assume that \(a_{21}= a_{12}, a_{31}= a_{13}\) and \( a_{32}= a_{23} \). We also define the following coefficients, which will help us to build our scheme \( a_{11}(t,x,y,\alpha ) = {\overline{a}}_1(t,x, y, \alpha )\,x^2, a_{22}(t,x,y,\alpha ) = {\overline{a}}_2(t,x,y,\alpha ) y^2,\; a_{33}(t,x,y,\alpha ) = {\overline{a}}_3(t,x,y,\alpha ) z^2\), \( a_{1 2}=a_{2 1} = d_1(t,x,y,\alpha )\, x\,y\,z\), \( a_{1 3}=a_{3 1} = d_2(t,x,y,\alpha )\, x\,y\,z \) and \( a_{2 3}=a_{3 2} = d_3(t,x,y,\alpha )\, x\,y\,z\). Although this initial value problem (9) is defined on the unbounded region \( {\mathbb {R}}^3 \), for computational reasons we often restrict to a bounded region. As usual the three dimensional domain is truncated to \( I_{x}= [0,x_{\text {max}}] \), \(I_{y}= [0,y_{\text {max}}] \) and \( I_{z}= [0,z_{\text {max}}] \). The truncated domain will be divided into \( N_1 \), \( N_2 \) and \( N_3 \) sub-intervals
\( i=0\ldots N_1-1,\,\,j=0\ldots N_2-1,\,\,\,k=0\ldots N_3-1\) with \( 0 = x_{0}< x_{1}< \cdots \cdots < x_{N_1} = x_{\text {max}},\,\) \(0 = y_{0}< y_{1}< \cdots \cdots < y_{N_2}= y_{\text {max}} \) and \( 0 = z_{0}< z_{1}< \cdots \cdots < z_{N_3}= z_{\text {max}} \). This defines on \( I_{x} \times I_{y} \times I_{z} \) a rectangular mesh.
By setting
for each \( i=1\ldots N_1-1\) \( j=1\ldots N_2-1\) and each \( k=1\ldots N_3-1\). These mid-points form a second partition of \( I_{x} \times I_{y} \times I_{z}\) if we define \( x_{-1/2} = x_{0}\), \( x_{N_1+1/2} = x_{\text {max}}\), \( y_{-1/2} = y_{0}\), \( y_{N_2+1/2} = y_{\text {max}}\) and \( z_{-1/2} = z_{0}\), \( z_{N_3+1/2} = z_{\text {max}}\). For each \(i = 0, 1, \ldots ,N_1 \), \(j = 0, 1, \ldots ,N_2 \) and \(k = 0, 1,\ldots ,N_3 \), we set \(h_{x_i} = x_{i+1/2} - x_{i-1/2} \), \(h_{y_j} = y_{j+1/2} - y_{j-1/2} \), \(h_{z_k} = z_{k+1/2} - z_{k-1/2} \) and define the grids points as
Integrating both size of (9) over \( {\mathcal {R}}_{i,j,k}=\left[ x_{i-1/2}, x_{i+1/2} \right] \times \left[ y_{j-1/2}, y_{j+1/2}\right] \times \left[ z_{k-1/2}, z_{k+1/2}\right] \) we have
for \( i =1,2,\ldots , N_1-1 \), \( j =1,2,\ldots , N_2-1 \), \(k =1,2,\ldots , N_3-1 \).
Applying the mid-points quadrature rule to the first and the last point terms, we obtain the above
for \( i= 1,2,\ldots N_1-1 \), \( j= 1,2,\ldots N_2-1 \), \( k= 1,2,\ldots N_3-1 \) where \( l_{i,j,k} = \left( x_{i+1/2} - x_{i-1/2} \right) \times \left( y_{j+1/2} - y_{j-1/2}\right) \times \left( z_{k+1/2} - z_{k-1/2}\right) \) is the volume of \( {\mathcal {R}}_{i,j,k} \). Note that \( v_{i,j,k}(\tau ) \) denotes the nodal approximation to \( v(\tau , x_{i}, y_{j}, z_k) \) at each point of the grid.
We now consider the approximation of the middle term in (13). Let \(\mathbf{n} \) denote the unit vector outward-normal to \( \partial {\mathcal {R}}_{i,j,k} \). By Ostrogradski Theorem, integrating by parts and using the definition of flux k, we have
Note that
We shall look at (14) term by term. For the first term we want to approximate the integral by a constant, i.e,
To achieve this, it is clear that we now need to derive approximations of the \( k (v) \cdot \mathbf{n} \) defined above at the mid-point \( \left( x_{i+1/2},y_{j},z_{k} \right) \), of the interval \( I_{x_{i}} \) for \( i = 0, 1,\ldots N_1-1\). This discussion is divided into two cases for \( i \ge 1 \), and \( i = 0\, \) on the interval \( I_{x_0} = [0,x_{1}] \). This is really an extension of the two dimensional fitted finite volume presented (Huang et al. 2010).
Case I: For \( i\ge 1 \).
Let set \( a_{11}(\tau , x, y, z, \alpha ) = {\overline{a}}_1(\tau , x, y, z, \alpha )\,x^2 \). We approximate the term \( \left( a_{11} \dfrac{\partial v}{\partial x}+ x\,b_1\,v \right) \) by solving the following two points boundary value problem
integrating (17) yields the first-order linear equations
where \( C_1 \) denotes an additive constant. As in Huang et al. (2010), we get
Therefore,
where \( \beta _{i,j,k}(\tau ) =\dfrac{{b_1}_{i+1/2,j,k}(\tau ,\alpha _{i,j,k})}{{{\overline{a}}_1}_{i+1/2,j,k}(\tau ,\alpha _{i,j,k})} \), \( a_{12} = a_{21} = d_{1}(\tau ,x,y,z,\alpha )\,x\,y\,z \) and \( a_{13} = a_{31} = d_{2}(\tau ,x,y,z,\alpha )\,x\,y\,z \).
Note that in this deduction, we have assumed that \( {b_1}_{i+1/2,j,k}(\tau ,\alpha _{i,j,k}) \ne 0 \). Finally, we use the forward difference,
We finally have
Similarly, the second term in (14) can be approximated by
Case II Approximation of the flux at \( i = 0 \) on the interval \( I_{x_0} = [0,x_1] \). Note that the analysis in the case I does not apply to the approximation of the flux on \( I_{x_0} \) because it is the degenerated zone. Therefore, we reconsider the following form
where \( C_2 \) is an unknown constant to be determined. Integrating (23), we find
and deduce that
Remark 1
Notice that if \( I_{x}= [\zeta ,x_{\text {max}}]\) with \(\zeta \ne 0 \), we do not need to truncate the interval \( I_x \), we just apply the fitted finite volume method directly as for \( i \ge 1\).
Case III For \( j\ge 1 \). For the third term in (14) we want to approximate the integral by a constant, i.e,
Following the same procedure for the case I of this section, we find that
where \( {\beta _1}{i,j,k}(\tau ) =\dfrac{{b_2}_{i,j+1/2,k}(\tau ,\alpha _{i,j,k})}{{{\overline{a}}_2}_{i,j+1/2,k}(\tau ,\alpha _{i,j,k})} \), \( a_{22}(\tau , x, y, z,\alpha ) = {{\overline{a}}_2}(\tau ,x,y ,z,\alpha )\,y^2, \) and \( a_{23} = a_{32} = d_{3}(\tau ,x,y,z,\alpha )\,x\,y\,z\). Similary, the fourth term in (14) can be approximated by
Case IV Approximation of the flux at \( I_{y_0} \) i.e for \(j= 0 \). Using the same procedure for the approximation of the flux at \( I_{x_0} \), we deduce that
For the fifth term in (14) we want to approximate the integral with a constant. Following the same procedure as in the case I and case III, we have
where \( {\beta _2}{i,j,k}(\tau ) =\dfrac{{b_3}_{i,j,k+1/2}(\tau ,\alpha _{i,j,k})}{\bar{a_3}_{i,j,k+1/2}(\tau ,\alpha _{i,j,k})} \), \( a_{33}(\tau , x, y, z,\alpha ) = {\overline{a}}_3(\tau ,x,y ,z,\alpha )\,z^2 \).
Similarly, the sixth term in (14) can be approximated by
Case V Approximation of the flux at \( I_{z_0} \). Using the same procedure for the Approximation of the flux at \( I_{z_0} \), we deduce that
Equation (13) becomes by replacing the flux by his value for \( i = 1,\ldots ,N_1-1 \), \( j = 1,\ldots ,N_2-1 \), \( k = 1,\ldots ,N_3-1 \) and \( N =(N_1-1)\times (N_2-1)\times (N_3-1) \)
This can be rewritten as the Ordinary Differential Equation (ODE) coupled with optimization
or
where \( A (\tau ,\alpha ) = - E (\tau ,\alpha )\) is an \(N\times N\) matrix, \( {\mathcal {A}}^{N} = \underset{(N_{1}-1)\times (N_2-1)\times (N_3-1)}{\underbrace{{\mathcal {A}} \times {\mathcal {A}}\times \cdots \times {\mathcal {A}}}} \) \(G (\tau , \alpha ) =-F(\tau , \alpha ) \) depends of the boundary condition and the term c, \(\mathbf{v} = \left( v_{i,j,k}\right) \). By setting \(n_1=N_1-1,\; n_2=N_2-1; \;n_3=N_3-1, \;\; I:=I (i,j,k)= i + (j-1)n_1 +(k-1)n_1 n_2\) and \(J:=J (i',j',k')= i' + (j'-1)n_1 +(k'-1)n_1 n_2 \), we have \(E (\tau , \alpha ) (I,J)= \left( e_{i',j',k'}^{i,j,k}\right) \), \(i', i= 1,\ldots , N_1-1 \), \( j',j = 1,\ldots , N_2-1 \) and \(k', k = 1,\ldots , N_3-1 \) where the coefficients are defined by
and
for \( i = 2,\ldots , N_1-1 \), \( j = 2,\ldots , N_2-1 \) and \( k = 2,\ldots , N_3-1 \) and
G collects the given homogeneous boundary therm \( v_{0,j,k},\, v_{i,0,k}, \,v_{i,j,0},\, v_{N_1,j,k}, \, v_{i,N_2,k}\, \) and \(v_{i,j,N_3} \) for \( i = 1,\ldots , N_1-1 \), \( j = 1,\ldots , N_2-1 \) and \( k = 1,\ldots , N_3-1 \).
Theorem 1
Assume that the coefficients of A given by (10) are positive and \(c<0\).Footnote 1
Let
if h is relatively small then the matrix \(E (\tau ,\alpha )\) in the system (34) is an M-matrix for any \( \alpha _{i,j,k} \,\in \,{\mathcal {A}}^{N}\).
Proof
Let us show that \(E(\tau ,\alpha ) \) has positive diagonals, non-positive off-diagonals, and is diagonally dominant. We first note that
for \( i = 1,\ldots , N_1-1 \), \( j = 1,\ldots , N_2-1 \), \( k = 1,\ldots , N_3-1 \) and all \( {b_1}_{i+1/2,j,k}(\tau ,\alpha _{i,j,k}) \ne 0,\,\, {b_2}_{i,j+1/2,k}(\tau ,\alpha _{i,j,k}) \ne 0, \,\,{b_3}_{i,j,k+1/2}(\tau ,\alpha _{i,j,k}) \ne 0\) with \( \bar{a_1}_{i,j,k}(\tau ,\alpha _{i,j,k}) > 0 \), \( \bar{a_2}_{i,j,k}(\tau ,\alpha _{i,j,k}) > 0\) and \( \bar{a_3}_{i,j,k}(\tau ,\alpha _{i,j,k}) >0 \).
This also holds when \( {b_1}_{i+1/2,j,k}(\tau ,\alpha _{i,j,k})\rightarrow 0 \), \({b_2}_{i,j+1/2,k}(\tau ,\alpha _{i,j,k})\rightarrow 0 \) and \( {b_3}_{i,j,k+1/2}(\tau ,\alpha _{i,j,k})\rightarrow 0 \). Indeed
Indeed
Using the definition of \(E (\tau ,\alpha ) =\left( e_{i,j,k}^{i,j,k}\right) \), \( i= 1,\ldots , N_1-1 \), \( j = 1,\ldots , N_2-1 \) and \( k = 1,\ldots , N_3-1 \) given above, we see that
For \( i = 2,\ldots , N_1-1 \), \( j = 2,\ldots , N_2-1 \) and \( k = 2,\ldots , N_3-1 \), since \(x_{i+1}^{\beta _{i,j,k}(\tau )} \approx x_{i}^{\beta _{i,j,k}(\tau )} + x_{i}^{\beta _{i,j,k}(\tau )-1}\,{\beta _{i,j,k}(\tau )}\,h_{x_i}\), \(x_{i-1}^{\beta _{i-1,j,k}(\tau )} \approx x_{i}^{\beta _{i-1,j,k}(\tau )} - x_{i}^{\beta _{i-1,j,k}(\tau )-1}\,{\beta _{i-1,j,k}(\tau )}\,h_{x_i}\) \(y_{j+1}^{{\beta _1}_{i,j,k}(\tau )} \approx y_{j}^{{\beta _1}_{i,j,k}(\tau )} + y_{j}^{{\beta _1}_{i,j,k}(\tau )-1}\,{{\beta _1}_{i,j,k}(\tau )}\,h_{y_j}\),
\(y_{j-1}^{{\beta _1}_{i,j-1,k}(\tau )} \approx y_{j}^{{\beta _1}_{i,j-1,k}(\tau )} - y_{j}^{{\beta _1}_{i,j-1,k}(\tau )-1}\,{{\beta _1}_{i,j-1,k}(\tau )}\,h_{y_j}\) \(z_{k+1}^{{\beta _2}_{i,j,k}(\tau )} \approx z_{k}^{{\beta _2}_{i,j,k}(\tau )} + z_{k}^{{\beta _2}_{i,j,k}(\tau )-1}\,{{\beta _2}_{i,j,k}(\tau )}\,h_{z_k}\) and \(z_{k-1}^{{\beta _2}_{i,j,k-1}(\tau )} \approx z_{k}^{{\beta _2}_{i,j,k-1}(\tau )} - z_{k}^{{\beta _2}_{i,j,k-1}(\tau )-1}\,{{\beta _2}_{i,j,k-1}(\tau )}\,h_{z_k}\), when \( h = \max \{h_{x_i},\, h_{y_j},\,\,h_{z_k}\} \longrightarrow 0 \),
we have
We also have similar inequalities when one of the indices i, j, k is equal to 1. Therefore \( \,E(\tau ,\alpha ) \) is an M -matrix. \(\square \)
4 Fitted Finite Volume Scheme in n Dimensional Spatial Domain
The goal here is to update our three dimension fitted schemes in high dimensional space (\( n \ge 3 \)). Recall that the HJB equation in \( n\ge 1 \) dimensional space is given by
The divergence form of equation (42) by setting \( \tau = T-t \) is given by
where \(k(v(\tau , x)) = A(\tau , x,\alpha )\nabla v(\tau , x)+ b(\tau , x, \alpha )\,v(\tau , x)\) with
Indeed this divergence form is not a restriction as the differentiation is respect to x and not respect to the control \(\alpha \), which may be discontinuous in some applications. We will assume that for \( i\ne r,\,\,a_{ir} = a_{ri},\, r,i =1,\ldots ,n\). We also define the following coefficients, which will help us to build our scheme smoothly
\(i,r=1,\ldots ,n. \) As usual the n dimensional domain is truncated to \( I_{x_i}= [0, {x_i}_{\text {max}}] \), \( i = 1,\ldots ,n \) be divided into \( N_i \) sub-intervals
\( j = 0\ldots N_1-1,\,\,k = 0\ldots N_2-1,\,\,\,l=0\ldots N_3-1,\ldots , m=0\ldots N_n-1,\) with \( 0 = {x_i}_{0}< {x_i}_{1}< \cdots \cdots < {x_i}_{p} = {x_i}_{\text {max}},\,\).
This defines on \( I_{x} = \mathop {\prod }\nolimits _{i=1}^{n} I_{x_i} \) a rectangular mesh. By setting
for each \( j=1\ldots N_1-1\), \( k=1\ldots N_2-1\), \( l=1\ldots N_3-1,\ldots , m=1\ldots N_n-1 \). These mid-points form a second partition of \( I_{x} = \mathop {\prod }\nolimits _{i=1}^{n} I_{x_i} \) if we define \( {x_i}_{-1/2} = {x_i}_{0}\), \( {x_i}_{N_i+1/2} = {x_i}_{\text {max}}\), \( i=1,2,\ldots , n \). For each \(j = 0, 1, \ldots ,N_1 \), \(k = 0, 1, \ldots ,N_2 \), \(l = 0, 1,\ldots , N_3,\ldots , m = 0, 1,\ldots ,N_n \) we put \(h_{{x_1}_j} = {x_1}_{j+1/2} - {x_1}_{j-1/2} \), \(h_{{x_2}_k} = {x_2}_{k+1/2} - {x_2}_{k-1/2} \), \(h_{{x_3}_l} = {x_3}_{l+1/2} - {x_3}_{l-1/2} , \ldots , h_{{x_n}_m} = {x_n}_{m+1/2} - {x_n}_{m-1/2} \) and \( h = \max \{h_{{x_1}_j},\,h_{{x_2}_k},\,h_{{x_3}_l},\ldots , h_{{x_n}_m}\} \). Integrating both size of (42) over \( {\mathcal {R}}_{j,k,l,\ldots ,m} = \left[ {x_1}_{j-1/2}, {x_1}_{j+1/2} \right] \times \left[ {x_2}_{k-1/2}, {x_2}_{k+1/2} \right] \times \left[ {x_3}_{l-1/2}, {x_3}_{l+1/2} \right] \times \cdots \times \left[ {x_n}_{m-1/2}, {x_n}_{m+1/2} \right] \) we have
for \( j =1,2,\ldots N_1-1 \), \( k =1,2,\ldots N_2-1 \), \(l =1,2,\ldots N_3-1,\ldots ,m =1,2,\ldots N_n-1 \).
Applying the mid-points quadrature rule to the first and the last point terms, we obtain the above
where \( l_{j,k,l,\ldots ,m} = \left( {x_1}_{j+1/2} - {x_1}_{j-1/2} \right) \times \left( {x_2}_{k+1/2} - {x_2}_{k-1/2}\right) \times \left( {x_3}_{l+1/2} - {x_3}_{l-1/2}\right) \times \cdots \times \left( {x_n}_{m+1/2} - {x_n}_{m-1/2}\right) \) is the volume of \( {\mathcal {R}}_{j,k,l,\ldots ,m} \). Note that \( v_{j,k,l,\ldots ,m}(\tau ) \) denotes the nodal approximation to \( v(\tau , {x_1}_{j}, {x_2}_{k}, {x_3}_{l},\ldots ,{x_n}_{m}) \) at each point of the grid.
We now consider the approximation of the middle term in (47). Let \(\mathbf{n} \) denote the unit vector outward-normal to \( \partial {\mathcal {R}}_{j,k,l,\ldots ,m} \). By General Stokes Theorem, integrating by parts and using the definition of flux k, we have
We will approximate the first term using the the mid-points quadrature rule as
where the value of the subscript \( \nu \in \{j,k,l,\ldots ,q,s,\ldots ,m\} \) depends respectively of the value taking by \( r \in \{1,2,3,\ldots ,i, \ldots ,n\} \). To achieve this, it is clear that we now need to derive approximations of the \( k(v) \cdot \mathbf{n} \) defined above at the mid-point \(\left( {x_1}_{j},{x_2}_{k},{x_3}_{l},\ldots ,{x_i}_{q+1/2},{x_{i+1}}_{s},\ldots ,{x_n}_{m}\right) \), of the interval \( I_{{x_i}_q} \) for \( q = 0, 1,\ldots N_i-1\), \(i=1,2,\ldots ,n \). This discussion is divided into two cases for \( q \ge 1 \), and \( q = 0\, \) on the interval \( I_{{x_i}_0} = [0, {x_i}_1],\,\, i=1,2,\ldots ,n \). This is really the generalization of the fitted finite scheme.
Case I For \( q\ge 1 \).
We follow the same procedure as in three dimension and have the following generalization
where the value of the subscript \( \nu \in \{j,k,l,\ldots ,q,s,\ldots ,m\} \) depends respectively of the value taking by \( r \in \{1,2,3,\ldots ,i,\ldots ,n\} , \beta _{j,k,l,\ldots ,q,s,\nu \ldots ,m}(\tau ) = \dfrac{{b_i}_{j,k,l,\ldots ,q+1/2,s,r\ldots ,m}(\tau , \alpha _{j,k,l,\ldots ,q,s,\nu ,\ldots ,m})}{{{{\overline{a}}_i}}_{j,k,l,\ldots ,q+1/2,s,\nu \ldots ,m}(\tau , \alpha _{j,k,l,\ldots ,q,s,\nu ,\ldots ,m})}\ne 0.\) Similarly
where \( \beta _{j,k,l,\ldots ,q-1,s,\nu \ldots ,m}(\tau ) = \dfrac{{b_i}_{j,k,l,\ldots ,q-1/2,s,\nu ,\ldots ,m}(\tau , \alpha _{j,k,l,\ldots ,q,s,\nu ,\ldots ,m})}{{{{\overline{a}}_i}}_{j,k,l,\ldots ,q-1/2,s,\nu ,\ldots ,m}(\tau , \alpha _{j,k,l,\ldots ,q,s,\nu ,\ldots ,m})}\ne 0.\)
Case II Approximation of the flux at \( q = 0 \) on the interval \( I_{{x_i}_0} = [0, {x_i}_1],\,\,i=1,\ldots ,n\). Note that the analysis in case I does not apply to the approximation of the flux on \( I_{{x_i}_0} \) because it is the degenerated zone. Follow the same lines as for the three dimensional case, we get
Equation (47) becomes by replacing the flux by its value for \( j = 1,\ldots ,N_1-1 \), \( k = 1,\ldots ,N_2-1 \), \( l = 1,\ldots ,N_3-1,\ldots , m = 1,\ldots ,N_n-1, \) and \( N = \prod _{i=1}^{n} (N_i-1)\).
This can be rewritten as the ordinary differential equation (ODE) coupled with optimization
where \( E (\tau ,\alpha )\) is an \(N\times N\) matrix, \( {\mathcal {A}}^N=\underset{N}{\underbrace{{\mathcal {A}}\times \cdots \times {\mathcal {A}}}} \), \(G (\tau , \alpha ) =-F(\tau , \alpha ) \) depends of the boundary condition and the term c. \(\mathbf{v} = \left( v_{j,k,l,\ldots ,q,s,\nu ,\ldots ,m}\right) \), and \(G (\tau , \alpha ) =-F(\tau , \alpha ) \). By setting \(n_1=N_1-1,\; n_2=N_2-1; \;n_3=N_3-1;,\ldots ,n_n=N_n-1;, \;\; I:=I (j,k,l,\ldots ,q,s,\nu ,\ldots ,m)= j + (k-1)n_1 +(l-1)n_1 n_2 + \cdots + (m-1)\mathop {\prod }\nolimits _{i=1}^{n-1} n_i\) and \(J:=J (j',k',l',\ldots ,q',s',\nu ',\ldots ,m')= j' + (k'-1)n_1 +(l'-1)n_1 n_2 + \cdots + (m'-1)\mathop {\prod }\nolimits _{i=1}^{n-1} n_i \), we have \(E (\tau , \alpha ) (I,J)= \left( e_{j',k',l'\ldots ,q',s',\nu ',\ldots ,m'}^{j,k,l,\ldots ,q,s,\nu ,\ldots ,m}\right) \), \(j', j = 1,\ldots , N_1-1 \), \( k',k = 1,\ldots , N_2-1 \) and \(l', l = 1,\ldots , N_3-1,\ldots ,m',m = 1,\ldots , N_n-1 \) and
for \(j= 2,\ldots , N_1-1 \), \( k = 2,\ldots , N_2-1 ,\ldots ,m = 2,\ldots , N_n-1 \). If one of the indices \( j, k, l,\ldots ,m \) is equal to 1,
The monotonicity of system matrix \(E (\tau ,\alpha ) \) is given in the following theorem.
Theorem 2
Assume that the coefficients of A given by (44) are positive and \(c<0\).Footnote 2If h is relatively small then the matrix \(E (\tau ,\alpha )\) in the system (53) is an M-matrix for any \( \alpha _{j,k,l,\ldots ,m} \,\in \,{\mathcal {A}}^{N}\).
Proof
The proof follows the same lines as in Theorem 1. \(\square \)
5 Temporal Discretization and Optimization Problem
This section is devoted to the numerical time discretization method for the spatially discretized optimization problem after the fitted finite volume method. Let us re-consider the differential equation coupled with optimization problem given in (33) by
For temporal discretization, we use a constant time step \(\varDelta t > 0\), of course variable time steps can be used. The temporal grid points given by \(\varDelta t = \tau _{n+1}-\tau _n \) for \(n = 1, 2,\ldots m-1 \). We denote \(\mathbf{v} (\tau _n) \approx \mathbf{v} ^n\) , \(A^n (\alpha ) = A(\tau _n,\alpha )\) and \(G^n (\alpha )=G(\tau _n,\alpha ).\)
For \(\theta \,\in \left[ \frac{1}{2}, 1\right] \), following (Peyrl et al. 2005), the \(\theta \)-Method approximation in time is given by
this also can be written as
We can see that to find the unknown \(\mathbf{v} ^{n+1}\), we need also to solve an optimization. Let
Then, the unknown \(\mathbf{v} ^{n+1}\) is solution of the following equation
Note that, for \(\theta = \dfrac{1}{2}\), we have the Crank Nickolson scheme and for \(\theta =1\) we have the Implicit scheme. Unfortunately (57)–(59) are nonlinear and coupled and we need to iterate at every time step. The following iterative scheme close to the one in Peyrl et al. (2005) is used.
-
1.
Let \( \left( \mathbf{v} ^{n+1}\right) ^0=\mathbf{v} ^{n}\),
-
2.
Let \( \hat{\mathbf{v }}^{k}= \left( \mathbf{v} ^{n+1}\right) ^k\),
-
3.
For \(k=0,1,2 \ldots \) until convergence (\(\Vert \hat{\mathbf{v }}^{k+1}-\hat{\mathbf{v }}^{k}\Vert \le \epsilon \), given tolerance) solve
$$\begin{aligned}&\alpha ^{k}_i \in \left( \underset{\alpha \in {\mathcal {A}}^N }{arg \sup } \left\{ \theta \,\varDelta t \left[ A^{n+1} (\alpha )\,\hat{\mathbf{v }}^k+ G^{n+1}(\alpha ) \right] _i + (1-\theta )\,\varDelta t \, \left[ A^{n} (\alpha )\,\mathbf{v} ^{n} + G^{n}(\alpha )\right] _i \right\} \right) \nonumber \\&\alpha ^{k}=(\alpha ^{k})_i\nonumber \\&[ I - \theta \, \varDelta t\,A^{n+1} (\alpha ^{k})]\,\hat{\mathbf{v }}^{k+1} = [I + (1-\theta )\,\varDelta t \, A ^{n}(\alpha ^{k})] \mathbf{v} ^{n} \nonumber \\&\quad +[\theta \, \varDelta t \, G^{n+1}(\alpha ^{k})+(1-\theta ) \varDelta t \,G^{n}(\alpha ^{k})], \end{aligned}$$(60) -
4.
Let \(k_l\) being the last iteration in step 3, set \(\mathbf{v} ^{n+1}:=\hat{\mathbf{v }}^{k_l}\), \(\alpha ^{n+1}:=\alpha ^{k_l}\).
The monotonicity of system matrix of (58), more precisely \( [I + \varDelta t \,\theta E^{n+1}] \) is given in the following theorem.
Theorem 3
Under the same assumptions as in Theorem 1, for any given \(n = 1, 2, \ldots , m - 1 \), the system matrix \( [I + \varDelta t \,\theta E^{n+1}] \) in (58) is an M-matrix for each\( \alpha \in {\mathcal {A}}^N. \)
Proof
The proof is obvious. Indeed as in Theorem 1, \( [I + \varDelta t \,\theta E^{n+1}] \) is (strictly) diagonally dominant since \( \varDelta t > 0 \). Then, it is an M-matrix. \(\square \)
The merit of the proposed method is that it is unconditionally stable in time because of the implicit nature of the time discretization. More precisely, following (Angermann and Wang 2007, Theorem 6 and Lemma 3), we can easily prove that the scheme (57) is stable and consistent, so the convergence of the scheme is ensured (see Barles and Souganidis 1991)
6 Application
To validate our method presented in the previous section, we present here some numerical experiments. All computations were performed in Matlab 2013.
Consider the following three dimensional Merton’s stochastic control problem such that \( \alpha = \alpha _1(t,x) \) is a feedback control in [0, 1] given by
s.t.
\(r_1\), \(\mu _1\), \(\mu _2\), \(\mu _2\), \(\sigma \) are positive constants, \( x_t,\, y_t,\, z_t\,\in \,{\mathbb {R}} \). We assume that \( \mu _1 > r_1 \). For the problem (61)–(62), the corresponding HJB equation is given by
where
and the different variable in (63) is given by
is the flux, \(b = (x\,b_1, y\,b_2, z\,b_3)^T\),
with
The domain where we compare the solution is \( \varOmega =\left[ 0, x_{{max}}\right] \times \left[ 0, y_{{max}}\right] \times \left[ 0, z_{{max}}\right] \). For each simulation, the exact or reference solution is the analytical solution using Ansatz method as we are going to develop in the next section.
6.1 Analytical Solution Using Ansatz Method
Here we propose the analytical solution using the Ansatz decomposition. Let set the Ansatz decomposition of v
where \( u(x) = \dfrac{x^p}{p},\) \(\,\, 0< p < 1\), \(\forall \, x \,\in {\mathbb {R}}_+ \) is the power utility function. The different derivative of v(t, x, y, z) gives us
plugging into (63), we get
We then obtained
So by setting \( \tau = T-t \), the analytical value function for Ansatz method is then equal to
We use the following \(L^2\left( [0,T]\times \varOmega \right) \) norm of the absolute error
where \(v^m\) is the numerical approximation of v computed from our numerical scheme. For our computation, we us we have \(\varOmega =[0,1/2]\times [0,1/4] \times [0,1/2]\) for computational domain with \(N_1= 10\), \(N_2 = 10\), \(N_3= 10\), \(r_1 = 0.0449\), \(\mu _1 = 0.0657\), \(\mu _2 = 0.067\), \(\mu _3 = 0.066\), \(\sigma = 0.2537\), \(p= 0.13\) and \(T=1 \). Figure 1 shows the structure of the matrix A after space discretisation with the fitted volume method. As you can observe the structure of the matrix is similar to the one from finite difference method. Figure 2 shows the optimal investment policy as function of x while using the fitted scheme. The optimal investment policy for finite difference method is quite similar. Indeed the optimal parameter \(\alpha \) is independent of y and z. The controller is the solution of (61). It is computed with the numerical procedure as outlined in Sect. 5. We have also found that in overall the value the maximum number of iterations in our optimisation algorithm is 3 in both fitted scheme and finite difference scheme.
We compare the fitted finite volume and the finite difference method in Table 1.
Figure 3 shows the structure of the matrix A and Fig. 4 shows the optimal investment policy as function of x. The controller is the solution of (61). It is computed with the numerical procedure as outlined in Sect. 5.
In Table 2, we have used \(\varOmega =[0,1/2]\times [0,1/4] \times [0,1/2]\) for computational domain with the following parameters \(N_1= 8\), \(N_2 = 9\), \(N_1= 10\), \(r_1 = 0.0449\), \(r_2 = 0.0448/3\), \(r_3 = 0.0447\), \(\mu _1 = 0.0657\), \(\mu _2 = 0.0656\), \(\mu _3 = 0.0655\), \(\sigma = 0.2537\), \(p= 0.17\) and \(T=1.5 \).
Tables 1 and 2 display the numerical errors of finite volume method and finite difference method. By fitting the data from Tables 1 and 2, we found that the convergence order in time 1 for the fitted finite volume method and the finite difference method. From the two tables, we can observe a slight accuracy of the implicit fitted finite volume comparing to the implicit finite difference method, thanks to the fitted technique.
7 Conclusion
We have introduced a novel scheme based on finite volume method with fitted technique to solve high dimensional stochastic optimal control problems (\(n\ge 3\)). The optimization problem is solved at every time step using iterative method. We have shown that the system matrix of the resulting non linear system is an M-matrix and therefore the maximum principle is preserved for the discrete system obtained after the fitted finite volume spatial discretization. Numerical experiments are used to demonstrate the accuracy of the novel scheme comparing to the standard finite difference method.
Notes
Indeed c can be positive but should be less than a certain threshold \(c_0>0\).
Indeed c can be positive but should be less than a certain threshold \(c_0>0\).
References
Angermann, L., & Wang, S. (2007). Convergence of a fitted finite volume method for the penalized Black–Scholes equation governing European and American Option pricing. Numerische Mathematik, 106, 1–40.
Barles, G., & Souganidis, P. (1991). Convergence of approximation schemes for fully nonlinear second-order equations. Asymptotic Analysis, 4, 271–283.
Bénézet, C., Chassagneux, J.-F., & Reisinger, C. (2019). A numerical scheme for the quantile hedging problem ar**v:1902.11228v1
Bonnans, J. F., & Zidani, H. (2003). Consistency of generalized finite difference schemes for the stochastic HJB equation. SIAM Journal of Numerical Analysis, 41, 1008–1021.
Dleuna Nyoumbi, C., & Tambue, A. (2021). A fitted finite volume method for stochastic optimal control problems in finance. AIMS Mathematics, 6(4), 3053–3079.
Crandall, M. G., Ishii, H., & Lions, P. L. (1992). User’s guide to viscosity solutions of second order partial differential equations. American Mathematical Society, 27, 1–67.
Crandall, M. G., Evans, L. C., & Lions, P. L. (1984). Some properties of viscosity solutions of Hamilton–Jacobi equations. Transactions of the American Mathematical Society, 282(2), 487–502.
Crandall, M. G., & Lions, P. L. (1983). Viscosity solutions of Hamilton–Jacobi equations. Transactions of the American Mathematical Society, 277(1), 1–42.
Crandall, M. G., & Lions, P. L. (1984). Two approximations of solutions of Hamilton–Jacobi equations. Mathematics of Computation, 43, 1–19.
Crandall, M. G., & Lions, P. L. (1996). Convergent difference schemes for nonlinear parabolic equations and mean curvature motion. Numerische Mathematik, 75, 17–41.
Fleming, W. H., & Soner, H. M. (2006). Controlled Markov processes and viscosity solutions, stochastic modelling and applied probability (p. 25). New York: Springer.
Forsyth, P., & Labahn, G. (2007). Numerical methods for controlled Hamilton–Jacobi–Bellman PDEs in finance. Journal of Computational Finance, 11(2), 1–43.
Gyöngy, I., & Šiška, D. (2009). On finite difference approximations for normalized Bellman’s equations. Applied Mathematics and Optimization 60, Article number 297.
Henderson, V., Kladívko, K., Monoyios, M., & Reisinger, C. (2020). Executive stock option exercise with full and partial information on a drift change point. ar**v:1709.10141v4.
Holth, J. (2011). Merton’s portfolio problem, constant fraction investment strategy and frequency of portfolio rebalancing. University of Oslo. M. http://hdl.handle.net/10852/10798
Huang, C.-S., Hung, C.-H., & Wang, S. (2006). A fitted finite volume method for the valuation of options on assets with stochastic volatilities. Computing, 77(3), 297–320.
Huang, C.-S., Hung, C.-H., & Wang, S. (2010). On convergence of a fitted finite volume method for the valuation of options on assets with stochastic volatilities. IMA Journal on Numerical Analysis, 30, 1101–1120.
Huang, C.-S., Wang, S., & Teo, K. L. (2004). On application of an alternating direction method to Hamilton–Jacobi–Bellman equations. Journal of Computational and Applied Mathematics, 27, 153–166.
Hull, J., & White, A. (1987). The pricing of options on assets with stochastic volatilities. Journal of Finance, 42(2), 281–300.
Jakobsen, E. R. (2003). On the rate of convergence of approximations schemes for Bellman equations associated with optimal stop** time problems. Mathematical Models and Methods in Applied Sciences, 13(05), 613–644.
Kocan, M. (1995). Approximation of viscosity solutions of elliptic partial differential equations on minimal grids. Numerische Mathematik, 72, 73–92.
Krylov, N. V. (2000). On the rate of convergence of finite-difference approximations for Bellman’s equations with variable coefficients. Probability Theory and Related Fields, 117, 1–16.
Krylov, N. V. (2005). The rate of convergence of finite-difference approximations for Bellman’s equations with Lipschitz coefficients. Applied Mathematics and Optimization, 52, 365–399.
Krylov, N. V. (1972). Control of a solution of a stochastic integral equation. Theory of Probability and Its Applications, 17, 406–446.
Krylov, N. V. (1999). Approximating value functions for controlled degenerate diffusion processes by using piece-wise constant policies. Electronic Journal of Probability, 4(2), 1–19.
Kushner, H. J. (1990). Numerical methods for stochastic control problems in continuous time. SIAM Journal on Control and Optimization, 28, 999–1048.
Oberman, A. M. (2006). Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton–Jacobi equations and free boundary problems. SIAM Journal of Numerical Analysis, 44, 879–895.
Peyrl, H., Herzog, F., & Geering, H. P. (2005). Numerical solution of the Hamilton–Jacobi–Bellman equation for stochastic optimal control problems. In WSEAS international conference on dynamical systems and control (pp. 489–497), Venice, Italy, November 2-4.
Pfeiffer, L. (2018). Two approaches to stochastic optimal control problems with a final-time expectation constraint. Applied Mathematics and Optimization, 77(2), 377–404.
Pham, H. (2000). Optimisation et contrôle stochastique appliqués à la finance. Mathématiques et applications. New York: Springer.
Rodriguez-Gonzalez, P. T., Rico-Ramirez, V., Rico-Martinez, R., & Diwekar, U. M. (2019). A new approach to solving stochastic optimal control problems. Mathematics, 7, 1207.
Song, N., Ching, W.-K., Siu, T.-K., & Yiu, C.K.-F. (2013). On optimal cash management under a stochastic volatility model. East Asian Journal on Applied Mathematics, 3(2), 81–92.
Valkov, R. (2014). Fitted finite volume method for a generalized Black Scholes equation transformed on finite interval. Numerical Algorithms, 65(1), 195–220.
Wang, S. (2004). A Novel fitted finite volume method for the Black Scholes equation governing option pricing. IMA Journal on Numerical Analysis, 24, 699–720.
Wang, S., Gao, F., & Teo, K. L. (2000). An upwind finite difference method for the approximation of viscosity solutions to Hamilton–Jacobi–Bellman equations. IMA Journal of Mathematical Control and Information, 17, 167–178.
Wilmott, P. (2005). The best of Wilmott 1: Incorporating the quantitative finance review. London: Wiley.
Zhao, W., Tao, Z., & Kong, T. (2017). High order numerical schemes for second-order FBSDEs with applications to stochastic optimal control. Communications in Computational Physics, 21(3), 808–834.
Zhu, S.-P., Ma, G. (2018). An analytical solution for the HJB equation arising from the Merton problem. International Journal of Financial Engineering, 05(01), 1850008.
Funding
Open access funding provided by Western Norway University Of Applied Sciences.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
All authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Dleuna Nyoumbi, C., Tambue, A. A Novel High Dimensional Fitted Scheme for Stochastic Optimal Control Problems. Comput Econ 61, 1–34 (2023). https://doi.org/10.1007/s10614-021-10197-4
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10614-021-10197-4
Keywords
- Stochastic optimal control
- Dynamic programming
- HJB equations
- Finite volume method
- Computational finance
- Degenerate parabolic equations