Bruno Bouchard
email: bouchard@ensae.fr

Marcel Nutz
email: marcel.nutz@math.ethz.ch.

Weak Dynamic Programming for Generalized State Constraints

Keywords: weak dynamic programming, state constraint, expectation constraint, Hamilton-Jacobi-Bellman equation, viscosity solution, comparison theorem AMS 2000 Subject Classications 93E20, 49L20, 49L25, 35K55

We provide a dynamic programming principle for stochastic optimal control problems with expectation constraints. A weak formulation, using test functions and a probabilistic relaxation of the constraint, avoids restrictions related to a measurable selection but still implies the Hamilton-Jacobi-Bellman equation in the viscosity sense. We treat open state constraints as a special case of expectation constraints and prove a comparison theorem to obtain the equation for closed state constraints.

Introduction

We study the problem of stochastic optimal control under state constraints.

In the most classical case, this is the problem of maximizing an expected reward, subject to the constraint that the controlled state process has to remain in a given subset of the state space. There is a rich literature on the associated partial dierential equations (PDEs), going back to [START_REF] Soner | Optimal control with state-space constraint[END_REF][START_REF] Soner | Optimal control with state-space constraint[END_REF][START_REF] Ishii | A new formulation of state constraint problems for rst-order PDEs[END_REF] in the rst order case and [START_REF] Lasry | Nonlinear elliptic equations with singular boundary conditions and stochastic control with state constraints. I. The model problem[END_REF][START_REF] Katsoulakis | Viscosity solutions of second order fully nonlinear elliptic equations with state constraints[END_REF] in the second order case. The connection between the control problem and the equation is given by the dynamic programming principle. However, in the stochastic case, it is frequent practice to make this connection only formally. Of course, there are specic situations where it is indeed possible to avoid proving the state-constrained dynamic programming principle; in particular, penalization arguments can be useful to reduce to the unconstrained case. See, e.g., [START_REF] Fleming | Controlled Markov Processes and Viscosity Solutions[END_REF][START_REF] Yong | Stochastic Controls. Hamiltonian Systems and HJB Equations[END_REF] for further background.

Generally speaking, it is dicult to prove the dynamic programming principle when the regularity of the value function is not known a priori, due to certain measurable selection problems. It was observed in [START_REF] Bouchard | Weak dynamic programming principle for viscosity solutions[END_REF] that, in the unconstrained case, these diculties can be avoided by a weak formulation of the dynamic programming principle where the value function is replaced by a test function. This formulation, which is tailored to the derivation of the PDE in the sense of viscosity solutions, avoids the measurable selection and uses only a simple covering argument. It turns out that the latter does not extend directly to the case with state constraints. Essentially, the reason is that if is some admissible control for the initial condition ∈ i.e., the controlled state process , started at remains in then may fail to have this property for a nearby initial condition ′ ∈ .

However, if is open and mild continuity assumptions are satised, then , ′ will violate the state constraint with at most small probability when ′ is close to . This observation leads us to consider optimization problems with constraints in probability, and more generally expectation constraints of the form [ ( , ( ))] ≤ for given ∈ ℝ. We shall see that, following the idea of [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF], such problems are amenable to dynamic programming if the constraint level is formulated dynamically via an auxiliary family of martingales. A key idea in this paper is that relaxing the level by a small constant allows to prove a weak dynamic programming principle for general expectation constraint problems (Theorem 2.4), while the PDE can be derived despite the relaxation. We shall then obtain the dynamic programming principle for the classical state constraint problem (Theorem 3.1) by passing to a limit ↓ 0, with a suitable choice of and certain regularity assumptions.

We exemplify the use of these results in the setting of controlled diusions and show how the PDEs for expectation constraints and state constraints can be derived (Theorems 4.2 and 4.6). For the latter case, we introduce an appropriate continuity condition at the boundary, under which we prove a comparison theorem. While the above concerned an open set and does not apply directly to the closed domain , we show via the comparison result that the value function for coincides with the one for , under certain conditions.

The remainder of the paper is organized as follows. In Section 2 we introduce an abstract setup for dynamic programming under expectation constraints and prove the corresponding relaxed weak dynamic programming principle. In Section 3 we deduce the dynamic programming principle for the state constraint . We specialize to the case of controlled diusions in Section 4, where we study the Hamilton-Jacobi-Bellman PDEs for expectation and state constraints. Appendix A provides the comparison theorem.

Throughout this paper, (in)equalities between random variables are in the almost sure sense and relations between processes are up to evanescence, unless otherwise stated.

Dynamic Programming Principle for Expectation Constraints

We x a time horizon ∈ (0, ∞) and a probability space (Ω, ℱ, ) equipped with a ltration = (ℱ ) ∈[0, ] . For each ∈ [0, ], we are given a set whose elements are seen as controls at time . Given a separable metric space , the state space, we denote by S := [0, ] × the time-augmented state space. For each ( , ) ∈ S and ∈ , we are given a càdlàg adapted process , = { , ( ), ∈ [ , ]} with values in , the controlled state process. Finally, we are given two measurable functions , : → ℝ. We assume that

[| ( , ( ))|] < ∞ and [| ( , ( ))|] < ∞ for all ∈ , (2.1)
so that the reward and constraint functions

( , ; ) := [ ( , ( ))], ( ,
; ) := [ ( , ( ))]
are well dened. We also introduce the value function

( , , ) := sup ∈ ( , , ) ( , ; ), ( , , ) ∈ Ŝ, (2.2)
where Ŝ := S × ℝ ≡ [0, ] × × ℝ and ( , ,

) := { ∈ : ( , ; ) ≤ } (2.3)
is the set of controls admissible at constraint level . Here sup ∅ := -∞.

The following observation is the heart of our approach: Given a control admissible at level at the point , relaxing the level will make admissible in an entire neighborhood of . This will be crucial for the covering arguments used below. We use the acronym u.s.c. (l.s.c.) to indicate upper (lower) semicontinuity.

Lemma 2.1. Let ( , , ) ∈ Ŝ, ∈ ( , , ) and assume that the function ′ → ( , ′ ; ) is u.s.c. at . For each > 0 there exists a neighborhood of ∈ such that ∈ ( , ′ , ′ + ) for all ′ ∈ and all ′ ≥ . Proof. We have ( , ; ) ≤ by the denition (2.3) of ( , , ). In view of the upper semicontinuity, there exists a neighborhood of such that

( , ′ ; ) ≤ + ≤ ′ + for ′ ∈ ; that is, ∈ ( , ′ , ′ + ).
A control problem with an expectation constraint of the form (2.3) is not amenable to dynamic programming if we just consider a xed level .

Extending slightly an idea from [START_REF] Bouchard | Stochastic target problems with controlled loss[END_REF][START_REF] Bouchard | Optimal control under stochastic target constraints[END_REF], we shall see that this changes if the constraint is formulated dynamically by using auxiliary martingales. To this end, we consider for each ∈ [0, ] a family ℳ ,0 of càdlàg martingales = { ( ), ∈ [ , ]} with initial value ( ) = 0. We also introduce

ℳ , := { + : ∈ ℳ ,0 }, ∈ ℝ.
We assume that, for all ( , ) ∈ S and ∈ , there exists

[ ] ∈ ℳ , such that [ ]( ) = ( , ( )), (2.4)
where, necessarily, = [ ( , ( ))]. In particular, given ∈ , the set

ℳ + , , ( ) := { ∈ ℳ , : ( ) ≥ ( , (
Then ( , , ) = { ∈ : ℳ + , , ( ) ∕ = ∅ } .
Proof. Let ∈ . If there exists some ∈ ℳ + , , ( ), then taking expectations yields

[ ( , ( ))] ≤ [ ( )] = and hence ∈ ( , , ).

Conversely, let ∈ ( , , ); i.e., we have The following assumption corresponds to one direction of the dynamic programming principle; cf. Theorem 2.4(i) below.

′ := [ ( , ( ))] ≤ . With [ ] as in (2.4), := [ ]+ -′ is an element of ℳ + , , ( ).
Assumption A. For all ( , , ) ∈ Ŝ, ∈ ( , , ),

∈ ℳ + , , ( ), ∈ and -a.e.
∈ Ω, there exists ∈ ( ( ), , ( )( ), ( )( ))

such that

[ ( , ( )) ℱ ] ( ) ≤ ( ( ), , ( )( );
) .

( (2.8)

The control ˜ is denoted by ⊗ ( ,Γ) ¯ and called a concatenation of and ¯ on ( , Γ).

(B2) Let ∈ ℳ ,0 . There exists a process ¯ = { ¯ ( ), ∈ [ , ]} such that ¯ (⋅)( ) = ( ¯ [ , ( )( )](⋅) ) ( ) on [ , ] -a.s.
and

1 [ , ) + 1 [ , ] ( 1 Ω∖Γ + [ ¯ -¯ ( ) + ( ) ] 1 Γ ) ∈ ℳ ,0 . (B3) Let
∈ ℝ and ∈ ℳ + , , ( ). For -a.e. ∈ Ω, there exist a control ∈ ( , , ( )( ), ( )( )).

In the second variant, the intermediate time is a stopping time and we have an additional assumption about the structure of the sets . This variant corresponds to Theorem 2.4(ii') below.

Assumption B'. Let ( , ) ∈ S, ∈ , ∈ , Γ ∈ ℱ and ¯ ∈ ∥ ∥ ∞ .

(B0')

⊇ ′ for all 0 ≤ ≤ ′ ≤ .

(B1') There exists a control ˜ ∈ , denoted by ⊗ ( ,Γ) ¯ , such that

˜ , (⋅) = , (⋅) on [ , ] × (Ω ∖ Γ); ˜ , (⋅) = ¯ , , ( ) (⋅) on [ , ] × Γ;
(2.9)

[ ( ˜ , ( )) ℱ ] ≥ ( , , (
); ¯ ) on Γ.

(2.10)

(B2') Let ∈ ℳ ,0 . There exists a process ¯ = { ¯ ( ), ∈ [ , ]} such that ¯ (⋅)( ) = ( ¯ ( ) [ , ( )( )](⋅) ) ( ) on [ , ] -a.s.
and

1 [ , ) + 1 [ , ] ( 1 Ω∖Γ + [ ¯ -¯ ( ) + ( ) ] 1 Γ ) ∈ ℳ ,0 . (B3') Let
∈ ℝ and ∈ ℳ + , , ( ). For -a.e. ∈ Ω, there exist a control ∈ ( ( ), , ( )( ), ( )( )). (2.11)

Under (B3), the same holds if takes countably many values. We remark that the invariance property (2.11) corresponds to one direction in the geometric dynamic programming of [START_REF] Soner | Dynamic programming for stochastic target problems and geometric ows[END_REF].

(iii) We note that (2.9) (and similarly (2.7)) states in particular that ( , ) → ( ¯ , , ( ) ( )

) ( ) := ( ¯ ( ), , ( )( ) ( ) ) ( )
is a well-dened adapted process (up to evanescence) on [ , ] × Γ. Of course, this is an implicit measurability condition on ( , ) → ¯ , .

(iv) For an illustration of (B1'), let us assume that the controls are predictable processes. In this case, one can often take

⊗ ( ,Γ) ¯ := 1 [0, ] + 1 ( , ] ( ¯ 1 Γ + 1 Ω∖Γ ) (2.12)
and the condition that ⊗ ( ,Γ) ¯ ∈ is called stability under concatenation. The idea is that we use the control up to time ; after time , we continue using in the event Ω ∖ Γ while we switch to the control ¯ in the event Γ. Of course, one can omit the set Γ ∈ ℱ by observing that Theorem 2.4. Let ( , , ) ∈ Ŝ, ∈ ( , , ) and ∈ ℳ + , , ( ). Let ∈ and let ⊆ Ŝ be a set such that ( , , ( ), ( )) ∈ holds -a.s.

⊗ ( ,Γ) ¯ = 1 [0, ′ ] + ¯ 1 ( ′ , ]
(i) Let Assumption A hold true and let

: Ŝ → [-∞, ∞] be a measurable function such that ≤ on . Then [ ( , , ( ), ) -] < ∞ and ( , ; ) ≤ [ ( , , ( ), ( ))
] .

(2.13)

(ii) Let > 0, let Assumption B hold true and assume that takes countably many values ( ) ≥1 . Let : Ŝ → [-∞, ∞) be a measurable function such that ≥ on . Assume that for any xed ¯ ∈ ,

( ′ , ′ ) → ( , ′ , ′ ) is u.s.c. ′ → ( , ′ ; ¯ ) is l.s.c. ′ → ( , ′ ; ¯ ) is u.s.c. ⎫  ⎬  ⎭ on (2.14)
for all ≥ 1, where

:= {( ′ , ′ ) : ( , ′ , ′ ) ∈ } ⊆ × ℝ. Then ( , , + ) ≥ [ ( , , ( ), ( )) ] .
(2.15)

(ii') Let > 0 and let Assumption B' hold true. Let : Ŝ → [-∞, ∞) be a measurable function such that ≥ on . Assume that ∩ D ⊆ Ŝ is -compact and that for any xed ¯ ∈ 0 , 0 ∈ [ , ], ( ′ , ′ , ′ ) → ( ′ , ′ , ′ ) is u.s.c. ( ′ , ′ ) → ( ′ , ′ ; ¯ ) is l.s.c. ( ′ , ′ ) → ( ′ , ′ ; ¯ ) is u.s.c. ⎫  ⎬  ⎭ on ∩ { ′ ≤ 0 }. (2.16)
Then (2.15) holds true.

The following convention is used on the right hand side of (2.15): if is any random variable, we set

[ ] := -∞ if [ + ] = [ -] = ∞.
(2.17)

We note that Assumption (B0') ensures that the expressions ( ′ , ′ ; ¯ ) and ( ′ , ′ ; ¯ ) in (2.16) are well dened for ′ ≤ 0 .

Remark 2.5. The dierence between parts (ii) and (ii') of the theorem stems from the fact that in the proof of (ii') we consider [0, ] × × ℝ as the state space while for (ii) it suces to consider × ℝ and hence no assumptions on the time variable are necessary. Regarding applications, (ii) is obviously the better choice if stopping times with countably many values (and in particular deterministic times) are sucient.

There is a number of cases where the extension to a general stopping time can be accomplished a posteriori by approximation, in particular if one has a priori estimates for the value function so that one can restrict to test functions with specic growth properties. Assume for illustration that is bounded from above, then so is and one will be interested only in test functions which are bounded from above; moreover, it will typically not hurt to assume that is u.s.c. (or even continuous) in all variables. Now let ( ) be a sequence of stopping time taking nitely many (e.g., dyadic)

values such that ↓ -a.s. Applying (2.15) to each and using Fatou's lemma as well as the right-continuity of the paths of , and

, we then nd that (2.15) also holds for the general stopping time .

On the other hand, it is not always possible to pass to the limit as above and then (ii') is necessary to treat general stopping times. The compactness assumption should be reasonable provided that is -compact; e.g., = ℝ . Then, the typical way to apply (ii') is to take ( , , ) ∈ int D and let be a open or closed neighborhood of ( , ,

) such that ⊆ D. Proof of Theorem 2.4. (i) Fix ( , , ) ∈ Ŝ. With as in (2.5), the deni- tion (2.
2) of and

≤ on imply that [ ( , ( ))|ℱ ] ( ) ≤ ( ( ), , ( )( ); ) ≤ ( ( ), , ( )( ), ( )( ) ) ≤ ( ( ), , ( )( ), ( )( ) ) -a.s.
After noting that the left hand side is integrable by (2.1), the result follows by taking expectations.

(ii) Fix ( , , ) ∈ Ŝ and let > 0.

, , ∈ ( , ′ , ′ + ) ( , ′ , ′ ) ≤ ( , , ) + ( , ′ ; , , ) ≥ ( , ; , , ) - ⎫  ⎬  ⎭ for all ( ′ , ′ ) ∈ ( , ) ∩ . (2.20)
Here the rst inequality may read -∞ ≤ -∞. We note that ⊆ ˆ is metric separable for the subspace topology relative to the product topology on ˆ . Therefore, since the family { ( , ) ∩ : ( , ) ∈ ˆ } forms an open cover of , there exists a sequence ( ,

) ≥1 in ˆ such that { ( , ) ∩ } ≥1
is a countable subcover of . We set := , , and := ( , ), so that ⊆ ∪ ≥1 .

(2.21)

We can now dene, for still being xed, a measurable partition ( ) ≥1 of ∪ ≥1 by

1 := 1 , +1 := +1 ∖ ( 1 ∪ ⋅ ⋅ ⋅ ∪ ), ≥ 1. Since ⊆ ,
( , ′ ; ) ≥ ( , ′ , ′ ) -3 for all ( ′ , ′ ) ∈ ∩ .
(2.22) 2. Concatenation. Fix an integer ≥ 1; we now focus on ( ) 1≤ ≤ . We may assume that 1 < 2 < ⋅ ⋅ ⋅ < , by eliminating and relabeling some of the . We dene the ℱ -measurable sets

Γ := { = and ( , ( ), ( )) ∈ } ∈ ℱ and Γ( ) := ∪ 1≤ , ≤ Γ .
Since the are distinct and

∩ ′ = ∅ for ∕ = ′ , we have Γ ∩ Γ ′ ′ = ∅ for ( , ) ∕ = ( ′ , ′
). We can then consider the successive concatenation

( ) := ⊗ ( 1 ,Γ 1 1 ) 1 1 ⊗ ( 1 ,Γ 1 2 ) 1 2 ⋅ ⋅ ⋅ ⊗ ( 1 ,Γ 1 ) 1 ⊗ ( 2 ,Γ 2 1 ) 2 1 ⋅ ⋅ ⋅ ⊗ ( ,Γ ) ,
which is to be read from the left with ⊗ ⊗ := ( ⊗ ) ⊗ . It follows from an iterated application of (B1) that ( ) is well dened and in particular ( ) ∈ . (To understand the meaning of ( ), it may be useful to note that in the example considered in (2.12), we would have

( ) = 1 [0, ] + 1 ( , ] ( 1 Ω∖Γ( ) + ∑ 1≤ , ≤ 1 Γ
) ;

i.e., at time , we switch to on Γ .) We note that (2.6) implies that

( ) , = , on Ω ∖ Γ( ) ∈ ℱ and hence [ ( ( ) , ( )) ℱ ] = [ ( , ( )) ℱ ] on Ω ∖ Γ( ).
(

, ( )) ℱ ] 1 Γ( ) ≥ ∑ 1≤ , ≤ ( , , ( ); )1 Γ ≥ ∑ 1≤ , ≤ ( ( , , ( ), ( )) -3 ) 1 Γ ≥ ( , , ( ), ( ))1 Γ( ) -3 .
(2.24)

3. Admissibility. Next, we show that ( ) ∈ ( , , + ). By (B2) there exists, for each pair 1 ≤ , ≤ , a process

= { ( ), ∈ [ , ]} such that (⋅)( ) = ( [ , ( )( )](⋅) ) ( ) on Γ (2.25)
and such that

( ) := ( + )1 [ , ) + 1 [ , ] ( ( + )1 Ω∖Γ( ) + ∑ 1≤ , ≤ [ - ( ) + ( ) + ] 1 Γ
) is an element of ℳ , + . We note that ( ) ( ) ≥ ( ) on Γ since ( ) ≤ ( ) + on Γ as a result of the rst condition in (2.20). Hence, using (2.7) and (2.25), we have

( ( ) , ( )) = ( , , ( ) ( ) ) ≤ ( ) ≤ ( ) ( ) on Γ .
(2.26)

This holds for all 1 ≤ , ≤ . On the other hand, using (2.6) and that ∈ ℳ + , , ( ), we have that

( ( ) , ( )) = ( , ( )) ≤ ( ) ≤ ( ) + = ( ) ( ) on Ω ∖ Γ( ).
( ] ;

( , , + ) ≥ [ ( ( ) , ( )) ] = [ [ (
( ) , ( )) ℱ ]] ≥ [ ( , , ( ), ( ))1 Γ( ) ] -3 + [ ( , (
to see this, consider separately the cases where the positive or the negative part of ( , , ( ), ( )) are integrable. Hence we have shown that ( , , + ) ≥ [ ( , , ( ), ( ))] -3 .

As > 0 was arbitrary, this completes the proof of (ii).

(ii') Fix ( , , ) ∈ Ŝ and let > 0. In contrast to the proof of (ii), we shall cover a subset of Ŝ rather than × ℝ. By (2.11), we may again assume that ∩ D = . Since ≥ on , the denition (2.2) of shows that there exists for each ( , , ) ∈ some , , ∈ ( , , ) satisfying ( , ; , , ) ≥ ( , , ) -.

(2.28)

Given ( , , ) ∈ , the semicontinuity assumptions (2.16) and a variant of Lemma 2.1 (including the time variable) imply that there exists a set

( , , ) ⊆ Ŝ of the form ( , , ) = ( ( -, ] ∩ [0, ] ) × ( , ),
where > 0 and ( , ( ,, ) is open for the product topology on [0, ]× ×ℝ if and ℝ are given the usual topology and [0, ] is given the topology generated by the half-closed intervals (the upper limit topology). Let us denote the latter topological space by [0, ] * . Like the Sorgenfrey line, [0, ] * is a Lindelöf space. Let ′ be the canoni-

) is an open ball in × ℝ + , such that , , ∈ ( ′ , ′ , ′ + ) ( ′ , ′ , ′ ) ≤ ( , , ) + ( ′ , ′ ; , , ) ≥ ( , ; , , ) - ⎫  ⎬  ⎭ for all ( ′ , ′ , ′ ) ∈ ( , , ) ∩ .
cal projection of ⊆ Ŝ ≡ [0, ]× ×ℝ to ×ℝ. Then ′ is again -compact.
It is easy to see that the product of a Lindelöf space with a -compact space is again Lindelöf; in particular, [0, ] * × ′ is Lindelöf. Moreover, since was -compact for the original topology on Ŝ and the topology of [0, ] * is ner than the original one, we still have that

⊆ [0, ] * × ′ is a countable
union of closed subsets and therefore is Lindelöf also for the new topology.

By the Lindelöf property, the cover { ( , , ) ∩ : ( , , ) ∈ Ŝ} of admits a countable subcover { ( , , ) ∩ } ≥1 . We set :=

, , and := ( , , ), then ⊆ ∪ ≥1 and

1 := 1 , +1 := +1 ∖ ( 1 ∪ ⋅ ⋅ ⋅ ∪ ), ≥ 1
denes a measurable partition of ∪ ≥1 . Since ⊆ , the inequalities (2.28) and (2.29) yield that

( ′ , ′ ; ) ≥ ( ′ , ′ , ′ ) -3 for all ( ′ , ′ , ′ ) ∈ ∩ .
Similarly as above, we rst x ≥ 1, dene the ℱ -measurable sets

Γ := { ( , , ( ), ( )) ∈ } and Γ( ) := ∪ 1≤ ≤ Γ and set ( ) := ( ⋅ ⋅ ⋅ (( ⊗ ( ,Γ 1 ) 1 ) ⊗ ( ,Γ 2 ) 2 ) ⋅ ⋅ ⋅ ⊗ ( ,Γ ) ) . To check that [ ( ( ) , ( )) ℱ ] ≥ ( , , ( ); ) on Γ for 1 ≤ ≤ ,
we use that ≤ on Γ , so that we can apply (2.10) with the stopping time

˜ := ∧ satisfying ∥˜ ∥ ∞ ≤ and thus ∈ ⊆ ∥˜ ∥ ∞ ; c.f. (B0').
The rest of the proof is analogous to the above.

Remark 2.6. The assumption on -compactness in Theorem 2.4(ii') was used only to ensure the Lindelöf property of ∩D for the topology introduced in the proof. Therefore, any other assumption ensuring this will do as well.

Let us record a slight generalization of Theorem 2.4(ii),(ii') to the case of controls which are not necessarily admissible at the given point ( , , ).

The intuition for this result is that the dynamic programming principle holds as before if we use such controls for a suciently short time (as formalized by condition (2.30) below) and then switch to admissible ones. More precisely, the proof also exploits the relaxation which is anyway present in (2.15). We use the notation of Theorem 2.4.

Corollary 2.7. Let the assumptions of Theorem 2.4(ii) hold true except that ∈ and ∈ ℳ , are not necessarily in ( , , ) and ℳ + , , ( ), respectively. In addition, assume that ( , , ( ), ( ) ) ∈ D -a.s.

(2.30)

Then the conclusion (2.15) of Theorem 2.4(ii) still holds true. Moreover, the same generalization holds true for Theorem 2.4(ii').

Proof. Let us inspect the proof of Theorem 2.4(ii). Using directly (2.30) rather than appealing to (2.11), the construction of the covering in Step 1 remains unchanged and the same is true for the concatenation in Step 2. In

Step 3, we proceed as above up to and including (2.26). Note that (2.27)

no longer holds as it used the assumption that ∈ ℳ + , , ( ). However, in view of (2.26) and ( )

, ( ) = , ( ) on Ω ∖ Γ( ), we still have

[ ( ( ) , ( )) ] ≤ [ ( ) ( )1 Γ( ) ] + [ ( , ( ))1 Ω∖Γ( ) ] .
Since ( , ( )) is integrable by (2.1) and Γ( ) ↑ Ω, the latter expectation is bounded by for large . Moreover, Γ( ) ∈ ℱ , the martingale property of ( ) , and the fact that

( ) = + on [0, ] yield that [ ( ) ( )1 Γ( ) ] = [ ( ) ( )1 Γ( ) ] = [ ( ( ) + )1 Γ( ) ] .
Since [ ( )] = , the right hand side is dominated by + 2 for large .

Together, we conclude that

[ ( ( ) , (
))] ≤ + 3 ; i.e., ( ) ∈ ( , , + 3 ) for all large . Step 4 of the previous proof then applies as before (recall that ( , ( )) is integrable by (2.1)), except that the changed admissibility of ( ) now results in ( , , + 3 ) ≥ [ ( , , ( ), ( ))].

However, since > 0 was arbitrary, this is the same as (2.15). The argument to extend Theorem 2.4(ii') is analogous.

While we shall see that the relaxation > 0 in (2.15) is harmless for the derivation of the Hamilton-Jacobi-Bellman equation, it is nevertheless interesting to know when the can be omitted; i.e., when is right continuous in . The following sucient condition will be used when we consider state constraints.

Lemma 2.8. Let ( , , ) ∈ D. For each > 0 there is ∈ ( , , + ) such that ( , ; ) ≥ -1 ∧ ( , , + ) -. Let 0 > 0 and assume that for all 0 < ≤ 0 there exists ˜ ∈ ( , , ) such that lim

↓0 { , ( ) ∕ = ˜ , ( ) } = 0
and such that the set

{[ ( , ( )) -( ˜ , ( )) ] + : 0 < ≤ 0 } ⊆ 1 ( ) (2.31)
is uniformly integrable. Then ′ → ( , , ′ ) is right continuous at .

Proof. The monotonicity of ′ → ( , , ′ ) implies that the right limit ( , , +) exists and that ( , , +) ≥ ( , , ); it remains to prove the opposite inequality. Since ′ → ( , , ′ ) is increasing, we have that ( , , ) ∈ D implies ( , , + ) ∕ = ∅ for all ≥ 0. Hence exists; of course, the truncation at -1 is necessary only if

( , , + ) = ∞. Let 0 < ≤ 0 and set := { , ( ) ∕ = ˜ , ( )}, then ( , , ) ≥ ( , , ˜ ) = ( , , ) - [ 1 ( ( , ( )) -( ˜ , ( )) )] ≥ -1 ∧ ( , , + ) -- [ 1 ( ( , ( )) -( ˜ , ( )) ) + ] .
Letting ↓ 0, we deduce by (2.31) that ( , , ) ≥ ( , , +).

Remark 2.9. } .

In the following discussion we assume that, for all ( , ) ∈ S and ∈ , , has continuous paths;

(3.2) ( , ) → , ( ) is continuous in probability, uniformly in ; (3.3) ¯ ( , ) ∕ = ∅ for ( , ) ∈ [0, ] × . ( 3
∖ whenever it is contained in : { , ( )( ), ∈ [ , ]} ⊆ if and only if , ,1 ( )( ) > 0.
We consider the augmented state process ¯ , , (⋅) := ( , (⋅), , , (⋅) )

on the state space ). Now the state constraint may be expressed as [ ( ¯ , ,1 ( ))] ≤ 0 and therefore ¯ ( , ) = ( , , 1, 0) and ¯ ( , ) = ( , , 1, 0); of course, the value 1 may be replaced by any number > 0. Here and in the sequel, we use the notation from the previous section applied to the controlled state process ¯ on × [0, ∞); i.e., we tacitly replace the variable by ( ,

× [0, ∞), then [ ( ¯ , , ( ))] = { , , ( ) ≤ 0} by setting ( , ) := 1 (-∞,0] ( ) for ( , ) ∈ × [0, ∞
)
to dene the set ( , , , ) of admissible controls and the associated value function ( , , , ).

One direction of the dynamic programming principle will be a consequence of the following counterpart of Assumption A.

Assumption Ā. For all ( , ) ∈ S, ∈ ¯ ( , ), ∈ and -a.e. ∈ Ω, there exists

∈ ¯ ( ( ), , ( )( )) such that [ ( , ( )) ℱ ] ( ) ≤ ( ( ), , ( )( );
) .

The more dicult direction of the dynamic programming principle will be inferred from Theorem 2.4 under a right-continuity condition; we shall exemplify in the subsequent section how to verify this condition. (ii) Let Assumption B' hold true for the state process ¯ on × [0, ∞) and let (3.2)(3.4) hold true. Moreover, assume that ( , , 1, 0) = ( , , 1, 0+)

(3.6)
and that

( ′ , ′ ) → ( ′ , ′ ; ) is l.s.c. on [0, 0 ] × for all 0 ∈ [ , ] and ∈ 0 . Then ¯ ( , ) ≥ sup ∈ ¯ ( , ) [ ( , , ( )) ]
(3.7)

for any u.s.c. function

: S → [-∞, ∞) such that ¯ ≥ .
Proof. (i) We may assume that ¯ ( , ) ∕ = ∅ as otherwise ¯ ( , ) = -∞. As in the proof of (2.13), we obtain that

( , ; ) ≤ [ ( , , ( ))
] for all ∈ ¯ ( , ). The claim follows by taking supremum over .

(ii) Again, we may assume that ¯ ( , ) ∕ = ∅ as otherwise the right hand side of (3.7) equals -∞. We set

:= [ , ] × × (0, ∞) × {0}. If ∈ ¯ ( , ), then ( ¯ , , 1 ( )
) = 0 and hence the constant martingale := 0 is contained in ℳ + ,0,( ,1) ( ). Moreover, , ,1 ( ) > 0 and hence ( , ¯

, ,1 ( ), ( )) ∈ for all ∈ [ , ], -a.s. Furthermore, if we dene

( ′ , ′ , ′ , ′ ) := { ( ′ , ′ ), ( ′ , ′ , ′ , ′ ) ∈ -∞, otherwise,
then is u.s.c. on . To see that the third semicontinuity condition in (2.16) is also satised, note that for any

( ′ , ′ , ′ ), ( ′′ , ′′ , ′′ ) ∈ [0, 0 ] × × [0, ∞) and ∈ 0 , | ′ , ′ , ′ ( )-′′ , ′′ , ′′ ( )| ≤ | ′ -′′ | + inf ∈[ ′ , ] ( ′ , ′ ( )) -inf ∈[ ′′ , ] ( ′′ , ′′ ( )) ≤ | ′ -′′ | + sup ∈[0, ] ( ′ , ′ ( ), ′′ , ′′ ( ) )
.

Hence (3.3) implies that ( ′ , ′ , ′ ) → ′ , ′ , ′ ( ) is continuous in probability.
As (-∞, 0] ⊂ ℝ is closed, we conclude by the Portmanteau theorem that

( ′ , ′ , ′ ) → { ′ , ′ , ′ ( ) ∈ (∞, 0] } ≡ ( ′ , ′ , ′ ; ) is u.s.c.
¯ ( , ) = ( , , 1, 0) = ( , , 1, 0+) ≥ [ ( , , ( ), , ,1 ( ), 0 )
] = [ ( , , ( ))].
As ∈ ¯ ( , ) was arbitrary, the result follows.

Remark 3.2. Similarly as in Theorem 2.4(ii), there is also a version of Theorem 3.1(ii) for stopping times taking countably many values. In this case, Assumption B replaces Assumption B', all conditions on the time variable are superuous, and one can consider a general separable metric space .

Application to Controlled Diusions

In this section, we show how the weak formulation of the dynamic programming principle applies in the context of controlled Brownian stochastic differential equations and how it allows to derive the Hamilton-Jacobi-Bellman PDEs for the value functions associated to optimal control problems with expectation or state constraints. As the main purpose of this section is to illustrate the use of Theorems 2.4 and 3.1, we shall choose a fairly simple setup allowing to explain the main points, rather than seeking for maximal generality.

Setup for Controlled Diusions

From now on, we take

= (ℱ ) ∈[0,
] is chosen to be the augmentation of ( -, ≤ ≤ ); in particular, is independent of ℱ .

Consider a closed set ⊆ ℝ and let be the set of all -valued predictable processes satisfying

[ ∫ 0 | | 2 ] < ∞. Then we set = { ∈ : is -predictable } .
This choice will be convenient to verify Assumption B'. We remark that the restriction to -predictable controls entails no loss of generality, in the sense that the alternative choice = would result in the same value function.

Indeed, this follows from a well known randomization argument (see, e.g.,

( ) = + ∫ ( ( ), ) + ∫ ( ( ), ) , ≤ ≤ , ( 4
ℳ ,0 = { ,0 : ∈ } .
In the following, we also use the notation

, := + ,0 .
Lemma 4.1. In the above setup, Assumptions A, ¯ , B, B' are satised and and satisfy (2.16).

Proof. Assumption (B0') is immediate from the denition of . We dene the concatenation of controls by (2.12).

The validity of Assumptions A, Ā and (B1') follows from the uniqueness and the ow property of (4.1); in particular, the control in Assumption A can be dened by ( ′ ) := ( ⊗ ′ ), ′ ∈ Ω, where the concatenated path ⊗ ′ is given by

( ⊗ ′ ) := 1 [0, ( )] ( ) + ( ′ -′ ( ) + ( ) ) 1 ( ( ), ] ( ).
While we refer to [START_REF] Bouchard | Weak dynamic programming principle for viscosity solutions[END_REF]Proposition 5.4] for a detailed proof, we emphasize that the choice of is crucial for the validity of (2.10): in the notation of Assumption B', (2.10) essentially requires that ¯ be independent of ℱ . Let , , , ¯ be as in Assumption B', we show that (B2') holds. Let ¯ where is the rst exit time of ( , , ( ), , ( )) ≥ from .

Proof. In view of Lemmata 2.2 and 4.1, part (i) is immediate from Theorem 2.4(i).

For part (ii) we use the extension of Theorem 2.4(ii') as stated in Corol- Proof of Theorem 4.2. (i) We rst prove the subsolution property. Let be a 2 -function and let ( 0 , 0 , 0 ) ∈ D be such that 0 ∈ (0, ) and ( 0 , 0 , 0 ) is a maximum point of *satisfying

( * -)( 0 , 0 , 0 ) = 0. (4.8)
Assume for contradiction that

( -∂ + * (⋅, , 2
) ) ( 0 , 0 , 0 ) > 0.

Since D = int D by (4.6), there exists a bounded open neighborhood ⊂ Ŝ of ( 0 , 0 , 0 ) such that

-∂ ¯ -, (⋅, ¯ , 2 ¯ ) > 0 on ∩ int D, for all ( , ) ∈ × ℝ , (4.9)
where ¯ ( , ,

) := ( 0 , 0 , 0 ) + ( | -0 | 2 + | -0 | 4 + | -0 | 4 ) .
Viewing (ˆ , ˆ ) as a constant control, it follows from Itô's formula and (4.13

) that ¯ ( , , ) ≤ [ ¯ ( , ˆ , ( ), ˆ , ( )) ] ,
where is the rst exit time of ( , ˆ , ( ), ˆ , ( )) ≥ from . For ( , , ) close enough to ( 0 , 0 , 0 ), this implies that For > 0 small enough, this yields a contradiction to Lemma 4.4(ii).

¯ ( 0 , 0 , 0 ) ≤ [ ¯ ( , ˆ , ( ), ˆ , ( )) ] + (

PDE for State Constraints

In this section, we discuss the Hamilton-Jacobi-Bellman PDE for the state constraint problem (cf. Section 3) in the case where the state process is given by a controlled SDE as introduced in Section 4. To make this work, we clearly need to have ¯ ( , ) ∕ = ∅ for all ( , ) in [0, ] × , which is anyway necessary for the value function ¯ from (3.1) to be nite. However, we need a slightly stronger condition; namely, that we can switch to an admissible control in a measurable way. A particularly simple condition ensuring this, is the existence of an admissible feedback control:

Assumption C. There exists a Lipschitz continuous mapping ˆ :

→ such that, for all ( , ) ∈ [0, ] × , the solution ˆ , of ˆ ( ) = + ∫ ( ˆ ( ), ˆ ( ˆ ( )) ) + ∫ ( ˆ ( ), ˆ ( ˆ ( )) ) , ∈ [ , ] (4
˜ := 1 [ , ] + 1 ( , ] ˆ ( ˆ ),
where ˆ is the solution of (4.16) on [ , ] with initial condition given by ˆ ( ) = , ( ). where is the rst exit time of ( , , ( )) ≥ from .

Proof. Let ˆ , , ( ) be the solution of (4.16) on [ , ] with the (square integrable) initial condition , ( ) at time . Then the claim holds true for ¯ := 1 [ , ] + 1 ( , ] ˆ ( ˆ , , ( ) ).

We have the following counterpart of Lemma 4.4. where is the rst exit time of ( , , ( )) ≥ from .

Proof. In view of Lemma 4.1, part (i) is immediate from Theorem 3.1(i).

Part (ii) follows from Theorem 3.1(ii) via Lemmata 4.7 and 4.8 .

Proof of Theorem 4.6. The result follows from Lemma 4.9 by the arguments in the proof of Theorem 4.2.

Boundary Condition and Uniqueness

In this section, we discuss the boundary condition and the uniqueness for the PDE in Theorem 4.6. We shall work under a slightly stronger condition on our setup.

Assumption D'. The coecients ( , ) and ( , ) in the SDE (4.1) have linear growth in , uniformly in .

We also introduce the following regularity condition, which will be used to prove the comparison theorem. ∈ (0, ). Note that (i) is a condition on the boundary of ∂ ; it can be seen as a variant of the interior cone condition where the cone is replaced by a more general shape. Condition (ii) essentially states that is continuous along at least one curve approaching the boundary point through this shape. In Proposition 4.12 below, we indicate a sucient condition for ¯ * to be of class ℛ( ), which is stated directly in terms of the given primitives. We shall see in its proof that Denition 4.10 is well adapted to the problem at hand.

Before that, let us state the uniqueness result.

  It will be useful in the following to consider for each ∈ [0, ] an auxiliary subltration = (ℱ ) ∈[0, ] of such that , and are -adapted for all ∈ , ∈ and ∈ ℳ ,0 . Moreover, we denote by the set of -stopping times with values in [ , ].

Remark 2 . 3 .

 23 (i) Assumption B' implies Assumption B. Moreover, Assumption A implies (B3'). (ii) Let D := {( , , ) ∈ Ŝ : ( , , ) ∕ = ∅} denote the natural domain of our optimization problem. Then (B3') can be stated as follows: for any ∈ ( , , ) and ∈ ℳ + , ,

  for the -stopping time ′ := 1 Γ + 1 Ω∖Γ .We can now state our weak dynamic programming principle for the stochastic control problem (2.2) with expectation constraint. The formulation is weak in two ways; namely, the value function is replaced by a test function and the constraint level is relaxed by an arbitrarily small constant > 0 (cf. (2.15) below). The exibility of choosing the set appearing below, will be used in Section 3. We recall the set D introduced in Remark 2.3(ii).

( 2 .

 2 29)Note that we have exploited Assumption (B0'), which forces us to use the half-closed interval for the time variable. As a result,

. 4 )

 4 Explicitly, the condition (3.3) means that ( , ) → ( , ) implies sup ∈[0, ] ( , ( ), , ( ) ) → 0 in probability, where we set , ( ) := for < , (⋅, ⋅) denotes the Euclidean metric, and it is implicitly assumed that ∈ for all . We shall augment the state process so that the state constraint becomes a special case of an expectation constraint. To this end, we introduce the distance function ( ) := inf{ ( , ) : ∈ ∖ } for ∈ and the auxiliary process , , ( ) := ∧ inf ∈[ , ] ( , ( )), ∈ [ , ], ∈ [0, ∞).

(3. 5 )

 5 By (3.2), each trajectory { , ( )( ), ∈ [ , ]} ⊆ is compact; therefore,it has strictly positive distance to

Theorem 3 . 1 .

 31 Consider ( , ) ∈ S and a family { , ∈ ¯ ( , )} ⊆ . (i) Let Assumption ¯ hold true and let : S → [-∞, ∞] be a measurable function such that ¯ ≤ . Then [ ( , , ( )) -] < ∞ for all ∈ ¯ ( , ) and ¯ ( , ) ≤ sup ∈ ¯ ( , ) [ ( , , ( )) ] .

  as required. Since any open subset of a Euclidean space is -compact and since (3.4) implies ∩ D = , we can use (3.6) and Theorem 2.4(ii') with = 0 to obtain that

=

  ℝ and let Ω = ([0, ]; ℝ ) be the space of continuous paths, the Wiener measure on Ω, and the canonical process ( ) = . Let = (ℱ ) ∈[0, ] be the augmentation of the ltration generated by ; without loss of generality, ℱ = ℱ . For ∈ [0, ], the auxiliary ltration

[ 3 ,

 3 Remark 5.2]). Let denote the set of × matrices. Given two Lipschitz continuous functions : ℝ × → ℝ , : ℝ × → and ( , , ) ∈ [0, ] × ℝ × , we dene , (⋅) as the unique strong solution of the stochastic dierential equation (SDE)

be a càdlàg version

  of ¯ ( ) := [ ( ˆ , ( ))|ℱ ], ∈ [0, ], where ˆ := 1 [0, ] + 1 ( , ] ¯ . By the same argument as in [3, Proposition 5.4], we deduce from the uniqueness and the ow property of (4.1) and the fact that ¯ is independent of ℱ that [ ( ˆ , ( ))|ℱ ] = [ ( ¯ , , ( ) ( ))|ℱ ] = ¯ [ , ( )]( ) on [ , ]. Hence ¯ = ¯ [ , ( )] on [ , ].

lary 2. 7

 7 with := . Note that ( , , ( ), , ( )) ∈ ⊆ D; in particular, ∩ D = is closed and hence -compact. We can now deduce the PDE for from the dynamic programming principle in the form of Lemma 4.4. Although the arguments are the usual ones, we shall indicate the proof, in particular to show that the relaxation + in (4.7) does not aect the PDE.

≥ 0 .

 0 1 and required to stay in an open set ⊆ ℝ . Note that in this setup, the continuity conditions (3.2) and (3.3) are satised. We shall derive the PDE via Theorem 3.1. The basic idea to guarantee its condition (3.6) about right continuity in the constraint level runs as follows. Consider a control ∈ Then we shall construct a control , satisfying the state constraint, by switching to some admissible control ˆ shortly before , exits . As a result, coincides with on a set of large probability and therefore the reward is similar. Along the lines of Lemma 2.8 we shall then obtain the desired right continuity (cf. Lemma 4.7 below).

Lemma 4 . 9 .

 49 (i) Let ⊆ [0, ] × ℝ be an open neighborhood of a point ( , ) ∈ [0, ]× such that ¯ ( , ) is nite and let : → ℝ be a continuous function such that ¯ ≤ on . For all > 0 there exists ∈ ¯ ( , ) such that ¯ ( , ) ≤ [ ( , , ( )) ] + ,where is the rst exit time of ( , , ( )) ≥ from .(ii) Let Assumptions C and D hold true and let ⊆ [0, ] × be an open neighborhood of ( , ). For any ∈ and any continuous function: → ℝ satisfying ¯ ≥ on , ¯ ( , ) ≥ [ ( , ,( ))] ,

Denition 4 . 10 .

 410 Consider a set ⊆ ℝ and a function : [0, ] × → ℝ. Then is of class ℛ( ) if the following hold for any ( , ) ∈ [0, ) × ∂ : (i) There exist > 0, an open neighborhood of in ℝ and a function ℓ : ℝ + → ℝ such that lim inf →0 -1 |ℓ( )| < ∞ and (4.19) + ℓ( ) + ( ) ∈ for all ∈ ∩ and ∈ (0, ).

  20) we mean that if : ℝ + → ℝ is any function of class ( ), then there exists > 0 such that + ℓ( ) + ( ) ∈ for all

Proposition 4 . 11 .

 411 Let be continuous and let Assumptions C and D' hold true. Then ¯ has quadratic growth and the boundary condition is attained in the sense that ¯ * ( , ⋅) ≤ and ¯ * ( , ⋅) ≥ on .

  ( , ) ∈ S, ∈ , ∈ [ , ], ¯ ∈ and Γ ∈ ℱ .

	Assumption B. (B1) There exists a control ˜ ∈	such that
		˜ , (⋅) = , (⋅)	on [ , ] × (Ω ∖ Γ);	(2.6)
		˜ , (⋅) = ¯ , , ( ) (⋅)	on [ , ] × Γ;	(2.7)
	[	( ˜ , ( )) ℱ	]	≥ ( , , ( ); ¯ )	on Γ.
						.5)
	Next, we state two variants of the assumptions for the converse direction
	of the dynamic programming principle; we shall comment on the dierences
	in Remark 2.5 below. In the rst variant, the intermediate time is deter-
	ministic; this will be enough to cover stopping times with countably many
	values in Theorem 2.4(ii) below. We recall the notation	[ ] from (2.4).

Let

  on Ω and so Lemma 2.2 yields that ( ) ∈ ( , , + ).4. -Optimality. We may assume that either the positive or the negative

			.27)
	Combining (2.26) and (2.27), we have (
	part of	( , , ( ), ( )) is integrable, as otherwise our claim (2.15) is
	trivial by (2.17). Using the denition (2.2) of	as well as (2.23) and (2.24),
	we have that

( ) , ( )) ≤ ( ) ( )

  The integrability assumption (2.31) is clearly satised if is bounded. In the general case, it may be useful to consider the value function

	for a truncated function	in a rst step.
	3 Application to State Constraints
	We consider an open set	⊆	:= ℝ and study the stochastic control
	problem under the constraint that the state process has to stay in	. Namely,
	we consider the value function
	¯ ( , ) := sup	( , ; ), ( , ) ∈ S,	(3.1)
				∈ ¯ ( , )
	where
	¯ ( , ) :=	{	∈	:

, ( ) ∈ for all ∈ [ , ], -a.s.

  ℝ → ℝ is said to have subquadratic growth if ℎ( )/| | 2 → 0 as | | → ∞.This will be used to obtain the semicontinuity properties(2.16).Furthermore, we take ℳ ,0 to be the family of all càdlàg martingales which start at 0 and are adapted to . By the independence of the incre-

	where ℎ : ments of	, we see that	∈ ℳ ,0 is then also a martingale in the ltration
	and that	= 0 for ≤ . For ∈ , we have	, ( ) ∈ 2 (ℱ , )
	and hence (2.4) is satised. It will be useful to express the martingales
	as stochastic integrals. Let	denote the set of ℝ -valued -predictable
	processes	such that	∫	0 | | 2 < ∞ -a.s. and such that
					,0 (⋅) :=	∫ ⋅	⊤
	is a martingale ( ⊤ denotes transposition). Then the Brownian representation
	theorem yields that
					.1)
	where we set	, ( ) = for ≤ . As , ( ) is square integrable for any
	∈ , (2.1) is satised whenever
					and	have quadratic growth,	(4.2)
	which we assume from now on. In addition, we also impose that
		{	is l.s.c. and -has subquadratic growth,
			is u.s.c. and + has subquadratic growth,	(4.3)

  The rest of this subsection is devoted to the proof of Theorem 4.2. We rst state a version of Theorem 2.4 which is suitable to derive the PDE.Lemma 4.4. (i) Let be an open neighborhood of a point ( , , ) ∈ D such that ( , , ) < ∞ and let : → ℝ be a continuous function such that ≤ on . For all > 0 there exist ( , ) ∈ × such that

	( , , ) ≤	[	( , , ( ), , ( )) ]	+	and	, ( ) ≥ ( , ( )),
	where is the rst exit time of ( , , ( ), , ( )) ≥ from .
	(ii) Let	be an open neighborhood of a point ( , , ) ∈ int D such that
	⊆ D and let ( , ) ∈	× . For any continuous function :	→ ℝ
	satisfying ≥ on and for any > 0,
			( , , + ) ≥	[	( , , ( ), , ( )) ] ,	(4.7)
					The last assertion of (B2') is clear by the
	denition of ℳ ,0 . As already mentioned in Remark 2.3, Assumption (B3')
	follows from Assumption A and Assumption B follows from Assumption B'.

  [START_REF] Bouchard | Optimal control under stochastic target constraints[END_REF] as → 0,

	which, by (4.12), (4.14) and (4.15), leads to
	( , ,	+ ) ≤	[	( , ˆ	, ( ), ˆ	,	( )) ]	-+ (1).

  .16) satises ˆ , ( ) ∈ for all ∈ [ , ], -a.s.

	Lemma 4.7. Let Assumptions C and D hold true. Then ( , , 1, 0+) =
	( , , 1, 0) for all ( , ) ∈ [0, ] × .
	Proof. For > 0, let	∈ ( , , ) be as in Lemma 2.8. Then the process
	, , dened in (3.5) satises	, ,1 ( ) > 0 outside of a set of measure at
	most . It follows that we can nd	∈ (0, 1 ∧ ( )) such that the set
	:= { , ,1 ( ) ≤ } satises [ ] ≤ 2 . Let	denote the rst time
	when	, ,1 reaches the level	and set
	The following is a simple condition guaranteeing the uniform integrability
	required in (2.31).

  Since the paths of , ,1 are nonincreasing, we have , we check that { ( , ( )), ∈ } is uniformly integrable. This is trivial if is bounded. Otherwise, Assumption D yields that the coecients ( , ) and ( , ) have uniformly linear growth in , and of course they are uniformly Lipschitz in as they are jointly Lipschitz. Thus { , ( ), ∈ } is bounded in for any nite and the uniform integrability follows from the quadratic growth assumption (4.2) on . It remains to apply Lemma 2.8. Lemma 4.8. Let Assumption C hold true and let be an open neighborhood of ( , ) ∈ [0, ] × . For all ∈ there exists ¯ ∈ such that

	lim ↓0	[ ˜

, ( ) ∕ = , ( )] ≤ lim ↓0 [ ≤ ] = lim ↓0 [ ] = 0. Next1 [ , ] + ¯ 1 ( , ] ∈ ¯ ( , ),

Research

supported by Swiss National Science Foundation Grant PDFM2-120424/1.

Next, we check that satises (2.16); i.e., that is l.s.c. For xed ∈ , ( , ) → , ( ) is 2 -continuous. Hence the semicontinuity from (4.3) and Fatou's lemma yield that ( , ) → [ ( , ( )) + ] is l.s.c. By the subquadratic growth from (4.3), we have that { ( , ( )) -: ( , ) ∈ } is uniformly integrable whenever ⊂ S is bounded, hence the semicontinuity of also yields that ( , ) → [ ( , ( )) -] is u.s.c. As a result, is l.s.c.

The same arguments show that also satises (2.16).

PDE for Expectation Constraints

In this section, we show how to deduce the Hamilton-Jacobi-Bellman PDE for the optimal control problem (2.2) with expectation constraint from the weak dynamic programming principle stated in Theorem 2.4. Given a suitably dierentiable function ( , ) on [0, ] × ℝ , we shall denote by ∂ its derivative with respect to and by and 2 the Jacobian and the Hessian matrix with respect to , respectively.

In the context of the setup introduced in the preceding Section 4.1, the Hamilton-Jacobi-Bellman operator is given by ( , , ) := inf ) .

Since the set × ℝ is unbounded, may be discontinuous and viscosity solution properties need to be stated in terms of the upper and lower semicontinuous envelopes of , * ( , , ) := lim sup

The value function dened in (2.2) may also be discontinuous and so we introduce * ( , , ) := lim sup

Here int D denotes the parabolic interior; i.e, the interior of D ∖ { = } in Ŝ, where { = } := {( , , ) ∈ Ŝ : = }. Moreover, we shall denote by D the closure of D. The main result of this subsection is the following PDE.

Theorem 4.2. Assume that is locally bounded on int D.

(i) The function * is a viscosity subsolution on

(ii) The function * is a viscosity supersolution on int D of

We shall not discuss in this generality the boundary condition and the validity of a comparison principle. In the subsequent section, these will be studied in some detail for the case of state constraints. We also refer to [START_REF] Bouchard | Optimal control under stochastic target constraints[END_REF] for the study of the boundary conditions in a similar framework and for an application.

Remark 4.3. We observe that the domain of the PDE in Theorem 4.2 is not given a priori; it is itself characterized by a control problem: if we dene

then

where * is the upper semicontinuous envelope of on [0, ) × ℝ . In particular, int D ∕ = ∅ since is locally bounded from above. In fact, in the present setup, we also have

where * is the lower semicontinuous envelope of on [0, ] × ℝ , and hence D ⊆ int D.

] .

For ( , , ) close enough to ( 0 , 0 , 0 ), this implies that

] -

This contradicts Lemma 4.4(i)

> 0 small enough.

(ii) We now prove the supersolution property. Let be a

-function

and let ( 0 , 0 , 0 ) ∈ int D be such that ( 0 , 0 , 0 ) is a minimum point of *satisfying ( * -)( 0 , 0 , 0 ) = 0.

(4.12)

Assume for contradiction that

)

Then there exist (ˆ , ˆ ) ∈ × ℝ and a bounded open neighborhood of

where

) .

Note that This assumption holds in particular if the control domain is bounded.

Remark 4.5. Assumption C implies that ¯ is locally bounded from below and Assumption D implies that ¯ is locally bounded from above.

Next, we introduce the notation for the PDE related to the value function ¯ from (3.1). The associated Hamilton-Jacobi-Bellman operator is given by ¯ ( , ,

where the Dynkin operator is dened by

Similarly as above, we introduce the semicontinuous envelopes

We can now state the Hamilton-Jacobi-Bellman PDE; the boundary condition is discussed in Proposition 4.11 below. Theorem 4.6. Assume that ¯ is locally bounded on [0, ) × .

, 2 ) ≤ 0. (ii) Under Assumptions C and D, the function ¯ * is a viscosity supersolution on [0, ) × of

The proof is given below, after some auxiliary results. We rst verify the right-continuity condition (3.6) for the value function ( , , , ) introduced in Section 3. We conclude this section with a sucient condition ensuring that ¯ * is of class ℛ( ); the idea is that the volatility should degenerate so that the state process can be pushed away from the boundary. We remark that conditions in a similar spirit exist in the previous literature (e.g., [START_REF] Katsoulakis | Viscosity solutions of second order fully nonlinear elliptic equations with state constraints[END_REF][START_REF] Ishii | A class of stochastic optimal control problems with state constraint[END_REF]). Proposition 4.12. Assume that ¯ * is nite-valued on [0, ] × and that , and satisfy the following conditions: (i) There exists a 1 -function , dened on a neighborhood of ⊆ ℝ , such that is locally Lipschitz continuous and > 0 on , = 0 on ∂ , < 0 outside .

Assume in addition that

(ii) There exists a locally Lipschitz continuous mapping ˇ : ℝ → such that for all ∈

there exist an open neighborhood of and > 0 satisfying ( , ˇ ( )) ⊤ ( ) ≥ and ( , ˇ ( )) = 0 for all ∈ ∩ and ∈ .

which is strictly positive for > 0 small enough. This implies (4.20). Consider ( , ) ∈ [0, ) × close to ( , ). For > 0 small enough, we can nd

Recall the degeneracy condition in (4.23). Setting

we obtain that

)

Recalling that ˇ ( ) → ˇ ( ) as → , this leads to

We recall that ¯ admits a (unique) continuous extension to [0, ] × under the stated conditions, so the assertion makes sense.

Proof. The easier direction of the dynamic programming principle for can be obtained as above, so the result of Lemma 4.

where * denotes the lower semicontinuous envelope of and the last equality is due to Proposition 4.11. It follows that all these functions coincide.

A Comparison for State Constraint Problems

In this appendix we provide, by adapting the usual techniques, a fairly general comparison theorem for state constraint problems which is suitable for the applications in Proposition 4.11 and Corollary 4.13.

In the following, ℋ denotes a continuous mapping from ℝ × ℝ × to ℝ which is nonincreasing in its third variable, is a given open subset of ℝ , and > 0 is a xed constant. We consider the equation

and the following condition on ℋ.

Assumption E. There exists > 0 such that lim inf

Theorem A.1. Let Assumption E hold true. Let 1 be an u.s.c. viscosity subsolution on and let 2 be an l.s.c. viscosity supersolution on of (A.1). If 1 and 2 have polynomial growth on and if 2 is of class ℛ( ), then

Remark A.2. Our result also applies to the equation

provided that ℋ is homogeneous of degree one with respect to its second and third argument, as it is the case for the Hamilton-Jacobi-Bellman operators in the body of this paper. Indeed, 1 is then a subsolution of (A.2) if and only if ( , ) → 1 ( , ) is a subsolution of (A.1), and similarly for the supersolution. Further extensions could also be considered but are beyond the scope of this paper.

Proof of Theorem A.1. Assume that 2 ≥ 1 on { } × . Let ≥ 1 and > 0 be such that 1 ( ,

Here > 0 is a xed constant which is large enough to ensure that ( , ) :=

with ℓ and given for 0 as in the statement of the Denition 4.10, and > 0. Note that (A.5), the assumption that 2 satises (4.22), and (A.3) imply that Φ ( , , , ) ≥ Φ ( 0 , 0 , 0 + ( -1 ), 0 + ℓ( -1 ) )

= + (1) as → ∞.

(A.6)

Recalling the growth condition on 1 , 2 and the denition of , it follows that, after passing to a subsequence, ( , , , ) converges to some

where (A.6) was used in the last step. After passing to a subsequence, we deduce that ( , , , ) → ( 0 , 0 , 0 , 0 ),

= + ( -1 ) + ( -1 ), = + ℓ( -1 ) + ( -1 ).

(A.9)

Since ( 0 , 0 ) ∈ [0, ) × ∂ , it follows from (4.20), (4.21) and (A.9) that ( , ) ∈ [0, ) × for large enough.

) .

In view of the sub-and supersolution properties of 1 and 2 , the fact that ( , ) ∈ [0, ) × for large, and Assumption E, we deduce that

) .

By the denitions of and , it follows that

) .

Recalling (A.7)(A.9), letting → ∞ leads to

which, by (4.19) and the denition of in (A.4), implies

( 1 -2 -2 )( 0 , 0 ) ≤ 2 ( 0 , 0 )

after letting → 0. Since > 0 has been chosen so that ≤ 0 on [0, ]×ℝ , this contradicts (A.3).

Case 2: 0 ∈ . This case is handled similarly by using After taking a subsequence, the corresponding sequence of maximum points ( , , , ) ≥1 again converges to ( 0 , 0 , 0 , 0 ), so that , ∈ for large enough. The rest of the proof follows the same arguments as in Case 1.

Lemma A.3. Under Assumption D', the operator ¯ dened in (4.17


Arnaud Blouin
email: arnaud.blouin@inria.fr

Brice Morin
email: brice.morin@sintef.no

Olivier Beaudoux
email: olivier.beaudoux@eseo.fr

Grégory Nain
email: gregory.nain@inria.fr

Patrick Albers
email: patrick.albers@eseo.fr

Jean-Marc Jézéquel
email: jezequel@irisa.fr

Combining Aspect-Oriented Modeling with Property-Based Reasoning to Improve User Interface Adaptation

Keywords: MDE, user interface, context, adaptation, aspect, runtime, malai ACM Classification H.5.2 Information Interfaces and Presentation: User Interfaces-Theory and methods, User Interface Management Systems (UIMS), D.2.1 Software Engineering: Requirements/ Specifications-Methodologies, H.1.0 Information Systems: Models and Principles-General

published or not. The documents may come   L'archive ouverte pluridisciplinaire

INTRODUCTION

The number of platforms having various interaction modalities (e.g., netbook and smart phone) unceasingly Author version increases over the last decade. Besides, user's preferences, characteristics and environment have to be considered by user interfaces (UI). This triplet <platform, user, environment>, called context1 [START_REF] Calvary | A unifying reference framework for multi-target user interfaces[END_REF], leads user interfaces to be dynamically (i.e. at runtime) adaptable to reflect any change of context. UI components such as tasks and interactions, enabled for a given context but disabled for another one, cause a wide number of possible adaptations. For example, [START_REF] Fleurey | A domain specific modeling language supporting specification, simulation and execution of dynamic adaptive systems[END_REF] describes an airport crisis management system that leads to 1,474,560 possible adaptations. Thus, an important challenge is to support UI adaptation of complex systems. This implies that dynamic adaptations must be performed in a minimal time, and respecting usability.

The contribution of this paper is to propose an approach that combines aspect-oriented modeling (AOM) with property-based reasoning to tackle the combinatorial explosion of UI adaptations. AOM approaches provide advanced mechanisms for encapsulating crosscutting features and for composing them to form models [START_REF]International Workshop on Aspect-Oriented Modeling[END_REF]. AOM has been successfully applied for the dynamic adaptation of systems [START_REF] Morin | Taming Dynamically Adaptive Systems with Models and Aspects[END_REF]. Property-based reasoning consists in tagging objects that compose the system with characterizing properties [START_REF] Fleurey | A domain specific modeling language supporting specification, simulation and execution of dynamic adaptive systems[END_REF]. At runtime, these properties are used by a reasoner to perform the adaptation the best suited to the current context. Reasoning on a limited number of aspects combined with the use of properties avoids the combinatorial explosion issue. Although these works tackle system adaptation at runtime, they do not focus on the dynamic adaptation of UIs. Thus, we mixed these works with Malai, a modular architecture for interactive systems [START_REF] Blouin | Improving modularity and usability of interactive systems with Malai[END_REF], to bring complex and dynamic user interface adaptations under control. We have applied our approach to EnTiMid, a middleware for home automation.

The paper is organized as follows. The next section introduces background research works used by our ap-proach. Then, the process to create an adaptive UI using our approach is explained. Next, the adaptation process that is automatically executed at runtime is detailed. Following, our approach is evaluated through EnTiMiD, a middleware for house automation. The paper ends with the related work and the conclusion.

BACKGROUND

The work presented in this paper brings an interactive system architecture and a software engineering approach together. Thus, this section starts with the presentation of the Malai architecture. The software engineering approach applied to Malai to allow complex UI adaptations at runtime is then introduced.

The Malai Architecture

The work presented in this paper is based on Malai, an architectural model for interactive systems [START_REF] Blouin | Improving modularity and usability of interactive systems with Malai[END_REF]. In Malai a UI is composed of presentations and instruments (see Figure 1). A presentation is composed of an abstract presentation and a concrete presentation. An abstract presentation is a representation of source data created by a Malan mapping (link ①). A concrete presentation is the graphical representation of the abstract presentation. It is created and updated by another Malan mapping (link ②) [START_REF] Blouin | Malan: A mapping language for the data manipulation[END_REF]. An interaction consumes events produced by input devices (link ③). Instruments transform input interactions into output actions (link ④). An action is executed on the abstract presentation (link ⑤); source data and the concrete presentation are then updated throughout a Malan mapping (link ⑥). Malai aims at improving: 1) the modularity by considering presentations, instruments, interactions, and actions, as reusable first-class objects; 2) the usability by being able to specify feedback provided to users within instruments, to abort interactions, and to undo/redo actions. Malai is well-suited for UI adaptation because of its modularity: depending on the context, interactions, instruments, and presentations, can be easily composed to form an adapted UI. However, Malai does not provide any runtime adaptation process. The next section introduces the research work on dynamic adaptive system that has been applied to Malai for this purpose.

Data

Dynamically Adaptive Systems

The DiVA consortium proposes an adaptation metamodel to describe and drive the adaptation logic of Dynamically Adaptive Systems (DAS) [START_REF] Fleurey | A domain specific modeling language supporting specification, simulation and execution of dynamic adaptive systems[END_REF]. The core idea is to design DAS by focusing on the commonalities and variabilities of the system instead of analyzing on all the possible configurations of the system. The features of the system are refined into independent fragments called aspect models. On each context change, the aspect models well adapted to the new context are selected and woven together to form a new model of the system. This model is finally compared to the current model of the system and a safe migration is computed to adapt the running system [START_REF] Morin | Taming Dynamically Adaptive Systems with Models and Aspects[END_REF].

The selection of the features adapted to the current context is performed by a reasoning mechanism based on multi-objective optimization using QoS Properties.

QoS properties correspond to objectives that the reasoner must optimize. For example, the properties of the system described in [START_REF] Fleurey | A domain specific modeling language supporting specification, simulation and execution of dynamic adaptive systems[END_REF] are security, CPU consumption, cost, performances, and disturbance. The importance of each property is balanced depending on the context. For instance, if the system is running on battery, minimizing CPU consumption will be more important than maximizing performances. The developer can specify the impact of the system's features on each property. For example, the video surveillance feature highly maximizes security but does not minimize CPU consuming. The reasoner analyzes these impacts to select features the best suited to the current context.

If DiVA proposes an approach that tames dynamic adaptations of complex systems, it lacks at considering UI adaptations. The following sections describe the combined use of Malai and DiVA to bring adaptations of complex interactive systems under control.

CONCEPTION PROCESS

This section describes the different steps that developers have to perform during the conception of adaptable UIs. The first step consists in defining the context and the action models. Then a mapping between these two models can be defined to specify which context elements disable actions. The last step consists in defining the presentations and the instruments that can be selected at runtime to compose the UI.

All these models are defined using Kermeta. Kermeta is a model-oriented language that allows developers to define both the structure and the behavior of models [START_REF] Muller | Weaving executability into object-oriented meta-languages[END_REF]. Kermeta is thus dedicated to the definition of executable models. All the properties of the current context should be maximized. But adapting UIs is a multiobjective problem where all objectives (i.e. QoS properties) cannot be maximized together; a compromise must be found. For example, a developer may prefer productivity to the aesthetic quality of UIs even if maximizing both would be better. Values associated with properties aim at balancing these objectives.

Our approach does not provide predefined properties. Developers add their own properties on the UI components and the context. The unique constraint for the developers is to reuse in the context model properties defined in UI components and vice versa. Indeed, properties of the current context are gathered at runtime to then select the most respectfully UI components towards these properties. The efficiency of the reasoner thus depends on the appropriate definition of properties by the developers.

Actions Definition

Actions are objects created by instruments. Actions modify the source data or parameters of instruments.

The main difference between actions and tasks, such as CTT tasks [START_REF] Paternò | ConcurTaskTrees: A diagrammatic notation for specifying task models[END_REF], is that the Malai's action metamodel defines a life cycle composed of methods do, canDo, undo, and redo. These methods, that an action model must implement, bring executability to actions. Method canDo checks if the action can be executed. Methods do, undo, and redo respectively executes, cancels, and re-executes the action. An action is also associated to a class which defines the attributes of the action and relations with other actions.

Listing 2. Excerpt of nurse actions

Listings 2 defines an excerpt of the home automation action model in Kermeta. Abstract action NurseAction (line 1) defines the common part of actions that nurses can perform. Action AddNurseVisit (line 3) is a nurse action that adds an event into the nurse calendar (see method do line 12). Method canDo checks if the event can be added to the calendar (line 9). Methods undo and redo respectively remove and re-add the event to the calendar (lines 15 and 18). Action CallEmergency-Service in another nurse action that calls the emergency service (line 23).

Mapping Context Model to Action Model

Actions can be disabled in certain contexts. For instance elderly people cannot perform actions specific to the nurse. Thus, action models must be constrained by context models. To do so we use Malan, a declarative mapping language [START_REF] Blouin | Malan: A mapping language for the data manipulation[END_REF]. Because it is used within the Malai archetecture, the Malan language has been selected. Context-to-action models consists of a set of Malan expressions. For instance, one of the constraints of the home automation system states that elderly people cannot perform nurse actions. The Malan expression for this constraint is:

E l d e r l y P e r s o n -> ! N u r s e A c t i o n

where NurseAction means that all actions that inherit from action NurseAction are concerned by the mapping.

Another constraint states that nurses can call ambulances only if the house has a phone line. The corresponding Malan expression is:

House [ ! phoneLine ] -> ! C a l l E m e

r g e n c y S e r v i c e

where the expression between brackets (i.e., !phone-Line) is a predicate that uses attributes and relations of the corresponding class of the context (i.e. House in the example) to refine the constraint.

By default all the actions are enabled. Only actions targeted by context-to-action mappings can be disabled: on each context change, mappings are re-evaluated to enable or disable their target action.

Presentation Definition

Developers can define several presentations for the same UI: several presentations can compose at runtime the same UI to provide users with different viewpoints on the manipulated data; defining several presentations allows to select at runtime the presentations the best suited to the current context. For instance, the calendar that the nurse uses to add visits can be presented through two presentations: 1) a 2D-based presentation that displays the events of the selected month or week; 2) a list-based presentation that shows the events into a list widget. ). An Agenda has a name, contains Event and Date instances. An event has a name, a place, a description, a starting and an ending Timeslot instances. A time-slot specifies the hour and the minute. A date defines its day, month and year.

1 c l a s s Agenda { 2 a t t
The concrete presentation defines the graphical representation of the nurse agenda (see Listing 4). The graphical representation of agendas (class AgendaUI ) contains representations of days, events, and time-slot lines (respectively classes DayUI, EventUI and Line-HourUI ). These representations have coordinates x and y. Classes DayUI and EventUI also specify their width and height. An agenda has two handlers associated to the selected event. These handlers are used to change the time-slot of the selected event.

Similarly to context models, presentations can be tagged with QoS properties. These properties provide context reasoner with information about, for example, the easiness of use or the size of the presentation. For instance, the 2D-based and list-based presentations have characteristics well-suited for some platforms and users. Listing 4 shows the QoS properties of the 2D-based presentation defined as annotations: the 2D-based presentation optimizes the aesthetic quality (property aesthetic-Quality "high") but not space (property space "low"). By contrast, the list-based presentation optimizes space to the detriment of the aesthetic quality. While properties specified on contexts define objectives to optimize at runtime, properties on presentations declare characteristics used to select appropriated presentations depending on the current context and its objectives. For instance, if the current context states that the the aesthetic quality must be highly considered, the 2D-based presentation will be selected.

Instrument Definition

Instruments transform input interactions into output actions. Instruments are composed of links and of a class model. Each link maps an interaction to a resulting action. Instrument's class model defines attributes and relations the instrument needs. Widgets handled by instruments and that compose the UI are notably defined into the class model of instruments.

VisitTypeSelector is an instrument operating on the nurse agenda. This instrument defines the type of visit to add to the agenda. The selection of the type of visit can be performed using different widgets: several toggle buttons (one of each visit type) or a list can be used. While toggle buttons are simpler to use than a list (a single click to select a button against two clicks to select an item of a list), lists are usually smaller than a set of toggle buttons. The choice of using such or such widgets thus depends on the current context: if space is a prior objective, list should be privileged; otherwise, toggle buttons should be selected. One of the contributions of our work consists of being able to choose the best suited interaction for a link at runtime: while defining instruments, developers can let interactions undefined. Interactions and widgets are automatically chosen and associated to instruments at runtime depending on the current context. For instance, Figure 2(a) describes the model of instrument VisitTypeSelector as defined by developers. This model is composed of an incomplete link that only specifies the produced action SetVisitType; the way this action is performed let undefined. The class model of this instrument only defines a class corresponding to the instrument (class VisitTypeSelector ). This class model will also be completed at runtime. Figure 2(b) corresponds to the model of Figure 2(a) completed at runtime. Toggle buttons have been chosen to perform action SetVisitType. The interaction corresponding to the click on buttons (interaction Button-Pressed ) is added to complete the link. A set of toggle buttons (class ToggleButton) is also added to the class model. This interaction and these widgets come from a predefined aspect encapsulating them. We defined a set of aspects for WIMP 2 interactions (i.e. based on widgets) that can automatically be used at runtime to complete instrument models. Figure 2(c) corresponds to another completed model. This time, a list has been chosen. Interaction Item-Changed, dedicated to the handle of lists, completes the link. A list widget (class List) has been also added to the class model. This widget and its interaction also come from a predefined aspect. Figure 3 presents an example of the instrument Times-lotSetter completed with interactions. This instrument changes the time-slot of events of the nurse agenda (action SetTimeslotEvent). Figure 3(a) shows this instrument completed with a drag-and-drop interaction (DnD) and handlers. Handlers surround the selected event. When users drag-and-drop one of these handlers the time-slot of the event is modified. This interaction 2 "Windows, Icons, Menus and Pointing device" and these handlers were encapsulated into an aspect defined by the developer.

Figure 3(b) shows another aspect defined by the developer for instrument TimeslotSetter : when the current platform supports bi-manual interactions, such as smartphones or tabletops, time-slot setting can be performed using such interactions instead of using a DnD and handlers. Such flexibility on interactions and widgets is performed using QoS properties. Widgets and interactions are tagged with properties they maximize or minimize. Widgets are also tagged with properties corresponding to simple data type they are able to handle. For in-stance, the toggle button widget is tagged with four properties: property simplicity high means that toggle buttons are simple to use; property space low means that toggle buttons do not optimize space; properties enum and boolean mean that toggle buttons can be used to manipulate enumerations and booleans. At runtime, these properties are used to find widgets appropriate to the current context.

ADAPTATION PROCESS AT RUNTIME

This section details the adaptation process at runtime. This process begins when the current context is modified. The context reasoner analyzes the new context to determine actions, presentations, interactions, and widgets that will compose the adapted UI. The weaver associates WIMP interactions and widgets to instruments. The UI composer adapts the UI to reflect the modifications.

Reasoning on Context

The context reasoner is dynamically notified about modifications of the context. On each change, the reasoner follows these different steps to adapt actions, presentations, instruments, interactions, and widgets, to the new context: The process of enabling and disabling actions (line 2 of Algorithm 1) is performed thanks to the contextto-action mapping: if the change of context concerns a mapping, this last is re-evaluated. For instance with the home automation example, when the user switches from the nurse to the elderly person, mappings described in the previous section are re-evaluated. Actions that inherit from NurseAction are then disabled. Once actions are updated, instruments are checked: instrument's links that use the disabled, respectively enabled, actions are also disabled, respectively enabled (lines 3 and 4). Links using interactions that cannot be performed anymore are also disabled (line 5). For example, vocal-based interactions can only work on platforms providing a microphone. Instruments with no more link enabled are disabled (line 6).

foreach Context
Presentations that will compose the UI can now be selected (line 7). This process selects presentations by aligning their properties with those of the current context. In the same way, WIMP interactions and widgets are selected for instruments (line 8) using properties. These selections can be performed by different kind of optimization algorithms such as genetic algorithms or Tabu search. These algorithms are themselves components of the system. That allows to change the algorithm at runtime when needed.

We perform this reasoning on properties using the genetic algorithm NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: Nsga-ii[END_REF]. Genetic algorithms are heuristics that simulate the process of evolution. They are used to find solutions to optimization problems. Genetic algorithms represent a solution of a problem as a chromosome composed of a set of genes. Each gene corresponds to an object of the problem. A gene is a boolean that states if its corresponding object is selected. For example with our UI adaptation problem, each gene corresponds to a variable part of the UI (the nurse actions, the toggle button aspect, the list aspect, the different presentations, etc.). The principle of genetic algorithms is to randomly apply genetic operations (e.g. mutations) on a set of chromosomes. The best chromosomes are then selected to perform another genetic operations, and so on. The selection of chromosomes is performed using fitness functions that maximize or minimize objectives. In our case, objectives are properties defined by the developer. For instance readability is an objective to maximize. For each chromosome its readability is computed using the readability value of its selected gene:

f readability (c) = n i=1 prop readability (c i )x i
Where f readability (c) is the fitness function computing the readability of the chromosome c, c i is the gene at the position i in the chromosome c, prop readability (c i ) the value of the property readability of the gene c i , and x i the boolean value that defines if the gene c i is selected. For example :

f readability (001100111001011) = 23
The fitness functions are automatically defined at design time from the properties used by the interactive system.

Chromosomes that optimize the result of fitness functions are selected. Constraints can be added to genetic algorithm problems. In our case a constraint can state that the gene corresponding to the calling emergency service action can be selected only if there is a line phone in the house. When genetic algorithms are stopped, they provide a set of solutions that tend to be the best ones.

Weaving Aspects to Complete Models

Once interactions and widgets are selected, they must be associated with their instruments. To do so, we reuse the process proposed in the DiVA project to weave aspects with models. An aspect must specify where its content (in our case the interaction and possible widgets and components) must be inserted: this is the role of the pointcut. In our case pointcuts target instruments and more precisely an action and the main class of the instrument. An aspect must also define its composition protocol that describes how to integrate the content of the aspect into the pointcut.

Composing and Updating the User Interface

The goal of the UI composer is two-fold: 1) It composes the selected presentations and widgets at startup. 2) Once composed, the UI composer updates the UI on context changes if necessary. Because modifications of the UI must be smooth enough not to confuse the users, the UI must not be recomposed from scratch using 1). The existing UI must be updated to minimize graphical changes and to keep usability.

EVALUATION

Our proposal is based on two hypotheses: 1) it tames the combinatorial explosion of complex interactive systems adaptations; 2) adaptations performed using our proposal are well adapted to the current context. We evaluated these two hypotheses by applying our proposal to EnTiMid, a middleware for home automation. Each component of the UI of EnTiMid is developed with the Kermeta implementation of Malai. At the end of the conception time, executable models are compiled as OSGi components [START_REF]OSGi service platform core specification[END_REF] to run on the top of DiVA. The use of OSGi permits instruments, actions, and presentations to be easily enabled and disabled at runtime.

The experiments described in this section have been performed on Linux using a laptop with a Core2Duo at 3.06GHz and 4Gb of RAM. Each result presented below is the average result of 1000 executions.

EnTiMid: a Middleware for Home Automation

EnTiMid is a middleware for home automation. It notably addresses two issues of the home automation domain, by providing a sufficient level of abstraction. The first issue is about interoperability of devices. Built by many manufacturers, devices are often not compatible with one another because of their communication protocol. EnTiMid offers a mean to abstract from these technical problems and consider only the product's functionalities. The second issue is about adaptation. Changes in the deployed peripherals or in the user's habits imply changes in the interactive system dealing with the home. Moreover, many people with different skills will have to interact with the interactive system, and the UI must adapt to the user. Considering models at runtime, En-TiMid permits such dynamic adaptation. Figure 4 shows a part of the EnTiMid's UI that manages home devices such as heaters, shutters, and lights. A possible adaptation is if the home does not have any shutter, related actions will be disabled and the UI adapted to not provide the shutter tab.

Hypothesis 1: Combinatorial explosion taming

We evaluate this hypothesis by measuring the adaptation time of five versions of EnTiMid, called v 1 to v 5 . These versions have an increasingly level of complexity, respectively around 0.262, 0.786, 4.7, 42.4, and 3822 millions of configurations. These different levels of complexity have been obtained by removing features from version v 5 . A configuration defines which components of the interactive system are enabled or disabled.

The adaptation time starts after a change of context and ends when the UI is adapted accordingly. The adaptation time is composed of: the time elapsed to select the optimal possible configuration in a limited time; the time elapsed to reconfigure the interactive system and its UI. That because the parameters of the reasoner (e.g. the number of generations, the size of the population) are automatically modified in function of the complexity of the system to run between 500 and 1000ms. Figure 5 also shows that the configuration time (i.e. when the system and its UI are modified) remains constant around 200ms. That brings the full adaptation time to around 1 second for the most complex version of EnTiMid.

Hypothesis 2: Adaptations quality

Finding a configuration in a limited time makes sense only if the configuration found is of good quality. Thus, we now evaluate the quality of the configurations found by the genetic reasoner in the limited time-slots described above. We compared these configurations with the optimal configurations. Optimal configurations are configurations giving the best results using the fitness functions. These optimal configurations have been computed by an algorithm exploring all the solutions. Such computations took 4.5s, 10s, 480s, and 7200s for respectively v 1 , v 2 , v 3 , and v 4 . We were not able to compute the optimal solutions of v 5 due to time and resource constraints. In average the reasoner always found optimal configurations for every version of EnTiMid tested. However, the performance slightly decreases while the complexity increases. For example with v 4 , several adaptations among the 1000 performed did not find some of the optimal configurations. This result is normal since we cannot obtain same quality results in the same limited time for problems whose complexity differ.

We can state that the genetic reasoner gives good results for EnTiMid. But it may not be the case for less complex or different interactive systems. One of the advantages of our proposal is that the reasoner is also a component that can be selected in function of the context. For instance with a simple interactive system (e.g. 10000 configurations), the selected reasoner should be a reasoner that explores all the configuration since it will not take more than 0.5s.

Threats to validity

An important remark on this evaluation is that in our current implementation the configuration quality does not include the evaluation of the usability of adaptations, nor the user's satisfaction. For example our process may perform two following adaptations provoking big changes in the UI, that may disturb the user. Such evaluations can be performed by:

• The reasoner while selecting a configuration. In this case, the previous UI will be integrated into the genetic algorithm under the form of fitness functions maximizing the consistency of the adapted UI.

• A configuration checker that would evaluate the best configuration among the best ones found by the reasoner.

The configurations found by the genetic reasoner mainly depend on the properties defined on the components of the interactive systems. The developers have to balance them through simulations to obtain good results [START_REF] Fleurey | A domain specific modeling language supporting specification, simulation and execution of dynamic adaptive systems[END_REF].

This paper does not focus on the UI composition. The UI composer used in this evaluation is basic and takes a negligible amount of time during the reconfiguration. The use of a more complex composer will slow down the configuration process.

RELATED WORK

The conception of dynamic adaptable systems has been widely tackled in the software engineering domain [START_REF] Morin | Taming Dynamically Adaptive Systems with Models and Aspects[END_REF].

Software engineering approaches use model-driven engineering (MDE) to describe the system as a set of models. These models are sustained at runtime to reflect the underlying system and to perform adaptations. This process thus bridges the gap between design time and runtime. Yet these approaches do not focus on the adaptation of UIs. For example in [START_REF] Cetina | Autonomic computing through reuse of variability models at runtime: The case of smart homes[END_REF], Cetina et al. propose an approach to autonomic computing, and thus to dynamic adaptation, applied on home automation. This approach lacks at considering the system as an interactive system whose UI needs adaptations.

Based on MDE, UI adaptation has been firstly tackled during design time to face the increasing number of platforms (e.g., Dygmes [START_REF] Coninx | Dygimes: Dynamically generating interfaces for mobile computing devices and embedded systems[END_REF], TERESA [START_REF] Mori | Design and development of multidevice user interfaces through multiple logical descriptions[END_REF] and Florins et al.. [START_REF] Florins | Graceful degradation of user interfaces as a design method for multiplatform systems[END_REF]). These adaptation approaches mainly follow the CAMELEON top-down process composed of 1) the task model 2) the abstract UI 3) the concrete UI 4) the final UI [START_REF] Calvary | A unifying reference framework for multi-target user interfaces[END_REF]. Using the CAMELEON process, developers define several concrete UIs using one abstract UI to support different platforms. Users and the environment have been also considered as adaptation parameters, such as in UsiXML [START_REF] Limbourg | UsiXML: a user interface description language for specifying multimodal user interfaces[END_REF] and Contextual Con-curTaskTrees [START_REF] Bergh | Contextual concurtasktrees: Integrating dynamic contexts in task based design[END_REF]. A need to adapt at runtime UIs thus appear to face to any change of user, environment and platform.

Approaches have been proposed to consider models of UIs at runtime [START_REF] Balme | CAMELEON-RT: A software architecture reference model for distributed, migratable, and plastic user interfaces[END_REF][START_REF] Sottet | Model-driven adaptation for plastic user interfaces[END_REF][START_REF] Blumendorf | Bridging models and systems at runtime to build adaptive user interfaces[END_REF]. In [START_REF] Blumendorf | Executable models for human-computer interaction[END_REF][START_REF] Blumendorf | Bridging models and systems at runtime to build adaptive user interfaces[END_REF], Blumendorf et al.

propose a framework for the development and execution of UIs for smart environments. Their proposal shares several points with ours: the use of a mapping metamodel to map models; they consider that bridging design time and runtime implies that models are executable. However, they focus on the link between the models and the underlying system while we focus on the adaptation of complex interactive systems.

In [START_REF] Sottet | Model-driven adaptation for plastic user interfaces[END_REF], Sottet et al. propose an approach to dynamically adapt plastic UI. To do so, a graph of models that describe the UI is sustained and updated at runtime. The adaptation is based on model transformations: in function of the context change, the appropriate transformation is identified and then applied to adapt the UI. This process follows the event-conditionaction paradigm where the event is the context change and the action the corresponding transformation. The main drawbacks of this approach are that: transformations must be maintained when the interactive system evolves; the development of complex interactive systems will lead to the combinatorial explosion of the number of needed transformations.

CAMELEON-RT is a conceptual architecture reference model [START_REF] Balme | CAMELEON-RT: A software architecture reference model for distributed, migratable, and plastic user interfaces[END_REF]. It allows the distribution, migration, and dynamic adaptation of interactive systems. Adaptations are performed using rules predefined by developers and users, or learned by the evolution engine at runtime. A graph of situations is used to perform adaptations: when the context changes, the corresponding situation is searched into the graph. The found situation is then provided to the evolution engine that performs the adaptation. This approach focuses on the usability of adaptations. However, it can hardly deal with complex systems because of the need to define a graph of situations.

ReWiRe is a framework dedicated to the dynamic adaptation of interactive systems [START_REF] Vanderhulst | ReWiRe: Creating interactive pervasive systems that cope with changing environments by rewiring[END_REF]. As in our approach, ReWiRe's architecture uses a component-based system that facilitates the (de-)activation of the system's components. But ReWiRe suffers from the same main limitation than CAMELEON-RT: it can hardly deal with complex systems because of the increasing complexity of the ontology describing the whole runtime environment.

In [START_REF] Demeure | COMET(s), a software architecture style and an interactors toolkit for plastic user interfaces[END_REF], Demeure et al. propose a software architecture called COMETs. A COMET is a task-based interactor that encapsulates different presentations. It also embeds a reasoner engine that selects the presentation the more adapted to the current context. While we define a unique reasoner for the entire interactive system, COMETs defines one reasoner for each widget. We think that tagging widgets with properties that a global reasoner analyzes is a process that requires less effort than defining several reasoners. The approach presented in [START_REF] Hariri | Context aware business adaptation toward user interface adaptation[END_REF] is close to COMETs where UI components can embed several presentations and an inference engine deducing from the context the presentation to use.

In [START_REF] Schwartze | Behavior-sensitive user interfaces for smart environments[END_REF], Schwartze et al. propose an approach to adapt the layout of UIs at runtime. They show that the UI composer must also be context-aware to layout UIs in function of the current user and its environment. For example, our reasoner decides the components that will compose the UI, but not their disposition in the adapted UI. It is the job of the UI composer that analyzes the context to adapt the layout of the UI accordingly.

DYNAMO-AID is a framework dedicated to the development of context-aware UIs adaptable at runtime [START_REF] Clerckx | DynaMo-AID: A design process and a runtime architecture for dynamic model-based user interface development[END_REF].

In this framework, a forest of tasks is generated from the main task model and its attached abstract description. Each task tree of this forest corresponds to the tasks possible for each possible context. Because of the combinatorial explosion, such process can be hardly scalable to complex interactive systems.

In [START_REF] Gajos | Supple: automatically generating user interfaces[END_REF], Gajos and Weld propose an approach, called Supple, that treat the generation of UIs as an optimization problem. Given a specific user and device, Supple computes the best UI to generate by minimizing the user effort and respecting constraints. This approach is close to our reasoning step. However, Supple is not MDE-driven and only consider user effort as objective while our approach allows developers to define their own objectives.

CONCLUSION

Adapting complex interactive systems at runtime is a key issue. The software engineering community has proposed approaches to dynamically adapt complex systems. However, they lack at considering the adaptation of the interactive part of systems. In this paper, we have described an approach based on the Malai architectural model and that combines aspect-oriented modeling with property-based reasoning. The encapsulation of variable parts of interactive systems into aspects permits the dynamic adaption of user interfaces. Tagging UI components and context models with QoS properties allows the reasoner to select the aspects the best suited to the current context. We applied the approach to a complex interactive system to evaluate: the time spent adapting UIs on context changes; the quality of the resulting adapted UIs.

Future work will focus on the consideration of adaptations quality during the reasoning process. It will assure consistency between two adapted UIs. Work on context-aware composition of UIs will be carried out as well.

Figure 1 .

 1 Figure 1. Organization of the architectural model Malai

  [START_REF] Paternò | ConcurTaskTrees: A diagrammatic notation for specifying task models[END_REF] 23 c l a s s C a l l E m e r g e n c y S e r v i c e i n h e r i t s N u r s e A c t i o n { 24 // . . . 25 }

  Listings 3 and 4 describe parts of the 2D-based presentation of the nurse agenda. Its abstract presentation defines the agenda model (see Listing 3

Figure 2 .

 2 Figure 2. Instrument VisitTypeSelector

Figure 3 .

 3 Figure 3. Instrument TimeslotSetter

Figure 4 .

 4 Figure 4. Part of the EnTiMid UI that controls the lights, the heaters, and the shutters of the home

Figure 5 .

 5 Figure 5. Average adaptation time of EnTiMid using an increasingly number of possible configurations Figure 5 presents our results using the reasoner based on the NSGA-II genetic algorithm. It shows that the reasoning time remains linear between 600 and 800ms. That because the parameters of the reasoner (e.g. the number of generations, the size of the population) are

  Possible configurations (in millions)Average number on 1000 adaptations Minimal number on 1000 adaptations Maximal number on 1000 adaptations

Figure 6 .

 6 Figure 6. Comparison between the optimal solutions and solutions found by the genetic reasoner

In this paper, the term "context" is used instead of "context of use" for conciseness.

ACKNOWLEDGMENTS

The research leading to these results has received funding from the European Communitys Seventh Framework Program FP7 under grant agreements 215412 (http://www.ict-diva.eu/) and 215483 (http://www.scube-network.eu/).