Imène Ben Latifa
email: benlatifa@cmap.polytechnique.fr

Joseph Frédéric Bonnans

Mohamed Mnif
email: mohamed.mnif@enit.rnu.tn

A general optimal multiple stopping problem with an application to Swing Options

Keywords: Optimal multiple stopping, swing option, jump diffusion process, Snell envelope, viscosity solution

, Carmona and Touzi have studied an optimal multiple stopping time problem in a market where the price process is continuous. In this paper, we generalize their results when the price process is allowed to jump. Also, we generalize the problem associated to the valuation of swing options to the context of jump diffusion processes. We relate our problem to a sequence of ordinary stopping time problems. We characterize the value function of each ordinary stopping time problem as the unique viscosity solution of the associated Hamilton-Jacobi-Bellman Variational Inequality (HJBVI in short).

Introduction

Optimal stopping problems in general setting was the object of many works. Maingueneau [START_REF] Maingueneau | Temps d'arrêt optimaux et theorie générale[END_REF] and El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF] characterized the optimal stopping time as the beginning of the set where the process is equal to its Snell envelope. In the Markovian context, Pham [START_REF] Pham | Optimal stopping and American option in jump diffusion model[END_REF] studied the valuation of American options when the risky assets are modeled by a jump diffusion process. He showed that the last problem is equivalent to an optimal stopping problem which leads to a parabolic integrodifferential free boundary problem. For details we refer to El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF], when the reward process is non-negative, right continuous, F-adapted and left continuous in expectation and its supremum is bounded in L p , p > 1, Karatzas and Shreve [START_REF] Karatzas | Methods of mathematical finance[END_REF] in the continuous setting and Peskir and Shiryaev [START_REF] Peskir | Optimal Stopping and Free-Boundary Problems[END_REF] in the Markovian context. Optimal multiple stopping of linear diffusion are investigated in Carmona and Dayanik [START_REF] Carmona | Optimal multiple stopping of linear diffusions[END_REF]. Carmona and Touzi [START_REF] Carmona | Optimal Multiple Stopping and valuation of Swing Options[END_REF] introduced the problem of optimal multiple stopping time where the underlying process is continuous. They characterized the optimal multiple stopping time as the solution of a sequence of ordinary stopping time problems. As an application, they studied the valuation of swing options. The latter products are defined as American options with many exercise rights. In fact, the holder of a swing option has the right to exercise it or not at many times under the condition that he respects the refracting time which separates two successive exercises. The consumption in the energy market is not simple, in fact it depends on Foreign parameters like temperature and weather. When the temperature has a high variation, the power consumption has a sharp increase and price follow. Although these spikes of consumption are infrequent, they have a large financial impact, and so the underlying process should be càd-làg. In Dahlgren and Korn [START_REF] Dahlgren | The swing option on the stock market[END_REF] the Swing option on the stock market is investigated and a continuous time model for the price of the option in the Black-Scholes framework is derived. Bouzguenda and Mnif [START_REF] Bouzgenda Zeghal | Optimal Multiple stopping and valuation of Swing Options in Lévy Models[END_REF] generalized the valuation of the swing option where the reward process is allowed to jump. Kobylanski et al. [START_REF] Kobylanski | Optimal multiple stopping time problem, to appear[END_REF] studied an optimal multiple stopping time problem. They showed that such a problem is reduced to compute an optimal one stopping time problem where the new reward function is no longer a right continuous left limited (RCLL) process but a family of positive random variables which satisfy some compatibility properties. Bender et al. [START_REF] Bender | Dual Representations for General Multiple Stopping Problems[END_REF] studied the dual representation for generalized multiple stopping problem. They extended the works by Bender (2011a) [START_REF] Bender | Primal and Dual Pricing of Multiple Exercise Options in Continuous Time[END_REF] and [START_REF] Bender | Dual Pricing of Multi-Exercise Options under Volume Constraints[END_REF] [START_REF] Bender | Dual Pricing of Multi-Exercise Options under Volume Constraints[END_REF] on multiple exercise options. They take into consideration a refraction period and volume constraints both simultaneously. In the present paper, the holder of the option is restricted to buying at most one package per time and he wait for a refraction period δ. In Bender et al. [START_REF] Bender | Dual Representations for General Multiple Stopping Problems[END_REF], exercised times are discrete but in our paper they are continuous. In a general non-Markovian setting, Bender and Dokuchaev [START_REF] Bender | A First Order BSPDE for Swing Option Pricing: Classical Solutions[END_REF] studied an optimal control problem related to swing option pricing. They showed that the value process solves a first-order non-linear backward stochastic partial differential equation, and they derived a dual minimization problem. In discrete time, Bender and Schoenmakers [START_REF] Bender | An Iterative Method for Multiple Stopping: Convergence and Stability[END_REF] presented an iterative procedure for solving the multiple stopping problem. In the present paper, we present a generalization of the classical theory of optimal stopping introduced by El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF]. We relate our multiple stopping time problem to a sequence of ordinary stopping time problems, we prove the existence of an optimal multiple stopping time. In Bouzguenda and Mnif [START_REF] Bouzgenda Zeghal | Optimal Multiple stopping and valuation of Swing Options in Lévy Models[END_REF], they assumed that the expectation of the Snell envelope variation is equal to zero for every predictable time, i.e. E[Y

(i) τ -Y (i)
τ -] = 0 for any predictable stopping time τ and for all i = 1, ..., , where (Y (i) t ) is associated to the Snell envelope when the holder of the option exercised (i -1) times. Such assumption is checked when the process is modeled by the exponential of Lévy process. In the present paper, we get rid of this assumption. As in El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF], we assume that the state process is non-negative, right continuous, F-adapted and left continuous in expectation and its supremum is bounded in L p , p > 1 and so we can apply our result for a general jump diffusion process. We characterize the value function of each ordinary problem as the unique viscosity solution of the associated HJBVI. Such characterization is important in the sense that if we propose a monotone consistent and stable numerical scheme, then it converges to the unique viscosity solution of the associated HJBVI. This part is postponed in future research. Bouzguenda and Mnif [START_REF] Bouzgenda Zeghal | Optimal Multiple stopping and valuation of Swing Options in Lévy Models[END_REF] solved numerically the sequence of optimal stopping problem by using Malliavin Calculus to approximate the conditional expectation, but they didn't obtain a convergence result. In our case such convergence result is possible thanks to the powerful tool of viscosity solutions. This paper is organized as follows, in section 2 we formulate the problem. In section 3 we provide the existence of a multiple optimal stopping time. In section 4 we study the valuation of swing options in the jump diffusion case. The regularity of the value function is studied in section 5. In the last section we prove that each value function is the unique viscosity solution of the associated HJBVI.

Problem Formulation

Let (Ω, F, P) be a complete probability space, and F = {F t } t≥0 a filtration which satisfies the usual conditions, i.e. an increasing right continuous family of subσ-algebras of F such that F 0 contains all the P-null sets. Let T ∈ (0, ∞) be the option maturity time i.e. the time of expiration of our right to stop the process or exercise, S the set of F-stopping times with values in [0, T ] and S σ = {τ ∈ S ; τ ≥ σ} for every σ ∈ S. We shall denote by δ > 0 the refraction period which separates two successive exercises. We also fix ≥ 1 the number of rights we can exercise. Now, we define by S ( ) σ the set:

S ( ) σ := (τ 1 , ..., τ ) ∈ S , τ 1 ∈ S σ , τ i -τ i-1 ≥ δ on {τ i-1 + δ ≤ T } a.s, τ i = (T + ) on {τ i-1 + δ > T } a.s, ∀ i = 2, ..., , (2.1)
where T + is a cemetery time. Let X = (X t ) 0≤t≤T be a non-negative, right continuous, left continuous in expectation (see definition 2.1 below) and F-adapted process, and assume that X T + = 0. We recall the definition of left continuous in expectation.

Definition 2.1 A process X is said to be left continuous in expectation (LCE), if for any τ ∈ S and for any sequence (τ n ) n≥0 of stopping times such that τ n ↑ τ a.s. one has

lim n→∞ E [X τn ] = E [X τ ].
We assume that X satisfies the integrability condition :

E Xp < ∞ for some p > 1, where X = sup 0≤t≤T X t . (2.2)
we assume that :

X t = 0, ∀t > T. (2.3)
We introduce the following optimal multiple stopping problem :

Z ( ) 0 := sup (τ 1 ,...,τ )∈S ( ) 0 E i=1 X τ i . (2.4)
It consists in computing the maximum expected reward Z ( ) 0

and finding the optimal exercise strategy (τ 1 , ..., τ ) ∈ S ( ) 0 at which the supremum in (2.4) is attained, if such a strategy exists. To solve the optimal multiple stopping problem, we define inductively the sequence :

Y (0) := 0 and Y (i) t := ess sup τ ∈St E X (i) τ |F t , ∀ t ≥ 0, ∀ i = 1, ..., , (2.5)
where the i-th exercise reward process X (i) is given by :

X (i) t := X t + E Y (i-1) t+δ |F t for 0 ≤ t ≤ T -δ (2.6)
and

X (i) t := X t for t > T -δ. (2.7)
Since the paths of X (i) are right continuous, it is known ( [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF], [START_REF] Maingueneau | Temps d'arrêt optimaux et theorie générale[END_REF]) that for every stopping time θ

Y (i) θ = ess sup τ ∈S θ E X (i) τ |F θ , ∀ i = 1, ..., .
Notation .1 Note that the constants which appear in this paper are generic constants and could change from line to line.

3 Existence of an optimal multiple stopping time

In this section, we shall prove that Z ( ) 0 can be computed by solving inductively single optimal stopping problems sequentially. This result is proved in [START_REF] Carmona | Optimal Multiple Stopping and valuation of Swing Options[END_REF] under the assumption that the process X is continuous a.s.. As it is proved by El Karoui [13, Theorem 2.18, p.115], the existence of the optimal stopping strategy for a right continuous, non-negative and F-adapted process X requires assumption (2.2) in addition to the left continuity in expectation (see Definition 2.1) of the process X. Definition 3.1 For all stopping time τ , we said that θ * ∈ S τ is an optimal stopping time of the problem

Y (i) τ = ess sup θ∈Sτ E X (i) θ |F τ , ∀ i = 1, ..., . (3.1)
if

Y (i) τ = E X (i) θ * |F τ a.s..
In Lemmas 3.1, 3.2 and Proposition 3.1 we show that the i-th exercise reward process X (i) satisfies the conditions required to solve the i-th optimal stopping problem.

Lemma 3.1 Suppose that the non-negative F-adapted and right continuous process X satisfies the condition (2.2). Then, for all i = 1, ..., , the process X (i) satisfies :

E X(i) p < ∞, p > 1, where X(i) := sup 0≤t≤T X (i) t ,
Proof. We proceed by induction on i.

For i = 1 we have that X (1) = X so by assumption (2.2) we have that E[ X(1) p ] < ∞. Let i ∈ {2, ..., }, let us assume that E[ X(i-1) p ] < ∞, we will show that E[ X(i) p ] < ∞.

We have that for all τ ∈ S 0 , 0

≤ t ≤ T E[X (i-1) τ |F t ] ≤ E sup 0≤s≤T X (i-1) s |F t := X(i-1) t then Y (i-1) t = ess sup τ ∈St E X (i-1) τ |F t ≤ X(i-1) t , hence E sup 0≤t≤T (Y (i-1) t ) p ≤ E sup 0≤t≤T ( X(i-1) t ) p . (3.2)
We have that X(i-1) is F-adapted,

E[ X(i-1) t ] ≤ E E sup 0≤s≤T X (i-1) s |F t = E sup 0≤s≤T X (i-1) s := E[ X(i-1) ] < ∞ and for u ≤ t, E[ X(i-1) t |F u ] = E E sup 0≤s≤T X (i-1) s |F t |F u = E sup 0≤s≤T X (i-1) s |F u := X(i-1) u , then ( X(i-1) t
) is a martingale. Hence Doob's L p inequality and Jensen's inequality show:

E sup 0≤t≤T ( X(i-1) t ) p ≤ p p -1 p sup 0≤t≤T E ( X(i-1) t ) p ≤ p p -1 p E ( X(i-1) ) p (3.3)
From (3.2), (3.3) and the induction assumption we deduce that:

E sup 0≤t≤T (Y (i-1) t ) p ≤ p p -1 p E ( X(i-1) ) p < ∞.
(3.4)

From inequality (3.4), using the supermartingale property of Y (i-1) and since sup 0≤t≤T

Y (i-1) t p = sup 0≤t≤T (Y (i-1) t
) p , we obtain

E ( X(i) ) p 1/p ≤ E sup 0≤t≤T X t + E Y (i-1) t+δ |F t p 1/p ≤ E X + sup 0≤t≤T E Y (i-1) t+δ |F t p 1/p ≤ C   E Xp 1/p + E sup 0≤t≤T E Y (i-1) t+δ |F t p 1/p   ≤ C   E Xp 1/p + E sup 0≤t≤T (Y (i-1) t ) p 1/p   < ∞, (3.5)
where C is a positive constant. Inequality (3.5) implies that:

E ( X(i) ) p < ∞. 2
Lemma 3.2 Suppose that the non-negative F-adapted process X is right continuous, then for all i = 1, ..., , the process X (i) is non-negative F-adapted and right continuous.

Proof. The process X is non-negative and F-adapted, then from the definition of the process X (i) (see equalities (2.6) and (2.7)), we have for i = 1, ..., the process X (i) is non-negative and F-adapted.

Let us prove by induction that for all i = 1, ..., , X (i) is right continuous. For i = 1 we have that X (1) = X, which is right continuous. Let i ∈ {1, ..., -1}, assume that X (i) is right continuous and let us prove that X (i+1) is right continuous. The process X is right continuous, then from the definition of

X (i+1) (equation (3.1)) it suffices to prove that E Y (i)
t+δ |F t is right continuous. To prove this it suffices to prove that Y (i) is right continuous (see Dellacherie and Meyer [12, Theorem 47 p.119]). Since X (i) is non-negative and F-adapted (from (3.6)), bounded in L 1 (P) (from Lemma 3.1) and right continuous (from the induction assumption), then from El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF]Theorem 2.15,p.113] we obtain that Y (i) is right continuous. We deduce then (by Dellacherie and Meyer [START_REF] Dellacherie | Probabilités et potentiel. Chapitres V à VIII : théorie des martingales[END_REF]Theorem 47 p.119]) that the optional projection E Y (i) t+δ |F t of Y (i) is right continuous and then X (i+1) is also. We conclude then the right continuity of

X (i) for i = 1, ..., . 2
To prove the existence of optimal stopping time for problem (3.1) we start by giving the definition of a closed under pairwise maximization family and proving that E X

(i-1) τ |F t , τ ∈ S t is such a family.
Definition 3.2 A family (X i ) i∈I of random variables is said to be closed under pairwise maximization if for all i, j ∈ I, there exists k

∈ I such that X k ≥ X i ∨ X j . Lemma 3.3 Let t ∈ [0, T ], the family E X (i-1) τ |F t , τ ∈ S t is closed under pairwise maximization. Proof. Let τ 1 , τ 2 ∈ S t and X(i-1) t,τ j := E X (i-1) τ j
|F t (j = 1, 2). We define the stopping time

τ := τ 1 1 { X(i-1) t,τ 1 ≥ X(i-1) t,τ 2 } + τ 2 1 { X(i-1) t,τ 1 < X(i-1) t,τ 2 } .
We have that τ ∈ S t and E X

(i-1) τ |F t ≥ E X (i-1) τ j |F t , for j = 1, 2. We deduce then that E X (i-1) τ |F t , τ ∈ S t is closed under pairwise maximization. 2
This Lemma added to Proposition A.2 p.230 of El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF] and Theorem 8.1 (see Appendix) gives the following Lemma.

Lemma 3.4 For i = 1, ..., , for all t ∈ [0, T ] E Y (i) t = sup τ ∈St E X (i) τ .
(3.7)

Our aim now is to prove the left continuity in expectation of X (i) , for i = 1, ..., . In the following proposition we prove that X (i) is LCE.

Proposition 3.1 Suppose that the non-negative F-adapted process X is right continuous, left continuous in expectation (LCE) and satisfies condition (2.2). Then, for all i = 1, ..., , the process X (i) is LCE.

Proof. We proceed by induction. For i = 1, we have that X (1) = X, so it is left continuous in expectation. Let 1 ≤ i ≤ -1, assume that X (i) is LCE and we will show that X (i+1) is LCE. We begin by proving that Y (i) is LCE. Let τ ∈ S and (τ n ) be a sequence of stopping times such that τ n ↑ τ a.s.. Note that by the supermartingale property of Y (i) we have

E Y (i) τn ≥ E Y (i) τ , ∀n ∈ N. (3.8)
Since X (i) is non-negative, F-adapted, bounded in L 1 (P) and LCE, then by El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF]

θ (i) n = inf{t ≥ τ n , X (i) t = Y (i) t }
is an optimal stopping time of

Y (i) τn = ess sup τ ∈Sτ n E X (i) τ |F τn . (3.9)
So by the Definition 3.1, we obtain that

E Y (i) τn = E X (i) θ (i) n . Moreover, it is clear that θ (i) n i
is a nondecreasing sequence of stopping times dominated by T . Let us define θ(i) := lim n→∞ ↑ θ (i) n . Note that θ(i) is a stopping time. Also, as for each n, θ (i) n ≥ τ n a.s., it follows that θ(i) ∈ S τ . Therefore, since X (i) is LCE and since θ (i) n is an optimal stopping time of (3.9), we obtain

E Y (i) τ = sup θ∈Sτ E X (i) θ ≥ E X (i) θ(i) = lim n→∞ E X (i) θ (i) n = lim n→∞ E Y (i)
τn .

(3.10)

By inequalities (3.8) and (3.10) we deduce that Y (i) is LCE. Let τ be a stopping time and (τ n ) n a sequence of stopping times such that τ n ↑ τ a.s., we have that

E[X (i+1) τn ] = E[X τn ] + E Y (i) τn+δ .
Sending n to ∞, we obtain that E[X

(i+1) τn ] → E[X (i+1) τ
], and then X (i+1) is LCE. We conclude then that for all i = 1, ..., , X (i) is LCE.

2

Let us set:

τ * 1 := inf{t ≥ 0 ; Y ( ) t = X ( ) t }. (3.11) Since Y ( ) T = X ( ) T , then τ * 1 ≤ T a.s.. Next, for 2 ≤ i ≤ , we define τ * i := inf{t ≥ δ + τ * i-1 ; Y ( -i+1) t = X ( -i+1) t }1 {δ+τ * i-1 ≤T } + (T + )1 {δ+τ * i-1 >T } . (3.12)
Clearly, τ * := (τ * 1 , ..., τ * ) ∈ S ( ) 0 . Since for all i = 1, ..., , X ( -i+1) is a non-negative right continuous F-adapted process that satisfies the integrability condition E ess sup τ ∈S X ( -i+1) τ < ∞ and which is LCE along stopping times, then we obtain the existence of optimal stopping time (see El Karoui [13, Theorem 2.18, p.115], Theorem 8.2 and Proposition 8.2 in the Appendix). We can then cite the following Theorem.

Theorem 3.1 (Existence of optimal stopping time) For each τ ∈ S there exists an optimal stopping time of the problem

Y ( -i+1) τ = ess sup θ∈Sτ E X ( -i+1) θ |F τ , ∀ i = 1, ..., .

Moreover τ *

i is the minimal optimal stopping time of the problem

Y ( -i+1) τ * i-1 +δ = ess sup τ ∈S τ * i-1 +δ E X ( -i+1) τ |F τ * i-1 +δ , ∀ i = 1, ..., .
( by convention τ * 0 + δ = 0 ). We have also that

E Y ( -i+1) τ * i = sup τ ∈S τ * i-1 +δ E X ( -i+1)
τ and the stopped supermartingale {Y

( -i+1) t∧τ * i , τ * i-1 + δ ≤ t ≤ T } is a martingale.
By Theorem 3.2 we generalize Theorem 1 of [START_REF] Carmona | Optimal Multiple Stopping and valuation of Swing Options[END_REF] to right-continuous price processes.

Theorem 3.2 Let us assume that the non-negative, F-adapted process X is right continuous, left continuous in expectation and satisfies condition (2.2). Then,

Z ( ) 0 = Y ( ) 0 = E i=1 X τ * i ,
where (τ * 1 , ..., τ * ) represents the optimal exercise strategy.

Proof. From Theorem 3.1, τ * i is an optimal stopping time for the problem

Y ( -i+1) τ * i-1 +δ = ess sup τ ∈S τ * i-1 +δ E X ( -i+1) τ |F τ * i-1 +δ (3.13)
Let τ = (τ 1 , ..., τ ) be an arbitrary element in S ( ) 0 . For ease of notation, we set τi := τ -i+1 .

A) Let us prove that, for all 1

≤ i ≤ E   j=1 X τ j   ≤ E   X (i) τi + j=i+1 X τj   . (3.14)
We prove this result by induction. For i = 1 we have that

E   j=1 X τ j   ≤ E   X (1) τ1 + j=2 X τj   ,
since X (1) ≡ X and for all ≥ 1 we have

j=1 X τ j = j=1
X τj . We conclude then that the

inequality (3.14) is true for i = 1. Let 1 ≤ i ≤ -1, suppose that (3.14) is true for i.
We prove that it is true for i + 1.

We have that

E   j=1 X τ j   = E   j=1 X τj   = E   i j=1 X τj + j=i+1 X τj   , (3.15)
so by the assumption (3.14) we have that

E[X (i) τi ] ≥ E   i j=1 X τj   . (3.16)
Let us prove that

E[X (i) τi ] ≤ E[X (i+1) τi+1 -X τi+1 ].
(3.17)

• If T -δ < τi+1 ≤ T , then X (i+1) τi+1 = X τi+1 . We have that τ -i = τi+1 > T -δ so τi = τ -i+1 ≥ δ + τ -i > T , then X (i) τi = 0, see assumption (2.
3), and then

E[X (i) τi ] = 0 = E[X (i+1) τi+1 -X τi+1 ].
(3.18)

• If 0 ≤ τi+1 ≤ T -δ, we have that τi = τ -i+1 ≥ τ -i + δ = τi+1 + δ, then τi ∈ S τi+1 +δ , which implies E[X (i) τi ] = E E X (i) τi |F τi+1 +δ ≤ E Y (i) τi+1 +δ = E[X (i+1) τi+1 -X τi+1 ]. (3.19)
Then the inequality (3.17) holds in both cases.

In view of (3.17) and in addition with (3.16) it gives that

E   i j=1 X τj   ≤ E[X (i+1) τi+1 -X τi+1 ].
In addition with (3.15) we obtain that

E   j=1 X τ j   ≤ E[X (i+1) τi+1 ] + E   j=i+1 X τj   -E[X τi+1 ] = E[X (i+1) τi+1 ] + E   j=i+2 X τj
E   j=1 X τ j   ≤ E[X ( ) τ 1 ] ≤ Y ( ) 0 = E[X ( ) τ * 1 ]. (3.20)
We have that E[X

( ) τ * 1 ] = E X τ * 1 + E[Y ( -1) τ * 1 +δ |F τ * 1 ] , then E   j=1 X τ j   ≤ Y ( ) 0 = E X τ * 1 + E[Y ( -1) τ * 1 +δ ]. ( 3
E[Y ( -i) τ * i +δ ] = E[X ( -i) τ * i+1 ] = E[X τ * i+1 ] + E[Y ( -i-1) τ * i+1 +δ ] (3.22)
By equations (3.21), (3.22) and the assumption that Y (0) = 0, we obtain that

E i=1 X τ i ≤ Y ( ) 0 ≤ E[X τ * 1 + ... + X τ * ].
We have that (τ 1 , ..., τ ) is an arbitrary element in S ( ) In this section, we consider a jump diffusion model. We prove that conditions ensuring the existence of an optimal stopping time vector for the optimal multiple stopping time problem are satisfied. Then, we give the solution to the valuation and a vector of optimal stopping times of the swing option under the risk neutral probability measure for general jump diffusion processes.

0 so Z ( ) 0 = sup τ ∈S ( ) 0 E i=1 X τ i ≤ Y ( ) 0 ≤ E[X τ * 1 + ... + X τ * ]. ( 3

The jump diffusion Model

We consider two assets (S 0 , X), where S 0 is the bond and X is a risky asset. The dynamics of S 0 is given by dS 0 t = rS 0 t dt, where r > 0 is the interest rate. We assume that the financial market is incomplete, so there are many equivalent martingale measures. We denote by Q an equivalent martingale measure, and the expectation under Q by E Q . We define under Q, an F-standard Brownian motion W and an F-homogeneous Poisson random measure v with intensity measure q(ds, dz) = ds × m(dz), m is the Lévy measure on R of v and ṽ(ds, dz) := (v -q)(ds, dz) is called the compensated jump martingale random measure of v. The process X = (X t ) 0≤t≤T evolves according to the following stochastic differential equation:

dX s = b(s, X s -)ds + σ(s, X s -)dW s + R\{0} γ(s, X s -, z)ṽ(ds, dz), X t = x, (4.1)
where b, σ, and γ are continuous functions with respect to (t, x). The Lévy measure m is a positive, σ-finite measure on R, such that

|z|≥1 m(dz) < +∞. ( 4.2)
Furthermore, we shall make the following assumptions: there exists K > 0, ρ : R → R + , with

R\{0} ρ 2 (z)m(dz) < ∞, (4.3)
such that for all t ∈ [0, T ], x, y and z ∈ R,

|b(t, x) -b(t, y)| + |σ(t, x) -σ(t, y)| ≤ K|x -y| (4.4) |γ(t, x, z) -γ(t, y, z)| ≤ ρ(z)|x -y| (4.5) |γ(t, x, z)| ≤ ρ(z)(1 + |x|). (4.6)
Notice that the continuity of b, σ and γ with respect to (t, x) and the Lipschitz condition (4.4) implies the global linear condition

|b(t, x)| + |σ(t, x)| ≤ K(1 + |x|). (4.7)
Assumptions on b, σ and γ ensure that there exists a unique càdlàg adapted solution to (4.1) such that

E Q sup s∈[0,T ] |X s | 2 < ∞,
(see Øksendal and Sulem [START_REF] Øksendal | Applied Stochastic Control of Jump Diffusions[END_REF]). We shall also use the notation X t,x s for X s whenever we need to emphasize the dependence of the process X on its initial condition. Let us give an example for which these technical conditions, especially on the jump component, are satisfied.

Example 4.1 m is a finite measure on R : m(dz) = λh(z)dz, and h is a probability density which admits second order moment. γ(t, x, z) = xz so that assumptions (4.5)-(4.6) are satisfied with ρ(z) = z.

Remark 4.1 The process X solution of (4.1) is quasi-left continuous (see [START_REF] Rogers | Diffusions, Markov Processes and Martingales[END_REF]Chapter III]). It means that ∆X τ = 0 a.s on the set {τ < ∞}, for every predictable time τ .

Formulation of the Optimal Multiple Stopping Time Problem

The value function of the swing option problem with exercise rights and refraction time δ > 0 is given by:

v ( ) (x) := v ( ) (0, x) := sup (τ 1 ,...,τ )∈ S ( ) 0 E Q i=1 e -rτ i φ(X 0,x τ i ) , (4.8)
where φ : R -→ R + is a Lipschitz payoff function with linear growth.

To solve the problem (4.8), we need to define the dynamic version:

v (k) (t, x) := ess sup τ ∈ St E Q e -r(τ -t) φ (k) (τ, X τ )|X t = x , v (0)
≡ 0 (4.9)

where k = 1, ..., and

φ (k) (t, x) := φ(x) + e -rδ E Q v (k-1) (t + δ, X t+δ )|X t = x , ∀ 0 ≤ t ≤ T -δ (4.10) φ (k) (t, x) := φ(x), ∀ T -δ < t ≤ T.
Assume that for all s > T , φ (k) (s, X s ) = 0. It is well-known that the process e -rs v (k) (s, X s ) s∈[0,T ] is the Snell envelope of the process e -rs φ (k) (s, X s ) s∈[0,T ] . To apply the general result, Theorem 3.2, on the optimal multiple stopping time problem obtained in the previous section, we have to show that section 2 conditions are satisfied. This is proved in Proposition 4.1, where the reward process is then given by U s := e -rs φ(X s ).

Proposition 4.1 The F-adapted process U satisfies the following conditions :

U is right continuous, (4.11)

E Q Ū 2 < ∞ where Ū = sup 0≤s≤T U s , (4.12)
U is left continuous in expectation, (

Proof. Since φ is a continuous function and X is right continuous, then the process (U s ) s∈[0,T ] = (e -rs φ(X s )) s∈[0,T ] is right continuous.

From the growth condition of φ, we have

∀ 0 ≤ s ≤ T, U s ≤ K(1 + |X s |) a.s. and E Q [|X s | 2 ] ≤ E Q sup 0≤u≤T |X u | 2 < ∞,(4.14) then E Q Ū 2 < ∞.
Since X is quasi left continuous, then from the continuity of the payoff function φ we deduce that it is also the case for the process U . By the dominated convergence theorem, we deduce that lim

n→∞ E Q [U τn ] = E Q [U τ ] and then U is left continuous in expectation. 2 Let us set θ * 1 := inf{s ≥ 0 ; v ( ) (s, X s ) = φ ( ) (s, X s )}.
For 2 ≤ k ≤ , we define

θ * k := inf{s ≥ δ + θ * k-1 ; v ( -k+1) (s, X s ) = φ ( -k+1) (s, X s )}1 {δ+θ * k-1 ≤T } + (T + )1 {δ+θ * k-1 >T } .
Our aim is to relate problem (4.8) to the sequence of problems defined in (4.9). The next theorem allows us to use Theorem 3.1 in the Markovian context.

Theorem 4.1 For each k = 1, ..., , there exists an optimal stopping time for problem (4.9). Moreover θ * k is the minimal optimal stopping time of the problem

v ( -k+1) (θ * k-1 + δ, X θ * k-1 +δ ) = ess sup τ ∈ S θ * k-1 +δ E Q e -r(τ -θ * k-1 -δ) φ ( -k+1) (τ, X τ )|F θ * k-1 +δ . Also we have v ( ) (x) = E Q i=1 e -rθ * i φ(X θ * i ) .
Proof. By Proposition 4.1 we have that U is left continuous in expectation and satisfies E Q [ Ū 2 ] < ∞, so by Proposition 3.1 we obtain that for each k = 1, ..., , U (k) := (e -rs φ (k) (s, X s )) is also left continuous in expectation. In addition, it is a non negative right continuous F-adapted process and satisfies E Q ( Ū (k) ) 2 < ∞, see Lemma 3.1. By Theorem 3.1 we obtain the first required result, and by Theorem 3.2, we obtain the second. 2

Properties of the value functions

In this section we study the regularity of the sequence of the payoff functions defined by (4.10) and the sequence of value functions defined by (4.9).

Lemma 5.1 For all k = 1, ..., , there exists K > 0 such that for all (t, x)

∈ [0, T ] × R |φ (k) (t, x)| ≤ K(1 + |x|) and |v (k) (t, x)| ≤ K(1 + |x|).
Proof. We proceed by induction on k.

For k = 1, by the linear growth of φ we have that

φ (1) (t, x) := φ(t, x) ≤ K(1 + |x|) (5.1)
and by Lemma 3.1 of Pham [23, p.9]

v (1) (t, x) ≤ K(1 + |x|). Let 1 ≤ k ≤ -1, suppose that there exists K > 0 such that for all (t, x) ∈ [0, T ] × R, |φ (k) (t, x)| ≤ K(1 + |x|) and |v (k) (t, x)| ≤ K(1 + |x|), then φ (k+1) (t, x) = φ(x) + e -rδ E Q v (k) (t + δ, X t,x t+δ ) ≤ K(1 + |x|). (5.2)
Then by Lemma 3.1 of Pham [23, p.9] we obtain that

v (k+1) (t, x) = sup τ ∈ St E Q e -r(τ -t) φ (k) (X t,x τ ) ≤ K(1 + |x|). (5.3)
Which proves the desired result. 2

Proposition 5.1 For all k = 1, ..., , there exists K > 0 such that for all t ∈ [0, T ],

x, y ∈ R

|φ (k) (t, x) -φ (k) (t, y)| ≤ K|x -y| and |v (k) (t, x) -v (k) (t, y)| ≤ K|x -y|.
Proof. We proceed by induction on k.

For k = 1, we have that φ (1) := φ which is Lipschitz and

|v (1) (t, x) -v (1) (t, y)| ≤ sup τ ∈ St E Q |φ(X t,x τ ) -φ(X t,y τ )| ≤ K|x -y|. (5.4) Let 1 ≤ k ≤ -1, suppose that there exists K > 0 such that for all t ∈ [0, T ], x, y ∈ R, |φ (k) (t, x) -φ (k) (t, y)| ≤ K|x -y| and |v (k) (t, x) -v (k) (t, y)| ≤ K|x -y|, then |φ (k+1) (t, x) -φ (k+1) (t, y)| ≤ |φ(x) -φ(y)| + Ke -rδ E Q [|X t,x t+δ -X t,y t+δ |] ≤ K|x -y|,
(5.5) so φ (k+1) is Lipschitz with respect to x. Let us prove that it is also for v (k+1) , we have

|v (k+1) (t, x) -v (k+1) (t, y)| ≤ sup τ ∈ St E Q |φ (k+1) (τ, X t,x τ ) -φ (k+1) (τ, X t,y τ )| ≤ K|x -y|, (5.6)
then v (k+1) is Lipschitz with respect to x.

We conclude then that for all k = 1, ..., , φ (k) and v (k) are both Lipschitz with respect to x. 2

To prove the following theorem, we need to recall the Dynamic Programming Principle.

Proposition 5.2 [23](Dynamic Programming Principle) For all (t, x) ∈ [0, T ] × R, h ∈ S t , k = 1, ..., we have v (k) (t, x) = sup τ ∈ St E Q 1 {τ <h} e -r(τ -t) φ (k) (τ, X t,x τ ) + 1 {τ ≥h} e -r(h-t) v (k) (h, X t,x h ) .
Theorem 5.1 There exists a constant C > 0 such that, for k = 1, ..., , for all t < s ∈ [0, T ], x ∈ R,

φ (k) (t, x) -φ (k) (s, x) ≤ C(1 + |x|) √ s -t (5.7)
and

v (k) (s, x) -v (k) (t, x) ≤ C(1 + |x|) √ s -t.
(5.8)

Proof. Let us prove this theorem by induction.

For k = 1, we have that φ (1) (t, x) = φ (1) (s, x) = φ(x), then the inequality (5.7) is true for k = 1. Let 0 ≤ t < s ≤ T , by the Dynamic Programming Principle, the Lipschitz property of φ and v (1) , Lemma 3.1 of Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF] and from the growth condition of v (1) we obtain that

|v (1) (t, x) -v (1) (s, x)| ≤ C(1 + |x|) √ s -t.
(5.9)

Let 1 ≤ k ≤ -1, suppose that (5.7) and (5.8) are true for k and let us prove that there are true for k + 1. By the induction assumption and Lemma 8.1 (see Appendix) we obtain

φ (k+1) (t, x) -φ (k+1) (s, x) ≤ C(1 + |x|) √ s -t.
By the Dynamic Programming Principle, the Lipschitz property of φ (k+1) and v (k+1) , Lemma 3.1 of Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF] and from the growth condition of v (k+1) we obtain that

|v (k+1) (t, x) -v (k+1) (s, x)| ≤ C(1 + |x|) √ s -t.
(5.10)

We can then conclude that (5.7) and (5.8) are true for all k = 1, ..., . 2

Viscosity solutions and comparison theorem

The aim of this section is to characterize the value function as the unique viscosity solution of the associated HJBVI defined by

min{rv (k) (t, x) - ∂v (k) ∂t (t, x)-A(t, x, ∂v (k) ∂x (t, x), ∂ 2 v (k) ∂x 2 (t, x)) -B(t, x, ∂v (k) ∂x (t, x), v (k) ); v (k) (t, x) -φ (k) (t, x)} = 0, ∀(t, x) ∈ [0, T ) × R (6.1) v (k) (T, x) = φ(x), ∀x ∈ R (6.2)
where, φ (k) is introduced in (4.10) and for t ∈ [0, T ], x ∈ R, p ∈ R, M ∈ R the operator:

A(t, x, p, M ) := 1 2 σ 2 (t, x)M + b(t, x)p. (6.3)
For ϕ ∈ C 1,2 ([0, T ] × R) ∩ C 2 ([0, T ] × R), we define: B(t, x, ∂ϕ ∂x (t, x), ϕ) := R\{0} [ϕ(t, x + γ(t, x, z)) -ϕ(t, x) -γ(t, x, z) ∂ϕ ∂x (t, x)]m(dz), (6.4)
where

C 2 ([0, T ] × R) := {ϕ ∈ C 0 ([0, T ] × R)/ sup [0,T ]×R |ϕ(t, x)| 1 + |x| 2 < +∞}. Let us prove that B is well defined. For t ∈ [0, T ], x ∈ R, p ∈ R and ϕ ∈ C 1,2 ([0, T ] × R),
we can define:

B 1 (t, x, ϕ) := 0<|z|≤1 [ϕ(t, x + γ(t, x, z)) -ϕ(t, x) -γ(t, x, z) ∂ϕ ∂x (t, x)]m(dz).
This integral term can be written also:

B 1 (t, x, ϕ) = 0<|z|≤1 γ 2 (t, x, z) 1 0 (1 -y ∂ 2 ϕ ∂ 2 x (t, x + yγ(t, x, z))dym(dz).
From inequality (4.6) and the regularity of ϕ we obtain that the integrand of B 1 (t, x, ϕ) is bounded by C t,x ρ 2 (z). Then from assumption (4.3) we prove that B 1 is well defined. We define also for ϕ ∈ C 2 ([0, T ] × R):

B 1 (t, x, p, ϕ) := |z|≥1 [ϕ(t, x + γ(t, x, z)) -ϕ(t, x) -γ(t, x, z)p]m(dz).
The integrand of B 1 (t, x, p, ϕ) is bounded by C p,x (1 + |γ(t, x, z)| 2 ) and then from assumptions (4.2) on m and (4.6) on γ this integral term is convergent. We conclude that the integrodifferential operator B is well defined for all

ϕ ∈ C 1,2 ([0, T ] × R) ∩ C 2 ([0, T ] × R) and B(t, x, ∂ϕ ∂x (t, x), ϕ) = B 1 (t, x, ϕ) + B 1 (t, x, ∂ϕ ∂x (t, x), ϕ).
Let us give the definition of viscosity solution which is introduced by Crandall and Lions [START_REF] Crandall | Viscosity solutions of Hamilton-Jacobi equations[END_REF] for the first order equation, then generalized to the second order by Gimbert and Lions [START_REF] Gimbert | Existence and regularity results for solutions of second order integrodifferential operators[END_REF]. Definition 6.1 Let k = 1, ..., , and u (k) be a continuous function. (i) We say that u (k) is a viscosity supersolution (subsolution) of (6.1) if

min{rϕ(t 0 , x 0 ) - ∂ϕ ∂t (t 0 , x 0 )-A(t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ∂ 2 ϕ ∂x 2 (t 0 , x 0 )) -B(t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ϕ); ϕ(t 0 , x 0 ) -φ (k) (t 0 , x 0 )} ≥ 0 (6.5) (≤ 0) whenever ϕ ∈ C 1,2 ([0, T )×R)∩C 2 ([0, T ]×R) and u (k) -ϕ has a strict global minimum (maximum) at (t 0 , x 0 ) ∈ [0, T ) × R.
(ii) We say that u (k) is a viscosity solution of (6.1) if it is both super and subsolution of (6.1).

Theorem 6.1 For all k = 1, ..., , the value function v (k) is a viscosity solution of the HJBVI (6.1) on [0, T ) × R.

Proof. Viscosity supersolution:

Let ϕ ∈ C 1,2 ([0, T ) × R) ∩ C 2 ([0, T ] × R) and (t 0 , x 0 ) ∈ [0, T ) × R be a strict global minimum of ϕ such that 0 = (v (k) -ϕ)(t 0 , x 0 ) = min (t,x)∈[0,T )×R (v (k) -ϕ)(t, x). (6.6)
Let η > 0, we define the stopping time

θ := inf{t > t 0 : (t, X t 0 ,x 0 t ) / ∈ B η (t 0 , x 0 )} ∧ T where B η (t 0 , x 0 ) := {(t, x) ∈ [0, T ] × R such that |t -t 0 | + |x -x 0 | ≤ η}. (6.7)
Then from the Dynamic Programming Principle, it follows that

ϕ(t 0 , x 0 ) = v (k) (t 0 , x 0 ) ≥ E Q e -r(θ∧(t 0 +h)) ϕ(θ ∧ (t 0 + h), X t 0 ,x 0 θ∧(t 0 +h) ) . (6.8)
By applying Itô's Lemma to e -rs ϕ(s, X t 0 ,x 0 s ) and using inequality (6.8) we obtain

0 ≥ E Q 1 h θ∧(t 0 +h) t 0 e -rs (-rϕ(s, X t 0 ,x 0 s ) + ∂ϕ ∂s (s, X t 0 ,x 0 s ) + A(s, X t 0 ,x 0 s , ∂ϕ ∂x (s, X t 0 ,x 0 s ), ∂ 2 ϕ ∂x 2 (s, X t 0 ,x 0 s )) + B(s, X t 0 ,x 0 s , ∂ϕ ∂x (s, X t 0 ,x 0 s ), ϕ))ds ,
where A and B are defined by (6.3) and (6.4) respectively. Sending h to 0, we deduce by the mean value theorem that 1 h θ∧(t 0 +h)

t 0 e -rs ((-rϕ + ∂ϕ ∂s )(s, X t 0 ,x 0 s ) + A(s, X t 0 ,x 0 s , ∂ϕ ∂x (s, X t 0 ,x 0 s ), ∂ 2 ϕ ∂x 2 (s, X t 0 ,x 0 s )) + B(s, X t 0 ,x 0 s , ∂ϕ ∂x (s, X t 0 ,x 0 s ), ϕ))ds -→
e -rt 0 (-rϕ + ∂ϕ ∂s )(t 0 , x 0 ) + A t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ∂ 2 ϕ ∂x 2 (t 0 , x 0 ) + B t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ϕ .

Then it follows from assumption (4.2) and the dominated convergence theorem that

rϕ(t 0 , x 0 ) - ∂ϕ ∂s (t 0 , x 0 ) -A t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ∂ 2 ϕ ∂x 2 (t 0 , x 0 ) -B t 0 , x 0 , ∂ϕ ∂x (t 0 , x 0 ), ϕ ≥ 0, then v (k)
is a viscosity supersolution of (6.1).

Viscosity subsolution:

Let ϕ ∈ C 1,2 ([0, T ) × R) ∩ C 2 ([0, T ] × R), and (t 0 , x 0 ) ∈ [0, T ) × R such that 0 = (v (k) -ϕ)(t 0 , x 0 ) > (v (k) -ϕ)(t, x) for all (t, x) ∈ [0, T ) × R\{(t 0 , x 0 )}, (6.9)
then there exits η > 0 such that for all (t, x) /

∈ B η (t 0 , x 0 ) (v (k) -ϕ)(t, x) ≤ -ξ, (6.10)
where B η (t 0 , x 0 ) is defined in (6.7) and ξ > 0.

In order to prove the required result, we assume to the contrary that there exists ε > 0 such that for all (t, x) ∈ B η (t 0 , x 0 ) min{-∂ϕ ∂t (t, x) -Lϕ(t, x); ϕ(t, x) -φ (k) (t, x)} ≥ ε, (6.11) where Lϕ(t, x) := -rϕ(t, x) + A t, x, ∂ϕ ∂x (t, x), ∂ 2 ϕ ∂x 2 (t, x) + B t, x, ∂ϕ ∂x (t, x), ϕ .

Let us define the stopping times:

θ 1 k := inf{t > t 0 : (t, X t 0 ,x 0 t ) / ∈ B η (t 0 , x 0 )} ∧ T θ 2 k := inf{t > t 0 : φ (k) (t, X t 0 ,x 0 t ) = v (k) (t, X t 0 ,x 0 t )} ∧ T. On the set {θ 1 k ≤ θ 2 k }: We have that (θ 1 k , X t 0 ,x 0 θ 1 k ) / ∈ B η (t 0 , x 0 ), then by (6.10) we deduce that v (k) (θ 1 k , X t 0 ,x 0 θ 1 k ) + ξ ≤ ϕ(θ 1 k , X t 0 ,x 0 θ 1 k
). By applying Itô's Lemma to e -r(s-t 0 ) ϕ(s, X t 0 ,x 0 s ), we obtain

e -r(θ 1 k -t 0 ) (v (k) (θ 1 k , X t 0 ,x 0 θ 1 k ) + ξ) -v (k) (t 0 , x 0 ) ≤ θ 1 k t 0
e -r(s-t 0 ) ∂ϕ ∂s (s, X t 0 ,x 0 s ) + Lϕ(s, X t 0 ,x 0 s ) ds

+ θ 1 k t 0 e -r(s-t 0 ) σ(s, X t 0 ,x 0 s ) ∂ϕ ∂x (s, X t 0 ,x 0 s )dW s + θ 1 k t 0
e -r(s-t 0 ) R\{0} ϕ(s, X t 0 ,x 0 s - + γ(s, X t 0 ,x 0 s -, z)) -ϕ(s, X t 0 ,x 0 s -) ṽ(ds, dz). (6.12)

On the set {θ 1 k > θ 2 k }: We have that (θ 2 k , X t 0 ,x 0 θ 2 k
) ∈ B η (t 0 , x 0 ), so by (6.11) and by applying Itô's Lemma to e -r(s-t 0 ) ϕ(s, X t 0 ,x 0 s

) we obtain

e -r(θ 2 k -t 0 ) ε + φ (k) (θ 2 k , X t 0 ,x 0 θ 2 k ) -v (k) (t 0 , x 0 ) ≤ θ 2 k t 0
e -r(s-t 0 ) ∂ϕ ∂s (s, X t 0 ,x 0 s ) + Lϕ(s, X t 0 ,x 0 s ) ds

+ θ 2 k t 0 e -r(s-t 0 ) σ(s, X t 0 ,x 0 s ) ∂ϕ ∂x (s, X t 0 ,x 0 s )dW s + θ 2 k t 0 e -r(s-t 0 ) R\{0} [ϕ(s, X t 0 ,x 0 s - + γ(s, X t 0 ,x 0 s -, z)) -ϕ(s, X t 0 ,x 0 s -)]ṽ(ds, dz). (6.13)
Let us denote by θ k := θ 1 k ∧ θ 2 k , then using inequalities (6.11), (6.12) and (6.13) we obtain

εE Q e -r(θ 2 k -t 0 ) 1 {θ 1 k >θ 2 k } + E Q e -r(θ 1 k -t 0 ) v (k) (θ 1 k , X t 0 ,x 0 θ 1 k )1 {θ 1 k ≤θ 2 k } -v (k) (t 0 , x 0 ) + ξE Q e -r(θ 1 k -t 0 ) 1 {θ 1 k ≤θ 2 k } + E Q e -r(θ 2 k -t 0 ) φ (k) (θ 2 k , X t 0 ,x 0 θ 2 k )1 {θ 1 k >θ 2 k } ≤ -εE Q θ k t 0
e -r(s-t 0 ) ds < 0. (

Let us suppose that for all ξ > 0, we have that

H := ξE Q e -r(θ 1 k -t 0 ) 1 {θ 1 k ≤θ 2 k } + εE Q e -r(θ 2 k -t 0 ) 1 {θ 1 k >θ 2 k } ≤ ξ , (6.15) then 0 ≤ ξE Q e -r(θ 1 k -t 0 ) 1 {θ 1 k ≤θ 2 k } ≤ ξ .
By sending ξ to 0, we obtain that 1 {θ 1 k ≤θ 2 k } = 0 a.s., then θ 1 k > θ 2 k a.s. So we obtain that H = εE Q e -r(θ 2 k -t 0 ) ≤ ξ . By sending ξ to 0 we obtain that εE Q e -r(θ 2 k -t 0 ) ≤ 0, which is in contradiction with the fact that εE Q e -r(θ 2 k -t 0 ) > 0. We conclude then that there exists ξ > 0 such that H ≥ ξ . On the other hand, we have that {e -rt v (k) (t, X t 0 ,x 0 t ), t 0 ≤ t ≤ T } is a supermartingale, then by [16, Theorem D.9, p.355], the stopped supermartingale {e

-r(t∧θ 2 k ) v (k) (t ∧ θ 2 k , X t 0 ,x 0 t∧θ 2 k ), t 0 ≤ t ≤ T } is a martingale. From the growth condition on v (k) , the martingale {e -r(t∧θ 2 k ) v (k) (t ∧ θ 2 k , X t 0 ,x 0 t∧θ 2 k ), t 0 ≤ t ≤ T } is bounded in L 1 (
Q) and so uniformly integrable. By Doob's optional Stopping Theorem (see [START_REF] Protter | Stochastic integration and differential equations[END_REF]Theorem 18,p.10]), we obtain that

e -rt 0 v (k) (t 0 , x 0 ) = E Q e -r(t∧θ k ) v (k) (t ∧ θ k , X t 0 ,x 0 t∧θ k ) ∀t ∈ S t 0 , (6.16)
and so

v (k) (t 0 , x 0 ) = E Q e -r(θ 1 k -t 0 ) v (k) (θ 1 k , X t 0 ,x 0 θ 1 k )1 {θ 1 k ≤θ 2 k } + E Q e -r(θ 2 k -t 0 ) φ (k) (θ 2 k , X t 0 ,x 0 θ 2 k )1 {θ 1 k >θ 2 k } . (6.17)
From inequality (6.14) and the fact that H ≥ ξ , we deduce that ξ ≤ 0, which contradicts the fact that ξ > 0.

We conclude then that the value function v (k) is a viscosity subsolution of the equation (6.1) on [0, T ) × R. 2

The last theorem prove the uniqueness of viscosity solutions.

Theorem 6.2 (Comparison Theorem)

Assume that the assumptions (4.2), (4.4), (4.7) and the Lipschitz continuity of φ hold. Let u (k) (resp. v (k) ), k = 1, ..., , be a viscosity subsolution (resp. supersolution) of (6.1). Assume also that u (k) and v (k) are Lipschitz, have a linear growth in x and holder in t. If

u (k) (T, x) ≤ v (k) (T, x) ∀x ∈ R, (6.18)
then

u (k) (t, x) ≤ v (k) (t, x) ∀(t, x) ∈ [0, T ] × R. (6.19)
The proof is similar to the one given by Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF]. In our case we need to use an induction argument.

Conclusion

In this paper we generalized the results of Carmona and Touzi from continuous to right continuous and left continuous in expectation processes. In the second part we characterized the value function of the multiple stopping problem for a jump diffusion process as the unique viscosity solution of a sequence of HJBVI.

We can solve numerically the sequence of the HJBVI by using a discrete time scheme and the quantization method to compute the conditional expectations appearing in this scheme. The convergence of such scheme could be achieved by using viscosity solution arguments. This work is postponed in a further research. Theorem 8.2 Let X be a right continuous, nonnegative, bounded, adapted and LCE. Let Y be the Snell envelope of X, i.e. the smallest right continuous supermartingale wich dominate X, it is defined by

Y t := ess sup u∈St E[X u |F t ]a.s. (8.1)
The stopping time D t := inf{u ≥ t, X u = Y u a.s.} is an optimal stopping time of (8.1), i.e. It remains to show the reverse inequality. This will be done in two steps. For ease of notation, we denote by

Y t := ess sup u∈St E[X u |F t ] = E[X Dt |F t ]
U λ t := E Y D λ t |F t .
Step 1: Let us prove that (U λ τ , τ ∈ S) is a supermartingale. Fix τ, τ ∈ S such that τ ≥ τ a.s., we have that E U The proof of step 2 is complete. By step 1 and the supermartingale property of Y we obtain that {λY τ + (1 -λ)U λ τ , τ ∈ S} is a supermartingale. By step 2, it dominates {X τ , τ ∈ S}. Consequently, by the characterization of Y as the smallest supermartingale which dominates X, we have

λY τ + (1 -λ)U λ τ ≥ Y τ a.

Remark 2 . 1 ≥ 1 ,

 211 Notice that Assumption (2.2) guaranties the finiteness of Z will also be finite.

  3.14) is true for i + 1. We conclude then that(3.14) is true for all 0 ≤ i ≤ . B) Now using (3.14) with i = , the definition of Y ( ) 0 and Theorem 3.1, we can see that:

. 21 )

 21 By Theorem 3.1 and equation (2.6) we have that for all i = 1, ..., -1

. 23 ) 2 4

 232 By the definition of Z ( )0 we have that E[X τ * 1 + ... + X τ * ] ≤ Z ( )0 , which joined to inequality (3.23) prove the optimality of the stopping times vector (τ * 1 , ..., τ * ) for the problem Z Swing Options in the jump diffusion Model

2 :

 2 λ τ |F τ = E E Y D λ τ |F D λ τ |F τ = E Y D λ τ |F τ a.s. From the right continuity of X and Y we have that A λ t is nonincreasing then D λ τ ≥ D λ τ a.s. Since (Y t ) is a supermartingale then E Y D λ τ F D λ τ ≤ Y D λ τ a.s. Consequently, E U λ τ |F τ ≤ E Y D λ τ |F τ = U λ τ a.s; which ends the proof of step 1.Step Let us show that for each τ ∈ S and each λ ∈ (0, 1),λY τ + (1 -λ)U λ τ ≥ X τ a.s.Fix τ ∈ S and λ ∈ (0, 1). We have that onB := {X τ ≥ λY τ }, D λ τ = τ a.s., then U λ τ := E Y D λ τ |F τ = E [Y τ |F τ ] = Y τ a.s. on B.This implies the inequalityλY τ + (1 -λ)U λ τ = Y τ ≥ X τ a.s. on B. (8.4) Furthermore, since B c := {X τ < λY τ } and since U λ τ is nonnegative, then λY τ + (1 -λ)U λ τ ≥ λY τ ≥ X τ a.s. on B c . (8.5)

  a.s..To prove this Theorem we need to the following Theorem and Proposition. Let (X t ) t be a nonnegative right continuous supermartingale. If σ, τ are stopping times with σ ≤ τ , we have E[X τ |F σ ] ≤ X σ a.s.

	Theorem 8.3 Then,
	∀ t ∈ S, Y t = E Y D λ t	|F t a.s.	(8.2)
	Proof. Since X is a supermartingale and since D λ t ≥ t a.s. then we have
	E Y D λ t	|F t ≤ Y t a.s.	(8.3)

Proposition 8.1 For all λ ∈ (0, 1), let A λ be the set A λ t := {(ω, s); s ≥ t, X s (ω) ≥ λY s (ω)}, and D λ t the first time of A λ greater than t, i.e. D λ t := inf{s ≥ t; X s ≥ λY s }.

  s.(8.6) Hence, U λ τ ≥ Y τ a.s. (note that the strict inequality λ < 1 is necessary here). We conclude that for each τ ∈ S, E Y D λ τ |F τ := U λ τ = Y τ a.s. 2Let us now prove Theorem 8.2. Proof. Let (λ n ) be a nondecreasing sequence of reals valued in (0, 1), such that lim n→∞ λ n = 1. It is clear that the sets A λn t are nonincreasing and D λn t are nondecreasing. Since the map λ → D λ t is nondecreasing on (0, 1), the random variable Dt defined by Dt := lim is a stopping time. Let us prove that it is an optimal stopping time of (8.1), i.e.Y t := ess sup u∈St E[X u |F t ] = E[X Dt |F t ] a.s. Since X and Y are right continuous then D λn t ∈ A λn t , i.e. X D λn Dt |F t ]]. Since Y t ≥ E[X Dt |F t ] a.s., the last equality gives Y t = E[X Dt |F t ] a.s. which prove the optimality of Dt . It is clear that Dt ≤ D t , since for all n we have {u ≥ t; X u = Y u } ⊂ A λn and hence Dt ≤ D t . Let us prove that Dt ≥ D t . Since Dt is an optimal stopping time, then E X Dt = E[Y t ]. On the other hand, using Y ≥ X and applying Theorem 8.3 to the supermartingale Y we obtain that E X Dt≤ E Y Dt ≤ E[Y t ]. Therefore, E Y Dt = E X Dt . Since Y Dt ≥ X Dt then Y Dt = X Dt a.s., so Dt ≥ D t . We conclude that D t := inf{u ≥ t, X u = Y u } is an optimal stopping time of (8.1).2Proposition 8.2 Let τ * be an optimal stopping time of (8.1), then the stopped processY τ * defined by Y τ * s = Y τ * ∧s , t ≤ s ≤ T is aP-(F) t martingale.Proof. We have that τ * is an optimal stopping time of (8.1) then Y t = E[X τ * |F t ] a.s. and hence E[Y t ] = E[X τ * ]. On the other hand, using Y ≥ X and the supermartingale property of Y , we have E[X τ * ] ≤ E[Y τ * ] ≤ E[Y t ]. Therefore, [t, T ]. So we have that for all t ≤ u ≤ u ≤ T , E[Y τ * ∧u ] = E[Y τ * ∧u ]. From the supermartingale property of Y , we have that E[Y τ * ∧u |F u ] ≤ Y τ * ∧u a.s., this inequality together with the last equality is equivalent to Y τ * ∧u = E[Y τ * ∧u |F u ] a.s. We obtain then the desired result. 2

		n→∞	D λn t
	1 λ n	E X D λn

t ≥ λ n Y D λn t . Hence using Proposition 8.1, we obtain Y t = E Y D λn t |F t ≤ 1 λ n E X D λn t |F t a.s. and so E[Y t ] ≤ t . Passing to the limit as n tends to ∞ and using the fact that X is LCE we get E[Y t ] ≤ E[X Dt ] and hence E[Y t ] = E[X Dt ] = E[E[X t then D λn t ≤ D t E[Y τ * ] = E[Y t ]. (8.7) From the supermartingale property of Y we have that for all s ∈ [t, T ], E[Y τ * ] ≤ E[Y τ * ∧s ] and E[Y t ] ≥ E[Y τ * ∧s ]. Using equality (8.7) we obtain that E[Y t ] = E[Y τ * ∧s ] for all s ∈

We recall the classical following theorem (see for example Karatzas Shreve (1998)). Theorem 8.1 (Essential supremum) Let (Ω, F, P) be a probability space and let X be a non empty family of nonnegative random variables defined on (Ω, F, P). Then there exists a random variable X * satisfying 1. for all X ∈ X , X ≤ X * a.s. , 2. if Y is a random variable satisfying X ≤ Y a.s. for all X ∈ X , then X * ≤ Y a.s.. This random variable, which is unique a.s., is called the essential supremum of X and is denoted ess sup X∈X X. Furthermore, if X is closed under pairwise maximization (that is:

Proof. Let X 1 and X 2 two processes such that

We obtain then in addition to the Lipschitz continuity and the linear growth condition in x of b, σ and γ that

From Lemma 3.1 of Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF] and assumption (4.2), we deduce that

We obtain then in addition to the linear growth conditions in x of b, σ and γ that

From Lemma 3.1 of Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF] and assumption (4.2), we deduce that

We deduce then that in both cases we have that

Then by Fubini's theorem and by Gronwall's lemma we deduce that

We recall the theorem 2.18 of El Karoui [START_REF] Karoui | Les aspects probabilistes du controle stochastique[END_REF].


Imène Ben Latifa
email: benlatifa@cmap.polytechnique.fr

Joseph Frédéric Bonnans

Mohamed Mnif
email: mohamed.mnif@enit.rnu.tn

Numerical methods for an optimal multiple stopping problem

Keywords: quantization, Swing option, optimal multiple stopping time problem

This paper deals with numerical solutions to an optimal multiple stopping problem. The corresponding dynamic programming (DP) equation is a variational inequality satisfied by the value function in the viscosity sense. The convergence of the numerical scheme is shown by viscosity arguments. An optimal quantization method is used for computing the conditional expectations arising in the DP equation. Numerical results are presented for the price of swing option and the behavior of the value function.

Introduction

In their paper, Carmona and Touzi presented and implemented a numerical method to solve an optimal multiple stopping time problem by using Malliavin calculus to compute the conditional expectation arising in the DP equation and the Monte Carlo method. In this work we use the optimal quantization method and we prove the convergence of our numerical scheme to the unique viscosity solution of the associated Hamilton-Jacobi-Bellman Variational Inequality (HJBVI in short).

Optimal quantization has been developed in the 50s in the field of Signal Processing. Its main purpose consists in approximating a continuous signal by a discrete one on an optimal way. In the 90s, its application has been extended to the field of Numerical Integration to compute some integral estimations by using finite weighted sums. And in the early 2000s, this method has been applied to the field of Numerical Probabilities and Financial Mathematics. This extension has been motivated by the necessity of designing efficient methodologies for pricing and hedging more and more sophisticated financial products. Indeed optimal quantization brought a natural answer to the conditional expectation computations appearing in these financial models (see for example Guilbaud et al. [START_REF] Guilbaud | Numerical methods for an optimal order execution problem[END_REF] for numerical methods for an optimal order execution problem). Given a random variable X, a quantization algorithm should provide a finite grid G and the quantized approximation of X is then defined by the closest-neighbor projection of X onto G. One of the main challenges is to compute the optimal grid ensuring that the distance between X and its quantized approximation is minimal for a L p norm. There already exist algorithms for such purposes such as Lloyd's Method and the competitive learning vector quantization procedure [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF][START_REF] Gray | Quantization[END_REF][START_REF] Pagès | Optimal quantization methods and applications to numerical problems in finance[END_REF]. We fix the option maturity time T ∈ (0, ∞), i.e. the time of expiration of our right to stop the process or exercise. Let (Ω, F, P) be a complete probability space modeling the randomness of the market, with a filtration F = {F t } 0≤t≤T satisfying the usual conditions, i.e. an increasing right continuous family of sub-σ-algebras of F such that F 0 contains all the P-null sets. We consider that the state process (X t ) t∈[0,T ] follows the SDE:

dX t = b(X t )dt + c(X t )dW t , X 0 = x ∈ R d , (1.1)
where W denotes a d-dimensional Brownian motion defined on the probability space (Ω, F, P), b : R d → R d and c : R d → M(d, q) are Lipschitz continuous, where M(d, q) denotes the set of matrix with d rows and q columns. The value function of the swing option problem with exercise rights and refraction time δ > 0 is given by:

v ( ) (x) = sup (τ 1 ,...,τ )∈ S ( ) 0 E Q i=1 e -rτ i φ(X 0,x τ i ) , (1.2)
where φ : R d -→ R + is a Lipschitz payoff function with linear growth, and S ( ) 0 := (τ 1 , ..., τ ) ∈ S 0 , τ 1 ∈ S 0 , τ i -τ i-1 ≥ δ on {τ i-1 + δ ≤ T } a.s, τ i = (T + ) on {τ i-1 + δ > T } a.s, ∀ i = 2, ..., . ,

where S 0 is the set of stopping times taking values in [0, T ].

The optimal multiple stopping time problem (1.2) can be seen as sequential ordinary optimal stopping problems. It is known that the solution of each ordinary problem is the unique viscosity solution of the HJBVI

min{rv (k) (t, x)- ∂v (k) ∂t (t, x) -Lv (k) (t, x); v (k) (t, x) -φ v (k-1) (t, x)} = 0, ∀(t, x) ∈ [0, T ) × R d (1.4) v (k) (T, x) = φ(x) ∀x ∈ R d , (1.5)
where φ : R d -→ R + is a Lipschitz payoff function, k = 1, ..., ,

Lv (k) (t, x) := 1 2 d i=1 d j=1 c(t, x)c T (t, x) i,j ∂ 2 v (k) ∂x i ∂x j (t, x) + d i=1 b i (t, x) ∂v (k) ∂x i (t, x) and φ v (k-1) (t, x) = φ(x) + e -rδ E v (k-1) (t + δ, X t,x t+δ ) , ∀ 0 ≤ t ≤ T -δ (1.6)
φ v (k-1) (t, x) = φ(x), ∀ T -δ < t ≤ T.
We refer to [START_REF] Ben Latifa | A general optimal multiple stopping problem with an application to Swing Options[END_REF] in the jump diffusion case. We recall the definition of the viscosity solution.

Definition 1.1 Let k = 1, ..., , and u (k) be a continuous function.

(i) We say that u (k) is a viscosity super-solution (sub-solution) of (1.4)-(1.5) if

min{rψ(t 0 , x 0 ) - ∂ψ ∂t (t 0 , x 0 ) -Lψ(t 0 , x 0 ); ψ(t 0 , x 0 ) -φ (k) (t 0 , x 0 )} ≥ 0 (1.7) (≤ 0) whenever ψ ∈ C 1,2 ([0, T )×R)∩C 2 ([0, T ]×R) and u (k) -ψ has a strict global minimum (maximum) at (t 0 , x 0 ) ∈ [0, T ) × R. (ii) We say that u (k) is a viscosity solution of (1.4)-(1.5) if it is both super and sub-solution of (1.4)-(1.5).
Where

C 2 ([0, T ] × R) := {ψ ∈ C 0 ([0, T ] × R)/ sup [0,T ]×R |ψ(t, x)| 1 + |x| 2 < +∞}.
The optimal quantization method is used for pricing an American option in a continuoustime Markov process, which consists in solving a standard optimal stopping problem (see Bally et al. [START_REF] Bally | A quantization tree method for pricing and hedging multidimensional American options[END_REF]). In this paper we extend their result for a multiple stopping time problem. We estimate the price of a swing option expiring at time T , with rights of exercise when the price process is solution of (1.1). The exact simulation of the diffusion at time t is not possible. We use the Markovian discretization scheme, e.g. the Euler scheme:

X t n+1 = X tn + b(X tn ) T M + c(X tn )(W t n+1 -W tn ), 0 ≤ n ≤ M -1, (1.8)
where M is a positive integer and t n := nT /M . We approximate the Snell envelope by quantization of the Euler scheme (1.8). Using Zador's Theorem we prove the convergence of our algorithm.

In one dimensional case, we consider that the price process X = (X t ) 0≤t≤T satisfies the following stochastic differential equation (SDE)

dX t = rX t dt + σX t dW t , X 0 = x > 0, (1.9)
where W denotes a one-dimensional Brownian motion defined on the probability space (Ω, F, P), r > 0 and σ ∈ R. The filtration considered here is the natural filtration of the Brownian motion completed by the P-null sets. It is known that there exists a unique strong solution for the SDE, X t = xe (r-σ 2 2 )t+σWt . So it suffices to consider a quantization of the Brownian motion itself.

The paper is organized as follows. In section 2, we recall some basic facts about optimal quantization. In section 3, we present our numerical scheme on general multidimensional diffusion process and we prove, for some assumptions on b and c, the convergence of our

algorithm with rate O M 1+ 1 d N 1 d
, where N := N 0 + ... + N M (N n is the size of Xn , the optimal discretization of X n ). In section 4, we present our numerical scheme on the specific one-dimensional linear setting and we prove that our scheme is monotonous, stable and consistent and consequently, it converges to the solution of our optimal multiple stopping time problem. In section 5, we present some numerical results on one-dimensional linear setting which are similar to those of Carmona and Touzi [START_REF] Carmona | Optimal Multiple Stopping and valuation of Swing Options[END_REF], we discuss the complexity of the algorithm and we end by a comparison of our method with the finite difference one.

Background on optimal quantization

We begin with a brief introduction to optimal quantization of random variable [START_REF] Bally | A quantization tree method for pricing and hedging multidimensional American options[END_REF] (see Graf and Luschgy [8] for an overview). Let (Ω, F, P) be a probability space and let X be a random variable with distribution P X . Assume that X ∈ L p , optimal L p mean quantization (p > 1) with level N consists in studying the best L p approximation of X by some random variable X = q(X), where q : R d → R d is a Borel function taking at most N values. We associate to every Borel function q(X) taking at most N values, the L p -mean quantization error X -q(X) p measuring the distance between the two random vectors X and q(X) w.r.t. the mean L p -norm, where X p := (E|X| p ) 1/p and |.| denotes an arbitrary norm on R d . Minimizing the L p mean quantization error, X -q(X) p , can be decomposed into two successive phases:

1. Let Γ = (x 1 , ..., x N ) ∈ (R d ) N , find a quantizer q Γ : R d → x 1 , ..., x N such that X -q Γ (X) p = inf{ X -q(X) p , q : R d → x 1 , ..., x N , Borel function}. (2.1) 2. Find an N -tuple Γ * ∈ (R d ) N that achieves the infimum of X -XΓ p over (R d ) N , that is X -XΓ * p = inf{ X -XΓ p , Γ ∈ (R d ) N },
where XΓ = q Γ (X) and

X -XΓ p p = N i=1 E 1 C i (Γ) |X -x i | p = E min 1≤i≤N |X -x i | p = R d min 1≤i≤N |x i -y| p P X (dy). (2.2)
The solution of the first optimization problem, denoted q Γ , is the closest neighbor projections induced by the Voronoi tessellations of u as defined below.

Definition 2.1 (i) Let Γ = (x 1 , ..., x N ) ∈ (R d ) N . A Borel partition C i (Γ), i = 1, ..., N , of R d is a Voronoi tessellation of u if for every i ∈ 1, ..., N , C i (Γ) satisfies C i (Γ) ⊂ {y ∈ R d , |x i -y| = min 1≤j≤N |x j -y|}.
(ii) The closest neighbor projection or Voronoi quantizer (function) q Γ induced by the Voronoi tessellation (C i (Γ)) 1≤i≤N is defined, for every y ∈ R d , by q Γ (y) = 1≤i≤N

x i 1 C i (Γ) (y).

(iii) The random variable

XΓ = q Γ (X) = 1≤i≤N x i 1 C i (Γ) (X)
is called a Voronoi quantization of X. The N -tuple Γ is often called an N -quantizer.

One shows (see [START_REF] Bally | A quantization tree method for pricing and hedging multidimensional American options[END_REF]) that the solution of the second problem (2.1) is given by

X -XΓ * p = min{ X -Z p , Z : Ω → R d , random variable , |Z(Ω)| ≤ N },
and XΓ * is called an optimal quantizer of X. We can see that when the grids are optimal (in the quadratic quantization sense), the spatial order of convergence is better then that obtained with usual grid methods. Zador's Theorem (see [7], [START_REF] Bucklew | Multidimensional Asymptotic Quantization Theory with r th Power Distortion Measures[END_REF] and [START_REF] Graf | Foundations of quantization for probability distributions[END_REF]) says that

X -Xx * p = C X,p N -1/d + o(N -1/d ).
3 Multi-dimentional diffusion process

First, let us give some notations that will be used throughout this paper. Notations:

• |.| will denote the canonical Euclidean norm on R d .

• M(d, q) will denote the set of matrix with d rows and q columns.

• For every matrix A ∈ M(d, q), set A 2 := T r(AA * ) (which corresponds to its Euclidean norm as an element of R d×q ).

• For a Lipschitz continuous function f , [f ] Lip denotes the Lipschitz constant of φ : R d → R.

The process X is the diffusion process solution of the stochastic differential equation

X t = x + t 0 b(X s )ds + t 0 c(X s )dW s , x ∈ R d (3.1)
where b : R d → R d and c : R d → M(d, q) are Lipschitz continuous, there exists a positive constant C Lip such that

c(x) -c(x ) + |b(x) -b(x )| ≤ C Lip |x -x |, ∀(x, x ) ∈ R d × R d . (3.2)
Note that b and c have at most linear growth. We will assume that this real constant C Lip also satisfies

c(x) + |b(x)| ≤ C Lip (1 + |x|), ∀x ∈ R d . (3.3)
It is known that for all p ≥ 1, there exists a positive constant C p,T such that

E sup t∈[0,T ] |X t | p ≤ C p,T (1 + |x| p )
Let us define the following HJBVI

min{rv (k) (t, x)- ∂v (k) ∂t (t, x) -Lv (k) (t, x); v (k) (t, x) -φ v (k-1) (t, x)} = 0, ∀(t, x) ∈ [0, T ) × R d (3.4) v (k) (T, x) = φ(x) ∀x ∈ R d , (3.5)
where φ : R d -→ R + is a Lipschitz payoff function, k = 1, ..., ,

Lv (k) (t, x) := 1 2 d i=1 d j=1 c(t, x)c T (t, x) i,j ∂ 2 v (k) ∂x i ∂x j (t, x) + d i=1 b i (t, x) ∂v (k) ∂x i (t, x) and φ v (k-1) (t, x) = φ(x) + e -rδ E v (k-1) (t + δ, X t,x t+δ ) , ∀ 0 ≤ t ≤ T -δ (3.6) φ v (k-1) (t, x) = φ(x), ∀ T -δ < t ≤ T.
Assume that v (0) = 0 and for all t > T , v (k) (t, X t ) = 0. For k = 1, ..., , we have that the solution of the following stopping time problem

v (k) (t, x) = ess sup τ ∈ St E e -r(τ -t) φ v (k-1) (τ, X τ )|X t = x , (3.7)
is the viscosity solution of the HJBVI (3.4)- (3.5), where S t := {τ ∈ S 0 ; t ≤ τ ≤ T } for every t ∈ S 0 .

Numerical scheme

Time discretization consists in approximating the continuous time diffusion (X t ) t∈[0,T ] by the following Euler scheme. Set t n := nT /M , where M ≥ 1 is an integer, the Euler scheme is defined by

Xt n+1 = Xtn + b( Xtn ) T M + c( Xtn )(W t n+1 -W tn ), X0 = x. (3.8)
We denote by P n,i the transition from Xn to Xn+i ,

P n,i (v)(x) := E[v( Xn+i )| Xn = x],
where v is a function from R d to R. We have that the transition P n,i is Lipschitz in the following sense: for every Lipschitz continuous function f :

R d → R [P n,i f ] Lip (1 + C b,c,T T /M )[f ] Lip , (3.9)
where C b,c,T is a positive constant depending on b, c and T , (see, e.g., [START_REF] Bally | A quantization algorithm for solving multidimensional discrete-time optimal stopping problems[END_REF] for a proof).

For k = 1, ..., , n = 0, ..., M , let

V (k) n
the solution of

V (k) n = ess sup τ ∈ Θn E e -r(τ -tn) φ V (k-1) (τ, Xτ )|F tn , (3.10)
where Θ n denotes the set of {t n , ..., t M }-valued (F tu ) u∈{n,...,M } stopping times. It satisfies the so-called backward programming formula (see [START_REF] Neveu | Martingales à temps discret[END_REF]):

V (k) M := φ( XM ), V (k) n := max{e -rh E[V (k) n+1 |F tn ], φ V (k-1) n ( Xn )}, 0 ≤ n ≤ M -1, (3.11)
where

φ V (k-1) n ( Xn ) = φ( Xn ) + e -rδ E[V (k-1) n+i 0 |F tn ], 0 ≤ n ≤ M -i 0 , φ V (k-1) n ( Xn ) = φ( Xn ), M -i 0 < n ≤ M -1.
i 0 is an integer such that δ = i 0 T /M . Using the Markov property, we derive a dynamic programming formula in distribution:

for k = 1, ..., , V (k) n = v (k) n ( Xn ), n ∈ {0, ..., M }, where the function v (k) n is solution of v (k) M := φ, v (k) n := max{e -rh P n,1 (v (k) n+1 ), φ v (k-1) n }, 0 ≤ n ≤ M -1, (3.12)
where for x ∈ R d ,

φ v (k-1) n (x) = φ(x) + e -rδ E[v (k-1) n+i 0 |X n = x], 0 ≤ n ≤ M -i 0 , φ v (k-1) n (x) = φ(x), M -i 0 < n ≤ M.
We assume that v

[v (k) n ] Lip ≤ C[φ] Lip .
Proof. We will prove this proposition by induction in k.

For k = 1, we have that v

(1)

M = φ, then v (1)
M is Lipschitz continuous function and [v

M ] Lip = [φ] Lip . Using the inequality | max(a, b) -max(c, d)| ≤ max(|a -c|, |b -d|), one concludes by induction in n that, for n = 0, ..., M , v (1)
n is Lipschitz continuous function and [v (1) n ] Lip ≤ C[φ] Lip . Let 1 ≤ k ≤ -1, assume that for n = 0, ..., M , v (k) n is Lipschitz continuous function with [v (k) n ] Lip ≤ C[φ] (1)
Lip and let us prove that it is also for v (k+1) n .

For n = M , we have that v

(k+1) M = φ, then v (k+1) M is Lipschitz continuous function and [v (k+1) M ] Lip = [φ] Lip . Let M -i 0 + 1 ≤ n ≤ M , assume that v (k+1) n+1 is Lipschitz continuous function with [v (k+1) n+1 ] Lip ≤ C[φ] Lip and let us prove that it is also for v (k+1) n . Using the Lipschitz property of P n,1 , we have that for x, y ∈ R d |v (k+1) n (x) -v (k+1) n (y)| ≤ max{[φ] Lip , C[v (k+1) n+1 ] Lip }|x -y| ≤ C[φ] Lip |x -y|. Then, for M -i 0 + 1 ≤ n ≤ M , v (k+1) n is Lipschitz continuous function with [v (k+1) n ] Lip ≤ C[φ] Lip . Now, let 0 ≤ n ≤ M -i 0 , assume that v (k+1) n+1 is Lipschitz continuous function with [v (k+1) n+1 ] Lip ≤ C[φ]
Lip and let us prove that it is also for v (k+1) n

. Using the Lipschitz property of P n,1 and P n,i 0 , we have that for

x, y ∈ R d |v (k+1) n (x) -v (k+1) n (y)| ≤ max{([φ] Lip + C[v (k) n+i 0 ] Lip ), C[v (k+1) n+1 ] Lip }|x -y| ≤ C[φ] Lip |x -y|.
We conclude that for k = 1, ..., and n = M, ..., 0, v

(k) n is Lipschitz continuous function with [v (k) n ] Lip ≤ C[φ] Lip . 2
Now we discretize the random variable Xtn by some σ( Xtn )-random variable Xn taking finitely many values in R d . Xn is the optimal quantization of Xtn . Let N := N 0 + ... + N M denote the total number of elementary quantizers used to quantize the whole Markov chain ( Xtn ) 0≤n≤M . We denote by {x n 1 , ..., x n Nn } = q n (R d ) the grid of N n points used to quantize Xtn , and by x n := (x n 1 , ..., x n Nn ) the induced N n -tuple. Note that X0 = x, so that X0 = x is the best possible L p -mean quantization of X0 and N 0 = 1. We replace Xn in (3.11) by its quantized random vector Xn and we obtain the quantized dynamic programming formula

V (k) M = φ( XM ), V (k) n = max{e -rh E[ V (k) n+1 | Xn ], φ V (k-1) n ( Xn )}, 0 ≤ n ≤ M -1, (3.13)
where

φ V (k-1) n ( Xn ) = φ( Xn ) + e -rδ E[ V (k-1) n+i 0 | Xn ], 0 ≤ n ≤ M -i 0 , φ V (k-1) n ( Xn ) = φ( Xn ), M -i 0 < n ≤ M.
V (k) n ≡ V (k) n ≡ 0 for n > M . We define the function v(k) n by        v(k) M (x M i ) = φ(x M i ), ∀i ∈ {1, ..., N M } v(k) n (x n i ) = max{e -rh N n+1 j=1 π n,1 ij v(k) n+1 (x n+1 j ), φ N v(k-1) (t n , x n i )}, 1 ≤ i ≤ N n , 0 ≤ n ≤ M -1, (3.14)
where

φ N v(k-1) (t n , x n i ) = φ(x n i ) + e -rδ N n+i 0 j=1 π n,i 0 ij v(k-1) n+i 0 (x n+i 0 j ), 1 ≤ i ≤ N n , 0 ≤ n ≤ M -i 0 , φ N v(k-1) (t n , x n i ) = φ(x n i ), 1 ≤ i ≤ N n , M -i 0 < n ≤ M,
and for m ∈ {1, i 0 }, i = 1, ..., N n , j = 1, ..., N n+1 , n = 0, ..., M -m π n,m ij :=P( Xn+m = x n+m j | Xn = x n i ) = P( Xn+m ∈ C j (x n+m )| Xn ∈ C i (x n )) = p n,m ij p m i with p n,m ij := P( Xn+m ∈ C j (x n+m ), Xn ∈ C i (x n )) and p m i := P( Xn ∈ C i (x n )).
Assume that v(0) ≡ 0. We can see that

V (k) n = v(k) n ( Xn ).
Let us now move to the convergence of our method.

Convergence of the quantization method

In this paragraph we show some a priori L p -error bounds for

V (k) n - V (k) n p , k = 1, .
.., and n = 0, ..., M , based on the L p -mean quantization errors Xn -Xn p , n = 0, ..., M .

Theorem 3.1 Let ( V (k) n ) 0≤n≤M and (V (k) n ) 0≤n≤M , k = 1, .
.., , be like in (3.11) and (3.13) respectively. For every n = 0, ..., M , let Xn denote the quantization of Xn . Then, for every p ≥ 1 there exists a real positive constant C such that

V (k) n -V (k) n p ≤ C M i=n Xi -Xi p . (3.15)
Proof. For k = 1, ..., , n = 0, ..., M and j a strictly positive integer, set ψ

(k) n,j := P n,j (v (k) n+j ). This function satisfies E[v (k) n+j ( Xn+j )|F tn ] = E n [v (k) n+j ( Xn+j )] = ψ (k) n,j ( Xn ).
It is known from inequality (3.9) that ψ

(k) n,j is Lipschitz continuous function and [ψ (k) n,j ] Lip ≤ C[v (k) n+j ] Lip . We similarly define ψ(k) n,j by the equality ψ(k) n,j ( Xn ) := Ên [v (k) n+j ( Xn+j )]. First step: For k = 1.
For n = M we have that V

(1)

M = φ, then V (1) M is Lipschitz continuous function and [V (1) M ] Lip = [φ] Lip .
For n = 0, ..., M , |V (1) n -

V (1) n | ≤|φ( Xn ) -φ( Xn )| + |ψ (1) n,1 ( Xn ) - ψ(1) n,1 ( Xn )| ≤[φ] Lip | Xn -Xn | + |ψ (1) n,1 ( Xn ) -Ên [ψ (1) n,1 ( Xn )]| + | Ên [ψ (1) n,1 ( Xn )] - ψ(1) n,1 ( Xn )| (3.16)
On the other hand, we have

|ψ (1) n,1 ( Xn ) -Ên [ψ (1) n,1 ( Xn )]| ≤|ψ (1) n,1 ( Xn ) -ψ (1) n,1 ( Xn )| + Ên |ψ (1) n,1 ( Xn ) -ψ (1) n,1 ( Xn )| ≤ C[v (1) n+1 ] Lip (| Xn -Xn | + Ên | Xn -Xn |), then ψ (1) n,1 ( Xn ) -Ên [ψ (1) n,1 ( Xn )] p ≤ C[v (1) n+1 ] Lip Xn -Xn p .
(3.17) By using the tower property of the conditional expectation and since Xn is σ( Xn )measurable, we have

Ên [ψ (1) n,1 ( Xn )] - ψ(1) n,1 ( Xn ) = Ên [E n [v (1) n+1 ( Xn+1 )]] -Ên [v (1) n+1 ( Xn+1 )] = Ên [v (1) n+1 ( Xn+1 ) - v(1) n+1 ( Xn+1 )].
Then,

Ên [ψ (1) n,1 ( Xn )] - ψ(1) n,1 ( Xn ) p ≤ V (1) n+1 - V (1) n+1 p . (3.18)
Finally, it follows from the above inequalities and (3.16) that for n ∈ {0, ..., M }

V (1) n -V (1) n p ≤([φ] Lip + C[v (1) n+1 ] Lip ) Xn -Xn p + V (1) n+1 - V (1) n+1 p ≤C[φ] Lip Xn -Xn p + V (1) n+1 - V (1) n+1 p .
The last inequality is deduced from v

n+1 . On the other hand, V

M - V (1) M p ≤ [φ] Lip Xn -Xn p , so that V (1) n -V (1) n p ≤ C[φ] Lip M i=n Xi -Xi p . Second step: Let 1 ≤ k ≤ -1, assume that V (k) n -V (k) n p ≤ C[φ] Lip M i=n Xi -Xi p , (1)
and let us prove that it is true for k + 1.

We have that V

(k+1) M = φ, then V (k+1) M is Lipschitz continuous function and [V (k+1) M ] Lip = [φ] Lip .
For n = M, ..., 0, we have

|V (k+1) n -V (k+1) n | ≤ |ψ (k+1) n,1 ( Xn ) - ψ(k+1) n,1 ( Xn )| + |φ V (k) n ( Xn ) -φ V (k) n ( Xn )|. (3.19)
As it is done in the first step, we obtain that

ψ (k+1) n,1 ( Xn ) - ψ(k+1) n,1 ( Xn ) p ≤C[ψ (k+1) n,1 ] Lip Xn -Xn p + V (k+1) n+1 - V (k+1) n+1 p ≤C[φ] Lip Xn -Xn p + V (k+1) n+1 - V (k+1) n+1 p . (3.20)
According to the definitions of φ V (k)

n and φ V (k) n , we have that |φ V (k) n ( Xn ) -φ V (k) n ( Xn )| ≤ [φ] Lip | Xn -Xn | + |ψ (k) n,i 0 ( Xn ) -Ên [ψ (k) n,i 0 ( Xn )]| + | Ên [ψ (k) n,i 0 ( Xn )] - ψ(k) n,i 0 ( Xn )|. (3.21)
On the other hand, we have

|ψ (k) n,i 0 ( Xn ) -Ên [ψ (k) n,i 0 ( Xn )]| ≤|ψ (k) n,i 0 ( Xn ) -ψ (k) n,i 0 ( Xn )| + |ψ (k) n,i 0 ( Xn ) -Ên [ψ (k) n,i 0 ( Xn )]| ≤[ψ (k) n,i 0 ] Lip (| Xn -Xn | + Ên | Xn -Xn |), then ψ (k) n,i 0 ( Xn ) -Ên [ψ (k) n,i 0 ( Xn )] p ≤C[v (k) n+i 0 ] Lip Xn -Xn p ≤C[φ] Lip Xn -Xn p (3.22)
By using the tower property of the conditional expectation and since Xn is σ(X n )measurable, we have

Ên [ψ (k) n,i 0 ( Xn )] - ψ(k) n,i 0 ( Xn ) = Ên [E n [v (k) n+i 0 (X n+i 0 )]] -Ên [v (k) n+i 0 ( Xn+i 0 )] = Ên [v (k) n+i 0 (X n+i 0 ) - v(k) n+i 0 ( Xn+i 0 )]. Then Ên [ψ (k) n,i 0 ( Xn )] - ψ(k) n,i 0 ( Xn ) p ≤ V (k) n+i 0 - V (k) n+i 0 p . ( 3
V (k+1) n -V (k+1) n p ≤ C[φ] Lip Xn -Xn p + V (k+1) n+1 - V (k+1) n+1 p + V (k) n+i 0 - V (k) n+i 0 p
From the induction hypothesis we obtain that

V (k+1) n -V (k+1) n p ≤ C[φ] Lip Xn -Xn p + V (k+1) n+1 - V (k+1) n+1 p + C[φ] Lip M i=n Xi -Xi p ≤ C[φ] Lip M i=n Xi -Xi p + V (k+1) n+1 - V (k+1) n+1 p .
From the definition of

V (k+1) M and V (k+1)

M

, we have that

V (k+1) M - V (k+1) M p ≤ C[φ]
Lip XM -XM p and the result follows, i.e.

V (k+1) n - V (k+1) n p ≤ C[φ] Lip M i=n Xi -Xi p . 2
Remark 3.1 Bally and Pagès introduced the following assumption. they assumed that the L p -mean quantization errors of the Xn are ϕ-dominated, i.e. there exists a random vector R ∈ L p+η (P)(η > 0) and a sequence (ϕ m,n ) 0≤m≤n<∞ such that, for every n ≥ 1, every m ∈ {0, ..., n} and every N ≥ 1, Theorem 4] that: We assume that ( Xn ) 0≤n≤M is ϕ-dominated in the sense of (3.24) by ϕ n,M := c n/M . Let N ≥ M +1, assume that for every n ∈ {1, ..., M },

Xm -Xm p ≤ ϕ m,n R -R p . (3.24) It is shown in [2,
N n = | Xk (Ω)| :=     t d 2(d+1) n (N -1) t d 2(d+1) 1 + ... + t d 2(d+1) n + ... + t d 2(d+1) M    
, where x := min{k ∈ N|k ≥ x}. Then, there exists a positive constant C p such that

max 0≤n≤M V (k) n -V (k) n p ≤ C p M 1+ 1 d N 1 d .
4 Numerical scheme for one-dimensional case

From this section we will study the one-dimensional case. We define the process X = (X t ) 0≤t≤T which evolves according to the following stochastic differential equation:

dX t = rX t dt + σX t dW t , X 0 = x > 0, (4.1)
where W is a standard Brownian motion, r > 0 and σ ∈ R. We shall also use the notation X t,x s for X s whenever we need to emphasize the dependence of the process X on its initial condition. Let us define the following HJBVI

min{rv (k) (t, x)- ∂v (k) ∂t (t, x) - 1 2 σ 2 x 2 ∂ 2 v (k) ∂x 2 (t, x) -rx ∂v (k) ∂x (t, x); v (k) (t, x) -φ v (k-1) (t, x)} = 0, ∀(t, x) ∈ [0, T ) × (0, ∞) (4.2) v (k) (T, x) = φ(x) ∀x ∈ (0, ∞), (4.3)
where φ : R -→ R + is a Lipschitz payoff function (in later use we define φ(x) = (K -x) + ), k = 1, ..., and

φ v (k-1) (t, x) = φ(x) + e -rδ E v (k-1) (t + δ, X t,x t+δ ) , ∀ 0 ≤ t ≤ T -δ (4.4) φ v (k-1) (t, x) = φ(x), ∀ T -δ < t ≤ T.
Assume that v (0) = 0 and for all t > T , v (k) (t, X t ) = 0. For k = 1, ..., , we have that the solution of the following stopping time problem

v (k) (t, x) = ess sup τ ∈ St E e -r(τ -t) φ v (k-1) (τ, X τ )|X t = x , (4.5)
is the viscosity solution of the HJBVI (4.2)-(4.3), where S t := {τ ∈ S 0 ; t ≤ τ ≤ T } for every t ∈ S 0 . We can see that the diffusion process (X s ), solution of (4.1), is a function of the Brownian motion, defined by

X s = xe (r-σ 2 2 )(s-t)+σW s-t , for s > t, where X t = x.
Then, it suffices to consider a quantizer of the Brownian motion. Let U be a standard normal random variable, then we can write

X s ∼ xe (r-σ 2 2 )(s-t)+σ √ s-tU , for s > t, where X t = x.
Note that the optimal quantization has no closed formula for the solutions. Quadratic optimal N-quantization of the N (0, I d ) distributions has been carried out systematically for various sizes N ∈ {1, ..., 400} and dimensions d ∈ {1, ..., 10}. Some files of these optimal grids (including their weights) can be downloaded from the website [17]. Let (u 1 , ..., u N ) N real variables, Û the optimal quantizer of U with values in (u 1 , ..., u N ) and

Xt,x s = xe (r-σ 2 2 )(s-t)+σ √ s-t Û , for s > t,
where Xt,x t = x.

We define

P R : R -→ [0, R] x -→ x1 [0,R] + R1 (R,∞) , φ N,R v(k-1) h (t, x) = φ(x) + e -rδ E[v (k-1) h (t + δ, P R ( Xt,x t+δ ))] ∀t ∈ [0, T -δ], φ N,R v(k-1) h (t, x) = φ(x) ∀t ∈ (T -δ, T ].
We denote by v(k) h , the solution of

   v(k) h (t, x) = φ(x) ∀t ∈ [T -h, T ] v(k) h (t, x) = max{e -rh E[v (k) h (t + h, P R ( Xt,x t+h ))], φ N,R v(k-1) h (t, x)} ∀t ∈ [0, T -h). (4.6)
Assume that v(0) h ≡ 0 and v(k) h (t, x) = 0 for all t > T . We denote the numerical scheme of the HJBVI (4.2)-(4.3) by

S h,N,R,k (t, x, v(k) h (t, x), v(k) h , v(k-1) h ) = 0 ∀(t, x) ∈ [0, T -h) × (0, ∞) (4.7) v(k) h (t, x) = φ(x) ∀(t, x) ∈ [T -h, T ] × (0, ∞), (4.8)
where

S h,N,R,k (t, x, p k , a k , a k-1 ) := min{ p k -e -rh E[a k (t + h, P R ( Xt,x t+h ))] h ; p k -φ N,R a k-1 (t, x)}. (4.9)
The following proposition shows the Lipschitz property of v(k) h , k = 1, ..., and an upper bound of the corresponding Lipschitz constant. Proof. For k = 1, by the Lipschitz assumption of φ we have that for

t ∈ [T -h, T ], v(1) h (t, .) is Lipschitz and [v (k) h (t, .)] Lip = [φ] Lip . For t ∈ [T -2h, T -h) we have v(1) h (t, x) - v(1) h (t, y) ≤ max e -rh E v(1) h (t + h, P R ( Xt,x t+h )) - v(1) h (t + h, P R ( Xt,y t+h )) ; |φ(x) -φ(y)| ≤ [φ] Lip max e -rh E P R ( Xt,x t+h ) -P R ( Xt,y t+h ) ; |x -y| ≤ [φ] Lip max e -rh E Xt,x t+h -Xt,y t+h ; |x -y| ≤ [φ] Lip max e -rh |x -y| E e (r-σ 2 2 )h+σ √ h Û ; |x -y| ≤ [φ] Lip e σ 2 2 h |x -y| ,
where the last inequality is deduced from the fact that Û is the optimal quantizer of U , then E e σ

√ h Û = E e σ √ hE[U | Û ]
, and using Jensen's inequality we obtain

E e σ √ hE[U | Û ] ≤ E E e σ √ hU | Û = E e σ √ hU = e σ 2 h
, so

E e σ √ h Û ≤ e σ 2 h . ( 4
h (t, .)] Lip ≤ e σ 2 2 T [φ] Lip . Let 1 ≤ k ≤ -1, assume that v(k) h is Lipschitz in space with [v (k) h (t, .)] Lip ≤ ( k-1 j=0 e j(T +δ) σ 2 2 )e σ (1)
2 T [φ] Lip and let us prove that v(k+1) h is also. By the

Lipschitz assumption of φ we have that for t

∈ [T -h, T ], v(k+1) h (t, .) is Lipschitz with [v (k+1) h (t, .)] Lip = [φ] Lip . For t ∈ [T -2h, T -h), we have that v(k+1) h (t, x) - v(k+1) h (t, y) ≤ max(e -rh E v(k+1) h (t + h, P R ( Xt,x t+h )) - v(k+1) h (t + h, P R ( Xt,y t+h )) ; |φ(x) -φ(y)| + e -rδ E v(k) h (t + δ, P R ( Xt,x t+δ )) - v(k) h (t + δ, P R ( Xt,y t+δ )) ) ≤ max   e -rh [φ] Lip E Xt,x t+h -Xt,y t+h ; [φ] Lip |x -y| (1 + k j=1 e j(T +δ) σ 2 2 )   ≤ k j=0 e j(T +δ) σ 2 2 [φ] Lip |x -y| .
By repeating the same reasoning for t on each interval of the form [T -

(i + 1)h, T -ih), for i = 2, ..., M -1, we obtain that v(k+1) h (t, .) is Lipschitz in space with [v (k+1) h (t, .)] Lip ≤ e σ 2
2 (i-1)h k j=0 e j(T +δ) σ 2 2 [φ] Lip |x -y|. We deduce then the desired result. 2

Convergence of the scheme

We focus now on the convergence (when h goes to zero) of the solution v(k) h of (4.7)-(4.8) toward the value function v (k) solution of (4.2)-(4.3). Following Barles and Souganidis [START_REF] Barles | Convergence of approximation schemes for fully nonlinear second order equations[END_REF], we must show that the scheme S h,N,R,k defined by (4.9) is monotone, stable and consistent. We will prove such properties by induction arguments. For the consistency at step k + 1 (k ≥ 1), we need the convergence of the numerical scheme at step k. Let us first define the monotonicity, stability and consistency properties. Definition 4.1 For k = 1, ..., , we say that S h,N,R,k defined by (4.9) is monotonous if

S h,N,R,k (t, x, p k , a k , a k-1 ) ≥ S h,N,R,k (t, x, p k , b k , a k-1 ) if a k ≤ b k for all (t, x) ∈ [0, T ] × (0, ∞), p k ∈ R, a k , b k and a k-1
Lipschitz in space and satisfying the linear growth condition. Definition 4.2 For k = 1, ..., , we say that S h,N,R,k is stable if for all h > 0, there exists a solution v(k) h of (4.7)-(4.8) which is uniformly bounded in h, N and R.

Definition 4.3 For k = 1, ..., , we say that S h,N,R,k is consistent if for all Lipschitz function ψ ∈ C 1,2 ([0, T ] × (0, ∞)), and all (t, x) ∈ [0, T ] × (0, ∞)

lim N √ h,R→∞ h→0,(s,y)→(t,x) min ψ(s, y) -e -rh E[ψ(s + h, P R ( Xs,y s+h ))] h ; ψ(s, y) -φ N,R v(k-1) h (s, y) = min - ∂ψ ∂t (t, x) -Lψ(t, x); ψ(t, x) -φ v (k-1) (t, x) , where v(k-1)
h is the solution of (4.7)-(4.8), v (k-1) is the viscosity solution of (4.2)-( 4.3), and

Lψ(t, x) : = -rψ(t, x) + 1 2 σ 2 x 2 ∂ 2 ψ ∂x 2 (t, x) + rx ∂ψ ∂x (t, x).
Let us now present and prove the convergence theorem. Proof. For k ∈ {1, ..., }, we define v(k) (t, x) := lim sup

N √ h,R→∞ (s,y)→(t,x),h→0 v(k) h (s, y), v (k) (t, x) := lim inf N √ h,R→∞ (s,y)→(t,x),h→0 v(k) h (s, y) (4.12) and v(k) (T, x) := v (k) (T, x) := φ(x).
We claim that v(k) and v (k) are respectively sub-and super-solutions of (4.2)-(4.3). Assume for the moment that this claim is true; then, by the comparison theorem (see [START_REF] Ben Latifa | A general optimal multiple stopping problem with an application to Swing Options[END_REF]) we obtain that v(k) ≤ v (k) on D. But the opposite inequality is obvious by the definition of v(k) and

v (k) , hence v (k) = v(k) = v (k)
is the unique continuous solution of (4.2)-(4.3). This fact together with (4.12) also imply the local uniform convergence of v(k) h to v (k) . Our aim now is to prove the above claim. Let us prove that v(k) is a viscosity sub-solution of the HJBVI (4.2)-(4.3). Let (t 0 , x 0 ) be a strict local maximum of v(k) -ψ on D such that

∀(t, x) ∈ B((t 0 , x 0 ), r)\{(t 0 , x 0 )} ∩ D v(k) (t, x) -ψ(t, x) < v(k) (t 0 , x 0 ) -ψ(t 0 , x 0 ) := 0, (4.13)
where ψ is bounded and infinitely differentiable function defined on D, such that ψ ≥ 2C out side the ball B((t 0 , x 0 ), r) ψ ≤ C on the ball B((t 0 , x 0 ), r).

Where C > 0 is such that v(k) h (t, x) ≤ C, ∀(t, x) ∈ D, h, R > 0 and N ∈ N\{0}, the existence of C is insured by the boundedness of the function φ. It is known that there exist sequences

h n > 0, N n in N\{0}, R n in [0, ∞) and (s n , y n ) ∈ D such that as n → ∞, h n → 0, R n , N n √ h n → ∞, (s n , y n ) → (t 0 , x 0 ), v(k) hn (s n , y n ) → v(k) (t 0 , x 0 ) and (s n , y n ) is a global maximum point of v(k) hn -ψ. Let us prove that min - ∂ψ ∂t (t 0 , x 0 ) -Lψ(t 0 , x 0 ); ψ(t 0 , x 0 ) -φ v (k-1) (t 0 , x 0 ) ≤ 0. (4.14)
Denoting by ρ n the quantity v(k) hn (s n , y n ) -ψ(s n , y n ), then we have ρ n → 0 and

v(k) hn (t, x) ≤ ψ(t, x) + ρ n for all (t, x) ∈ D. (4.15)
The definition of v(k) hn , the monotonicity of S hn,Nn,Rn,k and (4.15) yield

S hn,Nn,Rn,k (s n , y n , ψ(s n , y n ) + ρ n , ψ + ρ n , v (k-1) hn
)

≤ S hn,Nn,Rn,k (s n , y n , ψ(s n , y n ) + ρ n , v (k) hn , v (k-1) hn ) = 0. (4.16)
Taking limits in (4.16) and using the consistency of S hn,Nn,Rn,k we obtain

0 ≥ lim n S hn,Nn,Rn,k (s n , y n , ψ(s n , y n ) + ρ n , ψ + ρ n , v (k-1) hn ) ≥ lim inf N √ h,R→∞,ρ→0 h→0,(s,y)→(t 0 ,x 0 ) S h,N,R,k (s, y, ψ(s, y) + ρ, ψ + ρ, v (k-1) hn ) ≥ min - ∂ψ ∂t (t 0 , x 0 ) -Lψ(t 0 , x 0 ); ψ(t 0 , x 0 ) -φ v (k-1) (t 0 , x 0 ) , (4.17)
then inequality (4.14) is proved and we conclude then that v(k) is a viscosity sub-solution of the HJBVI (4.2)-(4.3). We can prove identically that v (k) is a viscosity super-solution of the HJBVI (4.2)-(4.3). Then by the comparison theorem we obtain that v(k) h converges locally uniformly to the unique viscosity solution of (4.2)-(4.3).

2

Let us now prove the monotonicity, stability and consistency of our numerical scheme. For the consistency property, we will prove that our scheme is consistent for (t, x) ∈ [0, T ]\{T -δ}×(0, ∞). Then from the last theorem we obtain the local uniform convergence of v(k)

h to v (k) in [0, T ] \ {T -δ} × (0, ∞).
The monotonicity of the scheme is obvious. Proposition 4.2 For all k = 1, ..., , S h,N,R,k is monotonous.

Proposition 4.3 For k = 1, ..., , S h,N,R,k is stable. Proof. We have that for all (t, x) ∈ [0, T -h) × (0, ∞) S h,N,R,k (t, x, v(k) h (t, x), v(k) h , v(k-1) h ) = 0 ⇔ v(k) h (t, x) = max(e -rh E[v (k) h (t + h, P R ( Xt,x t+h ))]; φ N,R v(k-1) h (t, x)).
Our aim now is to prove that for k = 1, ..., , v(k) h is uniformly bounded in h, N and R. We define the pay-off function φ(x) := (K -x) + , where K > 0. For k = 1:

For t ∈ [T -h, T ], v (1)
h (t, x) = φ(x) ≤ K. For t ∈ [T -2h, T -h), v(1) h (t, x) = max e -rh E v(1) h (t + h, P R ( Xt,x t+h )) ; φ(x) ≤ K,
where the last inequality is deduced from the fact that t

+ h ∈ [T -h, T ). Then v(1) h is uniformly bounded in h, N and R when t ∈ [T -2h, T -h). By repeating this reasoning on each interval of the form [T -(i + 1)h, T -ih), for i = 2, ..., M -1, we obtain that v(1) h is uniformly bounded in h, N and R. Let 1 ≤ k ≤ , assume that v(k) h is uniformly bounded in h, N and R and let us prove that v(k) h is also. For t ∈ [T -h, T ], v (k+1) h (t
, x) = φ(x) ≤ K. For t ∈ [T -2h, T -h) there are two cases: 1 st case: If t ∈ (T -δ, T ], v(k+1) h (t, x) = max e -rh E v(k+1) h (t + h, P R ( Xt,x t+h )) ; φ(x) ≤ K. 2 nd case: If t ∈ [0, T -δ], v (k+1)
h (t, x) = max e -rh E v(k+1) h (t + h, P R ( Xt,x t+h )) ; φ(x) + e -rδ E v(k) h (t + δ, X t,x t+δ ) .
We have that when

t ∈ [T -h, T ], v (k+1)
h is uniformly bounded in h, N and R, then by the induction assumption and the definition of v(k+1) h , we deduce that it is uniformly bounded in h, N and R. We repeat the same argument on each interval of the form [T -(i + 1)h, T -ih), for i = 2, ..., M -1 we obtain that v(k+1) h is uniformly bounded in h, N and R. We conclude then the stability of S h,N,R,k for k = 1, ..., .

2

The definition of φ N,R

v(k) h differs if t ≤ T -δ or t > T -δ.
Then we will prove by induction the consistency of the numerical scheme for all t ∈ [0, T ] \ {T -δ}, here we choose D = [0, T ] \ {T -δ} × (0, ∞). We need the following two Lemmas. E[ψ(s + h, P R ( Xs,y s+h ))] -E ψ(s + h, X s,y s+h ) h = 0 (4.18)

Proof. We have that for all Lipschitz function ψ ∈ C

X s,y u = ye (r-σ 2
2 )(u-s)+σ √ u-sU a.s., then

E Xs,y s+h -X s,y s+h = ye (r-σ 2 2 )h E e σ √ h Û -e σ √ hU ≤ Cyσ √ he (r-σ 2 2 )h E (e σ √ h Û + e σ √ hU )| Û -U | ≤ Cyσ √ he (r-σ 2 2 )h E (e σ √ h Û + e σ √ hU ) 2 E | Û -U | 2 ≤ Cyσ √ he (r-σ 2 2 )h E e 2σ √ h Û + E e 2σ √ hU E | Û -U | 2 .
As in (4.11), we have E e 2σ √ h Û ≤ e 2σ 2 h , and by Zador's Theorem we have

E | Û -U | 2 = O 1 N , then E Xs,y s+h -X s,y s+h ≤ 1 N Cyσ √ he (r+ σ 2 2 )h . (4.20) Let N = h α , where α < -1 2 , then E Xs,y s+h -X s,y s+h h ≤ ε(h), (4.21)
where ε(h) := Cyσh - Then to prove the consistency of S h,N,R,k+1 we will just prove that lim

N √ h,R→∞ h→0,(s,y)→(t,x) φ N,R v(k) h (s, y) = φ v (k) (t, x).
(4.26)

We will prove this equality by induction.

For k = 1, by the assumption v

(0) h ≡ v(0) h ≡ 0, we obtain that φ v (0) (t, x) = φ(x) and φ N,R v(0) h (s, y) = φ(y), then equality (4.26) is satisfied for k = 1.
Let 1 ≤ k ≤ -1, assume that equality (4.26) is satisfied for k, then S h,N,R,k is consistent, and let us prove that so is for k + 1. We have that S h,N,R,k is monotonous, stable and consistent for t = T -δ, then by theorem 4.1, we obtain that for t = T -δ, v(k) h converges to v (k) .

For s near t we have two cases:

s and t are in [0, T -δ) or in (T -δ, T ]. 1 st case: For s and t in [0, T -δ) φ N,R v(k) h (s, y) -φ v (k) (t, x) ≤ |φ(y) -φ(x)| + E v(k) h (s + δ, P R ( Xs,y s+δ )) -v (k) (t + δ, X t,x t+δ ) ≤ C|x -y| + E v(k) h (s + δ, P R ( Xs,y s+δ )) -v (k) (s + δ, X s,y s+δ ) + E v (k) (s + δ, X s,y s+δ ) -v (k) (t + δ, X t,x t+δ ) .
Using the Lipschitz property of v(k) h and inequality (4.20) we obtain that

E v(k) h (s + δ, P R ( Xs,y s+δ )) -v (k) (s + δ, X s,y s+δ ) ≤E v(k) h (s + δ, P R ( Xs,y s+δ )) - v(k) h (s + δ, X s,y s+δ ) + E v(k) h (s + δ, X s,y s+δ ) -v (k) (s + δ, X s,y s+δ ) ≤ 1 N Cyσ √ he (r+ σ 2 2 )h + E v(k) h (s + δ, X s,y s+δ ) -v (k) (s + δ, X s,y s+δ ) . So by the convergence of v(k) h to v (k) we obtain that lim N √ h,R→∞ h→0,(s,y)→(t,x) E v(k) h (s + δ, P R ( Xs,y s+δ )) -v (k) (s + δ, X s,y s+δ ) = 0. (4.27) E v (k) (s + δ, X s,y s+δ ) -v (k) (t + δ, X t,x t+δ ) ≤E v (k) (s + δ, X s,y s+δ ) -v (k) (s + δ, X t,x t+δ ) + E v (k) (s + δ, X t,x t+δ ) -v (k) (t + δ, X t,x t+δ ) ≤CE X s,y s+δ -X t,x t+δ + CE 1 + X t,x t+δ |s -t| ≤C|x -y| + C(1 + |x|) |s -t|,
where the second inequality is deduced by the continuity of v (k) , see [START_REF] Ben Latifa | A general optimal multiple stopping problem with an application to Swing Options[END_REF], and the last one is deduced by Pham [START_REF] Pham | Optimal Stopping of Controlled Jump Diffusion Processes: A viscosity Solution Approach[END_REF]. We conclude then that lim

N √ h,R→∞ h→0,(s,y)→(t,x) E v (k) h (s + δ, Xs,y s+δ ) -v (k) (t + δ, X t,x t+δ ) = 0. (4.28) 2 nd case: For s and t in (T -δ, T ] φ N,R v(k) h (s, y) -φ v (k) (t, x) = |φ(y) -φ(x)| ≤ C|x -y|, (4.29)
which goes to 0 when (s, y) goes to (t, x).

In the two cases we obtain equality (4.26). We deduce then the consistency of S h,N,R,k , for k = 1, ..., .

We have proved that our scheme is monotonous and stable for t ∈ [0, T ] and consistent for t ∈ [0, T ] \ {T -δ}, then by theorem 4.1 we conclude that v(k) h converges locally uniformly on [0, T ] \ {T -δ} × (0, ∞) to the unique viscosity solution v (k) of (4.2)-(4.3). By the following corollary we obtain the convergence of v(k) h , on [0, T ] × (0, ∞), to the unique viscosity solution v (k) of (4.2)-(4.3). Proof. We have that v(k) h converges locally uniformly to v

(k) (t, x) in [0, T ]\{T -δ}×(0, ∞) then ∀x ∈ (0, ∞) lim (s,y)→(T -δ,x) s<T -δ v(k) h (s, y) = v (k) ((T -δ) -, x), (4.30) and lim
(s,y)→(T -δ,x) s>T -δ v(k) h (s, y) = v (k) ((T -δ) + , x). (4.31)
Equalities (4.30) and (4.31) added to the continuity of v

(k) on [0, T ] × (0, ∞), imply the convergence of v(k) h to v (k) on (T -δ, x
). We conclude then that v(k) h converges on [0, T ] × (0, ∞) to the unique viscosity solution v (k) of (4.2)-(4.3).

2

Note that the approximation scheme is not yet fully implementable, since it requires an approximation method for the expectations arising in (4.9). This is the concern of the next section.

Numerical solution for one-dimensional case

In this section, we introduce an implementable scheme. We discretize in time the optimal stopping problem (4.5). Let M ∈ N\{0} and h = T /M be the time step. We assume that there exists i 0 ∈ {1, ..., M } such that δ = i 0 h. For q = 0, ..., M , we denote by t q = qh. We define for i = 1, ..., N , q = M, ..., 0, x q i := xe (r-σ 2 2 )qh+σ √ qhu i , x 0 i := x, x q := {x q 1 , ..., x q N }, where (u 1 , ..., u N ) is an optimal quantization grid of the standard univariate normal distribution. Our aim now is to calculate the value v(k) h (0, x) for x > 0. Actually, setting K = max(M, N ), the complexity of the algorithm is O(K 2 ). Yet, practical implementation of the algorithm can achieve much better performance. In the optimal quantization for the computation of the expectations in the numerical algorithm, we can choose N = O(M 1/2+ ) for all > 0. In this case, the complexity is reduced to complexity = O(M 5/2+ ) for all > 0, which is satisfactory when considering that there are O(M ) points to compute in the time axis,. If we consider the space discretization with M points, the complexity of the algorithm will be complexity = O( M M 5/2+ ) for all > 0.

Comparison with the finite-difference scheme

Let us compare our result with usual finite difference scheme. Let us briefly introduce the class of theta schemes. We refer the reader to Lapeyre et al. [START_REF] Lapeyre | Simulation of financial models: Mathematical foundations and applications[END_REF] for a complete discussion about this class of schemes. We will assume that the value function is sufficiently smooth, and we focus in this section on the diffusive part of the HJBVI, so that the target equation we have to solve is

∂v (k) ∂t (t, x) + Lv (k) (t, x) = 0 ∀(t, x) ∈ [0, T ) × (0, ∞),
together with a terminal condition on {T } × (0, ∞), where

Lv (k) (t, x) = -rv (k) (t, x) + 1 2 σ 2 x 2 ∂ 2 v (k)
∂x 2 (t, x) + rx ∂v (k) ∂x (t, x).

To solve numerically this Kolmogorov parabolic equation with finite time horizon, we can discretize it using a theta scheme. Let θ ∈ [0, 1], ∆ := R/M , with M ∈ N * , denote the spatial step, and O ∆ := {i∆, i = 0, ..., M } be the associated spatial grid. We denote by h := T /K, with K ∈ N * , the time step. The approximation consists in the following: ∂v (k) ∂t (t, x) + Lv (k) (t, x) P θ h,∆ v (k) (t, x),

where

P θ h,∆ v (k) (t, x) := v (k) (t + h, x) -v (k) (t, x) ∆t + θL ∆ v (k) (t, x) + (1 -θ)L ∆ v (k) (t + h, x), L ∆ v (k) (t, x) := σ 2 x 2 2 v (k) (t, x + ∆) -2v (k) (t, x) + v (k) (t, x -∆) ∆ 2 + rx v (k) (t, x + ∆) -v (k) (t, x -∆) 2∆ -rv (k) (t, x).
The discretized equation is

P θ h,∆ v (k) (t, x) = 0 ∀(t, x) ∈ O ∆ × [0, T ).
From the finite-differences approximation, we have the following precision:

∂v (k) ∂t (t, x) + Lv (k) (t, x) = P θ h,∆ v (k) (t, x) + O(h p + ∆ q ),
where p and q depend on the choice of θ: if θ = 1/2 we obtain that p = 1 and if θ = 1/2 we obtain that p = 2 which corresponds to the Crank-Nicholson scheme. Due to the second order derivative in L, and by using standard finite-difference approximation, the rate of convergence for the spatial approximation is q = 2, for all θ ∈ [0, 1]. Therefore, in our case, we see that theta schemes have order 1 in time and order 2 in space, except for the Crank-Nicholson scheme, which gives an order 2 in time and order 2 in space. For comparison purposes, the optimally quantized scheme that we use has a precision of o(h) in time provided that N ∼ h -(1/2+ε) , where N is the number of points in the optimal quantization grid. Indeed, we have that

∂v (k) ∂t (t, x) + Lv (k) (t, x) = 0 ∀(t, x) ∈ [0, T ) × (0, ∞).
Then by Lemma 4.1 and Lemma 4.2 we obtain that v(k) h (t, x) = E v(k) h (t + h, P R ( Xt,x t+h )) + o(h).

This prompts two comments. First, we see that, in contrast with the finite-difference scheme, the precision of the optimally quantized scheme is controlled by the number of points N of the optimal quantization grid, and not by the space step ∆. Therefore, we can improve the precision by increasing N without increasing the size of the grid, which is very interesting when dealing with high-dimensional state space. Second, using the optimally quantized method we keep a precision of o(h). Whereas, using a finite-difference scheme, the above result allows us to choose M K 1/4 , to obtain a precision of O(h 1/2 ) due to spatial approximation. Therefore, by using an optimally quantized scheme, we can obtain a satisfactory precision, while managing efficiently the size of the grid, and subsequently the memory needed to achieve computation, which is highly relevant when dealing with high-dimensional state space.

n

  ≡ 0 if n > M and v (0) n ≡ 0, for n = 0, ..., M . Let us prove the Lipschitz property of the function v (k) n for k = 1, ..., and n = 0, ..., M . Proposition 3.1 For k = 1, ..., , n = 0, ..., M , v (k) n is Lipschitz continuous function and there exists a positive constant C such that

For

  simplicity of notation we denote by Ên [.] := E[.| Xn ] and E n [.] := E[.|X n ], and we assume that

Proposition 4 . 1 2 T

 412 For k = 1, ..., , the solution v(k) h of (4.7)-(4.8) is Lipschitz with respect to the state variable and [v (k) h (t, .)] Lip ≤ ( [φ] Lip , where [φ] Lip := sup x =y |φ(x) -φ(y)| x -y (4.10)

Theorem 4 . 1

 41 Assume that for k = 1, ..., , S h,N,R,k is monotonous, consistent and stable for (t, x) ∈ D, where D is a subset of [0, T ] × (0, ∞). Then, as h → 0, N √ h and R → ∞, the solution v(k) h of (4.7)-(4.8) converges locally uniformly in D to the unique viscosity solution v (k) of (4.2)-(4.3).

Lemma 4 . 1

 41 For all Lipschitz function ψ ∈ C 1,2 ([0, T ] × (0, ∞)), ∀(s, y) ∈ [0, T ] × (0, ∞) and for N = h α , where α < -1/2, we have lim R→∞ h→0

Corollary 4. 1

 1 If v(k)h converges locally uniformly on [0, T ] \ {T -δ} × (0, ∞) to the unique viscosity solution v (k) of (4.2)-(4.3). Then v(k) h converges on [0, T ] × (0, ∞) to the unique viscosity solution v (k) of (4.2)-(4.3).

Figure 1 :

 1 Figure 1: graph of the functions v (k) (0, .) for k = 1, 2, 3, 4 and 5

  It is well known that there exists a normal random variable U such that, ∀u ∈ [s, T ]

		1,2 ([0, T ] × (0, ∞)) and for all
	(s, y) ∈ [0, T ] × (0, ∞)
	E ψ(s + h, P R ( Xs,y s+h )) -E ψ(s + h, X s,y s+h ) ≤ CE P R ( Xs,y s+h ) -X s,y s+h .
	So by applying the dominated convergence theorem we obtain that
	lim R→∞	E[ψ(s + h, P R ( Xs,y s+h ))] -E ψ(s + h, X s,y s+h ) ≤ CE Xs,y s+h -X s,y s+h . (4.19)

  For all Lipschitz function ψ ∈ C 1,2 ([0, T ] × (0, ∞)) and for all (t, x) ∈ [0, T ] × (0, ∞), we have For k = 1, ..., , S h,N,R,k is consistent for N = h α , where α < -1/2, and for t ∈ [0, T ] \ {T -δ}.

	Lemma 4.2 lim h→0 (s,y)→(t,x)	ψ(s, y) -e -rh E ψ(s + h, X s,y s+h ) h	= -	∂ψ ∂t	(t, x) -Lψ(t, x).	(4.23)
	Proof. By applying Itô's formula to u → e -r(u-s) ψ(u, X s,y u ) in [s, s + h] we obtain
	e -rh ψ(s + h, X s,y s+h ) -ψ(s, y) =	s	s+h	e -r(u-s) ∂ψ ∂t	(u, X s,y u ) + Lψ(u, X s,y u ) du
					+	s	s+h	e -r(u-s) ∂ψ ∂x	(u, X s,y u )σX s,y u dW u .
	By dividing the last inequality by h and taking the expectation we obtain
	e -rh E ψ(s + h, X s,y s+h ) -ψ(s, y) h	=	1 h	E	s	s+h	e -r(u-s) ∂ψ ∂t	(u, X s,y u ) + Lψ(u, X s,y u ) du .
	By sending h to 0 and using dominated convergence theorem we obtain that
	lim h→0	ψ(s, y) -e -rh E ψ(s + h, X s,y s+h ) h	= -	∂ψ ∂t	(s, y) -Lψ(s, y).	(4.24)
	Then by the regularity of ψ we obtain equality (4.23).	2
	Proposition 4.4 Proof. By Lemma 4.1 and Lemma 4.2 we obtain that for all Lipschitz function
	ψ ∈ C 1,2 ([0, T ] × (0, ∞)), and all (t, x) ∈ [0, T ] × (0, ∞)
	lim h→0,(s,y)→(t,x) R→∞	ψ(s, y) -e -rh E[ψ(s + h, P R ( Xs,y s+h ))] h	= -	∂ψ ∂t	(t, x) -Lψ(t, x).	(4.25)
			1 2 -α goes to 0 when h goes to 0. We deduce then by inequalities
	(4.19) and (4.21) that
	E[ψ(s + h, P R ( Xs,y s+h ))] -E ψ(s + h, X s,y s+h ) h	→ 0, when h → 0 and R → ∞. (4.22)
									2

We define

The following table presents Swing put option values for different numbers of simulations for = 5, T = 1 year, δ = 0.1 year, x = K = 100, r = 0.05, σ = 0. This result is similar to those of Carmona and Touzi [START_REF] Carmona | Optimal Multiple Stopping and valuation of Swing Options[END_REF].

We have implemented and tested the above algorithm for the swing put option with the following characteristics: maturity T = 1 year, refraction period δ = 0.1 year, r = 0.05, σ = 0.30, maximal number of exercise rights = 5 and the number of points in the optimal quantization grid N = 150. The following figure gives the plots of the graphs of the functions x → v (k) (0, x) for k = 1, 2, ..., 5.

Complexity of the algorithm

The computation of the value function has not an expensive computation cost. Indeed, this grid contains O(M ) points, and at each point t q , q = 0, ..., M , one has to compute (1) the approximation of conditional expectation E[v (k) h (t q + h, P R ( Xt,x tq+δ ))] that costs O(N ) unitary operations, (2) the localization procedure has constant computational cost O(1).