Exploitation of necessary and sufficient conditions for suboptimal solutions of multiobjective stochastic

control problems

F. Heyde  W. Grecksch  Chr. Tammer

Institut für Optimierung und Stochastik, Martin-Luther-Universität Halle-Wittenberg, Theodor-Lieser-Str. 5,D-06120 Halle, Germany (E-mail: heyde@mathematik.uni-halle.de, grecksch@mathematik.uni-halle.de, tammer@mathematik.uni-halle.de)

Abstract

In this paper necessary and sufficient conditions for a multicriteria stochastic control problem are stated. Moreover the convergence of a finite difference approximation method for the solution of the resulting system of second order PDEs is shown.

1 Introduction

In this paper we consider a multiobjective stochastic control problem which is described in section 2. Our aim was the exploitation of necessary conditions for approximate solutions which we proved in [7] for the development of numerical algorithms. The main problem is the computation of the adjoint process.

Regarding the case of complete observation we obtain a second order system of PDE’s for the adjoint process which is difficult to handle. Therefore we derive necessary and sufficient conditions leading to a system of PDEs which is numerical solvable by a finite difference method similar to that in Ma/Yong [9].

2 A model of a partially observed stochastic control problem

Let W_{t} be a Brownian motion on a complete probability space (Ω, A, μ) taking values in IR^{m}.

The σ- algebra of measurable states depending on t is denoted by F_{t} = σ(x_{s} : s ≤ t). In the following we assume

(C1) σ is an m × m - matrix - valued mapping σ = (σ_{ij}) defined on [0, 1] × C with C = C[0, 1], σ(t, x) is nonsingular, for 1 ≤ i, j ≤ m, σ_{ij}(t, x) is F_{t} - measurable in its second argument and Lebesgue - measurable in its first; each σ_{ij} satisfies a uniform Lipschitz condition in x with respect to the norm

||x||_{s} = sup_{0≤t≤s} |x(t)|;

and there is a constant k_{0} < ∞ such that

∑ ∫_{0}^{1} σ_{ij}^{2}dt ≤ k_{0} P − a.s.

Under this assumption the stochastic differential equation

dx(t) = σ(t, x)dW_{t}; x(0) = x_{0}

has a unique strong solution.

Consider now the stochastic differential equation

\begin{matrix}dx(t) = & f(t, x, u)dt + σ(t, x)dW_{t}, \\ x(0) = & x_{0} ∈ IR^{m}, \end{matrix} \}  (1)

0 ≤ t ≤ 1,

where the solution should be defined in the weak sense and x splits into an observed component y ∈ IR^{n} and an unobserved component z ∈ IR^{m−n}. the solution is defined in the weak sense. Furthermore, consider the observation σ - field Y_{t} generated by {y_{s} : s ≤ t}.

Definition 1 An Y_{t} - predictable mapping u : [0, 1]×C ⟶ U, where U is a Borel subset of IR, such that E|u(t, ·)| < ∞ for all t ∈ [0, 1], is called an admissible partially observable feedback control.

The set of such controls is denoted by V. We define on V for u_{1}, u_{2} ∈ V

d(u_{1}, u_{2}) = P̃({(t, x) : |u_{1}(t, x) − u_{2}(t, x)| > 0}),  (2)

where P̃ is the product measure of λ and P (λ is the Lebesgue measure on [0, 1] and P is the probability measure on C[0, 1] induced by the Brownian motion). Elliott and Kohlmann proved in [5] that (V, d) is a complete metric space.

Definition 2 The set of all functions ϕ : [0, 1] × C → IR^{m} with the properties

(i) ϕ(t, ·) is F_{t}-measurable for each t ∈ [0, 1],

(ii) ϕ(·, x) is Lebesgue measurable for each x ∈ C,

(iii) |σ^{−1}(t, x)ϕ(t, x)| ≤ M(1 + ||x||_{t}) for all (t, x) ∈ [0, 1] × C

will be denoted by Φ.

Now we suppose that

(C2) The function f : [0, 1]×C ×U ⟶ IR^{m} is jointly measurable, continuous in its third

component and

f^{u}(t, x) := f(t, x, u(t, x)) ∈ Φ ∀u ∈ V.

Under these assumptions it is possible to apply the Girsanov theorem (see Girsanov [6]) which states that the measure P_{u} defined by

P_{u}(A) = ∫_{A} exp {∫_{0}^{1} f(t, x, u(t, x))(σ(t, x)σ′(t, x))^{−1}dx_{t}

−\frac{1}{2} ∫_{0}^{1} f(t, x, u(t, x))(σ(t, x)σ′(t, x))^{−1}f(t, x, u(t, x))dt\} dP

=: ∫_{A} ρ_{0}^{1}(u)dP.

is a probability measure on (C, F_{1}) which is absolutely continuous with respect to P and the process W_{t}^{u} defined by

dW_{t}^{u} = dW_{t} − σ^{−1}(t, x)f^{u}(t, x)dt

is a Wiener Process with respect to P_{u}. This implies

dx(t) = σ(t, x)dW_{t} = f^{u}(t, x)dt + σ(t, x)dW_{t}^{u}

which ensures the existence of a weak solution of equation (1). Moreover the linear growth condition on |σ^{−1}f^{u}| ensures that E[ρ_{s}^{t}(u)|F_{s}] = 1 P -a.s. (see [1] and [2]).

Let g_{i} (i = 1, .., l) be bounded F_{1}-measurable functions. Now we introduce the multiobjective function

J(u) := ( \begin{matrix}E_{u}[g_{1}(x(1))] \\ ⋯ \\ E_{u}[g_{l}(x(1))] \end{matrix} ) ,

where E_{u} denotes the expectation with respect to P_{u} .

In the following we denote the topological interior of a set C ⊂ IR^{l} by int C, the topological boundary of C by bd C and the topological closure of C by cl C. We suppose

(C3) K ⊂ IR^{l} is a convex cone with int K ≠ ∅, B ⊂ IR^{l} is a pointed, convex cone with int B ≠ ∅ such that cl B + (K \ {0}) ⊂ int B.

Now, we formulate the multicriteria stochastic control problem under the assumptions (C1) − (C3)

(P_{C}): Compute a feasible control ū such that

J(u) ∉ J(ū) − (K \ {0})

for all admissible controls u.

In this way we study an extension of the stochastic control problem introduced by Elliott and Kohlmann [5].

3 Necessary Conditions

In [7] we proved the following Theorem.

Theorem 1 Consider the stochastic control problem (P_{C}) under the assumptions (C1) − (C3) and let k^{0} ∈ int K. Then there exists for each ε > 0 an admissible control u_{ε}, such that

1.

( \begin{matrix}E_{u}[g_{1}(x(1))] \\ ⋯ \\ E_{u}[g_{l}(x(1))] \end{matrix} ) ∉ ( \begin{matrix}E_{u_{ε}}[g_{1}(x(1))] \\ ⋯ \\ E_{u_{ε}}[g_{l}(x(1))] \end{matrix} ) − εk^{0} − (K \ \{0\})

for all feasible controls u ∈ V,

( \begin{matrix}E[p_{1ε}σ^{−1}f_{t}^{u} | Y_{t}] \\ ⋯ \\ E[p_{lε}σ^{−1}f_{t}^{u} | Y_{t}] \end{matrix} ) ∉ ( \begin{matrix}E[p_{1ε}σ^{−1}f_{t}^{u_{ε}} | Y_{t}] \\ ⋯ \\ E[p_{lε}σ^{−1}f_{t}^{u_{ε}} | Y_{t}] \end{matrix} ) − εk^{0} − int K

for all u ∈ V and the F_{t} - predictable process

p_{ε} = ( \begin{matrix}ρ_{0}^{t}(u_{ε})γ_{1ε} \\ ⋯ \\ ρ_{0}^{t}(u_{ε})γ_{lε} \end{matrix} ) .

In the proof of this theorem the adjoint process γ_{iε} was defined as the integrand of the martingale representation of

G_{i}^{t} = E_{u_{ε}}[g_{i}(x(1)) | F_{t}] = E_{u_{ε}}[g_{i}(x(1))] + ∫_{0}^{t} γ_{iε}dW_{t}^{u_{ε}}

Due to the Markov property of the diffusion process x(·) we have

G_{i}^{t} = E_{u_{ε}}[g_{i}(x(1)) | F_{t}] = E_{u_{ε}}[g_{i}(x(1)) | x(t)] =: G^{i}(t, x(t)).

Applying Ito’s formula we get

G_{i}^{t} = G(0, x_{0}) + ∫_{0}^{t} (G_{t}^{i} + ∑_{j} G_{x_{j}}^{i}f_{j}^{u_{ε}} + \frac{1}{2} ∑_{j,k,μ} G_{x_{j},x_{k}}^{i}σ_{jμ}σ_{kμ}) (t, x(t))dt

+ ∫_{0}^{t} (G_{x_{j}}^{i}σ_{j·}) (t, x(t))dW_{t}^{u_{ε}}.

Comparing this with the martingale representation we get

(G_{t}^{i} + ∑_{j} G_{x_{j}}^{i}f_{j}^{u_{ε}} + \frac{1}{2} ∑_{j,k,μ} G_{x_{j},x_{k}}^{i}σ_{jμ}σ_{kμ}) (t, x(t)) = 0  (3)

and

(G_{x_{j}}^{i}σ_{j·}) (t, x(t)) = γ_{iε}(t).

Moreover we get

G^{i}(1, x(1)) = G_{i}^{1} = E_{u_{ε}}[g_{i}(x(1)) | F_{1}] = g_{i}(x(1)).  (4)

In the case of complete observation condition 2. becomes

( \begin{matrix}ρ_{0}^{t}(u_{ε})G^{1}(t, x)f^{u}(t, x) \\ ⋯ \\ ρ_{0}^{t}(u_{ε})G^{l}(t, x)f^{u}(t, x) \end{matrix} ) ∉ ( \begin{matrix}ρ_{0}^{t}(u_{ε})G^{1}(t, x)f^{u_{ε}}(t, x) \\ ⋯ \\ ρ_{0}^{t}(u_{ε})G^{l}(t, x)f^{u_{ε}}(t, x) \end{matrix} ) − εk^{0} − int K.

If we assume that, given t, x, G_{x}^{i}(t, x), we can compute u_{ε}(t, x) satisfying assertion 2. of Theorem 1 we can write

f^{u_{ε}}(t, x) =: f̂(t, x, G_{x}(t, x)).

So we get the following system of PDEs

G_{t}^{i}(t, x) + ∑_{j} G_{x_{j}}^{i}(t, x)f̂_{j}(t, x, G_{x}(t, x)) + \frac{1}{2} ∑_{j,k,μ} (G_{x_{j} x_{k}}^{i}σ_{jμ}σ_{kμ}) (t, x) = 0

with terminal conditions

G^{i}(1, x) = g_{i}(x).

The adaption of the finite difference method introduced in Ma/Yong [9] for one PDE with one-dimensional state to this system was impossible for us, because if we define v_{j}^{i}(t, x) := G_{x_{j}}^{i}(1 − t, x) we get a second order system where v_{j t}^{i} dependens on v_{j x}^{ν} (ν ≠ i) which is the crucial problem.

4 Scalarization

In order to overcome this problem we proved a maximum principle with ”scalar” adjoint variable. For this theorem we can even weeken the assumtion (C3) by (C3’).

(C3’) K ⊂ IR^{l} is a convex cone with int K ≠ ∅, B ⊂ IR^{l} is a convex cone with B ≠ IR^{l} and K \ {0} ⊂ int B.

Theorem 2 Consider the stochastic control problem (P_{C}) under the assumptions (C1), (C2) and (C3′) and let k^{0} ∈ int K.

Then for each ε > 0 there exists an admissible control u_{ε} and a F_{t}-measurable adjoint process γ_{ε}, such that

1.

( E_{u}[g_{1}(x(1))] ; ⋮ ; E_{u}[g_{l}(x(1))] ) ∉ ( E_{u_{ε}}[g_{1}(x(1))] ; ⋮ ; E_{u_{ε}}[g_{l}(x(1))] ) − εk^{0} − K \ {0}

for all feasible controls u ∈ V,

2.

E[ρ_{0}^{t}(u_{ε})γ_{ε}σ^{−1}f_{t}^{u} | Y_{t}] ≥ E[ρ_{0}^{t}(u_{ε})γ_{ε}σ^{−1}f_{t}^{u_{ε}} | Y_{t}] − ε

P̃-a.s. for all u ∈ V.

Proof. Since B is a convex cone with B ≠ IR^{l} it follows 0 ∉ int B and due to int B ≠ ∅ we can apply a separation theorem (see Jahn [8] Theorem 3.16) to the sets B and {0}. This implies the existence of a continuous linear functional z̃ : IR^{l} → IR with z̃(b) < z̃(0) = 0 ∀b ∈ int B. Because of K \ {0} ⊂ int B we also get z̃(k) < 0 ∀k ∈ K \ {0} and z̃(k^{0}) < 0. Defining z(y) := \frac{z̃(y)}{z̃(k^{0})} ∀y ∈ IR^{l} yields z(k) > 0 ∀k ∈ K \ \{0\} and z(k^{0}) = 1.

If we define g(x) := z ( g_{1}(x) ; ⋮ ; g_{l}(x) ) and F (u) := E_{u}[g(x(1))] = z(J(u)) (due to the

linearity of z) we can apply Theorem 5.4 from Elliot/Kohlmann [5] and obtain for every ε > 0 the existence of an admissible control u_{ε} and an F_{t} predictable process γ_{ε} such that assertion 2. holds and

F (u_{ε}) ≤ F (u) + ε  (5)

for all admissible controls u. Now assertion 1. follows from (5) since otherwise there would exist an element u ∈ V with J(u_{ε}) − J(u) − εk^{0} ∈ K \ {0} what would imply z(J(u_{ε}) − J(u) − εk^{0}) > 0 which yields F (u) < F (u_{ε}) − ε in contradiction to (5).

Now the adjoint process γ_{ε} is defined by the martingale representation of a real-valued function G, i.e.

G(t, x(t)) = G^{t} = E_{u_{ε}}[g(x(1)) | F_{t}] = E_{u_{ε}}[g(x(1))] + ∫_{0}^{t} γ_{ε}dW_{t}^{u_{ε}}.

Applying the steps of the previous section we get the following PDE for G

G_{t}(t, x) + ∑_{j} G_{x_{j}}(t, x)f̂_{j}(t, x, G_{x}(t, x)) + \frac{1}{2} ∑_{j,k,μ} (G_{x_{j} x_{k}}σ_{jμ}σ_{kμ}) (t, x) = 0  (6)

with terminal condition

G(1, x) = g(x) = z ( g_{1}(x) ; ⋮ ; g_{l}(x) ) .  (7)

Another problem in using the above ε- maximum principle for the development of a numerical algorithm is caused by the ρ_{0}^{t}(u_{ε})-term in the maximum condition because this term is dependent on the whole past of the process and not only on the actual time and state what would be desirable for the computation of a feedback control dependent on t, x, G_{x} from this condition.

For this reason we state sufficient conditions for the multicriteria stochastic control problem without this factor.

5 Sufficient Conditions

Theorem 3 Let u_{ε} be an admissible control for the control problem (P_{C}) under the assumptions (C1) and (C2) with the following properties

(i) The real valued function G ∈ C^{1,2}([0, 1] × IR^{m}) satisfies the PDE

G_{t}(t, x) + ∑_{j} G_{x_{j}}(t, x)f_{j}^{u_{ε}}(t, x) + \frac{1}{2} ∑_{j,k,μ} G_{x_{j},x_{k}}(t, x)σ_{jμ}(t, x)σ_{kμ}(t, x) = 0 (8)

with terminal condition (7) where z : IR^{l} → IR is a linear, continuous, strictly K-monotone functional with z(k^{0}) ≥ 1.

(ii) For all (t, x) ∈ [0, 1] × IR^{m} and u ∈ U holds

∑_{j} G_{x_{j}}(t, x)f_{j}(t, x, u) ≥ ∑_{j} G_{x_{j}}(t, x)f_{j}(t, x, u_{ε}(t, x)) − ε.  (9)

Then J(u) ∉ J(u_{ε}) − εk^{0} − K \ {0} ∀u ∈ V.

Proof. Let J(u) := ( E_{u}[g_{1}(x(1))] ; ⋮ ; E_{u}[g_{l}(x(1))] ) , F (u) := z(J(u)). Due to the linearity of the

functional z it can be interchanged with the expectation. Applying Ito’s formula we get

F (u_{ε}) = E_{u_{ε}}[g(x(1))]
= E_{u_{ε}}[G(1, x(1))]
= E_{u_{ε}} [G(0, x^{0}) + ∫_{0}^{1} dG(t, x(t))]
= G(0, x^{0}) + E_{u_{ε}} [∫_{0}^{1} (G_{t} + G_{x}f^{u_{ε}} + \frac{1}{2}tr(G_{xx}σσ^{T})) (t, x(t))dt
+ ∫_{0}^{1} (G_{x}σ) (t, x(t))dW_{t}^{u_{ε}}]
= G(0, x^{0}).

For arbitrary u ∈ V we have

F (u) = E_{u}[g(x(1))]
= E_{u}[G(1, x(1))]
= E_{u} [G(0, x^{0}) + ∫_{0}^{1} dG(t, x(t))]

= G(0, x^{0}) + E_{u} [∫_{0}^{1} (G_{t} + G_{x}f^{u} + \frac{1}{2}tr(G_{xx}σσ^{T})) (t, x(t))dt
+ ∫_{0}^{1} (G_{x}σ) (t, x(t))dW_{t}^{u}]
≥ G(0, x^{0}) + E_{u_{ε}} [∫_{0}^{1} (G_{t} + G_{x}f^{u_{ε}} + \frac{1}{2}tr(G_{xx}σσ^{T}) − ε) (t, x(t))dt]
= G(0, x^{0}) − ε
= F (u_{ε}) − ε.  (10)

Now from the linearity and strict K-monotonicity of the functional z and the property z(k^{0}) ≥ 1 follows J(u) ∉ J(u_{ε}) − εk^{0} − K \ {0} ∀u ∈ V, since otherwise there would exist an element u ∈ V with J(u) ∈ J(u_{ε}) − εk^{0} − K \ {0} and the strict K-monotonicity of z would imply F (u) = z(J(u)) < z(J(u_{ε})−εk^{0}) ≤ F (u_{ε})−ε in contradiction to (10).

In the following we assume σ is constant. Since a := σσ^{T} is nonnegative definite it can be diagonalized, i.e. there is an orthogonal matrix Γ such that

ΓaΓ^{T} = D = ( \begin{matrix}d_{1} & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & d_{m} \end{matrix} )

with nonnegative diagonal elements d_{1}, ..., d_{m}. Assume now that σσ^{T} = D (diagonal matrix with nonnegative elements). This assumption can be done without loss of generality, since by coordinate transformation y = Γx we get

dy(t) = Γdx(t) = Γf^{u}(t, Γ^{T} y(t))dt + Γσdw_{t} =: f̃^{u}(t, y(t))dt + σ̃dw_{t}

where σ̃σ̃^{T} = D.

Define v(t, x) = G_{x}(1 − t, x) and f̄(t, x, v) := f̂(1 − t, x, v). Then equation (6) implies

v_{j t}(t, x)
= G_{x_{j} t}(1 − t, x)
= \frac{∂}{∂x_{j}} ∑_{μ} (G_{x_{μ}}(1 − t, x)f̄_{μ}(t, x, v(t, x)) + \frac{1}{2}d_{μ}G_{x_{μ} x_{μ}}(1 − t, x))

= ∑_{μ} (\frac{1}{2}d_{μ}v_{j x_{μ}x_{μ}}(t, x) + f̄_{μ}(t, x, v(t, x))v_{j x_{μ}}(t, x)

+ f̄_{μ x_{j}}(t, x, v(t, x))v_{μ}(t, x) + v_{μ}(t, x) ∑_{ν} f̄_{μ v_{ν}}(t, x, v(t, x))v_{ν x_{j}}(t, x)) .

Regarding v_{ν x_{j}} = v_{j x_{ν}} and exchanging ν and μ in the double sum we obtain

v_{j t}(t, x) = ∑_{μ} \frac{1}{2}d_{μ}v_{j x_{μ}x_{μ}}(t, x) + \underbrace{∑_{μ} f̄_{μ x_{j}}(t, x, v(t, x))v_{μ}(t, x)}_{=:b̂_{j}(t,x,v(t,x))}

+ ∑_{μ} \underbrace{(f̄_{μ}(t, x, v(t, x)) + ∑_{ν} f̄_{ν v_{μ}}(t, x, v(t, x))v_{ν}(t, x))}_{=:b_{μ}(t,x,v(t,x))} v_{j x_{μ}}(t, x)

For this PDE we can use a the following modification of the finite difference method introduced in Ma/Yong [9].

6 Finite Difference Method for the PDE

We will now give a finite difference method for the solution of the following system of PDEs

v_{t} = \frac{1}{2} ∑_{μ} d_{μ}v_{x_{μ} x_{μ}} + ∑_{μ} b_{μ}(t, x, v)v_{x_{μ}} + b̂(t, x, v)  (11)

with initial condition

v(0, x) = g_{x}(x)  (12)

under the following assumptions.

(A1) The functions b and b̂ are continuously differentiable in t and twice continuously differentiable in x, v. Moreover, if we denote any of these functions generically by ψ, then there exists a constant α ∈ (0, 1), such that for fixed v, ψ(·, ·, v) ∈ C^{1+ \frac{α}{2} ,2+α}, the space of all functions ϕ(t, x) which are differentiable in t and twice differentable in x such that ϕ_{t} and ϕ_{xx} is \frac{α}{2}- and α-Hölder continuous in t and x, respectively, with the norm

∥ϕ∥_{1,2,α} := ∥ϕ∥_{∞} + ∥ϕ_{t}∥_{∞} + ∥ϕ_{x}∥_{∞} + ∥ϕ_{xx}∥_{∞}

+ sup_{(t,x)≠(t′,x′)} \frac{|ϕ_{t}(t, x) − ϕ_{t}(t′, x′)| + |ϕ_{xx}(t, x) − ϕ_{xx}(t′, x′)|}{(|t − t′| + |x − x′|^{2})^{\frac{α}{2}}}.

Furthermore, for some L > 0,

∥ψ(·, ·, v)∥_{1,2,α} ≤ L, ∀v ∈ IR^{m}.

(A2) The function g belongs boundedly to C^{4+α} for some α ∈ (0, 1).

Now we know from Theorem 2.3. in [3] that under the assumptions (A1) and (A2) there is a unique classical solution v to the PDE (11) belonging to the space C^{2+ \frac{α}{2} ,4+α}, and all partial derivatives of v up to the second order in t and fourth order in x are bounded by a constant K > 0.

If we further add the boundary condition

v(t, x) = g_{x}(x) for ∥x∥_{∞} = R, 0 < t ≤ 1  (13)

then the solutions v^{R} of the system (11), (12) and (13) converge uniformly to the solution v of (11) and (12) with R → ∞ (see Ma/Yong [9] chapter 4).

Let Δt > 0 and h > 0 be fixed numbers. Let t_{k} = kΔt and for a multiindex i = (i_{1}, ..., i_{m}) define x^{i} = ih = (i_{1}h, ..., i_{m}h)^{T}.

In the following we will use v instead of v^{R} for the exact solution of the PDE with boundary restrictions and w for the solution of the finite difference method. For functions ϕ defined on IR × IR^{d} we use the abbreviation ϕ_{k}^{i} instead of ϕ(t_{k}, x^{i}).

Moreover we define

δ_{μ}^{(1)}(ϕ)_{k}^{i} := \{ \begin{matrix}\frac{ϕ_{k}^{i+1μ}−ϕ_{k}^{i}}{h} & if b_{μ}(t_{k}, x^{i}, w_{k−1}^{i}) ≥ 0 \\ \frac{ϕ_{k}^{i}−ϕ_{k}^{i−1μ}}{h} & if b_{μ}(t_{k}, x^{i}, w_{k−1}^{i}) < 0 \end{matrix}  (14)

δ_{μ}^{(2)}(ϕ)_{k}^{i} := \frac{ϕ_{k}^{i+1_{μ}} − 2ϕ_{k}^{i} + ϕ_{k}^{i−1_{μ}}}{h^{2}}  (15)

where 1_{μ} is the multiindex with 1 at μ-th position and 0 otherwise.

Now we compute w by the following recursive steps:

Step 0: Set w_{0}^{i} = g_{x}(x^{i}).

Step k: Suppose that w_{k−1}^{i} are defined for all i : h max_{1≤j≤m} |i_{j}| ≤ R. Then we obtain the grid values w_{k}^{i} as solutions of the difference equation

\frac{w_{k}^{i} − w_{k−1}^{i}}{Δt} = \frac{1}{2} ∑_{μ} d_{μ}δ_{μ}^{(2)}(w)_{k}^{i} + ∑_{μ} b_{μ}(t_{k}, x^{i}, w_{k−1}^{i})δ_{μ}^{(1)}(w)_{k}^{i} + b̂(t_{k}, x^{i}, w_{k−1}^{i}) (16)

for h max_{1≤j≤m} |i_{j}| < R and by

w_{k}^{i} = g_{x}(x^{i})

if h max_{1≤j≤m} |i_{j}| = R.

Now we will prove that the approximate solutions converge to the exact solution.

Theorem 4 Let the assumptions (A1) and (A2) be satisfied. Then the grid values w_{k}^{i} of the above finite difference method converge to the grid values v_{k}^{i} of the exact solution of the boundary value problem (11), (12) and (13).

Proof. Define

e_{k}^{i} := \frac{v_{k}^{i} − v_{k−1}^{i}}{Δt} − \frac{1}{2} ∑_{μ} d_{μ}δ_{μ}^{(2)}(v)_{k}^{i} − ∑_{μ} b_{μ}(t_{k}, x^{i}, v_{k−1}^{i})δ_{μ}^{(1)}(v)_{k}^{i} − b̂(t_{k}, x^{i}, v_{k−1}^{i}) (17)

Then

e_{k}^{i} = \{\frac{v_{k}^{i} − v_{k−1}^{i}}{Δt} − v_{t}(t_{k}, x^{i})\}

−\frac{1}{2} ∑_{μ} d_{μ} \{δ_{μ}^{(2)}(v)_{k}^{i} − v_{x_{μ}x_{μ}}(t_{k}, x^{i})\}

− ∑_{μ} {b_{μ}(t_{k}, x^{i}, v_{k−1}^{i})δ_{μ}^{(1)}(v)_{k}^{i} − b_{μ}(t_{k}, x^{i}, v_{k}^{i})v_{x_{μ}}(t_{k}, x^{i})}

− {b̂(t_{k}, x^{i}, v_{k−1}^{i}) − b̂(t_{k}, x^{i}, v_{k}^{i})}

= I_{k}^{1,i} + I_{k}^{2,i} + I_{k}^{3,i} + I_{k}^{4,i}

Now, using mean value theorem we get

|I_{k}^{1,i}| ≤ ∥v_{tt}∥_{∞}Δt,
|I_{k}^{2,i}| ≤ \frac{1}{2} ∑_{μ} d_{μ}∥v_{x_{μ}x_{μ}x_{μ}}∥_{∞}h,
|I_{k}^{3,i}| ≤ ∑_{μ} {|b_{μ}(t_{k}, x^{i}, v_{k−1}^{i})||δ_{μ}^{(1)}(v)_{k}^{i} − v_{x_{μ}}(t_{k}, x^{i})|
+|b_{μ}(t_{k}, x^{i}, v_{k−1}^{i}) − b_{μ}(t_{k}, x^{i}, v_{k}^{i})||v_{x_{μ}}(t_{k}, x^{i})|}
≤ ∑_{μ} {∥b_{μ}∥_{∞}∥v_{x_{μ}x_{μ}}∥_{∞}h + ∥b_{μ v}∥_{∞}∥v_{t}∥_{∞}Δt} ,
|I_{k}^{4,i}| ≤ ∥b̂_{v}∥_{∞}∥v_{t}∥_{∞}Δt.

Thus |e_{k}^{i}| ≤ C(Δt + h) where C is a generic constant. Let ζ := v − w. Then

\frac{ζ_{k}^{i} − ζ_{k−1}^{i}}{Δt} = \frac{1}{2} ∑_{μ} d_{μ}δ_{μ}^{(2)}(ζ)_{k}^{i} + ∑_{μ} [b_{μ}(t_{k}, x^{i}, v_{k−1}^{i})δ_{μ}^{(1)}(v)_{k}^{i} − b_{μ}(t_{k}, x^{i}, w_{k−1}^{i})δ_{μ}^{(1)}(w)_{k}^{i}]
+b̂(t_{k}, x^{i}, v_{k−1}^{i}) − b̂(t_{k}, x^{i}, w_{k−1}^{i}) + e_{k}^{i}
= \frac{1}{2} ∑_{μ} d_{μ}δ_{μ}^{(2)}(ζ)_{k}^{i} + ∑_{μ} [b_{μ}(t_{k}, x^{i}, w_{k−1}^{i})δ_{μ}^{(1)}(ζ)_{k}^{i}

+ (b_{μ}(t_{k}, x^{i}, v_{k−1}^{i}) − b_{μ}(t_{k}, x^{i}, w_{k−1}^{i})) δ_{μ}^{(1)}(v)_{k}^{i}]
+b̂(t_{k}, x^{i}, v_{k−1}^{i}) − b̂(t_{k}, x^{i}, w_{k−1}^{i}) + e_{k}^{i}.  (18)

Moreover we define

∥ζ_{k}∥ := max_{i} |ζ_{k}^{i}∥_{∞} = max_{i,j} |(ζ_{j})_{k}^{i}| = max_{i,j} max {(ζ_{j})_{k}^{i}; −(ζ_{j})_{k}^{i}}
= max {max_{i,j}(ζ_{j})_{k}^{i}; − min_{i,j}(ζ_{j})_{k}^{i}} = max {(ζ_{j_{max}(k)})_{k}^{i_{max}(k)}; −(ζ_{j_{min}(k)})_{k}^{i_{min}(k)}}

If we denote the indices i, j maximizing (ζ_{j})_{k}^{i} for given k by i_{max}(k), j_{max}(k) and the indeces minimizing (ζ_{j})_{k}^{i} for given k by i_{min}(k), j_{min}(k) then we get

δ_{μ}^{(2)}(ζ_{j_{max}(k)})_{k}^{i_{max}(k)} ≤ 0
δ_{μ}^{(2)}(ζ_{j_{min}(k)})_{k}^{i_{min}(k)} ≥ 0
b_{μ}(t_{k}, x^{i_{max}(k)}, w_{k}^{i_{max}(k)})δ_{μ}^{(1)}(ζ_{j_{max}(k)})_{k}^{i_{max}(k)} ≤ 0
b_{μ}(t_{k}, x^{i_{min}(k)}, w_{k}^{i_{min}(k)})δ_{μ}^{(1)}(ζ_{j_{min}(k)})_{k}^{i_{min}(k)} ≥ 0

and from (18) follows

(ζ_{j_{max}(k)})_{k}^{i_{max}(k)} ≤ (ζ_{j_{max}(k)})_{k−1}^{i_{max}(k)}

+ [∑_{μ} (b_{μ}(t_{k}, x^{i_{max}(k)}, v_{k−1}^{i_{max}(k)}) − b_{μ}(t_{k}, x^{i_{max}(k)}, w_{k−1}^{i_{max}(k)})) δ_{μ}^{(1)}(v_{j_{max}(k)})_{k}^{i_{max}(k)}

+b̂_{j_{max}(k)}(t_{k}, x^{i_{max}(k)}, v_{k−1}^{i_{max}(k)}) − b̂_{j_{max}(k)}(t_{k}, x^{i_{max}(k)}, w_{k−1}^{i_{max}(k)}) + (e_{j_{max}(k)})_{k}^{i_{max}(k)}] Δt

≤ ∥ζ_{k−1}∥ + [∑_{j} (∑_{μ} ∥b_{μ v_{j}}∥_{∞}∥v_{j_{max}(k) x_{μ}}∥_{∞} + ∥b̂_{j_{max}(k) v_{j}}∥_{∞}) |(ζ_{j})_{k−1}^{i_{max}(k)}|

+ C(h + Δt)] Δt

≤ (1 + CΔt)∥ζ_{k−1}∥ + CΔt(h + Δt).

In a similar way we can show that

−(ζ_{j_{min}(k)})_{k}^{i_{min}(k)} ≤ (1 + CΔt)∥ζ_{k−1}∥ + CΔt(h + Δt),

which implies

∥ζ_{k}∥ ≤ (1 + CΔt)∥ζ_{k−1}∥ + CΔt(h + Δt).

Together with ∥ζ_{0}∥ = 0 this yields

∥ζ_{k}∥ ≤ CΔt(h + Δt) ∑_{ν=1}^{k−1}(1 + CΔt)

= (h + Δt)[(1 + CΔt)^{k} − 1]
≤ (h + Δt)[(1 + CΔt)^{\frac{1}{Δt}} − 1]
≤ (h + Δt)[e^{C} − 1].

Thus ζ_{k} converges to 0 for all k with h and Δt converging to 0 so that the convergence of the solution of the finite difference method is shown.

References

[1] Benes VE (1971) Existence of optimal stochastic control laws. SIAM J. Control and Optimization 9: 446–472

[2] Davis MHA, Varaiya PP (1973) Dynamic programming conditions for partially observable stochastic systems. SIAM J. Control and Optimization 11: 226–261

[3] Douglas Jr J, Ma J, Protter P (1996) Numerical methods for forward-backward stochastic differential equations. The Annals of Applied Probability 6(3): 940–968

[4] Elliott RJ (1977) The optimal control of a stochastic system. SIAM J. Control and Optimization 15(5): 756–778

[5] Elliott RJ, Kohlmann M (1980) The variational principle and stochastic optimal control. Stochastics 3: 229–241

[6] Girsanov IV (1960) On transforming a certain class of stochastic processes by absolutely continuous substitution of measures. Theory Probability Appl. 5: 285–301

[7] Grecksch W, Heyde F, Tammer C (2000) An ϵ-minimum principle for multiobjective stochastic optimal control problems. Report No. 03 of the Institute of Optimization and Stochastics, Martin-Luther-Universität Halle-Wittenberg

[8] Jahn J (1986) Mathematical Vector Optimization in Partially Ordered Linear Spaces. Verlag Peter Lang, Frankfurt/M.

[9] Ma J, Yong J (1999) Forward-backward stochastic differential equations and their applications. Springer-Verlag, Berlin Heidelberg