J O Ël

Mamadou I Kon
email: mamadou.kone@malix.univ-paris1.fr

Joël Blot
email: blot@univ-paris1.fr

Mamadou I Koné

PONTRYAGIN PRINCIPLE FOR A MAYER PROBLEM GOVERNED BY A DELAY FUNCTIONAL DIFFERENTIAL EQUATION

Keywords: optimal control, Pontryagin principle, functional differential equation. MSC2010-AMS: 49J21, 49K21, 34K09

We establish Pontryagin principles for a Mayer's optimal control problem governed by a functional differential equation. The control functions are piecewise continuous and the state functions are piecewise continuously differentiable. To do that, we follow the method created by Philippe Michel for systems governed by ordinary differential equations, and we use properties of the resolvent of a linear functional differential equation.

Introduction

We consider the following problem of optimal control. It is called a problem of Mayer since its criterion takes into account only the final value of the state; it is governed by a functional differential equation in presence of terminal constraints.

Maximize J(x, u) := g 0 (x(T )) when x ∈ C 0 ([-r, T ], R n ), x ∈ P C 1 ([0, T ], R n ) u ∈ P C 0 ([0, T ], U ) ∀t ∈ [0, T ] \ F, x ′ (t) = f (t, x t , u(t))

x 0 = φ ∀j = 1, ..., n i , g j (x(T )) ≥ 0 ∀j = n i + 1, ..., n i + n e , g j (x(T )) = 0.

                   (M)
where the g j : R n → R are mappings, the state variable x is a piecewise continuously differentiable function (see Section 2), the control variable u is a piecewise continuous function (see Section 2), U is a nonempty subset of R d , F denotes a finite subset of [0, T ] (not a priori fixed), x t (θ) := x(t + θ) when θ ∈ [-r, 0], φ is fixed continuous function from [-r, 0] into R n . The only assumptions that we do on this problem are the following ones.

f ∈ C 0 ([0, T ] × C 0 ([-r, 0], R n ) × U, R n ) ∀(t, φ, ξ) ∈ [0, T ] × C 0 ([-r, 0], R n ) × U, D 2 f (t, φ, ξ) exists D 2 f ∈ C 0 ([0, T ] × C 0 ([-r, 0], R n ) × U, L(C 0 ([-r, 0], R n ), R n )) D 2 f is a bounded operator.        (1.1)
where C 0 (X, Y ) denotes the space of the continuous mappings from X into Y , D 2 f (t, φ, ξ) denotes the partial Fréchet differential of f with respect to its second Date: November 9, 2015.

1 variable, and L(E, E 1 ) is the vector space of the continuous linear mappings from E into E 1 when E and E 1 are normed vector spaces. ∀j ∈ {0, ..., n i + n e }, g j ∈ C 1 (R n , R).

(1.2)

where C 1 means continuously Fréchet differentiable.

To establish a Pontryagin principle for problem (M) under assumptions which are so light as possible, we follow the method created by Philippe Michel in [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF] for systems governed by ordinary differential equations. This method is also used in [START_REF] Alexéev | Commande optimale[END_REF] for Bolza problems. We can say that this work is an essay to generalize the method of Michel to the setting of systems governed by functional differential equations.

On the question of the resolvent of (nonautonomous) linear functional differential equations, the difference between the results that we use (issued from [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF]) and the results of Banks [START_REF] Banks | Representation of solutions of linear functional differential equations[END_REF] is the choice of the class of solutions: we use continuously differentiable and piecewise continuously solutions with a continuous vector field and Banks uses absolutely continuous solutions without the continuity of the vector field. On the problem of optimal control, the difference between our setting and the setting of Banks [START_REF] Banks | A maximum principle for optimal control problems with functional differential systems[END_REF] (except that Banks considers a Lagrange problem) is that we use piecewise continuously differentiable state variables and piecewise continuous control variables (as [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF] and [START_REF] Alexéev | Commande optimale[END_REF]) and banks uses absolutely continuous state variables and bounded measurable control variables. Now we describe the contents of the paper. In Section 2 we specify the notation. In Section 3 we recall some precise properties of the resolvent of linear functional differential equations in the framework of piecewise continuous functions. In Section 4 we give the statement of a Pontryagin principle. In Section 5 we give a proof of this Pontryagin principle.

Notation

M n (R) denotes the space of the real n × n matrices. • L denotes the norm of the linear continuous operators.

When a < b are two real numbers,

C 0 R ([a, b], R n ) (respectively C 0 L ([a, b], R n )) is the space of the right-continuous (respectively left-continuous) functions from [a, b] into R n , and C 1 ([a, b], R n ) is the space of the continuously differentiable functions from [a, b] into R n . BV ([a, b], R n ) is the space of the bounded variation functions from [a, b] into R n . When g ∈ BV ([a, b], R n ) the variation of g on [a, b] is denoted by V b a (g). We set N BV ([a, b], R n ) := {g ∈ BV ([a, b], R n ) ∩ C 0 L ([a, b], R n ) : g(a) = 0}. When g ∈ N BV ([a, b], R n ), g BV := V b a (g) defines a norm on N BV ([a, b], R n ). AC([a, b], R n ) is the space of the absolutely continuous functions [a, b] into R n . Let g : [a, b] → R n be
a function, and t ∈ [a, b) (respectively (a, b]) when it exists the right-hand limit (respectively the left-hand limit) of g at t is g(t+) := lim s→t,s>t g(s) (respectively g(t-) := lim s→t,s<t g(s)).

Let

f : [a, b] × [c, d] → R n be a mapping, and let (t, s) ∈ [a, b) × [c, d] (re- spectively (a, b] × [c, d]).
When it exists the right-partial derivative (respectively left-partial derivative)with respect to the first variable of f at (t, s) is denoted by ∂f (t,s) ∂t+ (respectively ∂f (t,s) ∂t-).

A function g : [a, b] → R n is called piecewise continuous when it is continuous or when there exists a finite list of points, t 0 = a < t 1 < ... < t p < t p+1 = b such that g is continuous at each t ∈ [a, b] \ {t k : k ∈ {0, ..., p + 1}} and such that, for all k ∈ {0, ..., p}, g(t k +) exists, and for all k ∈ {1, ..., p + 1}, g(t k -) exists. We denote by

P C 0 ([a, b], R n ) the space of the piecewise continuous functions from [a, b] into R n . g ∞ := sup{ g(t) : t ∈ [a, b]} defines a norm on P C 0 ([a, b], R n ); endowed with this norm, P C 0 ([a, b], R n ) is not complete. When g ∈ P C 0 ([a, b], R n ) we denote by N g the set points t ∈ [a, b] where g is not continuous at t. When we fix a finite subset π ⊂ [a, b], we set P C 0 π ([a, b], R n ) := {g ∈ P C 0 ([a, b], R n ) : N g ⊂ π}. Endowed with . ∞ , P C 0 π ([a, b], R n ) is a Banach space. A function g : [a, b] → R n is called piecewise-C 1 when g is C 1 on [a, b] or when g ∈ C 0 ([a, b], R n
) and there exists a finite list t 0 = a < t 1 < ... < t p < t p+1 = b such that g is C 1 on [t k , t k+1 ] for all k ∈ {0, ..., p} and such that, for all k ∈ {0, ..., p}, g ′ (t k +) exists and, for all k ∈ {1, ..., p+1}, g ′ (t k -) exists. We denote by

P C 1 ([a, b], R n ) the space of the piecewise-C 1 functions from [a, b] into R n . When g ∈ P C 1 ([a, b], R n ) we denote by N g ′ the set of the t ∈ [a, b] such that g ′ is not continuous at t. When we fix a finite subset π ⊂ [a, b], we set P C 1 π ([a, b], R n ) := {g ∈ P C 1 ([a, b], R n ) : N g ′ ⊂ π}.
In a normed space E, when x ∈ E and r ∈ (0, +∞) we set B(x, r) := {z ∈ E : zx ≤ r}.

Linear functional differential equations

3.1. The continuous time framework. We consider a mapping L :

[0, T ] → L(C 0 ([-r, 0], R n ), R n ) which satisfies the following condition. L ∈ C 0 ([0, T ], L(C 0 ([-r, 0], R n ), R n )). (3.1)
From L and a function φ ∈ C 0 ([-r, 0], R n ), when σ ∈ [0, T ], we consider the following linear functional differential equation under an initial condition.

x

′ (t) = L(t)x t , x σ = φ. (3.2)
When moreover h ∈ C 0 ([0, T ], R n ) we consider the nonhomogeneous following problem.

x ′ (t) = L(t)x t + h(t), x σ = φ.

(3.3) A solution of one of these problems is a function x ∈ C 0 ([-r, T ], R n ) which is of class C 1 on [0, T ] and whom the derative satisfies the equation at each point of [0, T ]. The only difference between Theorem 4.1 of [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF] and the following result is the choice of η(t, -r) = 0 instead of η(t, 0) = 0..

(i) ∀t ∈ [0, T ], η(t, •) ∈ N BV ([-r, 0], M n (R)) (ii) ∀t ∈ [0, T ], η(t, •) BV = L(t) L (iii) [t → η(t, •)] ∈ C 0 ([0, T ], N BV ([-r, 0], M n (R))) (iv) ∀t ∈ [0, T ], ∀φ ∈ C 0 ([-r, T ], R n ), L(t)φ = 0 -r d 2 η(t, θ)φ(θ) (v) η is Lebesgue measurable on [0, T ] × [-r, 0] (vi) η is Riemann integrable on [0, T ] × [-r, 0].
The following result is devoted to the resolvents of the equations of (3.2) and (3.3). It is proven in [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF]. Theorem 3.2. Under (3.1) there exists a mapping X : [0, T ] × [0, T ] → M n (R) which satisfies the following properties.

(i) X is bounded on [0, T ] × [0, T ] (ii) ∀s, t ∈ [0, T ] such that s ≥ t, X(t, s) = I (identity) (iii) ∀s ∈ [0, T ], X(•, s) ∈ AC([0, T ], M n (R)) (iv) ∀s, t ∈ [0, T ], X(•, s) is right-differentiable and left-differentiable at t, ∂X(•,s) ∂t+ ∈ C 0 R ([0, T ], M n (R)), ∂X(•,s) ∂t-∈ C 0 L ([0, T ], M n (R)) (v) ∀s, t ∈ [0, T ] such that s ≥ t, ∂X(t,s) ∂t+ -∂X(t,s) ∂t- = η(t, (s -t)+) -η(t, (s -t)) (vi) ∀s ∈ [0, T ], the set of the points of [0, T ] where X(•, s) is not differentiable is at most countable (vii) ∀t ∈ [0, T ], X(t, •) ∈ BV ([0, T ], M n (R)) ∩ C 0 L ([0, T ], M n (R)). We define the mapping Z : {(t, σ) ∈ [0, T ] × [0, T ] : t ≥ σ} × C 0 ([-r, 0], R n ) → R n by setting Z(t, σ, φ) := t σ X(t, ξ) σ-ξ -r d 2 η(ξ, θ)φ(ξ -σ + θ) dξ.
Then the following properties hold for all σ ∈ [0, T ] and for all φ

∈ C 0 ([-r, 0], R n ). (viii) Z(•, σ, φ) ∈ C 0 ([σ, T ], R n ) (ix) ∀t ∈ [σ, T ], Z(•, σ, φ) is right-differentiable and left-differentiable at t, ∂Z(•,σ,φ) ∂t+ ∈ C 0 R (([σ, T ], R n ), and ∂Z(•,σ,φ) ∂t- ∈ C 0 L (([σ, T ], R n ) (x) ∀t ∈ [σ, T ], ∂Z(t,σ,φ) ∂t+ -∂Z(t,σ,φ) ∂t- = ∂X(t,s)
∂t--∂X(t,s) ∂t+ . We define the set D := {(t, σ) ∈ [0, T ] × [0, T ] : t ≥ σ -r} and we define the mapping U :

D × C 0 ([-r, 0], R n ) → R n by setting U (t, σ, φ) := X(t, σ)φ(0) + Z(t, σ, φ) if t ≥ σ φ(t -σ) if σ -r ≤ t ≤ σ.
Then the following assertions hold for all σ ∈

[0, T ] for all φ ∈ C 0 ([-r, 0], R n ). (xi) U (•, σ, φ) | [σ,t] ∈ C 1 ([σ, T ], R n ), and U (•, σ, φ) ∈ C 0 ([σ -r, T ], R n ) (xii) U (•, σ, φ) is the (unique) solution of (3.2) on [σ, T ].
Moreover we define the mapping V :

D × C 0 ([-r, 0], R n ) × C 0 ([0, T ], R n ) → R n by setting V (t, σ, φ, h) := U (t, σ, φ) + t σ X(t, α)h(α)dα if t ≥ σ φ(t -σ) if σ -r ≤ t ≤ σ.
Then the following assertions hold for all σ

∈ [0, T ] for all φ ∈ C 0 ([-r, 0], R n ) and for all h ∈ C 0 ([0, T ), R n ) (xiii) V (•, σ, φ, h) | [σ,T ] ∈ C 1 ([σ, T ], R n ) and V (•, σ, φ, h) ∈ C 0 ([σ -r, T ], R n ) (xiv) V (•, σ, φ, h) is the (unique) solution of (3.3) on [σ, T ].
The proof of this theorem is contained into Section 6 of [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF]. The only differences between the results of [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF] and the present paper are the replacing of the condition g(b) = 0 by g(a) = 0 in the definition of N BV ([a, b], R n ) and the extension of η into η 1 with η 1 (t, θ) = 0 when θ < -r instead of η(t, θ) = 0 when θ > 0.

3.2. The piecewise continuous time framework. Instead of the continuity of the vector field L we assume that

L ∈ P C 0 ([0, T ], L(C 0 ([-r, 0], R n ), R n )). (3.4) When φ ∈ C 0 ([-r, 0], R n ), when σ ∈ [0, T ],
and when h ∈ P C 0 ([0, T ], R n ), we consider the following problems.

∀t ∈ [0, T ] \ N x ′ , x ′ (t) = L(t)x t , x σ = φ (3.5) ∀t ∈ [0, T ] \ N x ′ , x ′ (t) = L(t)x t + h(t), x σ = φ. (3.6) A solution of (3.5) or of (3.6) is a function x ∈ P C 1 ([0, T ], R n ); more precisely x ∈ P C 1 NL ([0, T ], R n ) for (3.5) and x ∈ P C 1 NL∪N h ([0, T ], R n ) for (3.6).
We can deduce the results of the piecewise continuous time from those of the continuous time framework by proceeding in the following way. If 0 = t 0 < t 1 < ... < t p < t p+1 = T are the points of N L , for all k ∈ {0, ..., p} we denote by L k the (continuous) restriction of L at [t k , t k+1 ]. When we fix σ ∈ [0, T ) we consider the index m such σ < t m < ... < t p+1 = T and we split the problem (3.5) into a finite list of problems like (3.2) as follows: first we have a solution z m of the problem (x

′ (t) = L m-1 (t)x t , x σ = φ) on [σ, t m ], secondly we have the solution z m+1 of the problem (x ′ (t) = L m (t)x t , x σ = φ m ) on [t m , t m+1 ], where φ m (θ) := z m (t m +θ) for θ ∈ [-r, 0],
and inductively until to have a solution z p+1 of the problem (x

′ (t) = L p (t)x t , x σ = φ p ) on [t p , t p+1 ], where φ p (θ) := z p (t p + θ) for θ ∈ [-r, 0]. Then the function z : [-t, T ] → R n , defined by z(t) := z k (t) when t ∈ [t k-1 , t k ], is a solution of (3.5).
Moreover using Proposition 3.1, for all k ∈ {0, ..., p}, we obtain the existence of

η k : [t k , t k+1 ] × [-r, 0] → M n (R)
(i) ∀t ∈ [0, T ], η(t, •) ∈ N BV ([-r, 0], M n (R)) (ii) ∀t ∈ [0, T ], η(t, •) BV = L(t) L (iii) [t → η(t, •)] ∈ P C 0 NL ([0, T ], N BV ([-r, 0], M n (R))) (iv) ∀t ∈ [0, T ], ∀φ ∈ C 0 ([-r, T ], R n ), L(t)φ = 0 -r d 2 η(t, θ)φ(θ) (v) η is Lebesgue measurable on [0, T ] × [-r, 0] (vi) η is Riemann integrable on [0, T ] × [-r, 0].
Now we want to obtain a result which is analogous to Theorem 3.2 for the piecewise continuous time framework. We proceed as in [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF], replacing the prop-

erty [t → η(t, •)] ∈ C 0 ([0, T ], N BV ([-r, 0], M n (R)) by the property [t → η(t, •)] ∈ P C 0 NL ([0, T ], N BV ([-r, 0], M n (R)
) and then we obtain the following result. Theorem 3.4. Under (3.4) there exists a mapping X :

[0, T ] × [0, T ] → M n (R) which satisfies the following properties. (i) X is bounded on [0, T ] × [0, T ] (ii) ∀s, t ∈ [0, T ] such that s ≥ t, X(t, s) = I (identity) (iii) ∀s ∈ [0, T ], X(•, s) ∈ AC([0, T ], M n (R)) (iv) ∀s, t ∈ [0, T ], X(•, s) is right-differentiable and left-differentiable at t, ∂X(•,s) ∂t+ ∈ C 0 R ([0, T ], M n (R)), ∂X(•,s) ∂t-∈ C 0 L ([0, T ], M n (R)) (v) ∀s ∈ [0, T ], ∀t ∈ [0, T ] \ N L such that s ≥ t, ∂X(t,s) ∂t+ -∂X(t,s) ∂t- = η(t, (s -t)+) -η(t, (s -t)) (vi) ∀s ∈ [0, T ], the set of the points of [0, T ] where X(•, s) is not differentiable is at most countable (vii) ∀t ∈ [0, T ], X(t, •) ∈ BV ([0, T ], M n (R)) ∩ C 0 L ([0, T ], M n (R)). We define the mapping Z : {(t, σ) ∈ [0, T ] × [0, T ] : t ≥ σ} × C 0 ([-r, 0], R n ) → R n by setting Z(t, σ, φ) := t σ X(t, ξ) σ-ξ -r d 2 η(ξ, θ)φ(ξ -σ + θ) dξ.
Then the following properties hold for all σ ∈ [0, T ] and for all φ

∈ C 0 ([-r, 0], R n ). (viii) Z(•, σ, φ) ∈ C 0 ([σ, T ], R n ) (ix) ∀t ∈ [σ, T ], Z(•, σ, φ) is right-differentiable and left-differentiable at t, ∂Z(•,σ,φ) ∂t+ ∈ C 0 R (([σ, T ], R n ), and ∂Z(•,σ,φ) ∂t- ∈ C 0 L (([σ, T ], R n ) (x) ∀t ∈ [σ, T ] \ N L , ∂Z(t,σ,φ) ∂t+ -∂Z(t,σ,φ) ∂t- = ∂X(t,s) ∂t--∂X(t,s) ∂t+ . We define the set D := {(t, σ) ∈ [0, T ] × [0, T ] : t ≥ σ -r} and we define the mapping U : D × C 0 ([-r, 0], R n ) → R n by setting U (t, σ, φ) := X(t, σ)φ(0) + Z(t, σ, φ) if t ≥ σ φ(t -σ) if σ -r ≤ t ≤ σ.
Then the following assertions hold for all σ ∈ [0, T ] for all φ ∈ C 0 ([-r, 0], R n ).

(xi) U (•, σ, φ) | [σ,t] ∈ P C 1 ([σ, T ], R n ), and U (•, σ, φ) ∈ C 0 ([σ -r, T ], R n ) (xii) U (•, σ, φ) is the (unique) solution of (3.5) on [σ, T ].
Moreover we define the mapping V :

D × C 0 ([-r, 0], R n ) × C 0 ([0, T ], R n ) → R n by setting V (t, σ, φ, h) := U (t, σ, φ) + t σ X(t, α)h(α)dα if t ≥ σ φ(t -σ) if σ -r ≤ t ≤ σ.
Then the following assertions hold for all σ Proof. We set k(α, s) := η(α, sα). After Theorem 5.4 in [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF], there exists R which satisfies R(t, s) = k(t, s) -t s R(t, α)k(α, s)dα. Ever after [START_REF] Blot | Resolvent of nonautonomous delay functional differential equations[END_REF] we have X(t, s) := I -t s R(α, s)dα. Then we calculate

∈ [0, T ] for all φ ∈ C 0 ([-r, 0], R n ) and for all h ∈ C 0 ([0, T ), R n ) (xiii) V (•, σ, φ, h) | [σ,T ] ∈ P C 1 ([σ, T ], R n ) and V (•, σ, φ, h) ∈ C 0 ([σ -r, T ], R n ) (xiv) V (•, σ, φ, h) is the (unique) solution of (3.6) on [σ, T ].
I - t s Y (α, t)k(α, s)dα = I - t s X(t, α)k(α, s)dα = I - t s (I - t α R(β, α)dβ)k(α, s)dα = I - t s k(α, s)dα + t s ( t α R(β, α)k(α, s)dβ)dα = I - t s k(β, s)dβ + t s ( β s R(β, α)k(α, s)dα)dβ = I - t s [k(β, s) - t s β s R(β, α)k(α, s)dα]dβ = I - t s R(β, s)dβ = X(t, s) = Y (s, t).
The integral equation which is present into the previous statement is called the adjoint equation of (3.5).

Pontryagin principle

First we give the qualification condition of Michel [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF], where (x, u) is an admissible process of (M).

(QC)

           ∀(c j ) 0≤j≤ni+ne ∈ R 1+p+q if ∀j = 0, ..., n i , c j ≥ 0 ∀j = 1, ..., n i , c j g j (x(T )) = 0 ni+ne j=0 c j Dg j (x(T )) = 0 then ∀j = 0, ..., n i + n e , c j = 0.
The main result of the paper is the following statement of a Pontryagin principle.

(Si) ∀j ∈ {0, ..., n i }, λ j ≥ 0 (Sl) ∀j ∈ {0, ..., n i }, λ j g j (x(T )) = 0 (AE) ∀t ∈ [0, T ], d dt (p(t) + min{t+r,T } t p(α)η(α, t -α)dα) = 0 (T) p(T ) = ni+ne j=0 λ j Dg j (x(T )) (MP) ∀t ∈ [0, T ], ∀u ∈ U , p(t)f (t, x t , u(t)) ≥ p(t)f (t, x t , u)
If moreover (QC) is fulfilled, we obtain the following additional conclusions.

(A2) There exists ǫ > 0 such that p(t) = 0 for all t ∈ (Tǫ, T ]. (A2) p(T ) = 0 and, for all t ∈ [0, T ], p | [t,min{t+r,T }] = 0.

In this statement, (NN) is a condition of non nullity of the multipliers, (Si) is a condition on the signs of multipliers, (Sl) is a condition of slackness on the final inequality constraints, (AE) is called the adjoint equation, (T) is the transversality condition, and (MP) is the maximum principle. The mapping η which is present into (AE) comes from Proposition 3.3 with L(t) = D 2 f (t, x t , u(t)).

proof of the Pontryagin principle

Our proof follows the proof given by Michel in [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF]; we provide the useful changes to adapt it to the setting of systems governed by a functional differential equation. Note that we can choose u as a right-continuous function without to lost generality. We arbitrarily fix S = {(t i , v i ) : i ∈ {1, ..., N }} where 0 ≤ t 1 ≤ ... ≤ t N < T and the v i ∈ U ; we denote by S the set of all these S. When a = (a 1 , ..., a N ) ∈ R N + , we define J(i) := {j ∈ {1, ..., i} : t j = t i } and we set b i := 0 when J(i) = ∅ and b i := j∈J(i) a j when J(i) = ∅. After that we define the subintervals Then the partial differential D a z(T, S, 0) exists and the following equality holds

I i := [t i + b i , t i + b i + a i )
D a z(T, S, 0)a = N i=1 a i X(T, t i )[f (t i , x ti , v i ) -f (t i , x ti , u(t i ))].
where X(T, t i ) comes from Theorem 3.4 when L(t) = D 2 f (t, x t , u(t)).

Proof. We set ∆(t, S, a) := [f (t, x t , u(t, S, a))-f (t, x t , u(t))] and using Theorem 3.4 we obtain z(T, S, a) = V (T, 0, 0, ∆(•, S, a))= X(T, 0)0+

T 0 X(T, ξ)( 0 -r d 2 η(ξ, θ)0(ξ+ θ)dξ + T 0 X(T, ξ)∆(ξ, S, a)dξ = T 0 X(T, ξ)∆(ξ, S, a)dξ. Since ∆(ξ, S, a) = 0 when ξ ∈ [0, T ] \ ∪ 1≤i≤N I i , we obtain z(T, S, a) = N i=1 ti+bi+ai ti+bi X(T, ξ)[f (t i , x ti , v i ) -f (t i , x ti , u(t i ))]dξ. Note that a i X(T, t i )[f (t i , x ti , v i ) -f (t i , x ti , u(t i ))] = ti+bi+ai ti+bi X(T, t i )[f (t i , x ti , v i ) -f (t i , x ti , u(t i ))]dξ.
Since u(t, S, 0) = u(t) we have ∆(t, S, 0) = 0 and then z(T, S, 0) = 0. For all i ∈ {1, ..., N } we define ρ i := S × R N + → R n by setting

̺ i (S, a) := 1 a i ti+bi+ai ti+bi [X(t, s)∆(s, S, a)-X(T, t i )(f (t i , x ti , v i )-f (t i , x ti , u(t i )))]ds

BLOT KON É

Since ∆(T, S, 0) = 0 we have σ(T, 0) = 0. We set Ξ

i := f (t i , x ti , v i )-f (t i , x ti , u(t i )).
Then we have e(T, a)e(T, 0)

-N i=1 a i Ξ i = T 0 ∆(t, S, a) dt -0 -N i=1 a i Ξ i = [0,T ]\∩ N i=1 Ii ∆(t, S, a) dt + ∩ N i=1 Ii ∆(t, S, a) dt - N i=1 a i Ξ i = 0 + N i=1 Ii ∆(t, S, a) dt - N i=1 a i Ξ i = N i=1 ti+b++ai ti+bi ∆(t, S, a) dt - N i=1 ti+b++ai ti+bi Ξ i dt = N i=1 a i 1 ai ti+b++ai ti+bi ( ∆(t, S, a) -Ξ i )dt.
And so defining the function

ν i : S × (R N + ∩ B(0, δ)) → R + by setting ν i (S, a) := 1 ai ti+b++ai ti+bi ( ∆(t, S, a) -Ξ i )dt if a i = 0 0 if a i = 0, we obtain, for all a ∈ R N + ∩ B(0, δ), e(T, a) = e(T, 0) + N i=1 a i Ξ i + N i=1 a i ν i (S, a). (5.5)
Using the change of variable

s = t i + b i + θa i we obtain ν i (S, a) = 1 0 ( ∆(t i + b i + θa i , S, a) -Ξ i )dθ.
In the previous proof we have yet seen that lim a→0 ( ∆(t i + b i + θa i , S, a) -Ξ i ) = 0, and that there exists c ∈ (0, +∞) such that, for all

a ∈ R N + ∩ B(0, δ), for all θ ∈ [0, 1], | ∆(t i + b i + θa i , S, a) -Ξ i | ≤ c.
And so we can use the theorem of the dominated convergence of Lebesgue and assert that lim a→0 ν i (S, a) = 0. And then, using (5.5) we can say that e(T, •) is differentiable at 0 and that its partial differential is D 2 e(T, 0).a = N i=1 a i Ξ i that implies the existence of a mapping µ : S × (R N + ∩ B(0, δ)) → R such that lim a→0 µ(a) = 0 and e(T, a)e(T, 0) -

N i=1 a i Ξ i = a • µ(a). We fix δ 1 ∈ (0, δ] such that a ≤ δ 1 =⇒ |µ(a)| ≤ 1. Then, when a ∈ R n + ∩ B(0, δ 1 )
we have e(T, a) = |σ(T, a)| ≤ D 2 σ(T, 0) • a + a|. To conclude it suffices to take c 2 := D 2 e(T, 0) + 1.

Lemma 5.3. Let Γ : [0, T ] × C 0 ([-r, 0], R n ) → R n . Let 0 = τ 0 < τ 1 < ... < τ ℓ < τ ℓ+1 =
T and F := {τ i : i ∈ {0, ..., ℓ}}. We assume that, for all i ∈ {0, ..., ℓ}, Γ is continuous on

[τ i , τ i+1 ] × C ([-r, 0], R n ).Then the Nemytskii operator N Γ : C 0 ([0, T ], C 0 ([-r, 0], R n )) → P C 0 F ([0, T ], R n ), defined by N Γ (Φ) := [t → Γ(t, Φ(t))], is continuous. Proof. Let Φ ∈ C 0 ([0, T ], C 0 ([-r, 0], R n )). Then, for all i ∈ {0, ..., ℓ}, the restriction of Φ at [τ i , τ i+1 ] belongs to C 0 ([τ i , τ i+1 ], C 0 ([-r, 0], R n )). Since Γ is continuous on [τ i , τ i+1 ] × C 0 ([-r, 0], R n ), we know that N Γ (Φ) ∈ C 0 ([τ i , τ i+1 ], R n ). Moreover we obtain that N Γ (Φ) ∈ P C 0 F ([0, T ], R n ). We arbitrarily fix Φ ∈ C 0 ([0, T ], C 0 ([-r, 0], R n ))
. Using Lemma 3.10 in [START_REF] Blot | Superposition operators between various almost periodic function spaces and applications[END_REF], we know that: ∀i ∈ {0, ..., ℓ},∀ǫ > 0, ∃β ǫ,i > 0, such that,

∀Ψ i ∈ C 0 ([τ i , τ i+1 ], C 0 ([-r, 0], R n )), sup t∈[τi,τi+1] Ψ i (t) -P (t) ≤ β ǫ,i =⇒ sup t∈[τi,τi+1] Γ(t, Ψ i (t)) -Γ(t, Φ(t)) ≤ ǫ.
We arbitrarily fix ǫ > 0 and we set

β ǫ := min 0≤i≤ℓ β ǫ,i > 0. Let Ψ ∈ C 0 ([0, T ], C 0 ([-r, 0], R n )) such that sup t∈[0,T ] Ψ(t) -Φ(t) ≤ β ǫ ; then we have, ∀i ∈ {0, ..., ℓ}, sup t∈[τi,τi+1] Ψ(t) -Φ(t) ≤ β ǫ,i
that implies: ∀i ∈ {0, ..., ℓ}, sup t∈[τi,τi+1] Γ(t, Ψ(t)) -Γ(t, Φ(t)) ≤ ǫ, and consequently we obtain that sup t∈[0,T ] Γ(t, Ψ(t)) -Γ(t, Φ(t)) ≤ ǫ. Lemma 5.4. There exist δ 2 ∈ (0, +∞) and c 4 ∈ (0, +∞) such the following assertions hold.

(i) ∀a ∈ R N + ∩ B(0, δ 2 ), x(•, S, a) is defined on [0, T ] all over. (ii) ∀a ∈ R N + ∩ B(0, δ 2 ), ∀t ∈ [0, T ], x(t, S, a) -x(t) ≤ c 4 . a . Proof. Let a ∈ R N + ∩ B(0, δ 1 )
where δ 1 is provided by the previous lemma. By induction we built the sequence (x m (•, S, a)) m∈N of functions from [0, T ] into R n in the following way.

   x 0 (•, S, a) := x ∀m ≥ 1, ∀t ∈ [0, T ], x m (t, S; a) = x(0) + t 0 f (s, x m-1 (•, S, a) s , u(s, S, a))ds ∀m ≥ 1, x m 0 = φ We have x 1 (t, S, a)-x 0 (t, S, a) = x 1 (t, S, a)-x(t) = t 0 f (s, x s , u(s, S, a))ds- t 0 f (s, x s , u(s))ds ≤ t 0 f (s, x s , u(s, S, a)) -f (s, x s , u(s)) ds ≤ T 0 f (s, x s , u(s, S, a)) -f (s, x s , u(s)) ds ≤ c 2 • a .
And so we have proven the followowing assertion:

∀a ∈ R N + ∩ B(0, δ 1 ), ∀t ∈ [0, T ], x 1 (t, S, a) -x 0 (t, S, a) ≤ c 2 . a . Then, for all t ∈ [0, T ], ∀θ ∈ [-r, 0], if t + θ ≥ 0 then x 1 (t + θ, S, a) - x 0 (t + θ, S, a) ≤ c 2 • a , and if t + θ < 0 then x 1 (t + θ, S, a) -x 0 (t + θ, S, a) = φ(θ) -φ(θ) = 0 ≤ c 2 • a .
And so we have proven the following assertion.

∀a ∈ R N + ∩ B(0, δ 1 ), ∀t ∈ [0, T ], x 1 (•, S, a) t -x 0 (•, S, a) t ≤ c 2 • a . (5.6)
We introduce the set

B := {(t, φ, v) ∈ [0, T ] × C 0 ([-r, 0], R n ) × U : φ -x t ∞ ≤ r, v ∈ {u(t), v 1 , ..., v N }}.
Note that B is bounded since it is included into the bounded set [0, T ] × B(x, r) × (u([0, T ])∪{v 1 ..., v N }). Since D 2 f is a bounded operator, c 3 := sup{ D 2 f (t, φ, v) : (t, φ, v) ∈ B} < +∞. Now we want to prove by induction the following relation, for all a ∈ R N + ∩ B(0, δ 1 ) such that a ≤ r c2 e -c3T , ∀m ∈ N, ∀t ∈ [0, T ]:

x m (•, S, a) t -x 0 (•, S, a) t ≤ r, x m+1 (•, S, a) t -x m (•, S, a) t ≤ 1 m! c 2 a (c 3 t) m .
(5.7)

For m 0, using Lemma 5.2 and (5.6) we obtain, for all t ∈ [0, T ], x 1 (•, S, a) tx 0 (•, S, a) t ≤ c 2 • a = 1 0! c 2 • a (c 3 t) 0 , and c 2 • a ≤ re -c3T ≤ r. Now we assume that (5.7) holds for the integer n ≤ p -1. Then, for all t ∈ [0, T ], we have

x p (t, S, a) -x 0 (t, S, a) = p-1 m=0 (x m+1 (t, S, a) -x m (t, S, a)) ≤ p-1 m=0 x m+1 (t, S, a) -x m (t, S, a) ≤ p-1 m=0 ( 1 m! c 2 a (c 3 t) m ) = c 2 • a p-1 m=0 (c3t) m m! ≤ c 2 • a e c3t ≤ c 2 • a e c3T ≤ r,
and since x p (•, S, a) 0 = x 0 (•, S, a) 0 = φ we deduce from the previous inequality that we have ∀t ∈ (0, T ], x p (•, S, a) tx 0 (•, S, a) t ≤ r.

And so (t, x p (•, S, a) t , u(t, S, a)) ∈ B, and using the assumption of induction and the mean value theorem with the boundedness of D 2 f we obtain, for all t ∈ [0, T ], f (t, x p (•, S, a) t , u(t, S, a))f (t, x p-1 (•, S, a) t , u(t, S, a)) (5.8)

≤ c 3 • x p (•, S, a) t -x p-1 (•, S, a) t ≤ c 3 (c3t) p-1 (p-1)! c 2 • a = c p 3 t p-1 (p-1)! c 2 • a
We have yet seen that x m (t, S, a)-x 0 (t, S, a) = x m (t, S, a)-x(t) ≤ c 2 • a e c3T for all t ∈ [0, T ]. And so setting c 4 := ke c2T and taking m → +∞ we obtain x(t, S, a)x(t) = x * (t, S, a)x(t) ≤ c 4 .

Lemma 5.5. For all S ∈ S, the two assertions hold.

(i) x(T, S, •) is differentiable at 0. (ii) For all i ∈ {1, ..., N }, ∂x(T, S, 0) ∂a i = X(T, t i )[f (t i , x ti , v i ) -f (t i , x ti , u(t i ))].
Proof. After Lemma 5.1 we know that z(T, S, •) is differentiable at 0. Then to prove (i) it suffices to prove that the mapping x(T, S, •)z(T, S, •) is differentiable at 0.

= ∂x(t,S,a) ∂t -x ′ (t) -∂z(t,S,a) ∂t = f (t, x(•, S, a) t , u(t, S, a)) -f (t, x t , u(t) -D 2 f (t, x t , u(t))z(•, S, a) t -f (t, x t , u(t, S, a)) + f (t, x t , u(t)) = f (t, x(•, S, a) t , u(t, S, a)) -f (t, x t , u(t, S, a)) -D 2 f (t, x t , u(t))z(•, S, a) t
which implies, using (5.9) and (5.10), that

ξ(t, S, a) = ∂ζ(t,S,a) ∂t -D 2 f (t, x t , u(t))(x(•, S, a) -x t -z(•, S, a)) = f (t, x(•, S, a) t , u(t, S, a)) -f (t, x t , u(t, S, a)) -D 2 f (t, x t , u(t))(x(•, S, a) -x t ) = 1 0 D 2 f (t, x t + θ[x(•, S, a) -x t ], u(t, S, a))dθ(x(•, S, a) -x t ) -D 2 f (t, x t , u(t))(x(., S, a) -x t )
and so we obtain (5.13) lemma in a straightforward way. To treat the last condition, note that Dψ j (0) = Dg j (x(T ))D a x(T, S, 0), and then the last conclusion of the previous lemma is: ∀a ∈ R N + , ni+ne j=0

λ j Dg j (x(T )).D a x(T, S, 0)a ≤ 0. If (e i ) 1≤i≤n denotes the canonical basis of R N , we obtain 0 ≥ ni+ne j=0 λ j Dg j (x(T ))D a x(T, S, 0)a = p+q j=0 a j λ j Dg j (x(T )) ∂x(T, S, 0) ∂a i and we conclude by using Lemma 5.5.

The following lemma ensures the existence of multipliers which do not depend of S ∈ S.

Lemma 5.8. There exists (λ j ) 0≤j≤ni+ne ∈ R 1+ni+ne which satisfies the following properties.

(i) ni+ne j=0

|λ j | = 1 (ii) ∀j = 0, ..., n i , λ j ≥ 0 (iii) ∀j = 1, ..., n i , λ j g j (x(T )) = 0 (iv) ∀t ∈ [0, T ], ∀u ∈ U , ni+ne j=0 λ j Dg j (x(T ))X(T, t)[f (t, x t , u)f (t, x t , u(t))] ≤ 0.

The proof of this lemma is completely similar to this one of Lemme 3 in [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF]. The idea of this proof is the following one: at each S ∈ S we associate the set K(S) as the set of the (λ j ) 0≤j≤ni+ne ∈ R 1+ni+ne which satisfy the conclusion (iiv) of Lemma 5.7. Denoting by S(0, 1) the unit spere of R 1+ni+ne for the norm (λ j ) 0≤j≤ni+ne := ni+ne i=0

|λ j |, we see that K(S) is nonempty (by Lemma 5.7), is closed into the compact S(0, 1). For all finite list (S k ) 1≤k≤ℓ of elements of S, we can build S * ∈ S such that K(S * ) ⊂ ∩ 1≤k≤ℓ K(S k ) that proves that ∩ 1≤k≤ℓ K(S k ) = ∅. Then the compactness of S(0, 1) and the closedness of the K(S) imply that ∩ S∈S K(S) = ∅. It suffices to take (λ j ) 0≤j≤ni +ne ∈ ∩ S∈S K(S) and to note that each (t, u) ∈ [0, T ] × U belongs to S to obtain the conclusion (iv) of the lemma.

The end of the proof of Theorem 4.1. The scalar multipliers λ 0 ,..., λ ni+ne are provided by Lemma 5.8. From lemma 5.8 we see that the conditions (NN), (Si) and (Sl) of Theorem 4.1 are fulfilled.We define the function p : [0, T ] → R n * by setting p(t) := ni+ne j=0 λ j Dg j (x(T ))X(T, t).

(5.14)

From (iv) of Lemma 5.8, we see that the condition (MP) is fulfilled. Since X(T, T ) = I (identity), from (5.14) we see that the condition (T) is fulfilled. Using Proposition 3.5, we have X(T, t) = I -T t X(T, α)η 1 (α, tα)dα, which implies p(t) = ni+ne j=0 λ j Dg j (x(T ))X(T, t) = ni+ne j=0 λ j Dg j (x(T )) -T t ni+ne j=0 λ j Dg j (x(T ))X(T, α)η(α, tα)dα = ni+ne j=0 λ j Dg j (x(T )) -T t p(α)η 1 (α, tα)dα and so we see that the function [t → p(t)+ T t p(α)η(α, t-α)dα] is constant on [0, T ]. Note that α > t + r implies tα < -r and then η 1 (α, tα) = 0 and consequently T t p(α)η 1 (α, tα)dα = min{t+r,T } t p(α)η 1 (α, tα)dα = min{t+r,T } t p(α)η(α, tα)dα that proves that the condition (AE) holds.

Proposition 3 . 1 .

 31 Under (3.1) there exists a mapping η : [0, T ] × [-r, 0] → M n (R) which satisfies the following properties.

  which satisfies the conclusions of Proposition 3.1 where [t k , t k+1 ] replaces [0, T ] and where L k replaces L. We define η : [0, T ] × [-r, 0] → M n (R) by setting η(t, θ) := η k (t, θ) when t ∈ [t k , t k+1 ), θ ∈ [-r, 0] when k ∈ {0, ..., p -1} and η(t, θ) := η p (t, θ) when t ∈ [t p , T ], θ ∈ [-r, 0]. And so, from Proposition 3.1 we deduce the following result. Proposition 3.3. Under (3.4) there exists a mapping η : [0, T ] × [-r, 0] → M n (R) which satisfies the following properties.

3. 3 .Proposition 3 . 5 .

 335 Adjoint equation. Let X be provided by Theorem 3.4 and η be provided by Proposition 3.1. We define Y : [0, T ] × [0, T ] → M n (R) by setting Y (s, t) := X(t, s). Then when s ≤ t, the following equation is satisfied: Y (s, t) = I -t s Y (α, t)η(α, s-α)dα.

Theorem 4 . 1 .

 41 Under the assumptions (1.1) and (1.2), if (x, u) is a solution of the Mayer problem (M) then there exist λ 0 ,..., λ ni+ne ∈ R and there exists p ∈ BV ([0, T ], R n * ) ∩ C 0 L ([0, T ], R n * ) which satisfy the following conditions. (NN) (λ 0 , ..., λ ni+ne ) = (0, ..., 0)

Remark 4 . 2 .

 42 The conclusion (AE) is equivalent to say that the function[t → p(t)+ min{t+r,T } t p(ξ)η(ξ, ξt)dξ] is constant on [0, T ]. Sincemin{T +r,T } T p(ξ)η(ξ, ξ -t)dξ = 0, using (TC), we obtain that (AE) is equivalent to ∀t ∈ [0, T ], p(t) + min{t+r,T } t p(ξ)η(ξ, ξt)dξ = p(T ) = ni+ne j=0 λ j Dg j (x(T )).

Lemma 5 . 1 .

 51 and u(t, S, a) := v i when t ∈ I i and the control u(t, S, a) := u(t) when t ∈ [0, T ] \ ∪ 1≤i≤N I i . Taking a small enough we have I i ⊂ [0, T ] and the I i are pairwise disjoint. We denote by x(•, S, a) the unique solution on [0, T ] of the following problem of Cauchy ∀t ∈ [0, T ] \ N u(•,S,a) , ∂x(t, S, a) ∂t = f (t, x(•, S, a) t , u(t, S, a)), x(•, S, a) 0 = φ. We fix S ∈ S and a ∈ R N + . We denote by z(•, S, a) the solution on [0, T ] of the following linear problem    ∀t ∈ [0, T ] \ N u(.,S,a) , ∂z(t,S,a) ∂t = D 2 f (t, x t , u(t))z(•, S, a) t + [f (t, x t , u(t, S, a))f (t, x t , u(t))] z(•, S, a) 0 = 0.

p 3 s p- 1 (p- 1 )! )ds = c 2 • a c p 3 ( 0 f

 1130 which implies x p+1 (t, S, a)x p (t, S, a) = t 0 f (s, x p (•, S, a) s , u(s, S, a))ds -t 0 f (s, x p-1 (•, S, a) s , u(s, S, a))ds ≤ t 0 f (s, x p (•, S, a) s , u(s, S, a))f (s, x p-1 (•, S, a) s , u(s, S, a)) ds≤ t 0 (c 2 • a c p-1 ds = c 2 • a c p 3 t p p!and since x p+1 (•, S, a) 0 = x p (•, S, a) 0 = φ we deduce from the previous inequality that we have finished the induction and so the formula (5.7) is proven. From (5.7) it is easy to see that([t → x m (•, S, a) t ]) m∈N is a Cauchy sequence into (C 0 ([0, T ], C 0 ([-r, 0], R n )), • ∞ ) and consequently we obtain that (x m (•, S, a)) m∈N is a Cauchy sequence into C 0 ([-r, T ], R n ). Since this last space is complete, there exists x * (•, S, a) ∈ C 0 ([-r, T ], R n ) such that lim m→+∞ sup t∈[-r,T ] x m (t, S, a)x * (t,S, a) = 0 which implies that lim m→+∞ sup t∈[0,T ] x m (•, S, a) t -x * (•, S, a) t = 0. Using Lemma 5.3 with F = N u(•,S,a) and Γ(t, φ) = f (t, φ, u(t, S, a)) we obtain lim m→+∞ sup t∈[0,T ] f (t, x m (•, S, a) t , u(t, S, a))f (t, x * (•, S, a) t , u(t, S, a)) = 0 which implies, ∀t ∈ [0, T ], lim m→+∞ t (s, x m (•, S, a) s , u(s, S, a))ds = t 0 f (s, x * (•, S, a) s , u(s, S, a)ds. Taking m → +∞ into the formula x m (t, S, a) = φ(0) + t 0 (f (s, x m-1 (•, S, a) s , u(s, S, a))ds we obtain x * (t, S, a) = φ(0) + t 0 f (s, x * (•, S, a) s , u(s, S, a))ds. Note that the set of the discontinuity points of the integrand of this last integral is included into N u(•,S,a) = N u ∪ {t i + b i : i ∈ {1, ..., N }} ∪ {t i + b i + a i : i ∈ {1, ..., N }}. And so x * (•, S, a) ∈ C 0 ([-r, T ], R n ) ∩ P C 1 ([0, T ], R n ). From the last integral equation we deduce ∀t ∈ [0, T ] \ N u(•,S,a) , ∂x * (t, S, a) ∂t = f (t, x * (•, S, a) t , u(t, S, a)). Since x m (•, S, a) 0 = φ for all m ∈ N, we have also x * (•, S, a) 0 = φ. Then using the uniqueness of the solution of a Cauchy problem we obtain that x * (•, S, a) = x(•, S, a).

1 0 D 2 fFrom ( 5 .

 125 ξ(t, S, a) = x(•, S, a) tx t ∞ • E(t, S, a) (5.11) where E(t, S, a) := (t, x t + θ[x(•, S, a)x t ], u(t, S, a))dθ -D 2 f (t, x t , u(t)) x(•,S,a)t-xt x(•,S,a)t-xt if x(•, S, a) t = x t and E(t, S, a) := 0 if x(•, S, a) t = x t . Since D 2 f is bounded, there exists c 4 > 0 such that, for all t ∈ [0, T ], for all a ∈ B(0, δ 2 ), E(t, S, a) ≤ c 4 . Note that E(t, S, a) = 0 when t ∈ [0, T ] \ ∪ 1≤i≤N I i , and consequently we have T 0 E(t, S, a) dt = ∪ 1≤i≤N Ii E(t, S, a) dt + [0,T ]\∪ 1≤i≤N Ii E(t, S, a) dt = N i=1 Ii E(t, S, a) dt = N i=1 ti+bi+ai ti+bi E(t, S, a) dt ≤ N i=1 a i c 4 = c 4 • a 10) we have ∂ζ(t,S,a) ∂t = D 2 f (t, x t , u(t))ζ(•, S, a) t + ξ(t, S, a), and from (5.9) we also have ζ(•, S, a) 0 = x(•, S, a) 0x 0z(•, S, a) = φφ -0, and so we can use Theorem 3.4 and assert that ζ(t, S, a) = X(t, 0)0 + t 0 X(t, y)( -y -r d 2 η(y, θ)0(y + θ))dy) + t 0 X(t, α)ξ(α, S, a)dα = 0 + 0 + t 0 X(t, α)ξ(α, S, a)dα, and so we have established the following formula ζ(T, S, a) = T 0 X(T, t)ξ(t, S, a)dt.

when a i = 0 and ̺ i (S, a) := 0 when a i = 0. Then the following formula holds. z(T, S, a) = z(T, S, 0) + N i=1 a i X(T, t i )∆(t i , S, a) + N i=1 a i ̺ i (S, a).

(5.1)

Now to prove the result, it sufffices to prove that the following assertion holds.

∀i ∈ {1, ..., N }, lim a→0 ̺ i (S, a) = 0.

(5.2)

In the formula of ̺ i we do the change of variable s = t i + b i + θa i with θ ∈ [0, 1], setting ̟ i (S, a, θ) := X(T, t i + b i + θa i )∆(t i + b i + θa i , S, a) -X(T, t i )∆(t i , S, a), we obtain the following formula.

we arbitrarily fix θ ∈ [0, 1). Note that, for all i ∈ {1, ..., N }, we have lim a→0 a i = 0 and lim a→0 b i = 0. Since X(T, •) is right-continuous ((vi) of Theorem 3.4) we obtain lim a→0 X(T,

And so we obtain the following property.

∀θ ∈ [0, 1), lim a→0 ̟ i (S, a, θ) = 0.

(5.4)

We fix δ ∈ (0, +∞) small enough to have

and then the closure of this subset is compact. Since

Since a constant is Lebesgue integrable on [0, 1], we can use the theorem of the dominated convergence of Lebesgue to assert that lim a→0 ̺ i (S, a) = 1 0 0dθ = 0. Then (5.2) is proven, and the conclusion of the lemma follows from (5.1). Lemma 5.2. Let S ∈ S. There exists δ 1 ∈ (0, +∞) and c 2 ∈ (0, +∞) such that, for all a ∈ R N + ∩ B(0, δ 1 ),

Proof. Note that the integrand in the formula is ∆(t, S, a) . We introduce e : [0, T ] × (R N + ∩ B(0, δ)) → R + by setting e(t, a) := t 0 ∆(t, S, a) dt.

We know that X is bounded on [0, T ] × [0, T ], and using Lemma 5.4, (5.13) and (5.11) we obtain (x(T, S, a)z(T, S, a) -(x(T, S, 0)z(T, S, 0)) = ζ(T, S, a)

which implies (using (5.12)) that the mapping x(T, S, •)z(T, S, •) is differentiable at 0 and that its differential at 0 is equal to zero. Then using lemma 5.1 we obtain D a X(T, S, 0)a = D a z(T, S,

The following multiplier rule comes from [START_REF] Michel | Une démonstration élémentaire du principe du maximum de Pontriaguine[END_REF]. Lemma 5.6. Let V be a neighborhood of 0 into R N . Let n i , q e ∈ N. Let ψ j : V → R be differentiable functions at 0, for j ∈ {0, ..., n i + n e }. We assume that 0 is a solution of the following maximization problem

Then there exists (λ 0 , ..., λ ni+ne ) ∈ R 1+ni+ne which satisfies the following conditions.

λ j Dψ j (0).a ≤ 0. Now we apply this multiplier rule to our problem that permits us to obtain the following lemma.

Lemma 5.7. Let S ∈ S. Then there exists Λ(S) = (λ j ) 0≤j≤ni+ne ∈ R 1+p+q which satisfies the following properties.

(i) ni+ne j=0

Proof. Since the process (x, u) is optimal for (M), it is also optimal among the processes (x(•, S, a), u(•, S, a)) when a belongs to a neighborhood of 0 into R N + . Recall that x(•, S, 0) = x and u(•, S, 0) = u. And then 0 is an optimal solution of the following maximisation static problem

Maximize g 0 (x(T, S, a)) when a ∈ B(0, δ 2 ) ∩ R n + ∀j = 1, ..., n i , g j (x(T, S, a)) ≥ 0 ∀j = n i + 1, ..., n i + n e , ; g j (x(T, S, a)) = 0.

We use the previous lemma by setting ψ j (a) := g j (x(T, S, a)). Since the set of the lists of multipliers is a cone the non nullity of (λ j ) 0≤j≤ni +ne permits us to choose it to satisfy (i). The conclusions (ii) and (iii) are given by the previous

BLOT KON É

Using (QC), if p(T ) = 0 since (NN), (Si) and (Sl) hold we obtain a contradiction, and so we have p(T ) = 0 under (QC). Since X(T, t) = I -T t R(ξ, t)dξ, and since R is bounded, if we choose ǫ ∈ (0, R -1 ∞ ], then, when t ∈ (Tǫ, T ], we obtain that X(T, t) is invertible. Using (TC), we have p(t) = p(T )X(T, t), ans since p(T ) = 0, we obtain p(t) = 0. And so (A1) is proven. To prove (A2), we proceed by contradiction. We assume that there exists τ ∈ [0, T ] such that p(t) = 0 when t ∈ [τ, min{τ + r, T }]. Note that τ < T since p(T ) = 0. Using (AE) and (TC) we have, p(τ ) + min{τ +r,T } τ p(ξ)η(ξ, τξ)dξ = p(T ) which implies 0 + 0 = p(T ) that is impossible. And so (A2) is proven and the proof of Theorem 4.1 is complete.


Emmanuelle Saillard
email: emmanuelle.saillard@cea.fr

Patrick Carribault
email: patrick.carribault@cea.fr

Denis Barthou
email: denis.barthou@labri.fr

Static/Dynamic Validation of MPI Collective Communications in Multi-threaded Context

Keywords: D.2.5 [Software Engineering]: Testing and Debugging aids Static, Verification, MPI+OpenMP, Control Flow

Scientific applications mainly rely on the MPI parallel programming model to reach high performance on supercomputers. The advent of manycore architectures (larger number of cores and lower amount of memory per core) leads to mix MPI with a threadbased model like OpenMP. But integrating two different programming models inside the same application can be tricky and generate complex bugs. Thus, the correctness of hybrid programs requires a special care regarding MPI calls location. For example, identical MPI collective operations cannot be performed by multiple non-synchronized threads. To tackle this issue, this paper proposes a static analysis and a reduced dynamic instrumentation to detect bugs related to misuse of MPI collective operations inside or outside threaded regions. This work extends PARCOACH [4] designed for MPI-only applications and keeps the compatibility with these algorithms. We validated our method on multiple hybrid benchmarks and applications with a low overhead.

Introduction

Hybrid programming with MPI and a shared-memory programming language such as OpenMP is a promising solution for writing parallel applications for supercomputers. The MPI-2 standard defines multiple levels of multi-threading integration, known as thread levels, to indicate how MPI communications should interact with threads. Even if some hybrid applications do not require a specific thread level, performing MPI communications inside parallel threaded regions may help reducing the penalty of Amdhal's law. Thus, three thread levels enable MPI communications inside OpenMP parallel regions. However, according to the standard, it is the user's responsibility to ensure that MPI communications (including collective calls) are correctly placed, according to the thread level used. More specifically, if the number of expected calls to a collective operation or their sequence is not the same for all processes, this can lead to errors or deadlocks. Finding such bugs and, moreover, the source of the errors may be challenging.

Even if hybrid applications are more and more common, most debugging tools are focused on one type of parallelism at a time. However errors in hybrid programs (whatever the thread-level support) can result from the combination of both forms of parallelism. To our knowledge, Marmot [START_REF] Hilbrich | Detection of violations to the MPI standard in hybrid OpenMP/MPI applications[END_REF] is the only tool that provides a support for detecting collective errors in MPI+OpenMP programs.

We propose an extension of PARCOACH [START_REF] Saillard | PARCOACH:combining static and dynamic validation of mpi collective communications[END_REF] to verify the flow of MPI collective operations in a multi-threaded context. The proposed method is compatible with all possible thread levels. It de-tects deadlocks or error situations due to MPI collectives, stops program execution as soon as this situation is unavoidable and reports to the user the control-flow divergence and the parallel constructs responsible for this situation. Our analysis is designed to be compatible with existing dynamic tools like MUST [START_REF] Hilbrich | Runtime MPI collective checking with tree-based overlay networks[END_REF] and is focused on detecting the MPI collective mismatches in a multi-threaded context. The correctness of collectives arguments or the multithreaded model used is not checked. The multi-threaded model should be an explicit fork/join model, with perfectly nested regions. OpenMP corresponds to this kind of model. Throughout the rest of the paper we consider MPI+OpenMP programs.

Compile-Time Verification

In our context, the problem statement can be expressed as follows: A hybrid program is correct if all MPI processes execute the same MPI collective operations in the same order in a deterministic way. This means there is a total order between MPI collective calls within each process and this order is the same for all MPI processes. To prove that a hybrid program is correct, the analysis is decomposed into three phases:

1. All MPI collectives are executed in a monothreaded context; 2. Any two collective executions are ordered sequentially; 3. All MPI processes execute the same sequence of collectives.

(1) and (2) ensure that collective operations are executed in an order that does not depend on the number of threads, nor on their execution schedule. [START_REF] Jourden | HERA: A hydrodynamic AMR Platform for Multi-Physics Simulations[END_REF] shows that the same sequence of collectives is executed for all MPI processes, and when the compile-time analysis is not able to prove this property due to some control flow statements, checks are inserted at these statements.

The compile-time phase of PARCOACH takes place in the middle of the compilation chain where the code is represented as a control-flow graph (CFG). In addition to the modification done in [START_REF] Saillard | PARCOACH:combining static and dynamic validation of mpi collective communications[END_REF] to highlight nodes containing a MPI collective operation, OpenMP directives are put into separate basic blocks and new nodes are added for implicit thread barriers. To verify the total order of MPI collective calls, we define a parallelism word pw[n] for a node n as the sequence of the parallel constructs (pragma parallel, single, . . . ) and the barriers traversed from the begining of a function to the node. Parallel regions are denoted by P i , with i the id of the node with the OpenMP construct, single threaded regions (such as single, master,. . . ) are denoted similarly S i , and barrier by B. A simplification is done when OpenMP regions end. Because the considered thread-based models such as OpenMP have perfect nested parallelism, the control flow has no impact on the parallelism word.

Checking that a collective is executed in a monothreaded region boils down to check the parallelism word of its node. This requires to use MPI with at least the MPI THREAD SERIALIZED level. If a collective is executed in a multithreaded region, this requires further the use of the level MPI THREAD MULTIPLE and the code is then correct if only one thread executes the collective. To be in a monothreaded region, the parallelism word has to end with an S (Bs are ignored as barriers do not influence the level of thread parallelism). Moreover, if the parallelism word has a sequence of two or more P with no S in-between, it implies the parallelism is nested: Even if the word ends with an S, one thread for each thread team can execute the collective. We assume then the collective is not executed in a monothreaded region. The language L defined by L = (S|P B * S) * describes the accepted words. The initial parallelism word at the function entrance is considered as an empty word. A node n is then in a monothreaded context if pw[n] ∈ L.

As in practice, the initial parallelism word of the function is an initial prefix unknown at compile-time, the programmer can select with an option given to the analysis the initial level to consider at compile-time. Whenever a collective is in a multi-threaded context, a warning related to the initial level with the name of the collective is returned to the programmer. Two sets are created: S and Sipw containing respectively collective nodes in multithreaded regions and the nodes that dominate these collective nodes before the execution/control flow changes. Different MPI collectives can be called in monothreaded regions, and still be executed simultaneously if the regions are executed in parallel. The second step of the static analysis detects concurrent collective calls. Two nodes n1 and n2 are said to be in concurrent monothreaded regions if they are in monothreaded regions and if pw[n1] = wS j u and pw[n2] = wS k v where w is a common prefix, j = k, u and v words in (P |S|B) * . Two nodes in monothreaded regions can be executed simultaneously if and only if they are in concurrent monothreaded regions. Two sets are created: S and Scc. When collective nodes with the same number of B are detected these nodes are put in the set S and the nodes that begin the monothreaded regions are put in the set Scc.

Once the sequence of MPI collective calls is verified in each process we must check that all sequences are the same for all processes. To this end, we resort to the Algorithm 1 proposed in [START_REF] Saillard | PARCOACH:combining static and dynamic validation of mpi collective communications[END_REF].

Static Instrumentation for Execution-Time Verification

The static analysis could lead to false positives relatively to the CFG that is possibly not correlated with the actual control flow. To deal with false positive results, a dynamic instrumentation is added in the nodes created by the static analysis (S, Sipw and Scc).

For each node in Sipw and Scc a runtime check is done to ensure the node is actually in a monothreaded region. For each node in Scc the number of threads concurrently executing a given node is counted dynamically. The check function CC depicted Algorithm

Experimental results

We tested our analyses on the NAS Parallel benchmarks multizone (NASPB-MZ v3.2) using class B, a mixed mode MPI/OpenMP benchmark suite v1.0 (EPCC suite) and HERA [START_REF] Jourden | HERA: A hydrodynamic AMR Platform for Multi-Physics Simulations[END_REF], a large multiphysics 2D/3D AMR hydrocode platform. At compile-time our analysis issues warnings for potential MPI collective errors within an MPI process and between MPI processes. The type of each potential error is specified (collective mismatch, concurent collective ..) with the names and lines in the source code of MPI collective calls involved. Figure 1 presents the compile-time overhead with and without code generation for each benchmark. The overhead acquired is acceptable as it does not exceed 6%.

Conclusion

Although large MPI+Threads applications appear, the lack of debugging tools for hybrid programs does not encourage the development of such applications and limits the use of thread levels. In this paper we propose a method to overcome this issue, extending PAR-COACH to detect collective patterns that can raise errors/deadlocks in a multi-threaded context. First our method statically identifies MPI collective operations that can deadlock or be performed by multiple non-synchronized threads. Then we validate these potential errors/deadlocks during execution by a code transformation. The cost of the runtime checks is limited by a selective instrumentation, avoiding unnecessary checks.

Figure 1 .

 1 Figure 1. Overhead of average compilation time with and without verification code generation

in[START_REF] Saillard | PARCOACH:combining static and dynamic validation of mpi collective communications[END_REF] is inserted before each MPI collective operation and before return statements. As multiple threads may call CC before return statements, this function is wrapped into a single pragma. In all cases if an error is about to occur, the program is stopped and an error message is returned with error type information.