Mouchère Harold
email: harold.mouchere@univ-nantes.fr

Li Jinpeng

Viard-Gaudin Christian

Chen Zhao-Xin

符识别的动态时间归 多笔画联机手写

算法

算法 在部分笔画匹配时

, 算法保留着次序约束,并用 A

算法降低计算复杂度 文中还通过流程

数据 多笔画符

号识别实验对比了 Dtw-A

算法 Dtw

算法 改良豪斯多夫距离

种算法的性能 , 结果

A Dynamic Time Warping Algorithm for Recognition of Multi-Stroke On-Line Handwritten Characters*

Keywords: pattern recognition, handwriting recognition, dynamic time warping

Dynamic time warping (DTW) is a famous distance to compare two mono-stroke symbols online. It obeys boundary and continuity constraints. The extension of DTW to multi-stroke symbols raises specific problems. A naive solution is to convert the multi-stroke symbol into a single one via a direct concatenation in the handwriting order. However, people may write a symbol with different stroke directions and orders. Applying a brute force method by searching all the possible directions and orders leads to prohibitive calculation times. To reduce the searching complexity, DTW-A* algorithm, which keeps the continuity constraint during each partial matching and reduces the searching complexity by using the A* algorithm, is proposed. Experimental results on a flowchart dataset mainly containing multi-stroke symbols indicate that DTW-A* algorithm helps to achieve the highest recognition rate and stability in cross-validation, as compared with such two other algorithms as DTW and modified Hausdorff distance.

Introduction

In this paper, a distance applied to on-line handwriting, whose basic elements are temporal point sequences (strokes), is proposed. A sequence is started from the pen-down point and is ended at the pen-up point, with variable point number. Based on the elastic point-to-point matching, the famous DTW algorithm computes the distance between two sequences [1] , i.e. two single-stroke symbols, and obeys continuity and boundary constraints during the matching.

Many works [2] extend the temporal continuity constraint to a spatial continuity constraint in two spatial dimensions. It aims at finding a mapping between two sets of points (pixels). The contribution of this paper is to focus on how to design a matching between two sets of sequences, i.e. two multi-stroke symbols.

Each instance of a handwritten graphical symbol is different from the other because of the variability of human handwriting. Different people may write a visually same symbol with different stroke directions and orders. In writer identification, these characteristics help to efficiently distinguish writers [3] . However, to understand or communicate the same symbol written by different writers, stroke direction and order could be ignored. For instance, a symbol containing a horizontal stroke "-" can be written by two different approaches, namely the way from left to right ""or an inverse way "". Comparing two opposite direction strokes, the DTW distance dist DTW (, ) naturally produces a large value because of two inverse directions. A simple solution is to choose the smaller distance between two possible directions of one stroke: min(dist DTW (, ), dist DTW (inv(), )), where inv(.) is an operator for reversing stroke trajectory direction.

However, when comparing two multi-stroke symbols, the number of possible directions and orders increases very fast as a function of the stroke number. Table 1 illustrates an example of how to write "E" within four strokes. With this example, 384 different writing sequences are possible.

This example shows the complexity of the combination of different stroke directions and orders. In general, the number of different temporal writing paths for a symbol is given by [START_REF] Vuori | Adaptive methods for on-line recognition of isolated handwritten characters[END_REF] where N is the stroke number of a symbol. For calculating the DTW distance between two multi-stroke symbols, a simple solution is to concatenate the strokes using different stroke directions and orders.

Table 1 Variability of stroke direction and order of on-line handwritten symbol For example, for the DTW distance between (4 strokes) and (2 strokes), 384 × 8 = 3092 possible matching should be calculated. This large combination number is due to different writing orders of N strokes (N!) and due to the two directions of each written order (2 N ).

In a more extreme case, we can get rid of all the temporal information and consider the symbol as a set of points ignoring the sequences they produce. This leads to the use of the Hausdorff distance [4] . This metric is mainly used in image processing domain. Furthermore, another varied version is the modified Hausdorff distance (MHD) [5] .

However, there exists one disadvantage that the temporal continuity property of sequences is ignored. In this paper, a distance between two multi-stroke symbols is proposed, which is called DTW A* and preserves the temporal continuity constraint. In the investigation, the classical DTW between two sequences is first recalled, and is then extended to process two sets of sequences. Finally, the corresponding experimental results are presented and a conclusion is drawn.

DTW Between Two Point Sequences

We start with the simple case in which the two characters are composed of only one stroke, respectively. In this case, two strokes (two time-varying-data sequences), denoted as S 1 = (p 1 (1), p 1 (2),... , p 1 (N 1 )) and S 2 = (p 2 (1), p 2 (2),... , p 2 (N 2 )), are compared. Giving a warping path P(h) = (i(h),j(h)), 1 ≤ h ≤ H, defining the point-to-point associated pairs where h is a pair index from the i(h)th point in S 1 and from the j(h)th point in S 2 . P(h) should consider the boundary constraint and the continuity constraint. It means that the first two beginning points should be matched in the two strokes, and so do the two ending points. The second temporal continuity constraint implies that the point-to-point matching shift is equal to one. In addition, all the points are matched at least for one time. Calculating the distance between two sequences involves the search of a warping path that minimizes the sum of the point-to-point associated cost function: [START_REF] Uchida | A survey of elastic matching techniques for handwritten character recognition[END_REF] where dist(.,.) is the Euclidean distance in the point feature space.

The solution to Eq. ( 2) can be resolved by means of dynamic programming. The dynamic programming searches the minimum warping path from a cumulative distance matrix [START_REF] Tan | Automatic writer identification framework for online handwritten documents using character prototypes[END_REF] with D(i, j; 0) = 0 for initialization. Once the cumulative distance matrix is computed, we can use backtracking to find the minimum warping path. 3). We first compute a cumulative distance matrix as explained in Fig. 2. The best warping path can be found by means of backtracking from the ending point couple to the starting point couple to obtain: P(1), P(2),..., P(9) = (1,1), (2,2), (3,3), [START_REF] Tan | Automatic writer identification framework for online handwritten documents using character prototypes[END_REF][START_REF] Huttenlocher | Comparing images using the Hausdorff distance[END_REF], (4,5), [START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF][START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF], [START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF][START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF], (6,7), [START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF][START_REF] Awal | First experiments on a new online handwritten flowchart database[END_REF]. We can see that, once we define the starting point couple and the ending point couple, the best warping path will be found. In Section 2, a comparison between two sets of point sequences will be introduced. Fig. 2 The cumulative distance matrix D(i, j; h) of Eq. ( 3) illustration and the best warping path

DTW Between Two Sets of Sequences

Here, we propose to extend the DTW algorithm to compare two multi-stroke symbols (i.e. two sets of sequences). A traditional method is to concatenate the strokes in the handwritten order [START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF] . Therefore, the distance between two multi-stroke symbols can be computed using DTW [1] . We call this method the classical DTW. However, because of the stroke-order and stroke-direction variation among writers, the classical DTW cannot easily match some symbols as discussed in the introduction. The MHD is a possible solution to cope with this variation. In this paper, the MHD between two symbols (S 1 = {pt i1 } and S 2 = {pt i2 }) is defined as [START_REF] Huttenlocher | Comparing images using the Hausdorff distance[END_REF] where

. The MHD here is slightly different from that defined in Ref. [START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF]. We choose an average distance rather than a maximum distance between two point sets to prevent the effect of outliers. However, the MHD does not consider the continuity constraint.

We now introduce a new distance called DTW A* to compare two multi-stroke symbols by keeping the continuity constraint.

Basically, as with the classical DTW, a point-to-point distance matrix is built via the dynamic programming. Giving two multi-stroke symbols, rows and columns of this matrix represent the two symbols, respectively, as shown in Fig. 3. The strokes of one symbol are placed in one side (rows or columns). The respective positions of the strokes in the two sequences are irrelevant and their matching has not to respect the temporal order.

The main idea insists in iteratively constructing a small warping path until all the points are used. Once we choose a starting point couple, four possible directions of warping path are possible. Each direction represents a point-to-point distance matrix for matching two strokes or two sub-parts from two strokes. In each iteration, we search a warping path that minimizes warping cost and finishes at least one stroke. To find the best warping path, four cumulative distance matrices (see Fig. 3) are explored in four directions, respectively.

For example, giving two symbols, one contains two strokes while the other contains one stroke, the two strokes of the first symbol are placed in rows and the stroke of the second symbol is placed in columns (one for each point), as shown in Fig. 3. Once we define a starting point (the small rectangle in the middle of Fig. 3), there are four possible matching directions (four possible warping paths) corresponding to four cumulative matrices. In each cumulative matrix, we can apply the classical DTW algorithm described in Fig. 2 to find the minimum cost warping path. We allow, however, DTW algorithm to not stop at the diagonal opposed point (the ending point) in the cumulative distance matrix but along the borders of the matrix (red cross signs). Fig. 3 Defining a starting point couple (the rectangle) and finding a warping path between the two-stroke symbol (symbol 1) and the single-stroke symbol (symbol 2) in four directions

In fact, from Fig. 2, it can be found that the warping path stopping at P(9)=(6, 8) is not the best as the distance increases after P [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF]. This warping path can be cut by choosing the minimum distance among the points of the cumulative matrix edges: D(1, N 2 ), D(2, N 2 ), ..., D(N 1 , N 2 ) and D(N 1 , 1), D(N 1 , 2), ..., D(N 1 , N 2 ). In reality, we first calculate the whole cumulative distance matrix till to the end of both two strokes. Then the warping path stops when finishing with at least one of two strokes. Thus, a new ending point couple is obtained. For example, in Fig. 2, we choose the sub-path: (1, 1), (2, 2), (3, 3), (3, 4), (4, 5), (5, 5), [START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF][START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF].

With this strategy, starting point couples are chosen to associate the two sub-sequences with respect to the continuity constraint in each step. In each step, we choose a starting point couple again from non-used points of the two strokes. The searching procedure finishes until all the points are associated in the warping path. Our objective is to find the warping path that minimizes the associated cost in Eq. ( 2). The distance of DTW A* is normalized by the number of couples.

Fig. 4 shows the best warping path for associating two sets of point sequences. This solution contains four DTW sub-warping paths, which are obtained from Step 1 to Step 4. The matching directions are not necessary to be the same. A set of sub-warping paths which minimizes the associated cost (the sum of point-to-point distances) are searched.

However, there are a large number of possibilities. To search the best warping path, an A* algorithm [7] is used to accelerate the search as discussed in Section 2.1.

A* Algorithm

In this section, the A* algorithm (A star) [7] to limit some futureless explorations is introduced. It iteratively searches the best path in a graph from the starting node (empty associated point) to the ending node (all associated points). However, not all the possible nodes are generated because of a heuristic function in the A* algorithm. In each step, only the best hypothesis is explored for the next step. The A* algorithm uses a distance-plus-cost heuristic function f(x) = g(x) + h(x) at each step x. The cost g(x) represents the cost of the best warping path from the starting step to the current step x, and the heuristic cost h(x) estimates the minimum distance to the ending step. Ref. [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF] described the A* algorithm in detail. In this section, we define the two functions, namely g(x) and h(x), for our problem. Considering the heuristic distance h(.), it should be as large as possible but equal to or less than the real optimal distance for reaching the ending step, which means that h(.) is admissible.

We first define each step x by a warping path P x (h)=(i x (h), j x (h)), 1 ≤ h ≤ H x , between the two symbols S 1 = (p 1 (1), p 1 (2), ..., p 1 (N1)) and S 2 = (p 2 (1), p 2 (2), ..., p 2 (N 2 )). The warping path is a sequence of associated index pairs. Its cost is defined by the sum of pair costs: [START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF] Defining a set of non-used points NUPt(Sym, x) for a symbol Sym in step x, the heuristic cost h(.) therefore can be defined by [START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF] where [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF] and

. This heuristic distance h(.) is admissible because we always choose the minimum distance between the two sets of non-used pair points during the association of the point pairs. Even though the A* algorithm is used to accelerate the searching, the number of combinations is still large. In order to further reduce the combination numbers, we try to limit the number of starting point couples rather than using all the non-used point couples. This strategy will be developed in Section 2.2.

Choosing Starting Points

In order to generate next steps from step x, one have to choose a non-used starting point couple, which is used for starting up two sequences with a matching in four directions in maximum. For each direction, a new step is obtained. Although the A* algorithm can reduce the searching complexity, there are still many possibilities when using all the non-used points for a next step. In this section, we propose a strategy to limit the starting point couple generation.

Defining the non-used segments in step x for each stroke in a symbol Sym by Segs(Sym, x), the boundary points of these segments are defined by FSeg(Sym, x). A set of new starting point couples {(p i , p j )} between two symbols, S 1 and S 2 , are produced from FSeg(S 1 , x) to the closest points in Segs(S 2 , x), and vice versa: [START_REF] Awal | First experiments on a new online handwritten flowchart database[END_REF] Fig. 5 shows the possible starting point couples of the first step in Fig. 4 which is as considered as the step x. In this case, there exist three starting couples, namely (P1, P6) with only one direction, (P1, P8) with two possible directions and (P5, P11) with only one possible direction. In the general case, up to four directions have to be considered. All the possibilities are explored by the A* algorithm for searching the best warping path. By limiting the number of starting couples, fewer branches are explored from the current step. It has two consequences: the system is faster but we cannot guarantee to select the best solution. In the next section, we will present experimental results of DTW A* algorithm.

Experiments

In this section, we first display a qualitative matching between two patterns so that we can intuitively understand how it works. Second, a handwriting dataset is presented. Then, the performances of three distances (DTW A*, Classical DTW and MHD) are compared on a handwriting dataset.

Fig. 6 illustrates the matching between two allographs of "x". Our algorithm finds the best solution in 5 steps which are 5 sub-warping paths. The first two steps show the point-to-point matching of the top-left branch of "x". The bottom-right branch is matched in the third step, etc.

Our algorithm can cut the strokes into sub-graphemes which minimize the DTW distance between segments from two symbols. In order to assess the recognition efficiency of DTW A*, we first present a handwriting dataset evaluated by a k-NN classifier. The handwriting dataset is a realistic handwritten flowchart dataset named FC dataset [8] . We also use six different graphical symbols (six classes) that represent the basic operations (data, terminator, process, decision, connection and arrow) without any handwritten text, as displayed in Fig. 7. This data set contains a training part (3641 symbols) and a test part (2494 symbols). In average, each symbol contains 2.4 strokes. As we can see, most symbols on the \textit{FC} dataset are composed of more than one stroke. People may write strokes in a symbol with different orders and directions. Fig. 7 An example of flowchart on the FC dataset Table 2 shows the recognition rates of three algorithms. DTW A* is slightly better (97.47%) than the classical DTW (96.79%), and more surprisingly MHD is also very efficient (97.31%). One explanation is that, for flowcharts, the sequence information is very irrelevant, and that it is better not to rely on. With the classical DTW, the strokes from one symbol are just concatenated, so that the time information is strongly kept. Thus, when a symbol is written in a different stroke order, the same stroke order should exist in the train dataset of the k-NN. To study the sensitivity with respect to the training size set, a 5-fold cross validation with a smaller training set size is also proposed. We can notice that DTW A* is quite stable (96.90%) although only one fifth of the training samples are available. Conversely, the performance of the classical DTW drops to 91.33%, in that case missing samples of the training set are not compensated by the flexibility of the matching process.

Even though we have optimized a lot for the A* algorithm in terms of time, it is still time-consuming and memory-consuming (storing a large number of hypotheses). In average, each comparison takes 0.04 s, but some of them consume several seconds.

Conclusions

As the brute force method produces a large number of possibilities, a distance between two sets of sequences is proposed, which keeps the continuity during each small matching. The proposed distance, namely DTW A*, uses the A* algorithm to reduce the complexity and only the promising candidates are considered. In addition, we limit the starting point couples. By the test on the FC dataset which contains flowchart symbols, it is found that the proposed DTW A* distance slightly outperforms the classical distances of DTW and MHD. The DTW A* remains quite stable during the cross-validation test. However, it is still not fast enough in practical usage. Further limitation of the starting point couples is a possible solution.

Fig. 1

 1 Fig.1 Two point sequences (two single-stroke symbols) Fig.1 illustrates an example of matching two single-stroke symbols. The starting point couple is marked with the two circled points. The search for the next couple is obtained with Eq. (3). We first compute a cumulative distance matrix as explained in Fig.2. The best warping path can be found by means of backtracking from the ending point couple to the starting point couple to obtain: P(1), P(2),..., P(9) = (1,1), (2,2),[START_REF] Tan | Automatic writer identification framework for online handwritten documents using character prototypes[END_REF][START_REF] Tan | Automatic writer identification framework for online handwritten documents using character prototypes[END_REF],[START_REF] Tan | Automatic writer identification framework for online handwritten documents using character prototypes[END_REF][START_REF] Huttenlocher | Comparing images using the Hausdorff distance[END_REF], (4,5),[START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF][START_REF] Dubuisson | A modified Hausdorff distance for object matching[END_REF],[START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF][START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF], (6,7),[START_REF] Ding | An investigation of imaginary stroke techinique for cursive online handwriting Chinese character recognition[END_REF][START_REF] Awal | First experiments on a new online handwritten flowchart database[END_REF]. We can see that, once we define the starting point couple and the ending point couple, the best warping path will be found. In Section 2, a comparison between two sets of point sequences will be introduced.

  (a) Step 1 (b) Step 2 (c) Step 3 (d) Step 4 Fig.4 A solution of warping path between two symbols (graphic and matrix views)

Fig. 5

 5 Fig.5 Three starting point couples (P1, P6), (P1, P8) and (P5, P11) for starting the second step in Fig.4

Fig. 6

 6 The best solution of two "x"

Table 2

 2 Results of k-NN classification (k = 5) and cross-validation on the FC dataset %

		DTW A* Classical DTW MHD
	Normal k-NN	97.47	96.79	97.31
	Cross-Validation	96.90	91.33	95.65
	Decrease	0.57	4.86	1.66


Oana-Silvia Serea
email: oana-silvia.serea@univ-perp.fr

Characterization of the optimal trajectories for the averaged dynamics associated to singularly perturbed control systems *

Keywords: Optimal control, Singular perturbations, occupational measures AMS Classification: 34A60, 34K26, 49J24, 49J45, 49L25, 93C15

The aim of this paper is to study singularly perturbed control systems. Firstly, we provide linearized formulation version for the calculus of the value function associated with the averaged dynamics. Secondly, we obtain necessary and sufficient conditions in order to identify the optimal trajectory of the averaged system.

Introduction

The aim of this parer is to study singularly perturbed control systems. Firstly, we provide linearized formulation version for the calculus of the value function associated with the averaged dynamics. Secondly, we obtain necessary and sufficient conditions in order to identify the optimal trajectory of the averaged system. Linear programming techniques have proved to be very useful in dealing with deterministic and stochastic control problems. A wide literature is available on the subject both in the deterministic and in the stochastic setting ( [START_REF] Fleming | Convex duality approach to the optimal control of diffusions[END_REF][START_REF] Bhatt | Occupation measures for controlled markov processes: Characterization and optimality[END_REF][START_REF] Gaitsgory | Limit occupational measures set for a control system and averaging of singularity perturbed control systems[END_REF][START_REF] Gaitsgory | Multiscale singularly perturbed control systems: Limit occupational measures sets and averaging[END_REF][START_REF] Gaitsgory | On a representation of the limit occupational measures set of a control system with applications to singularly perturbed control systems[END_REF][START_REF] Gaitsgory | Linear programming approach to deterministic long run average problems of optimal control[END_REF][START_REF] Borkar | Averaging of singularly perturbed controlled stochastic differential equations[END_REF][START_REF] Finlay | Linear programming solutions of periodic optimization problems: approximation of the optimal control[END_REF]). One of the advantages of transforming a nonlinear control problem into a linear optimization problem consists in the possibility of obtaining approximation results for the value function. Following the methods presented in [START_REF] Finlay | Linear programming solutions of periodic optimization problems: approximation of the optimal control[END_REF] and [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discouting[END_REF], one can approximate the occupational measures by Dirac measures and construct an optimal feedback control. Moreover, when considering the ergodic control problem (see, e.g. [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]), the study of the behavior of the value function is simplified whenever this value is expressed by a linear problem. Recently linearized versions of the standard continuous infinite horizon discounted control problems are provided in [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discouting[END_REF][START_REF] Buckdahn | Stochastic optimal control and linear programming approach[END_REF]. When the perturbed system is fully nonlinear it is very difficult to characterize the optimal trajectories using the classical methods given by the Pontryagin maximum principle because we do not know exactly the form of the averaged dynamics. For works in this direction we reefer the reader for instance to [START_REF] Friedman | Exact slow-fast decomposition of a class of non-linear singularly per-turbed optimal control problems via invariant manifolds[END_REF][START_REF] Naidu | Singular perturbations and time scales in control theory and applications: an overview[END_REF][START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF] and references therein. Fortunately, using our approach we can characterize optimal trajectories. Our method consists in embedding the trajectories into a space of probability measures satisfying a convenient condition. This condition is given in terms of the coefficient functions. The results allow to characterize the set of constraints as the closed convex hull of occupational measures associated to controls. We first consider a general Mayer control problem for explaining the approach. Secondly, using linearization techniques and the dual formulation we characterize the optimal occupational measures. Note that as far as we know our method was not used before in the singularly perturbed setting. Moreover, it's advantage consists in the fact that we do not require to "explicitly" calculate the averaged dynamics.

This paper is organized as follows: In the second section we aim at presenting singularly perturbed control systems and the averaging method and some important results concerning the singularly perturbed systems and the value functions associated with this problem. The third section deals with the linear formulation associated with classical control problems. The fourth section concerns with the characterization of optimal occupational measures for Mayer type control problems. In the fifth section we provide linearization techniques for the averaged system. In the sixth section we describe optimal occupational measures/trajectories for the averaged system. Finally, we provide an appendix for the convenience of the reader.

Singularly perturbed control systems

In the following we shortly present our problem. We consider the following dynamics:

(1)

   dx t,x,y,u s = f x t,x,y,u s , y t,x,y,u s , u s ds, εdy t,x,y,u s = g x t,x,y,u s , y t,x,y,u s , u s ds,
for all s ≥ t, where (t, x, y) ∈ [0, ∞) × R M × R N and ε is a small real parameter. The evolutions of the two state variables x and y of the system are of different scale. We call x the "slow" variable and y the "fast" variable. We recall that a control (u t ) t 0 ≤t<∈ is said to be admissible if it is Lebesgue-measurable on [t 0 , ∞) and u takes its values in a compact, metric space U . We let U denote the family of all admissible controls on [0, ∞) . The functions f : R M × R N × U → R M and g : R M ×R N ×U → R N are assumed to be continuous on [0, ∞)×R M ×R N and Lipschitz-continuous in (x, y), uniformly with respect to the control parameter u ∈ U.

We denote by x t,x,y,u;ε

(•) , y t,x,y,u;ε (•)
the solution of (1) starting from (t, x, y)

∈ [0, T ] × R M × R N , for some u ∈ U .
We let h : R M → R be a given bounded function and define the following payoff:

(2)

C t,x,y;ε (u) = h x t,x,y,u;ε T , for all (t, x, y) ∈ [0, T ] × R M × R N
and all u ∈ U . The value function associated with (1) and ( 2) is:

(3) W ε,h (t, x, y) = inf u∈U C t,x,y;ε (u) for all (t, x, y) ∈ [0, T ] × R M × R N .
The asymptotic behavior of the value function (3) when ε → 0 is a very interesting problem. Whenever the control system (1) has some stability property, it is possible to prove that the trajectories x t,x,y,u;ε (•) , y t,x,y,u;ε (•) of (1) converge towards some solution of some system obtained by formally replacing ε by 0 in [START_REF] Aubin | Viability theory[END_REF]. This is the so called Tikhonov approach which has been successfully developed in [START_REF] Tichonov | Systems of differential equations containing small parameter near derivatives[END_REF][START_REF] Veliov | A generalization of the tikhonov theorem for singularly perturbed differential inclusions[END_REF] for instance.

When dy t,x,y,u s = g x t,x,y,u s , y t,x,y,u s , u s ds is not stable, another approach consists in investigating relationships between the system (1) and a new differential inclusion (4) dx t,x s ∈ F x t,x s obtained by an averaging method, that will be described later on. We emphasize that, in general, the averaged system is set-valued. We refer the reader to [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF][START_REF] Grammel | Singularly perturbed differential inclusions. an averaging approach[END_REF] for averaging methods. It is important to notice that only the behavior of the "slow" variable x t,x,y,u;ε

(•)
is concerned by this approach.

Let us also recall that the sequence of functions (W ε,h (•, •, y)) ε>0 converges to the value function

W F,h : [0, T ] × R M -→ R defined by (5) W F,h (t, x) = inf x t,x (•) ∈S F (t,x) h x t,x T , for all (t, x) ∈ [0, T ] × R M if h is uniformly continuous and bounded.
Here, S F (t, x) stands for the set of solutions of (4) starting from (t, x) ∈ [0, T ]×R M and S ε (t, x, y) for the set of all the trajectories of (1) x t,x,y,u;ε (•) , y t,x,y,u;ε

(•) starting from (t, x, y) ∈ [0, T ]×R M ×R N .
Moreover, we define S F (0, x) =: S F (x) and by S ε (0, x, y) =: S ε (x, y), for all (x, y) ∈ R M +N .

The averaging method

Let us shortly explain the behavior of the perturbed system (1) as ε → 0. If one makes the change of variables τ = s ε in the system (1) with t = 0, and sets

(X τ , Y τ , U τ ) = (x ετ , y ετ , u ετ ) for τ ∈ [0, T ε ], one gets    dX t,x,y,u τ = εf X t,x,y,u τ , Y t,x,y,u τ , U τ dτ, dY t,x,y,u s = g X t,x,y,u τ , Y t,x,y,u τ , U τ dτ.
When ε tends to 0, we are led to consider the following associated system:

(6) dy t,y,u s = g x, y t,y,u s , u s ds, for s ∈ [0, +∞), where x is fixed in R M . For every fixed x ∈ R M , we denote by y t,y,u;x

(•)
the unique solution of (6) corresponding to the control u and to the initial value y.

We follow an averaging method (cf. for instance [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF], [START_REF] Grammel | Averaging of singularly perturbed systems[END_REF]): we set, for (x,

y) ∈ R M × R N , S > 0, and u ∈ U , A(x, y, S, u) = 1 S S 0 f x, y t,y,u;x s , u s ds, F (x, y, S) = {A(x, y, S, u); u ∈ U }.
We shall make the following assumption on the systems:

(7)         
∀R > 0, there exist nonempty bounded subsets N R and Ω R of R N such that:

1)∀(x, y) ∈ B(0, R) × N R , ∀ x 0,x,y,u;ε (•) , y 0,x,y,u;ε (•) ∈ S ε (0, x, y), y 0,x,y,u;ε s ∈ Ω R , for all s ∈ [0, T ] and all ε > 0. 2)∀(x, y) ∈ B(0, R) × N R , ∀ u ∈ U , y 0,y,u;x s ∈ Ω R , for all s ≥ 0.
Note that the previous assumption says in fact that all solutions of (1) starting from B(0, R)×N R and all solutions of (6) will belong to R N × Ω R and, respectively, to Ω R . Under an assumption of either total controllability or stability of the associated system (6), the set F (x, y, S) converges, in the sense of the Hausdorff metric, towards a compact convex set F (x) of R M .

If the set-valued map F is Lipschitz, then the set of slow solutions x t,x,y,u;ε

(•)
converges towards the set of solutions of the differential inclusion in the sense that

Π ε M (t, x, y) := x t,x,y,u;ε (•) : x t,x,y,u;ε (•) , y t,x,y,u;ε (•) ∈ S ε (t, x, y)
converges to S F (t, x) for the Hausdorff metric. Let us describe the following property of total controllability: every two points of Ω R can be joined in bounded time by a trajectory of the associated system for any x in B(0, R). Namely: [START_REF] Friedman | Exact slow-fast decomposition of a class of non-linear singularly per-turbed optimal control problems via invariant manifolds[END_REF] ∀R > 0, ∃ t R ≥ 0 such that : ∀x ∈ B(0, R), ∀y 1 , y 2 ∈ Ω R , there exists u ∈ U and s ≤ t R such that y 0,y 2 ,u;x s = y 1 .

We notice that, the previous assumption is in fact a controllability assumption. The controllability of systems is a very important property and a large literature studying it is available (see for instance [START_REF] Terrell | Some fundamental control theory i: Controllability, observability, and duality[END_REF], or Chapter 2 and 3 from [START_REF] Macki | Introduction to optimal control theory[END_REF]). Moreover, if (8) holds true, then, for every x in B(0, R), Ω R is actually invariant for the associated system [START_REF] Finlay | Linear programming solutions of periodic optimization problems: approximation of the optimal control[END_REF]. Indeed, if y is in Ω R , then it can be joined to a y 0 in N R , so that any point of a trajectory with initial value y is also a point of a trajectory with initial value y 0 . Hence, it belongs to Ω R by the assumption [START_REF] Fleming | Convex duality approach to the optimal control of diffusions[END_REF]. Conditions for invariance (or in particular, for having [START_REF] Fleming | Convex duality approach to the optimal control of diffusions[END_REF] and ( 8)) are presented for instance in [START_REF] Aubin | Viability theory[END_REF] (Chapter 5).

We also need the following stability property:

(9)      ∀R > 0, there exists ξ R ∈ L 1 ([0, +∞[, R + ) such that : ∀x ∈ B(0, R), ∀y 1 , y 2 ∈ Ω R , ∀u ∈ U , y t,y 1 ,u;x s -y t,y 2 ,u;x s ≤ ξ R (s) |y 1 -y 2 | for every s ≥ 0.
Remark 1 If one assumes the existence of some constant C R such that:

y 2 -y 1 , g (x, y 2 , u) -g (x, y 1 , u) ≤ -C R |y 2 -y 1 | 2 ,
for every u ∈ U , then ( 9) is satisfied with ξ R (τ ) = e -C R τ . This is a classical assumption in order to obtain Tychonoff 's Theorem, Under the assumption (9), the map F is Lipschitz (cf. [START_REF] Gaitsgory | Suboptimization of singularly perturbed control systems[END_REF]), while under the assumption (8) alone, the map F is only continuous, so one needs further conditions to get F Lipschitz-continuous. Whenever the system is weakly coupled (i.e. if the trajectories y t,y,u;x (•) of the associated system [START_REF] Finlay | Linear programming solutions of periodic optimization problems: approximation of the optimal control[END_REF] do not actually depend on x), then F is Lipschitz (cf. [START_REF] Grammel | Averaging of singularly perturbed systems[END_REF]). Another possibility to get F Lipschitz (or, at least, locally Lipschitz (cf. [START_REF] Quincampoix | Averaging method for discontinuous mayer's problem of singularly perturbed control systems[END_REF])) is to strengthen the assumption (8) into an assumption [START_REF] Gaitsgory | On a representation of the limit occupational measures set of a control system with applications to singularly perturbed control systems[END_REF] of Lipschitz controllability. This condition should guarantee that every two points of Ω R can be joined in a time less or equal to some constant C R multiplied by the distance between the initial points. We say that the system (1) satisfies [START_REF] Gaitsgory | On a representation of the limit occupational measures set of a control system with applications to singularly perturbed control systems[END_REF] if:

∀R > 0, ∃c R > 0, ∀y 1 , y 2 ∈ Ω R , ∀x ∈ B(0, R), ( 10
) ∃u ∈ U , ∃s ≤ c R |y 1 -y 2 | , such that y 0,y 2 ,u;x s = y 1 .
When F is locally Lipschitz, one has the following result: Proposition 2 (cf. [START_REF] Quincampoix | Averaging method for discontinuous mayer's problem of singularly perturbed control systems[END_REF]) We assume that (7) holds true, either the assumption [START_REF] Friedman | Exact slow-fast decomposition of a class of non-linear singularly per-turbed optimal control problems via invariant manifolds[END_REF] or the assumption ( 9) is true, f is bounded and F is locally Lipschitz. Then, for every R 0 > 0, every R ≥ R 0 + T |f | ∞ , there exists a function µ R : (0, +∞) → R, such that lim ε→0 µ R (ε) = 0 and, for every ε > 0 and every (x, y) ∈ B(0, R 0 ) × N R :

-for every x t,x,y,uε;ε

(•)
, y t,x,y,uε;ε

(•)
∈ S ε (t, x, y), there exists x t,x (•) ∈ S F (t, x) and:

(11) sup s∈[t,T ] x t,x,y,uε;ε s -x t,x s ≤ µ R (ε); -for any x t,x (•) ∈ S F (t, x), there exists (x ε (•), y ε (•)) ∈ x t,x,y,uε;ε (•)
, y t,x,y,uε;ε

(•)
∈ S ε (t, x, y), such that the inequality (11) holds.

Notice that the previous result can be reformulated using the Hausdorff distance for sets. More precisely, we have that

lim ε→0 d H (S ε (t, x, y) , S F (t, x) × {0}) = 0 ⇔ lim ε→0 d H (clS ε (t, x, y) , clS F (t, x) × {0}) = 0 ⇔ lim ε→0 d H (clS ε (t, x, y) , S F (t, x) × {0}) = 0
because of the regularity of F which implies that S F (t, x) is closed with respect to the uniform convergence topology.

If the cost function h is bounded and uniformly continuous, the convergence of the value functions is a direct consequence of the convergence of trajectories. More precisely, we have W ε,h → W F,h with respect with the uniform convergence.

Linear formulation for classical control problems

Throughout this section, we will be dealing with the following control system (12)

dx t 0 ,x 0 ,u t = b x t 0 ,x 0 ,u t , u t dt, t 0 ≤ t ≤ T, x t 0 ,x 0 ,u t 0 = x 0 ∈ R N ,
where T > 0 is a finite time horizon, t 0 ∈ [0, T ] and the control u is a measurable function which takes its values in a compact, metric space U . We let U denote the family of all admissible controls on [0, T ]. We assume that the dynamics b : R N × U -→ R N satisfies [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discouting[END_REF] b is bounded and uniformly continuous on

R N × U, |b (x, u) -b (y, u)| ≤ c |x -y| ,
for all (x, y, u) ∈ R N × R N × U , for some positive real constant c > 0.

Occupational measures

We begin by giving some properties of the linear formulation associated to control problems. Let us suppose that T > 0 is a fixed time horizon. We fix t ≥ 0 and x 0 ∈ R N . To every r > t and u ∈ U , one can associate a couple of occupational measures γ t,r,x 0 ,u = γ t,r,x 0 ,u 1 , γ t,r,x 0 ,u

2 ∈ P [t, r] × R N × U × P R N defined by γ t,r,x 0 ,u 1 (A × B × C) = 1 r-t r t 1 A×B×C s, x t,x 0 ,u s , u s ds, γ t,r,x 0 ,u 2 = δ x t,x 0 ,u r , for all Borel sets A ⊂ [t, r] , B ⊂ R N and C ⊂ U . When x ∈ R N , δ
x stands for the Dirac measure. One can also define γ t,t,x 0 ,u 1 , γ t,t,x 0 ,u

2 ∈ P {t} × R N × U × P R N by setting γ t,t,x 0 ,u 1 = δ t,x 0 ,ut , γ t,t,x 0 ,u 2 = δ x 0 .
For every r ≥ t, the family of occupational measures

(14) Γ (t, r, x 0 ) = γ t,r,x 0 ,u 1 , γ t,r,x 0 ,u 2
, for all u ∈ U can be embedded into a larger set

Θ (t, r, x 0 ) =    (γ 1 , γ 2 ) ∈ P [t, r] × R N × U × P R N , ∀φ ∈ C 1,1 b R + × R N , [t,r]×R N ×U ×R N (φ (t, x 0 ) + (r -t) L u φ (s, y) -φ (r, z)) γ 1 (dsdydu) γ 2 (dz) = 0    , where L u φ (s, y) = b (y, u) , Dφ (s, y) + ∂ t φ (s, y) , for all φ ∈ C 1,1 b R + × R N and all s ≥ 0, y ∈ R N . Here C 1,1 b R + × R N
is the class of real bounded, differentiable functions defined on R + × R N and having Lipschitz gradient.

Remark 3 1. For every finite time horizon T > 0, there exists a constant c > 0 such that, whenever u ∈ U , x t,x 0 ,u s ≤ c (1 + |x 0 |) , for all 0 ≤ t ≤ s ≤ T and all x 0 ∈ R N . Therefore, whenever γ ∈ Γ (t, r, x 0 ) ,

Supp (γ 1 ) ⊂ [t, r] × K x 0 ,c × U, Supp (γ 2 ) ⊂ K x 0 ,c , where K x 0 ,c = x ∈ R N : |x| ≤ c (1 + |x 0 |) .
We emphasize that the constant c can be chosen independently of t, x 0 , u.

Remark 4

The set Θ (t, r, x 0 ) contains all occupational measures γ t,r,x 0 ,u(•) issued from x 0 at time t. This follows from the following equality

-φ (t, x 0 ) + R N φ (r, z) γ t,r,x 0 ,u 2 (dz) = -φ (t, x 0 ) + φ r, x t,x 0 ,u r = r t ∂ t φ s, x t,x 0 ,u s + b x t,x 0 ,u s , u s , Dφ s, x t,x 0 ,u s ds = [t,r]×R N ×U (r -t) L u φ (s, y) γ t,r,x 0 ,u 1 (dsdydu) , for regular test functions φ ∈ C 1,1 b R + × R N .
One notices that the equality constraint in the definition of Θ (t, r, x 0 ) can alternatively be written

φ (t, x 0 ) + [t,r]×R N ×U (r -t) L u φ (s, y) γ 1 (dsdydu) - R N φ (r, z) γ 2 (dz) = 0.
It follows that Θ (t, r, x 0 ) is convex.

Linearized formulation for Mayer type control problems

We consider g ′ : R N -→ R assumed to satisfy1 (15)

   (i) the function g ′ is bounded, (ii) there exist real constants c, c 1 > 0 such that |g ′ (x) -g ′ (y)| ≤ c |x -y| , g ′ (x) ≥ c 1 for all (x, y) ∈ R N × R N . To every (t, x) ∈ [0, T ] × R N and u ∈ U , one associates the cost C g ′ (t, x, u) = g ′ x t,x,u
T and the corresponding value function [START_REF] Grammel | Singularly perturbed differential inclusions. an averaging approach[END_REF] V g ′ (t, x) = inf u∈U C g ′ (t, x, u) .

Under the assumptions ( 13) and ( 15), the value function V g ′ is the unique bounded, uniformly continuous viscosity solution of the Hamilton Jacobi (HJ) equation ( 17)

∂ t V g ′ (t, x) + H x, DV g ′ (t, x) = 0, for all (t, x) ∈ [0, T ] × R N , and V g ′ (T, •) = g ′ (•) on R N
, where the Hamiltonian is given by ( 18)

H (x, p) = inf u∈U b (x, u) , p , for all (t, x, p) ∈ R × R N × R N .
For proofs of the connection between V g ′ and ( 17), the reader is referred to [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF] and the references therein. We also consider the linearized problems

Λ g ′ (t, x) = inf γ=(γ 1 ,γ 2 )∈Θ(t,T,x) R N g ′ (z) γ 2 (dz)
and its dual

(19) η g ′ (t, x) = sup η ∈ R : ∃φ ∈ C 1,1 b R + × R N s.t. ∀ (s, y, v, z) ∈ [t, T ] × R N × U × R N , η ≤ (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x) ,
for all (t, x) ∈ [0, T ] × R N . The following result links the three quantities. Its proof follows the ideas in [START_REF] Buckdahn | Stochastic optimal control and linear programming approach[END_REF] and [START_REF] Goreac | Mayer and optimal stopping stochastic control problems with discontinuous cost[END_REF]. For reader's convenience, we give the proof in the Appendix.

Proposition 5 If ( 13) and ( 15) hold true, then, for every (t, x) ∈ [0, T ] × R N , one has

V g ′ (t, x) = Λ g ′ (t, x) = η g ′ (t, x) .
We have the following characterization of the set of constraints Θ (t, T, x 0 ) :

Corollary 6
The set Θ (t, T, x 0 ) is the closed convex hull of the family of occupational couples

Γ (t, T, x 0 ) Θ (t, T, x 0 ) = cl (co (Γ (t, T, x 0 ))) ,
for all T ≥ t ≥ 0. The operator cl designates the closure with respect to the topology induced by the weak convergence of probability measures.

For further details, the reader is referred to [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discouting[END_REF].

Remark 7 Consequently, if γ = (γ 1 , γ 2 ) ∈ Θ (t, T, x 0 ), there exists a sequence of convex combinations kn i=1 α n i γ t,T,x 0 ,u n i n converging to γ. Thus,

Supp (γ 1 ) ⊂ [t, T ] × K x 0 ,c × U, Supp (γ 2 ) ⊂ K x 0 ,c .
In particular, Θ (t, T, x 0 ) is compact.

Characterization of optimal measures

In this section we study necessary and sufficient conditions for characterizing optimal occupational measures. In the sequel we denote Θ(t, T, x) := Θ(t, x) for simplicity. Recall that

V g ′ (t, x) = Λ g ′ (t, x) = η g ′ (t, x)
and ( 20)

η g ′ (t, x) = sup η ∈ R : ∃φ ∈ C 1,1 b R + × R N s.t. ∀ (s, y, v, z) ∈ [t, T ] × R N × U × R N , η ≤ (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x)
,

for all (t, x) ∈ [0, T ] × R N . We denote by (21) D g ′ (t, x) = (η, φ) ∈ R × C 1,1 b R + × R N s.t. η = inf (s,y,v,z)∈[t,T ]×R N ×U ×R N {(T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x)} , for all (t, x) ∈ [0, T ] × R N .
Remark 8 We note that Θ(t, x) contains measures with compact support (see Remark 7). Consequently, we may consider that the test functions have also compact support. Moreover, in the formulation, we can replace the infimum over (s, y, v, z)

∈ [t, T ] × R N × U × R N
with the minimum over a compact set which contains the support of the occupational measures.

Consequently, the dual formulation becomes: [START_REF] Terrell | Some fundamental control theory i: Controllability, observability, and duality[END_REF] V g ′ (t, x) = sup{η, (η, φ) ∈ D g ′ (t, x)}.

Definition 9

We say that (η, φ) ∈ D g ′ (t, x) is an optimal pair whenever we have V g ′ (t, x) = η.

Remark 10 It is not always sure that optimal pairs exist. Fortunately, in this case we can define the set Ω using the sets

Ω 1 n associated to a sequence of pairs η 1 n , φ 1 n ∈ D g ′ (t, x) having the property that η 1 n ր η (t, x) = V (t, x). More precisely, 1 Ω coincides with the lim inf n→∞ 1 Ω 1 n
. Note that such a sequence always exists because of [START_REF] Terrell | Some fundamental control theory i: Controllability, observability, and duality[END_REF]. Definition 11 We denote by

(23) Ω g ′ (t, x) =    (s, y, v, z) ∈ [t, r] × R N × U × R N , s.t. η = (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x) , for every optimal pair (η, φ) ∈ D g ′ (t, x) .    Proposition 12 Let (t, x) ∈ [0, T ] × R N be fixed. Then, γ ∈ Θ (t, x) is optimal for Λ g ′ (t, x) iff γ Ω g ′ (t, x) = 1.

Proof.

Suppose that γ ∈ Θ (t, x) is such that γ Ω g ′ (t, x) = 1, i.e. the support of γ is included in Ω g ′ (t, x). Then, by definition, we have the following equality

η = (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x) .
on Ω g ′ (t, x), for all optimal pairs (η, φ) ∈ D g ′ (t, x). Consequently,

Ω g ′ (t,x) ηγ(dsdxdudz) = Ω g ′ (t,x) g ′ γ(dsdxdudz) = [t,T ]×R N ×U ×R N g ′ (z) γ(dsdxdudz) because γ ∈ Θ (t, x). It follows that γ (Ω (t, x)) η = V (t, x) = [t,T ]×R N ×U ×R N g ′ (z) γ(dsdxdudz)
and that γ ∈ Θ (t, x) is optimal. Conversely, suppose that γ ∈ Θ (t, x) is optimal. Then, we have:

V (t, x) = [t,T ]×R N ×U ×R N g ′ (z) γ(dsdxdudz) = [t,T ]×R N ×U ×R N (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x) γ(dsdxdudz) ≥ Ω g ′ (t,x) (T -t) L v φ (s, y) + g ′ (z) -φ (T, z) + φ (t, x) γ(dsdxdudz) = Ω g ′ (t,x) ηγ(dsdxdudz) = ηγ(Ω g ′ (t, x)) = V x) γ(Ω g ′ (t, x)).
for all optimal pairs (η, φ)

∈ D g ′ (t, x). Consequently, γ ∈ Θ (t, x) is such that γ Ω g ′ (t, x) = 1 Indeed, if γ Ω g ′ (t, x) < 1 we get V (t, x) = [t,T ]×R N ×U ×R N g ′ (z) γ(dsdxdudz) > V (t, x) .
because V (t, x) > 0. The last inequality leads to a contradiction.

Dual formulation for the averaged system

In order to characterize the optimal controls/measures for the averaged system, we first state it's dual formulation. In the sequel we assume that (7) holds true, either the assumption [START_REF] Friedman | Exact slow-fast decomposition of a class of non-linear singularly per-turbed optimal control problems via invariant manifolds[END_REF] or the assumption ( 9) is true, and F is locally Lipschitz. As previously, let us suppose that T > 0 is a fixed time horizon. We fix ε > 0, t ≥ 0 and (x 0 , y 0 ) ∈ R M × R N . To every u ∈ U , one can associate a couple of occupational measures γ t,T,x 0 ,y 0 ,u;ε = γ t,T,x 0 ,y 0 ,u;ε 1 , γ t,T,x 0 ,y 0 ,u;ε

2 ∈ P [t, T ] × R M × R N × U × P R M × R N defined by    γ t,T,x 0 ,y 0 ,u;ε 1 (A × B × C × D) = 1 T -t
T t 1 A×B×C×D s, x t,x 0 ,y 0 ,u;ε s , y t,x 0 ,y 0 ,u;ε s , u s ds, γ t,T,x 0 ,y 0 ,u;ε 2 = δ x t,x 0 ,y 0 ,u;ε T ,y t,x 0 ,y 0 ,u;ε T ,

for all Borel sets A ⊂ [t, T ], B ⊂ R M , C ⊂ R N and D ⊂ U . When (x, y) ∈ R M × R N , δ x,y
stands for the Dirac measure. One can also define γ t,t,x 0 ,y 0 ,u;ε = γ t,t,x 0 ,y 0 ,u;ε 1 , γ t,t,x 0 ,y 0 ,u;ε

2 ∈ P {t} × R M × R N × U × P R M × R N by setting γ t,t,x 0 ,y 0 ,u;ε 1 = δ t,x 0 ,y 0 ,ut , γ t,t,x,y,u;ε 2 = δ x,y .
The family of occupational measures [START_REF] Veliov | A generalization of the tikhonov theorem for singularly perturbed differential inclusions[END_REF] Γ (t, x 0 , y 0 ; ε) = γ t,T,x 0 ,y 0 ,u;ε 1 , γ t,T,x 0 ,y 0 ,u;ε

2

, for all u ∈ U .

can be embedded into a larger set

Θ (t, x 0 , y 0 ; ε) =                (γ 1 , γ 2 ) ∈ P [t, T ] × R M × R N × U × P R M × R N ∀φ ∈ C 1,1 b R + × R M × R N , [t,T ]×R M ×R N ×U ×R M ×R N (φ (t, x 0 , y 0 ) + (T -t) L u;ε φ (s, x, y) -φ (T, z, w)) γ 1 (dsdxdydu) γ 2 (dzdw) = 0,               
where L u;ε φ (s, x, y) = f (x, y, u) , 1 ε g (x, y, u) , Dφ (s, x, y) + ∂ t φ (s, x, y) ,

for all φ ∈ C 1,1 R + × R M × R N and all s ≥ 0, (x, y) ∈ R M × R N .
Remark 13 Using similar arguments as in the previous sections, the set Θ (t, T, x 0 , y 0 ; ε) contains all occupational measures γ t,T,x 0 ,y 0 ,u;ε issued from (x 0 , y 0 ) at time t. Moreover, it is also convex and relatively compact with respect to the weak convergence of probability measures (due to Prohorov's Theorem).

We suppose that h satisfies the hypotheses [START_REF] Goreac | Mayer and optimal stopping stochastic control problems with discontinuous cost[END_REF]. As previously, the linearized problem is

Λ ε,h (t, x 0 , y 0 ) = inf γ=(γ 1 ,γ 2 )∈Θ(t,x 0 ,y 0 ;ε) R M ×R N h (z) γ 2 (dzdw)
and its dual is

(25) η ε,h (t, x 0 , y 0 ) = sup    η ∈ R : ∃φ ∈ C 1,1 R + × R M × R N s.t. ∀ (s, x, y, v, z, w) ∈ [t, T ] × R M × R N × U × R × R N , η ≤ (T -t) L v;ε φ (s, x, y) + h (z) -φ (T, z, w) + φ (t, x 0 , y 0 ) .    , for all (t, x 0 , y 0 ) ∈ [0, T ] × R M × R N . Consequently, for every ε > 0 we have W ε,h (t, x 0 , y 0 ) = Λ ε,h (t, x 0 , y 0 ) = η ε,h (t, x 0 , y 0 ) .
We continue with the dual formulation for the averaged problem. We denote by

Θ (t, x 0 , y 0 ) =                        (γ 1 , γ 2 ) ∈ P [t, T ] × R M × R N × U × P R M × R N ∀ψ ∈ C 1,1 b R + × R M and ∀φ ∈ C 1,1 b R + × R M × R N , [t,T ]×R M ×R N ×U ×R M ×R N ψ (t, x 0 ) + (T -t) L u,f ψ (s, x) -ψ (T, z)) γ 1 (dsdxdydu) γ 2 (dzdw) = 0 and [t,T ]×R M ×R N ×U ×R M ×R N L u,g φ (s, x, y) γ 1 (dsdxdydu) γ 2 (dzdw) = 0                        where L u,f ψ (s, x, y) = f (x, y, u) , D x ψ (s, x) + ∂ t ψ (s, x) and L u,g φ (s, x, y) = g (x, y, u) , D y φ (s, x, y) , for all φ ∈ C 1,1 R + × R M × R N and all s ≥ 0, (x, y) ∈ R M × R N .
We define the following linearized problem

Λ h (t, x 0 , y 0 ) = inf γ=(γ 1 ,γ 2 )∈Θ(t,x 0 ,y 0 ) R M ×R N h (z) γ 2 (dzdw) .
We denote by

(26) η h (t, x 0 , y 0 ) = sup                  η ∈ R : ∃α ∈ C (R + ) with lim ε→0 α (ε) = 0 s.t. ∀ε > 0, ∃φ ∈ C 1,1 R + × R M × R N and ψ ∈ C 1,1 R + × R M s.t. φ -ψ ∞ + ∇ x φ -∇ x ψ ∞ ≤ α (ε) and s.t. ∀ (s, x, y, v, z, w) ∈ [t, T ] × R M × R N × U × R × R N , η ≤ (T -t) L v;ε φ (s, x, y) + h (z) -φ (T, z, w) + φ (t, x 0 , y 0 )                 
, for all (t, x 0 , y 0 ) ∈ [0, T ]×R M ×R N . Consequently, we can formulate the main result of this section:

Theorem 14 We have that W h (t, x 0 ) = Λ h (t, x 0 , y 0 ) = η h (t, x 0 , y 0 ) .

for all (t, x 0 , y 0 ) ∈ [0, T ] × R M × R N .

Proof. In a first step we recall that there exist an optimal measure γt,T,x 0 ,y 0 ;ε = γt,T,x 0 ,y 0 ;ε 1 γt,T,x 0 ,y 0 ;ε 2 ∈ Θ (t, x 0 , y 0 ; ε) such that Λ ε,h (t, x 0 , y 0 ) = R M ×R N h (z) γt,T,x 0 ,y 0 ;ε 2 (dzdw) for all (t, x 0 , y 0 ) ∈ [0, T ] × R M × R N and ε > 0. Moreover, we can find a subsequence and a probability measure γ such that γt,T,x 0 ,y 0 ;ε ⇀ γ (see Corollary 6 and Remark 7). Using the definitions of Θ (t, x 0 , y 0 ; ε) and Θ (t, x 0 , y 0 ), it is easy to see that γ ∈ Θ (t, x 0 , y 0 ). Consequently, for all γ ∈ Θ (t, x 0 , y 0 ). We have that (28) η h (t, x 0 , y 0 ) ≤ Λ h (t, x 0 , y 0 ) . ∀ (s, x, y, v, z, w)

Using

∈ [t, T ] × R M × R N × U × R M × R N ,
V δε ε,h (t, x 0 , y 0 ) ≤ (Tt) L v;ε V δε ε,h (s, x, y) + h (z) -V δε ε,h (T, z, w) + V δε ε,h (t, x 0 , y 0 ) .

Moreover lim ε→0

V δε ε,h (t, x 0 , y 0 ) = W h (t, x 0 ). Using the definition of η h (t, x 0 , y 0 ), we obtain that V δε ε,h (t, x 0 , y 0 ) ≤ η (t, x 0 , y 0 ). Consequently, (29) W h (t, x 0 ) = lim ε→0 V δε ε,h (t, x 0 , y 0 ) ≤ η h (t, x 0 , y 0 )

By combining the inequalities ( 27), ( 28) and (29) we complete the proof.

2 ( 2 (

 22 (27) Λ h (t, x 0 , y 0 ) ≤ R M ×R N h (z) γ t,T,x 0 ,y 0 dzdw) = lim ε→0 R M ×R N h (z) γ t,T,x 0 ,y 0 ;ε dzdw) = lim ε→0 Λ ε;h (t, x 0 , y 0 ) = lim ε→0 W ε,h (t, x 0 , y 0 ) = W h (t, x 0 ) for all (t, x 0 , y 0 ) ∈ [0, T ] × R M × R N .We continue by considering γ ∈ Θ (t, x 0 , y 0 ) and η ∈ R such that∃α ∈ C (R + ) with lim ε→0 α (ε) = 0 s.t. ∀ε > 0, ∃φ ∈ C 1,1 R + × R M × R N and ψ ∈ C 1,1 R + × R M s.t. φψ ∞ + ∇ x φ -∇ x ψ ∞ ≤ α (ε) and s.t. ∀ (s, x, y, v, z, w) ∈ [t, T ] × R M × R N × U × R × R N , η ≤ (Tt) L v;ε φ (s, x, y) + h (z)φ (T, z, w) + φ (t, x 0 , y 0 )By integrating with respect to γ we obtain thatη ≤ R M ×R N h (z) γ 2 (dzdw)and consequently,η h (t, x 0 , y 0 ) ≤ R M ×R N h (z) γ 2 (dzdw)

1 b[ 0 ,∈C 1 , 1 b[ 0 ,

 10110 Proposition 19 there exist two familiesV δε ε,h ∈ C 1,T + δ ε ] × R M × R N and V δε h T + δ] × R Nas in the definition of η (t, x 0 , y 0 ) s. t.

Note that we make the assumption g ′ (x) ≥ c1 > 0 for simplifying the calculus. Indeed, we can always add a positive constant sufficiently large to the function g ′ in order to obtain the previous inequality because g ′ is bounded.

Acknowledgments The author would like to thank the referee for valuable and very constructive comments which helped to improve the paper. The author was supported in part by the European project SADCO -Sensitivity Analysis for Deterministic Controller Design, (Marie Curie ITN-264735) and by the ANR Jeudy: ANR-10-BLAN 0112.

6 Characterization of optimal trajectories for the averaged system As already mentioned in the introduction, when the perturbed system is fully nonlinear it is very difficult to characterize the optimal trajectories using the Pontryagin maximum principle because we do not know exactly the form of the averaged dynamics. An alternative to this method is to look at the support of the occupational measures contained in the set Θ (t, x 0 , y 0 ) in order to obtain optimal trajectories from every (t, x 0 ) ∈ [0, T ] × R M . We denote by

Remark 15 We note that Θ(t, x 0 , y 0 ; ε) contains measures with compact support. Consequently, we may consider that the test functions have also compact support. Moreover, in the previous formulation, we can replace the infimum over (s, x, y, v, z, w)

with the minimum over a compact set which contains the support of the occupational measures.

Consequently, we can reformulate the dual formulation as folows:

Definition 16

We say that (η ε , φε ) ∈ D ε,h (t, x 0 , y 0 ) is an optimal pair whenever we have W ε,h (t, x 0 , y 0 ) = ηε .

Definition 17 Let (t, x 0 , y 0 ) ∈ [0, T ] × R M × R N be fixed. We denote by

and by (33)

1

Note that, as in Section 4, γ ε ∈ Θ (t, x 0 , y 0 ; ε) is optimal iff γ ε (Ω ε,h (t, x 0 , y 0 )) = 1 for all ε > 0.

Proof. First, suppose that γ ∈ Θ (t, x 0 , y 0 ) is such that γ (Ω h (t, x 0 , y 0 )) = 1. In order to shorten the formulas, we denote by ∆ :=

and

Consider now an optima pair η

x 0 , y 0 ) and with φ 1 n as in the definition of η h (t, x 0 , y 0 ). Using the previous estimation, we obtain

Consequently, γ ∈ Θ (t, x 0 , y 0 ) is optimal. Secondly, let γ ∈ Θ (t, x 0 , y 0 ) be optimal. For an optimal pair η 1 n , φ 1 n ∈ D 1 n ,h (t, x 0 , y 0 ) as in the definition of η (t, x 0 , y 0 ) we obtain

which leads to a contradiction.

Appendix

We prove the Proposition 5. We will make use of the following result due to N. V. Krylov (cf. [START_REF] Krylov | On the rate of convergence of finite-difference approximations for Bellman's equations with variable coefficients[END_REF], Theorem 2.1):

Proposition 19 There exists a constant C > 0 such that, for every δ ∈ (0, 1] , there exists a function

Proof. (of Proposition 5) We have seen that γ t,T,x,u ∈ Θ ( t, T, x) , for all (t, x) ∈ [0, T ] × R N and all u ∈ U . It follows that (34)

For any γ ∈ Θ (t, T, x) , whenever (η, φ)

To complete the proof, one only needs to show that (36) V g ′ (t, x) ≤ η g ′ (t, x) .

To this purpose, we apply the previous Proposition and get, for every δ > 0, the existence of some regular V δ such that ∂ t V δ (t, x) + H t, x, DV δ (t, x) ≥ 0, for all (t, x) ∈ [0, T ] × R N . Thus, choosing C as in Proposition 19, for every (t, s, x, y, z) ∈ [0, T ] 2 × R 3N and every v ∈ U , one has V δ (t, x) -≤t) L v V δ (s, y) + g ′ (z) -V δ (T, z) + V δ (t, x).

Hence,

V δ (t, x) -Cδ ≤ η g ′ (t, x) .

The inequality (36) follows by passing to the limit as δ → 0 and recalling that Proposition 19 (ii) holds true. The proof of our Theorem is now complete.