P Cannarsa

H Frankowska

T Scarinci

Sensitivity relations for the Mayer problem with differential inclusions

Keywords: Mayer problem, differential inclusions, optimality conditions, sensitivity relations. MSC Subject classifications: 34A60, 49J53

In optimal control, sensitivity relations are usually understood as inclusions that identify the pair formed by the dual arc and the Hamiltonian as a suitable generalized gradient of the value function, evaluated along a given minimizing trajectory. In this paper, sensitivity relations are obtained for the Mayer problem associated with the differential inclusion ẋ ∈ F (x) and applied to express optimality conditions. The first application of our results concerns the maximum principle and consists in showing that a dual arc can be constructed for every element of the superdifferential of the final cost as a solution of an adjoint system. The second and last application we discuss in this paper concerns optimal design. We show that one can associate a family of optimal trajectories, starting at some point (t, x), with every nonzero reachable gradient of the value function at (t, x), in such a way that families corresponding to distinct reachable gradients have empty intersection.

Introduction

Given a complete separable metric space U and a vector field f : R n × U → R n , smooth with respect to x, for any point (t 0 , x 0 ) ∈ (-∞, T ] × R n and Lebesgue measurable map u : [t 0 , T ] → U let us denote by x(•; t 0 , x 0 , u) the solution of the Cauchy problem ẋ(t) = f (x(t), u(t)) a.e. t ∈ [t 0 , T ],

x(t 0 ) = x 0 , (1.1)
that we suppose to exist on the whole interval [t 0 , T ]. Then, given a smooth function φ : R n → R, we are interested in minimizing the final cost φ(x(T ; t 0 , x 0 , u)) over all controls u.

In the Dynamic Programming approach to such a problem, one seeks to characterize the value function V , that is,

V (t 0 , x 0 ) = inf u(•) φ(x(T ; t 0 , x 0 , u(•))) (t 0 , x 0 ) ∈ (-∞, T ] × R n , (1.2)
as the unique solution, in a suitable sense, of the Hamilton-Jacobi equation

-∂ t v(t, x) + H(x, -v x (t, x)) = 0 in (-∞, T ) × R n v(T, x) = φ(x) x ∈ R n , 1
where the Hamiltonian H is defined as

H(x, p) = sup u∈U p, f (x, u) (x, p) ∈ R n × R n .
Now, the classical method of characteristics ensures that, given t 0 ∈ R n and as long as V is smooth, along any solution of the system of ODEs ẋ(t) = ∇ p H(x(t), p(t)), x(T ) = z ṗ(t) = ∇ x H(x(t), p(t)), p(T ) = -∇φ(z) t ∈ [t 0 , T ], (1.3) the gradient of V satisfies (H(x(t), p(t)), -p(t)) = ∇V (t, x(t)), ∀ t ∈ [t 0 , T ].

(1.4)

It is well known that the characteristic system (1.3) is also a set of necessary optimality conditions for any optimal solution x(•) of the Mayer problem (1.2). Observe that ∇V (t, x) allows to "measure" sensitivity of the optimal cost with respect to (t, x). For this reason, (1.4) is called a sensitivity relation for problem (1.2). Obviously, the above calculation is just formal because, in general, V cannot be expected to be smooth. On the other hand, relation (1.4) is important for deriving sufficient optimality conditions, as we recall in Section 2. This fact motivates interest in generalized sensitivity relations for nonsmooth value functions.

To the best of our knowledge, the first "nonsmooth result" in the above direction was obtained by Clarke and Vinter in [START_REF] Clarke | The relationship between the maximum principle and dynamic programming[END_REF] for the Bolza problem, where, given an optimal trajectory x(•), an associated arc p(•) is constructed to satisfy the partial sensitivity relation p(t) ∈ ∂ x V (t, x(t)) a.e. t ∈ [t 0 , T ].

(1.5)

Here, ∂ x V denotes Clarke's generalized gradient of V in the second variable. Subsequently, for the same problem, Vinter [START_REF] Vinter | New results on the relationship between dynamic programming and the maximum principle[END_REF] proved the existence of an arc satisfying the full sensitivity relation (H(x(t), p(t)), -p(t)) ∈ ∂V (t, x(t)) for all t ∈ (t 0 , T ), (1.6) with ∂V equal to Clarke's generalized gradient in (t, x). Full sensitivity relations were recognized as necessary and sufficient conditions for optimality in [START_REF] Cannarsa | Some characterizations of optimal trajectories in control theory[END_REF], where the first two authors of this paper studied the Mayer problem for the parameterized control system (1.1), with f depending also on time. More precisely, replacing the Clarke generalized gradient with the Fréchet superdifferential ∂ + V , the full sensitivity relation (H(t, x(t), p(t)), -p(t)) ∈ ∂ + V (t, x(t)) a.e. t ∈ [t 0 , T ],

(1.7)

together with the maximum principle p(t), ẋ(t) = H(t, x(t), p(t)) a.e. t ∈ [t 0 , T ], (1.8) for some p(t) ∈ R n , was shown to actually characterize optimal trajectories. Earlier, in [START_REF] Subbotina | The maximum principle and the superdifferential of the value function[END_REF], a similar result had been proved under stronger regularity assumptions with p(•) equal to the dual arc.

Following the above papers, the analysis has been extended in several directions. For instance, in [START_REF] Cannarsa | Optimality conditions and synthesis for the minimum time problem[END_REF], sensitivity relations were adapted to the minimum time problem for the parameterized control system ẋ(t) = f (x(t), u(t)) t ≥ 0, (1.9) taking the form of the inclusion p(t) ∈ ∂ + T (x(t)) for all t ∈ [0, T (x 0 )), (1.10) where T (•) denotes the minimum time function for a target K, ∂ + T is the Fréchet superdifferential of T , and x(•) is an optimal trajectory starting from x 0 which attains K at time T (x 0 ). In [START_REF] Cannarsa | The dual arc inclusion with differential inclusions[END_REF], the above result has been extended to nonparameterized systems described by differential inclusions.

For optimal control problems with state constraints, sensitivity relations were derived in [START_REF] Bettiol | Improved sensitivity relations in state constrained optimal control[END_REF] and [START_REF] Frankowska | On relations of the adjoint state to the value function for optimal control problems with state constraints[END_REF] using a suitable relaxation of the limiting subdifferential of the value function.

Obtaining sensitivity relations in terms of the Fréchet and/or proximal superdifferential of the value function for the differential inclusion ẋ(s) ∈ F (x(s)) a.e. s ∈ [t 0 , T ], (1.11) with the initial condition x(t 0 ) = x 0 , (1.12) is far from straightforward, when F cannot be parameterized as

F (x) = {f (x, u) : u ∈ U } with f smooth in x.
The main goal of the present work is to prove both partial and full sensitivity relations for the Mayer problem inf φ(x(T )), (1.13) the infimum being taken over all absolutely continuous functions x : [t 0 , T ] → R n that satisfy (1.11)- (1.12). The main assumptions we impose on the data, expressed in terms of the Hamiltonian

H(x, p) = sup v∈F (x) v, p (x, p) ∈ R n × R n , (1.14)
require H(•, p) to be semiconvex, H(x, •) to be differentiable for p = 0, and ∇ p H(•, p) locally Lipschitz continuous. We refer the reader to [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF], where this set of hypotheses was used to obtain the semiconcavity of the value function, for a detailed discussion of their role in lack of a smooth parameterization of F . For the Mayer problem (1.11)-(1.13), we shall derive sensitivity relations like (1.5) and (1.6) for both the proximal and Fréchet superdifferentials of the value function. More precisely, let x : [t 0 , T ] → R n be an optimal trajectory of problem (1.13) and let p : [t 0 , T ] → R n be an absolutely continuous function (that we call dual arc) such that the pair (x, p) solves the Hamiltonian inclusion

-ṗ(t) ∈ ∂ - x H(x(t), p(t)) ẋ(t) ∈ ∂ - p H(x(t), p(t)) a.e. in [t 0 , T ] , (1.15)
and p(T ) ∈ ∂φ(x(T )), (1.16) where ∂ - x H and ∂ - p H denote the Fréchet subdifferentials of H with respect to x and p, respectively1 . Then we show that all such arcs p(•) satisfy the proximal partial sensitivity relation

-p(t) ∈ ∂ +,pr x V (t, x(t)) for all t ∈ [t 0 , T ],
(1.17) whenever p(T ) ∈ ∂ +,pr φ(x(T )), (1.18) where ∂ +,pr denotes the proximal superdifferential. Moreover, replacing ∂ +,pr φ(x(T )) by the Fréchet superdifferential ∂ + φ(x(T )) in (1.18), we derive the full sensitivity relation

(H(x(t), p(t)), -p(t)) ∈ ∂ + V (t, x(t)) for all t ∈ (t 0 , T ). (1.19)
Thanks to (1.19) we can recover, under suitable assumptions, the same set of necessary and sufficient conditions for optimality that appears in the context of smooth parameterized systems. From a technical viewpoint, we note that the proof of (1.17) and (1.19) is entirely different from the one for parameterized control systems. Indeed, in the latter case, the conclusion is obtained by appealing to the variational equation of (1.1). In the present context, such a strategy is impossible to follow because F admits no smooth parameterization, in general. As in [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF], the role of the variational equation is here played by the maximum principle.

After obtaining sensitivity relations, we discuss two applications of (1.17) to the Mayer problem. Our first application concerns optimality conditions. Under our assumptions on H, the maximum principle in its available forms associates, with any optimal trajectory x : [t 0 , T ] → R n of problem (1.13), a dual arc p : [t 0 , T ] → R n such that (x, p) satisfies (1.15) and the transversality condition

-p(T ) ∈ ∂φ(x(T )), (1.20)
see, for instance, [START_REF] Frank | Optimization and nonsmooth analysis[END_REF]. Here, for F locally strongly convex (see Section 2.6 for the definition of locally strongly convex multifunction), we construct multiple dual arcs p(•) satisfying the maximum principle H(x(t), p(t)) = p(t), ẋ(t) a.e. in [t 0 , T ],

(1.21) by solving, for any q ∈ ∂ +,pr φ(x(T )), the adjoint system

-ṗ(s) ∈ ∂ - x H(x(s), p(s)) a.e. in [t 0 , T ] , -p(T ) = q.
Moreover, these dual arcs satisfy the full sensitivity relation (1.19). Our second application aims to clarify the connection between the set of all reachable gradients of V at some point (t, x), ∂ * V (t, x), and the optimal trajectories at (t, x). When the control system is parameterized as in (1.1), such a connection is fairly well understood: one can show that any nonzero reachable gradient of V at (t, x) can be associated with an optimal trajectory starting from (t, x), and the map from ∂ * V (t, x) {0} into the family of optimal trajectories is one-to-one (see [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]Theorem 7.3.10]). In this paper, we use a suitable version of (1.17) to prove an analogue of the above result (see Theorem 5.3 for more details) which takes into account the lack of uniqueness for the initial value problem (1.15)- (1.18). This paper is organized as follows. In Section 2, we set our notation, introduce the main assumptions, and recall preliminary results from nonsmooth analysis and control theory. In Section 3, sensitivity relations are derived in terms of the proximal and Fréchet superdifferentials. Finally, an application to the maximum principle is obtained in Section 4, and a result connecting reachable gradients of V with optimal trajectories in Section 5.

Preliminaries

Notation

Let us start by listing various basic notations and quickly reviewing some general facts for future use. Standard references are [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF][START_REF] Frank | Optimization and nonsmooth analysis[END_REF].

We denote by R + the set of strictly positive real numbers, by | • | the Euclidean norm in R n , and by •, • the inner product. B(x, ǫ) is the closed ball of radius ǫ > 0 and center x. S n-1 is the unit sphere in R n . ∂E and int(E) are the boundary and the interior of a subset E of R n , respectively. Given a continuous function x : [t 0 , T ] → R n , the compact tubular neighborhood of x([t 0 , T ]) is defined by, for r ≥ 0,

D r (x([t 0 , T ])) := {x ∈ R n : |x -x(t)| ≤ r for some t ∈ [t 0 , T ]}.

For any continuous function

f : [t 0 , t 1 ] → R n , let f ∞ = max t∈[t 0 ,t 1 ] |f (t)|. When f is Lebesgue integrable, let f L 1 ([t 0 ,t 1 ]) = t 1 t 0 |f (t)| dt. W 1,1 ([t 0 , T ]; R n ) is
the set of all absolutely continuous functions x : [t 0 , T ] → R n , which we usually refer to as arcs. Consider now a real-valued function f : Ω ⊂ R n → R, where Ω is an open set, and suppose that f is locally Lipschitz. We denote by ∇f (•) its gradient, which exists a.e. in Ω. A vector ζ is a reachable gradient of f at x ∈ Ω if there exists a sequence {x i } ⊂ Ω such that f is differentiable at x i for all i ∈ N and x = lim

i→∞ x i , ζ = lim i→∞ ∇f (x i ).
We denote by ∂ * f (x) the set of all such vectors. Furthermore, the (Clarke's) generalized gradient of f at x ∈ Ω, denoted by ∂f (x), is the set of all the vectors ζ such that

ζ, v ≤ lim sup y → x, h → 0 + f (y + hv) -f (y) h , ∀v ∈ R n . (2.1)
It is known that co(∂ * f (x)) = ∂f (x), where co(A) denotes the convex hull of a subset A of R n . Let f : Ω ⊂ R n → R be any real-valued function defined on a open set Ω ⊂ R n . For any x ∈ Ω, the sets

∂ -f (x) = p ∈ R n : lim inf y→x f (y) -f (x) -p, y -x | y -x | ≥ 0 , ∂ + f (x) = p ∈ R n : lim sup y→x f (y) -f (x) -p, y -x | y -x | ≤ 0
are called the (Fréchet) subdifferential and superdifferential of f at x, respectively. A vector p ∈ R n is a proximal supergradient of f at x ∈ Ω if there exist two constants c, ρ ≥ 0 such that

f (y) -f (x) -p, y -x ≤ c|y -x| 2 , ∀y ∈ B(x, ρ).
The set of all proximal supergradients of f at x is called the proximal superdifferential of f at x, and is denoted by ∂ +,pr f (x). Note that ∂ +,pr f (x) is a subset of the Fréchet superdifferential of f at x. For a mapping f : R n × R m → R, associating to each x ∈ R n and y ∈ R m a real number, ∇ x f , ∇ y f are its partial derivatives (when they do exist). The partial generalized gradient or partial Fréchet/proximal sub/superdifferential will be denoted in a similar way.

Let Ω be an open subset of R n . C 1 (Ω) and C 1,1 (Ω) are the spaces of all the functions with continuous and Lipschitz continuous first order derivatives on Ω, respectively. Let K ⊂ R n be a convex set. For v ∈ K, recall that the normal cone to K at v (in the sense of convex analysis) is the set

N K (v) = {p ∈ R n : p, v -v ≤ 0, ∀v ∈ K}.
A well-known separation theorem implies that the normal cone at any v ∈ ∂K contains a half line. Moreover, if K is not a singleton and has a C 1 boundary when n > 1, then all normal cones at the boundary points of K are half lines. Finally, recall that a set-valued map F : X ⇒ Y is strongly injective if F (x) ∩ F (y) = ∅ for any two distinct points x, y ∈ X.

Locally semiconcave functions

Here, we recall the notion of semiconcave function in R n and list some results useful in this paper. Further details may be found, for instance, in [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF].

We write [x, y] to denote the segment with endpoints x, y for any x, y ∈ R n .

Definition 2.1. Let A ⊂ R n be an open set. We say that a function u : A → R is (linearly) semiconcave if it is continuous in A and there exists a constant c such that

u(x + h) + u(x -h) -2u(x) ≤ c|h| 2 , for all x, h ∈ R n such that [x -h, x + h] ⊂ A.
The constant c above is called a semiconcavity constant for u in A. We denote by SC(A) the set of functions which are semiconcave in A. We say that a function u is semiconvex on A if and only if -u is semiconcave on A.

Finally, recall that u is locally semiconcave in A if for each x ∈ A there exists an open neighborhood of x where u is semiconcave.

In the literature, semiconcave functions are sometimes defined in a more general way. However, in the sequel we will mainly use the previous definition and properties recalled in the following proposition.

Proposition 2.2. Let A ⊂ R n be an open set, u : A → R be a semiconcave function with a constant of semiconcavity c, and x ∈ A. Then,

1. a vector p ∈ R n belongs to ∂ + u(x) if and only if u(y) -u(x) -p, y -x ≤ c|y -x| 2 (2.2)
for any point y ∈ A such that [y, x] ⊂ A. Consequently, ∂ + u(x) = ∂ +,pr u(x).

∂u(

x) = ∂ + u(x) = co(∂ * u(x)). 3. If ∂ + u(x) is a singleton, then u is differentiable at x.
If u is semiconvex, then (2.2) holds reversing the inequality and the sign of the quadratic term and the other two statements are true with the Fréchet/proximal subdifferential instead of the Frećhet/proximal superdifferential. In proving our main results we shall require the semiconvexity of the map x → H(x, p). Let us recall its consequence which will be used later on.

Lemma 2.3 ([8, Corollary 1]

). Let H be as in (1.14). If H is locally Lipschitz and the map x → H(x, p) is locally semiconvex, uniformly for p in all bounded subsets of R n , then

∂H(x, p) ⊂ ∂ - x H(x, p) × ∂ - p H(x, p), ∀(x, p) ∈ R n × R n .

Differential inclusions and standing assumptions

We recall that the Hausdorff distance between two compact sets

A i ⊂ R n , i = 1, 2, is dist H (A 1 , A 2 ) = max{dist + H (A 1 , A 2 ), dist + H (A 2 , A 1 )}, where dist + H (A 1 , A 2 ) = inf{ǫ : A 1 ⊂ A 2 + B(0, ǫ)
} is the semidistance. We say that a multifunction F : R n ⇒ R n with nonempty and compact values is locally Lipschitz if for each x ∈ R n there exists a neighborhood K of x and a constant c > 0 depending on K so that dist H (F (z), F (y)) ≤ c | zy | for all z, y ∈ K. Throughout this paper, we assume that the multifunction F satisfies a collection of classical conditions of the theory of differential inclusions, the so-called Standing Hypotheses:

(SH)    (i) F (x) is nonempty, convex, compact for each x ∈ R n , (ii) F is locally Lipschitz with respect to the Hausdorff metric, (iii) ∃γ > 0 so that max{|v| : v ∈ F (x)} ≤ γ(1 + |x|) ∀x ∈ R n .
Assumptions (SH)(i)-(ii) guarantee the existence of local solutions of (1.11)-(1.12) and (SH)(iii) guarantees that solutions are defined on [t 0 , T ]. Basic notions concerning differential inclusions can be found, for instance, in the monograph [START_REF] Aubin | Gründlehren der Mathematischen Wissenschaften[END_REF].

For the sake of brevity, we usually refer to the Mayer problem (1.11)-(1.13) as P(t 0 , x 0 ). Assuming (SH) and lower semicontinuity of φ implies that P(t 0 , x 0 ) has at least one optimal solution, that is, a solution x(•) ∈ W 1,1 ([t 0 , T ]; R n ) of (1.11) and (1.12) such that (1.11) satisfying (1.12). Actually, the Standing Hypotheses were first introduced assuming only the upper semicontinuity of F instead of (SH)(ii). Although upper semicontinuity suffices to deduce the existence of optimal trajectories, in this paper we prefer to formulate (ii) as above because we will often take advantage of Lipschitz continuity.

φ(x(T )) ≤ φ(x(T )), for any trajectory x(•) ∈ W 1,1 ([t 0 , T ]; R n ) of
Under assumption (SH) one can show that it is possible to associate with each optimal trajectory x(•) for P(t 0 , x 0 ) an arc p(•) such that the pair (x(•), p(•)) satisfies an Hamiltonian inclusion.

Theorem 2.4 ([9, Theorem 3.2.6]). Assume (SH) and that φ : R n → R is locally Lipschitz. If x(•) is an optimal solution for P(t 0 , x 0 ), then there exists an arc p : [t 0 , T ] → R n which, together with x(•), solves the differential inclusion

(-ṗ(s), ẋ(s)) ∈ ∂H(x(s), p(s)), a.e. s ∈ [t 0 , T ] , (2.3)
p(T ) ∈ ∂φ(x(T )).

(2.4)

If (q, v) belongs to ∂H(x, p), then v ∈ F (x) and p, v = H(x, p). Thus, system (2.3) encodes the equality

H(x(t), p(t)) = p(t), ẋ(t) for a.e. t ∈ [t 0 , T ]. (2.5)
This equality shows that the scalar product v, p(t) is maximized over F (x(t)) by v = ẋ(t). For this reason, the previous result is known as the maximum principle (in Hamiltonian form).

Recall now that the value function V : (-∞, T ] × R n → R associated with the Mayer problem is defined by: for all (t 0 , x 0 [START_REF] Frankowska | R-convexity of the integral of set-valued functions[END_REF] and (1.12) .

) ∈ (-∞, T ] × R n , V (t 0 , x 0 ) = inf φ(x(T )) : x ∈ W 1,1 ([t 0 , T ]; R n ) satisfies (1.
(2.6)

Under assumptions (SH), V is locally Lipschitz and solves in the viscosity sense the Hamilton-Jacobi equation

-∂ t u(t, x) + H(x, -u x (t, x)) = 0 in (-∞, T ) × R n , u(T, x) = φ(x), x ∈ R n , (2.7)
where H is the Hamiltonian associated to F . Indeed, if the multifunction F satisfies assumption (SH), then it always admits a parameterization as a locally Lipschitz function (see, e.g., [2, Theorem 7.9.2]) and the result is well-known for the Lipschitz-parametric case (see, e.g., [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]).

Proposition 2.5. Assume (SH) and that φ : R n → R is locally Lipschitz. Then the value function of the Mayer problem is the unique viscosity solution of the problem (2.7), where the Hamiltonian H is given by (1.14).

We conclude this part recalling that V satisfies the dynamic programming principle. Hence, if y(•) is any trajectory of the system (1.11)-(1.12), then the function s → V (s, y(s)) is nondecreasing, and it is constant if and only if y(•) is optimal.

Sufficient conditions for optimality

In the control literature, it is well known that the full sensitivity relation involving the Fréchet superdifferential of V , coupled with the maximum principle, is a sufficient condition for optimality. For reader's convenience, we adapt this result to our context omitting the proof which is similar to the one of [START_REF] Cannarsa | Some characterizations of optimal trajectories in control theory[END_REF]Theorem 4.1]. Recall that (see, e.g., [START_REF] Aubin | Systems & Control: Foundations & Applications[END_REF])

∂ + V (t, y) = (p ′ , p ′′ ) ∈ R × R n : ∀(θ ′ , θ ′′ ) ∈ R × R n , D ↓ V (t, y)(θ ′ , θ ′′ ) ≤ p ′ θ ′ + p ′′ , θ ′′ , (2.8)
where the upper Dini derivative of V at (t, y) in the direction (θ ′ , θ ′′ ) is given by

D ↓ V (t, y)(θ ′ , θ ′′ ) := lim sup τ →0 + V (t + τ θ ′ , y + τ θ ′′ ) -V (t, y) τ .
(2.9)

Theorem 2.6. Assume (SH), suppose φ is locally Lipschitz, and let x : [t 0 , T ] → R n be a solution of system (1.11)-(1.12). If, for almost every t ∈ [t 0 , T ], there exists p(t) ∈ R n such that

p(t), ẋ(t) = H(x(t), p(t)), (H(x(t), p(t)), -p(t)) ∈ ∂ + V (t, x(t)),
(2.10) then x is optimal for problem P(t 0 , x 0 ).

Main assumptions

We impose further conditions on the Hamiltonian associated with F :

(H1)    For each nonempty, convex and compact subset K ⊆ R n , (i) ∃ c ≥ 0 so that , ∀p ∈ R n , x → H(x, p) is semiconvex on K with constant c|p|, (ii) ∇ p H(x, p) exists and is Lipschitz continuous in x on K, uniformly for p ∈ R n {0}.
Remark 2.7. Note that H(x, •) is positively homogeneous of degree one, and ∇ p H(x, •) is positively homogeneous of degree zero. Then, assuming (H1) is equivalent to requiring that

(H1 * )   
for each non empty, convex and compact subset

K ⊆ R n , (i) ∃ c ≥ 0 so that , ∀p ∈ S n-1 , x → H(x, p) is semiconvex on K with constant c, (ii) ∇ p H(x, p) exists and is Lipschitz continuous in x on K, uniformly for p ∈ S n-1 .
Some examples of multifunctions satisfying (SH) and (H1) are given in [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF].

Let us start by analyzing the meaning of the above assumptions beginning with (H1)(i) which is equivalent to the mid-point property of the multifunction F on K, that is,

dist + H (2F (x), F (x + z) + F (x -z)) ≤ c | z | 2 ,
for all x, z so that x, x ± z ∈ K. Another consequence of (H1)(i) is the fact that the generalized gradient of H splits into two components, as described in Lemma 2.3. This implies that every solution of (2.3) is also a solution of the Hamiltonian inclusion (2.11) below.

Theorem 2.8 ([8, Corollary 2]). Assume that (SH) and (H1)(i) hold and suppose φ : R n → R is locally Lipschitz. If x(•) is an optimal solution for P(t 0 , x 0 ), then there exists an arc p : [t 0 , T ] → R n which, together with x(•), satisfies the system

-ṗ(s) ∈ ∂ - x H(x(s), p(s)), ẋ(s) ∈ ∂ - p H(x(s), p(s)), a.e. s ∈ [t 0 , T ] (2.11)
and the transversality condition p(T ) ∈ ∂φ(x(T )).

(2.12)

Given an optimal trajectory x(•), any arc p(•) satisfying (2.11) and the tranversality condition (2.12) is called a dual arc associated with x(•). Recall that any solution to (2.3) solves also the system (2.11).

Remark 2.9. Under the additional hypothesis that ∂ + φ(x(T )) = ∅, for every q ∈ ∂ + φ(x(T )) there exists an arc p such that the pair (x, p) solves (2.11) and the condition -p(T ) = q. Indeed, since q ∈ ∂ + φ(x(T )), there exists a function g ∈ C 1 (R n ; R) such that g ≥ φ, g(x(T )) = φ(x(T )), and ∇g(x(T )) = q (see, for instance, [7, Proposition 3.1.7]). Note that x is still optimal for the Mayer problem (1.11)-(1.13) with φ replaced by g. Thus, by Theorem 2.8 there exists an arc p such that the pair (x, p) solves (2.11) and satisfies the terminal condition -p(T ) = q.

Remark 2.10. Let x : [t 0 , T ] → R n be continuous and p be a solution ofṗ(s) ∈ ∂ -

x H(x(s), p(s)) a.e. in [t 0 , T ]. Observe that, if p vanishes at some time t ∈ [t 0 , T ], then it must vanish at every time. Indeed, let K ⊂ R n be a compact set containing x([t 0 , T ]). Denoting by c K a Lipschitz constant of F on K, we have that c K |p| is a Lipschitz constant for H(•, p) on the same set. Indeed, let x, y ∈ K and v x be such that H(x, p) = v x , p . By (SH), there exists v y ∈ F (y) such that

H(x, p) -H(y, p) ≤ v x -v y , p ≤ c K |p||x -y|.
(2.13)

Recalling (2.1), it follows that |ζ| ≤ c K |p|, ∀ζ ∈ ∂ x H(x, p), ∀x ∈ K, ∀p ∈ R n . (2.14)
Hence, in view of the differential inclusion verified by p,

| ṗ(s)| ≤ c K |p(s)|, for a.e. s ∈ [t 0 , T ]. (2.15)
By Gronwall's Lemma, we obtain that either p(s) = 0 for every s ∈ [t 0 , T ], or p(s) = 0 for every s ∈ [t 0 , T ]. Consequently, under assumptions (H1) a dual arc associated with an optimal trajectory vanishes either for all times or never.

Concerning the assumption (H1)(ii), the existence of the gradient of H with respect to p is equivalent to the fact that the argmax set of v, p over v ∈ F (x) is the singleton {∇ p H(x, p)}, for each p = 0. Thus, the following relation holds:

H(x, p) = ∇ p H(x, p), p , ∀p = 0. ( 2

R-convex sets

Let A be a compact and convex subset of R n and R > 0.

Definition 2.13. The set A is R-convex if, for each z, y ∈ ∂A and any vectors n

∈ N A (z), m ∈ N A (y) with | n |=| m |= 1, the following inequality holds true | z -y |≤ R | n -m | . (2.19)
The concept of R-convex set is not new. It is a special case of hyperconvex sets (with respect to the ball of radius R and center zero) introduced by Mayer in [START_REF] Mayer | Eine Überkonvexität[END_REF]. A study of hyperconvexity appears also in [START_REF] Vincensini | Sur les figures superconvexes planes[END_REF][START_REF] Pasqualini | Superconvexité[END_REF]. The notion of R-convexity was considered, among others, by Levitin, Poljak, Frankowska, Olech, Pliś, Lojasiewicz, and Vian (they called these sets R-regular, R-convex, as well strongly convex). We first recall some interesting characterizations of R-convex sets.

Proposition 2.14 ([11, Proposition 3.1]). Let A be a compact and convex subset of R n . Then the following conditions are equivalent

1. A is R-convex, 2.
A is the intersection of a family of closed balls of radius R, 3. for any two points x, y ∈ ∂A such that |x -y| ≤ 2R, each arc of a circle of radius R which joins x and y and whose length is not greater that πR is contained in A,

4. for each z ∈ ∂A and any n ∈ N A (z), | n |= 1, the ball of center z -Rn and radius R contains A, that is | z -Rn -x |≤ R for each x ∈ A,
5. for each z ∈ ∂A and any vector n ∈ N A (z) with |n| = 1, we have the inequality

|z -x| ≤ √ 2R z -x, n 1 2 , ∀x ∈ A. (2.20)
R-convex sets are obviously convex. Moreover, the boundary of an R-convex set A satisfies a generalized lower bound for the curvature, even though ∂A may be a nonsmooth set. Indeed, for every point x ∈ ∂A there exists a closed ball B x of radius R such that x ∈ ∂B x and A ⊂ B x . This fact suggests that, in some sense, the curvature of ∂A is bounded below by 1/R. Definition 2.15. A multifunction F : R n ⇒ R n is locally strongly convex if for each compact set K ⊂ R n there exists R > 0 such that F (x) is R-convex for every x ∈ K.

We can reformulate the above property of F in an equivalent Hamiltonian form. Here, we denote by F p (x) the argmax set of v, p over v ∈ F (x). The existence of ∇ p H(x, p) is equivalent to the fact that the set F p (x) is the singleton {∇ p H(x, p)}, whenever p = 0.

(H2)

For every compact K ⊂ R n , there exists a constant c ′ = c ′ (K) > 0 such that for all x ∈ K, p ∈ R n , we have:

v p ∈ F p (x) ⇒ v -v p , p ≤ -c ′ |p||v -v p | 2 , ∀v ∈ F (x).
In the next lemma we show that the local strong convexity of F is equivalent to assumption (H2) for the associated Hamiltonian, giving also a result connecting (H2) with the regularity of H.

Lemma 2.16. Suppose that F : R n ⇒ R n is a multifunction satisfying (SH). Let K be any convex and compact subset of R n . Then

Proof. For all x ∈ K and v ∈ ∂F (x), we have v ∈ F yv (x) for all y v ∈ N F (x) (v). Therefore, (H2) holds with constant c ′ on K if and only if for any

y v ∈ N F (x) (v) with | y v |= 1 we have v -v, y v ≥ c ′ |v -v| 2 , ∀v ∈ F (x),
or equivalently,

| v -v |≤ 2 1 2c ′ v -v, y v 1 2 , ∀v ∈ F (x), for all y v ∈ N F (x) (v) with | y v |= 1.
By Proposition 2.14, this is equivalent to the (2c ′ ) -1 -convexity of F (x) for each x ∈ K. For the proof of the second statement we refer to [8, Proposition 4].

The second statement of the above lemma is not an equivalence, in general, as is shown in the example below. Moreover, assumption (H1) does not follow from (H2).

Example 2.17. Let us denote by M ⊂ R 2 the intersection of the epigraph of the function f : R → R, f (x) = x 4 , and the closed ball B(0, R), R > 0. Let us consider the multifunction F : R 2 ⇒ R 2 that associates set M with any x ∈ R 2 . Observe that M fails to be strongly convex, since the curvature at x = 0 is equal to zero. Moreover, since M is a closed convex set and its boundary contains no line, the argmax of v, p over v ∈ M is a singleton for each p = 0. So, the Hamiltonian H(p) = sup v∈M v, p is differentiable for each p = 0. Note that the gradient ∇ p H is constant with respect to the x variable. Consequently, the Hamiltonian satisfies (H1) but F does not satisfy (H2).

Sensitivity relations

In this section, we discuss partial and full sensitivity relations for both the Fréchet and proximal superdifferential of the value function.

Theorem 3.1. Assume (SH), (H1) and let φ : R n → R be locally Lipschitz. Let x : [t 0 , T ] → R n be an optimal solution for P(t 0 , x 0 ) and let p : [t 0 , T ] → R n be an arc such that (x, p)

solves the system -ṗ(t) ∈ ∂ - x H(x(t), p(t)) ẋ(t) ∈ ∂ - p H(x(t), p(t)) a.e. in [t 0 , T ] , (3.1)
and satisfies the transversality condition

-p(T ) ∈ ∂ +,pr φ(x(T )). (3.2)
Then, there exist constants c, R > 0 such that, for all t ∈ [t 0 , T ] and all h ∈ B(0, R),

V (t, x(t) + h) -V (t, x(t)) ≤ -p(t), h + c | h | 2 . (3.3)
Consequently, p(•) satisfies the proximal partial sensitivity relation

-p(t) ∈ ∂ +,pr x V (t, x(t)) for all t ∈ [t 0 , T ]. (3.4)
To prove the above theorem, we need the following lemma.

Lemma 3.2. Assume p(T ) = 0 and fix t ∈ [t 0 , T ).

For h ∈ R n , let x h : [t, T ] → R n be the solution of the problem ẋ(s) = ∇ p H(x(s), p(s)), s ∈ [t, T ] , x(t) = x(t) + h. (3.5)
Let us consider a compact tubular neighborhood of x([t 0 , T ]), D r (x([t 0 , T ])), for some r > 0. Then, there exist constants k and c 1 , depending only on r, such that for all h ∈ B 0,

re -k(T -t 0 ) it holds that |x h (s) -x(s)| ≤ e k(T -t 0 ) | h |, for all s ∈ [t, T ], (3.6)
and

p(t), h + -p(T ), x h (T ) -x(T ) ≤ c 1 | h | 2 . ( 3
|x(s) -x h (s)| ≤ e k(s-t) |h|. (3.9)
Since s < T , for all h ∈ B 0, re -k(T -t 0 ) it holds that

|x(s) -x h (s)| < r. (3.10)
This contradicts the fact that |x h (s)x(s)| = r. Thus, x h ([t, T ]) ⊂ D r (x([t 0 , T ])) for all h ∈ B 0, re -k(T -t 0 ) , and using again the Gronwall's lemma it is easy to deduce that (3.6) holds true for all h ∈ B 0, re -k(T -t 0 ) .

In order to prove (3.7), note that

p(t), h + -p(T ), x h (T ) -x(T ) = T t d ds -p(s), x h (s) -x(s) ds = T t -ṗ(s), x h (s) -x(s) ds + T t -p(s), ẋh (s) -ẋ(s) ds := (I) + (II). Let c ′ > 0 be such that c ′ |p| is the semiconvexity constant of H(•, p) on D r (x([t 0 , T ])). Since -ṗ(s) ∈ ∂ - x H(x(s), p(s)) a.e. in [t 0 , T ], we obtain that (I) ≤ T t c ′ | p(s) | • | x h (s) -x(s) | 2 +H(x h (s), p(s)) -H(x(s), p(s)) ds.
Then, from (3.6), (i) either p(t) = 0 for all t ∈ [t 0 , T ],

(I) ≤ T t c ′ | p(s) | • | h | 2 e 2k(T -t 0 ) + H(x h (s), p(s)) -H(x(s), p(s)) ds ≤ (T -t 0 )c ′ p ∞ e 2k(
(ii) or p(t) = 0 for all t ∈ [t 0 , T ].

We shall analyze each of the above cases separately. Suppose, first, that p(t) = 0 for all t ∈ [t 0 , T ] and fix t ∈ [t 0 , T ). Then x(•) is the unique solution of the Cauchy problem

ẋ(s) = ∇ p H(x(s), p(s)) for all s ∈ [t, T ] , x(t) = x(t). (3.11)
First note that, owing to (3.2), there exist constants c, r > 0 so that, for all z ∈ B(0, r), φ(x(T ) + z)φ(x(T )) ≤ -p(T ), z + c|z| 2 .

(3.12)

Let k > 0 be a Lipschitz constant for ∇ p H(•, p) on D r (x([t 0 , T ])), where D r (x([t 0 , T ])) is a compact tubular neighborhood of x([t 0 , T ]) as in Lemma 3.2. For each h ∈ B 0, re -k(T -t 0 ) , let x h (•) be the solution of problem (3.5). By the optimality of x(•), the very definition of the value function, and the dynamic programming principle, we have that, for all h ∈ B 0, re -k(T -t 0 ) ,

V (t, x(t) + h) -V (t, x(t)) + p(t), h ≤ φ(x h (T )) -φ(x(T )) + p(t), h . (3.13)
Since |x h (T )x(T )| ≤ r, from (3.12) and (3.13) we conclude that for each h ∈ B 0, re -k(T -t 0 ) ,

V (t,x(t) + h) -V (t, x(t)) + p(t), h ≤ p(t), h + -p(T ), x h (T ) -x(T ) + c | x h (T ) -x(T ) | 2 . (3.14)
Therefore, in view of (3.14) and Lemma 3.2, we have that for all h ∈ B 0, re -k(T -t 0 ) ,

V (t, x(t) + h) -V (t, x(t)) + p(t), h ≤ c 2 | h | 2 , (3.15)
where c 2 := c 1 + ce 2k(T -t 0 ) . The proof of (3.3) has a solution, x h (•), that satisfies the inequality

x h -x ∞ ≤ e k 1 (T -t 0 ) | h | . (3.17)
By the optimality of x(•), the very definition of the value function, and the dynamic programming principle it follows that

V (t, x(t) + h) -V (t, x(t)) ≤ φ(x h (T )) -φ(x(T )). (3.18)
Moreover, owing to (3.2) an recalling that p(•) is equal to zero at each point, there exist constants c, r > 0 so that, for all z ∈ B(0, r),

φ(x(T ) + z) -φ(x(T )) ≤ c|z| 2 . (3.19) Let r 1 := min{1, re -k 1 (T -t 0 ) }.
In view of (3.17)-(3.19), we obtain that, for all t ∈ [t 0 , T ] and h ∈ B(0, r 1 ),

V (t, x(t) + h) -V (t, x(t)) ≤ ce 2k 1 (T -t 0 ) | h | 2 . (3.20)
The proof is complete also in case (ii).

Remark 3.3. The above proof shows also that: if x : [t 0 , T ] → R n is optimal for P(t 0 , x 0 ) and p : [t 0 , T ] → R n is an absolutely continuous function such that (x, p) solves the system

-ṗ(t) ∈ ∂ - x H(x(t), p(t)) ẋ(t) ∈ ∂ - p H(x(t), p(t)), -p(T ) ∈ ∂ +,pr φ(x(T )) a.e. in t, T , (3.21)
for some t 0 ≤ t < T , then (3.3) holds true for all t ∈ [t, T ], with uniform constants R, c on [t, T ].

Remark 3.4. One can easily adapt the previous proof to show that the above inclusion holds true with the Fréchet superdifferential as well, that is, if -p(T ) ∈ ∂ + φ(x(T )), then

-p(t) ∈ ∂ + x V (t, x(t)) for all t ∈ [t 0 , T ].
In this case, the term

c | h | 2 in (3.3) is replaced by o(| h |).
Theorem 3.5. Assume (SH), (H1) and let φ : R n → R be locally Lipschitz. Let x : [t 0 , T ] → R n be an optimal solution for problem P(t 0 , x 0 ) and let p : [t 0 , T ] → R n be such that (x, p)

solves the system -ṗ(t) ∈ ∂ - x H(x(t), p(t)) ẋ(t) ∈ ∂ - p H(x(t), p(t)) a.e. in [t 0 , T ] , (3.22)
and satisfies the transversality condition

-p(T ) ∈ ∂ + φ(x(T )). ( 3
D ↓ V (t, x(t))(α, α ẋ(t) + θ) = lim sup τ →0 + V (t + ατ, x τ (t) + τ α ẋ(t)) -V (t, x(t)) τ . ( 3
D ↓ V (t, x(t))(α, α ẋ(t) + θ) ≤ lim sup τ →0 + V (t + ατ, x τ (t + ατ )) -V (t, x(t)) τ ≤ lim sup τ →0 + φ(x τ (T )) -φ(x(T )) τ ≤ lim sup τ →0 + -p(T ), x τ (T ) -x(T ) τ .
(3.30)

In view of (3.7), the above upper limit does not exceed -p(t), θ . Recalling Remark 2.12, we have that H(x(t), p(t)) = ẋ(t), p(t) for all t ∈ [t 0 , T ]. Thus, we finally obtain

D ↓ V (t, x(t))(α, α ẋ(t) + θ) ≤ αH(x(t), p(t)) + -p(t), α ẋ(t) + θ . (3.31)
Hence, for all α ∈ R and

θ 1 ∈ R n , D ↓ V (t, x(t))(α, θ 1 ) ≤ αH(x(t), p(t)) + -p(t), θ 1 . (3.32)
The conclusion (3.24), in case (i), follows from (2.8), (2.9), and (3.32). Now, suppose to be in case (ii), that is p(s) = 0 for all s ∈ [t 0 , T ]. Thanks to (2.8), (2.9), and the fact that H(x, 0) = 0 the inclusion (3.24) holds true if and only if, for all (α, θ) ∈ R × R n , D ↓ V (t, x(t))(α, θ) ≤ 0 for all t ∈ (t 0 , T ).

(

D ↓ V (t, x(t))(α, θ) = lim sup τ →0 + V (t + ατ, x τ (t + ατ )) -V (t, x(t)) τ ≤ lim sup τ →0 + φ(x τ (T )) -φ(x(T )) τ ≤ 0. (3.36)
Then, the conclusion holds true also in case (ii).

Remark 3.6.

• The above reasoning can be also applied to the end-point t = T to prove that lim sup tրT, y→x(T )

V (t, y) -V (T, x(T )) + p(T ), y -x(T ) |y -x(T )| + |t -T | ≤ 0. (3.37)
Similarly, in the case of t = t 0 , one can show that lim sup

tցt 0 , y→x(t 0 ) V (t, y) -V (t 0 , x(t 0 )) + p(t 0 ), y -x(t 0 ) |y -x(t 0 )| + |t -t 0 | ≤ 0. (3.38) • If, in addition, ∇ p H(•, •) is locally Lipschitz in R n × (R n {0}),

Necessary and sufficient conditions for optimality

The first result of this section can be seen as a strengthening of the maximum principle. Roughly speaking, we want to prove that every solution p of system (4.1) below, where q is any proximal supergradient of the final cost, provides a dual arc associated with the optimal trajectory x, i.e. (x, p) satisfies the maximum principle (2.5). In the proof of a similar result for parameterized control systems (see, e.g., [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]Theorem in 7.3.1.]), a crucial role is played by the analysis of the response of the system to a variation of a fixed control. This approach is unavailable, in general, for differential inclusions. Here, the role of the variational equation will be played by the partial sensitivity relations of the previous section under a further assumption on the multifunction F .

Theorem 4.1. Assume (SH), (H1), and suppose F : R n ⇒ R n is locally strongly convex and φ : R n → R locally Lipschitz. Let -∞ < t 0 < T and let x : [t 0 , T ] → R n be an optimal solution of P(t 0 , x 0 ) and let q ∈ ∂ +,pr φ(x(T )). Then,

• there exists a solution p : [t 0 , T ] → R n of the differential inclusion

-ṗ(s) ∈ ∂ - x H(x(s), p(s)) a.e. in [t 0 , T ] , -p(T ) = q.
(4.1)

• any solution p(•) to (4.1) satisfies the maximum principle

H(x(t), p(t)) = ẋ(t), p(t) a.e. in [t 0 , T ]. (4.2)
Moreover, if q = 0, then (4.2) holds true everywhere in [t 0 , T ].

Proof. Let x(•) be an optimal solution of P(t 0 , x 0 ). Define the multifunction G :

[t 0 , T ] × R n ⇒ R n by G(s, p) = ∂ - x H(x(s), p).
Observe that:

• for each (t, p) ∈ [t 0 , T ] × R n , G(t, p
) is nonempty compact and convex set;

• by a known property of the generalized gradient, there exists a constant k > 0 such that, ∀(s, p) ∈ [t 0 , T ] × R n and ∀v ∈ G(s, p), it holds that |v| ≤ k|p|;

• G is upper semicontinuous.

In order to verify the last property, let us prove that

G has a closed graph in [t 0 , T ] × R n × R n .
The conclusion follows because a multifunction taking values in a compact set and having a closed graph is upper semicontinuous (see e.g. Corollary 1 p. 41 in [START_REF] Aubin | Gründlehren der Mathematischen Wissenschaften[END_REF]). The graph of G is

Graph(G) = {((t, p), q) , (t, p) ∈ [t 0 , T ] × R n : q ∈ ∂ - x H(x(t), p)}.
Let ((t i , p i ), q i ) be a sequence in Graph(G) which converges to some ((t, p), q). Since q i ∈ ∂ - x H(x(t i ), p i ), there exists an open set A containing x([t 0 , T ]) and a constant c = c(A) such that

H(y, p i ) -H(x(t i ), p i ) -q i , y -x(t i ) ≥ -c|p i ||y -x(t i )| 2 (4.3)
for any point y ∈ A and i large enough. Passing to the limit in (4.3), we see that q ∈ ∂ - x H(x(t), p). This proves that the graph of G is closed.

From the above three properties we deduce the existence of at least one solution, p(•), of (4.1) on [t 0 , T ]. Let us now show that every solution p(•) to (4.1) satisfies (4.2). Hence, in the sequel, let q and p be fixed as above. If q = 0, then, thanks to Remark 2.10, we conclude that the solution of (4.1) vanishes on [t 0 , T ]. In this case, equality (4.2) is obvious. Consider, next, the case of q = 0. Then, Remark 2.10 ensures that p(•) never vanishes on [t 0 , T ]. So, let us derive (4.2) in the stronger form ẋ(t) = ∇ p H(x(t), p(t))

for all t ∈ [t 0 , T ]. The proof is divided into two steps.

First step. In this step, we prove (4.4) on a suitable interval (Tτ , T ].

Observe that, since q ∈ ∂ +,pr φ(x(T )), there exist constants r 1 > 0 and c 1 > 0 such that

φ(y) -φ(x(T )) + p(T ), y -x(T ) ≤ c 1 |y -x(T )| 2 , (4.5)
whenever y ∈ B(x(T ), r 1 ). Thus, let us consider the tubular compact neighborhood of x([t 0 , T ]) defined by

D r 1 (x([t 0 , T ])) = {x ∈ R n : ∃t ∈ [t 0 , T ] such that |x -x(t)| ≤ r 1 }.
The following constants will be used in the rest of the proof:

• k is the Lipschitz constant of ∇ p H(•, p), for p = 0, on D r 1 (x([t 0 , T ])), • c ′ is such that c ′ |p| is the semiconvexity constant of H(•, p) on D r 1 (x([t 0 , T ])),
• R is the radius of strong convexity of the multifunction

F on D r 1 (x([t 0 , T ])).
We start with a brief observation. Consider the Cauchy problem: for all

τ 1 ∈ (0, T -t 0 ], ẋ(t) = ∇ p H(x(t), p(t)) for all t ≥ T -τ 1 , x(T -τ 1 ) = x(T -τ 1 ). (4.6) If τ 1 > 0 is such that τ 1 e kτ 1 = r 1 ẋ -∇ p H(x, p) ∞ +1
,

then the solution x to (4.6) is well-defined on the interval [T -τ 1 , T ] and |x(t) -x(t)| ≤ r 1 for all t ∈ [T -τ 1 , T ]. Indeed, otherwise, there exists t, T -τ 1 < t < T , such that |x(t) -x(t)| = r 1 and |x(t) -x(t)| < r 1 for all t ∈ [T -τ 1 , t).
On the other hand, note that:

|x(t) -x(t)| ≤ t T -τ 1 | ẋ(s) -∇ p H(x(s), p(s))| ds ≤ t T -τ 1 |∇ p H(x(s), p(s)) -∇ p H(x(s), p(s))| + | ẋ(s) -∇ p H(x(s), p(s))| ds ≤ k t T -τ 1 |x(s) -x(s)|ds + t T -τ 1 | ẋ(s) -∇ p H(x(s), p(s))|ds ≤ k t T -τ 1 |x(s) -x(s)|ds + (t -T + τ 1 ) ẋ -∇ p H(x, p) ∞ +1 . (4.7)
By the Gronwall inequality, we have that:

|x(t) -x(t)| ≤ (t -T + τ 1 )e k(t-T +τ 1 ) ẋ -∇ p H(x, p) ∞ +1 . (4.8) Then, since T -τ 1 < t < T , |x(t) -x(t)| < r 1 . (4.9)
This contradicts the choice of t. Now, set τ := min{τ 1 , τ 2 }, where τ 1 is as above and τ 2 > 0 is such that

e kτ 2 τ 1 2 2 2R(c 1 + c ′ p ∞ τ 1 ) min [t 0 ,T ] |p| = 1 2 .
Let us prove the equality in (4.4) on (Tτ , T ]. Define the admissible trajectory x 1 : [t 0 , T ] → R n in the following way:

• on the interval [t 0 , Tτ ), x 1 (•) coincides with the optimal trajectory x(•),

• on the interval [Tτ , T ], x 1 (•) is the solution of the Cauchy problem:

ẋ1 (t) = ∇ p H(x 1 (t), p(t)) for all t ∈ [T -τ , T ], x 1 (T -τ ) = x(T -τ ). (4.10)
Recall that D r 1 (x([t 0 , T ])). We are going to give a first estimate for xx 1 ∞ . Proceeding as in (4.7), we have that for all t ∈ [Tτ , T ],

|x(t) -x 1 (t)| ≤ k t T -τ |x(s) -x 1 (s)|ds + t T -τ | ẋ(s) -∇ p H(x(s), p(s))|ds. (4.11)
By the Gronwall inequality, the above estimate yields that, for every t ∈ [Tτ , T ],

|x(t) -x 1 (t)| ≤ e kτ T T -τ | ẋ(s) -∇ p H(x(s), p(s))|ds. (4.12)
The next point is to bound the right-hand side of (4.12). Since x 1 (T ) ∈ B(x(T ), r 1 ), by (4.5) we have that

φ(x 1 (T )) -φ(x(T )) + p(T ), x 1 (T ) -x(T ) ≤ c 1 |x 1 (T ) -x(T )| 2 . (4.13)
Observe that, since φ(x The semiconvexity of H(•, p) yields

1 (T )) -φ(x(T )) ≥ 0, p(T ), x 1 (T ) -x(T ) ≤ c 1 |x 1 (T ) -x(T )| 2 . (4.14)
(I) ≥ T T -τ H(x(s), p(s)) -H(x 1 (s), p(s)) -c ′ |p(s)||x 1 (s) -x(s)| 2 ds. (4.16)
As for (II), recalling (2.16) we have that

(II) = T T -τ H(x 1 (s), p(s)) -H(x(s), p(s)) + p(s), ∇ p H(x(s), p(s)) -ẋ(s) . Now, since F (x) is R-convex for all x ∈ D r 1 (x([t 0 , T ]
)), we can invoke Lemma 2.16 and (H2) to bound the above scalar product. We thus obtain

(II) ≥ T T -τ H(x 1 (s), p(s)) -H(x(s), p(s)) + 1 2R |p(s)||∇ p H(x(s), p(s)) -ẋ(s)| 2 ds. (4.17)
Combining (4.15)-(4.17) we conclude that

p(T ), x 1 (T ) -x(T ) ≥ T T -τ -c ′ |p(s)||x 1 (s) -x(s)| 2 + 1 2R |p(s)||∇ p H(x(s), p(s)) -ẋ(s)| 2 ds. (4.18)
Inequalities (4.14) and (4.18) imply that

T T -τ | ẋ(s) -∇ p H(x(s), p(s))| 2 ds ≤ 2R min [t 0 ,T ] |p| (c 1 + c ′ p ∞ τ ) x 1 -x 2 ∞ . (4.19)
So, we can go back to (4.12) and estimate the integral on the right-hand side using (4.19) and the Hölder inequality. We obtain that:

x -x 1 ∞ ≤ e kτ τ 1 2 2R(c 1 + c ′ p ∞ τ ) min [t 0 ,T ] |p| x 1 -x ∞ . (4.20)
By the choice of τ , it follows that xx 1 ∞ = 0. So, by (4.19), we finally conclude that In the first step we have constructed an element of such a set, proving that Γ is nonempty. So, it is enough to show that the supremum of Γ, τ m , is equal to Tt 0 . Arguing by contradiction, suppose τ m < Tt 0 . By Remark 3.3, there exist constants c 2 , r 2 > 0 such that Observe that x, restricted to [t 0 , Tτ m ], is an optimal trajectory of the above problem. Thus, recalling again that

ẋ(t) = ∇ p H(x(t), p(t)) a.e. in [T -τ , T ]. ( 4
V (t, y) -V (t, x(t)) + p(t), y -x(t) ≤ c 2 | y -x(t) | 2 , ( 4
-ṗ(s) ∈ ∂ - x H(x(s), p(s)) a.e. in [t 0 , T -τ m ], -p(T -τ m ) ∈ ∂ +,pr x V (T -τ m , x(T -τ m )), (4.24)
by our first step one can deduce the existence of a constant τ > 0 such that the equality in (4.4) holds true everywhere in (Tτ mτ , Tτ m ]. But this statement contradicts the fact that τ m is the supremum of Γ. We conclude that τ m = Tt 0 , and the equality in (4.4) holds true everywhere in [t 0 , T ]. This concludes the proof.

Remark 4.2. The above result and Theorem 3.5 together imply that, for any q ∈ ∂ +,pr φ(x(T )) and any solution p of (4.1), both the maximum principle and the full sensitivity relation (3.24) hold true. This is a stronger conclusion than the one of Theorem 2.8, which only affirms that the maximum principle (2.5) holds true for some q ∈ ∂φ(x(T )) and some solution p(•). For this reason, using the proximal superdifferential of φ instead of the generalized gradient seems more appropriate whenever (H1) is satisfied and F is locally strongly convex. Now, we are ready to give a set of necessary and sufficient conditions for optimality.

Theorem 4.3. Assume (SH), (H1). Let F : R n ⇒ R n be locally strongly convex and let φ : R n → R be locally semiconcave. A solution x : [t 0 , T ] → R n of system (1.11)-(1.12) is optimal for P(t 0 , x 0 ) if and only if, for every q ∈ ∂ + φ(x(T )), any solution p : [t 0 , T ] → R n of the differential inclusion

-ṗ(t) ∈ ∂ - x H(x(

Relations between reachable gradients of the value function and optimal trajectories

In the calculus of variations, the existence of a one-to-one correspondence between the set of minimizers starting from a point (t, x) and the set of all reachable gradients of the value function V at (t, x) is a well-known fact. This allows, among other things, to identify the singular set of the value function-that is, the set of points at which V is not differentiable-as the set of points (t, x) for which the given funtional admits more than one minimizer. The aim of this last section is to investigate the above property for Mayer functionals with differential inclusions. Here, the difficulty consists in the nonsmoothness of the Hamiltonian at p = 0 that will force us to study separately the case of 0 ∈ ∂ * V (t, x). When the Hamiltonian and the terminalt cost are of class C 1,1 loc (R n × (R n {0})) and C 1 (R n ), respectively, there is an injective map from ∂ * V (t, x) {0} to the set of all optimal trajectories starting from (t, x) (see, for instance, [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]Theorem 7.3.10] where the authors study parameterized optimal control problems with smooth data). However, we assume below neither the existence of a smooth parameterization, nor such a regularity of the Hamiltonian. Our assumptions for the terminal cost function are also milder than in [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]. It is precisely the lack of regularity of H that represents the main difficulty, since it does not guarantee the uniqueness of solutions to system (5.1) below. We shall prove that, in our case, there exists an injective set-valued map from ∂ * V (t, x) {0} into the set of optimal trajectories starting from (t, x). Lemma 5.1. Assume (SH) and (H1), and suppose φ is locally Lipschitz and such that ∂ + φ(z) = ∅ for all z ∈ R n . Then, given a point (t, x) ∈ (-∞, T )×R n and a vector p = (p t , p x ) ∈ ∂ * V (t, x) {0}, there exists at least one pair (y(•), p(•)) that satisfies the system ẏ(s) = ∇ p H(y(s), p(s)) for all s ∈ [t, T ], ṗ(s) ∈ ∂ -

x H(y(s), p(s)) a.e. in [t, T ],

(5.1)

together with the initial conditions

y(t) = x, p(t) = -p x , (5.2)
such that y(•) is optimal for P(t, x).

Proof. Observe, first, that if (p t , p x ) ∈ ∂ * V (t, x) {0}, then p x = 0. Indeed, V satisfies -V t + H(x, -V x (t, x)) = 0 at every point of differentiability. Therefore, taking limits, we have that -p t + H(x, -p x ) = 0 for every (p t , p x ) ∈ ∂ * V (t, x). Since H(x, 0) = 0, we conclude that if (p t , p x ) = 0, then p x = 0. Since (p t , p x ) ∈ ∂ * V (t, x), we can find a sequence

{(t k , x k )} such that V is differentiable at (t k , x k ) and lim k→∞ (t k , x k ) = (t, x), lim k→∞ ∇ x V (t k , x k ) = p x .
Let y k (•) be an optimal trajectory for P(t k , x k ). Since p x = 0, there exists k > 0 such that ∇ x V (t k , x k ) = 0 for all k > k. By Remark 2.9, there exists an arc p k such that (y k , p k ) satisfies

ẏk (s) ∈ ∂ - p H(y k (s), p k (s)) a.e. in [t k , T ], y k (t k ) = x k , -ṗk (s) ∈ ∂ - x H(y k (s), p k (s)) a.e. in [t k , T ], -p k (T ) ∈ ∂ + φ(y k (T )). (5.3)
Moreover, by Theorem 3.1, we have that

-p k (t k ) ∈ ∂ + x V (t k , x k ). Since V is differentiable at (t k , x k ), it follows that -p k (t k ) = ∇ x V (t k , x k ).
(•) in L 1 ([t -1, T ]; R n ). Now, observe that ((y k (s), p k (s)), -ṗk (s)) ∈ Graph(M ) a.e. in [t k , T ],
where M is the multifunction defined by M (x, p) := ∂ - x H(x, p). The multifunction M is upper semicontinuous; this can be easily derived as it was done for G in the proof of Theorem 4.1. Hence, from Theorem 7.2.2. in [START_REF] Aubin | Systems & Control: Foundations & Applications[END_REF]

p k (t k ) = -lim k→∞ ∇ x V (t k , x k ) = -p x = 0.
So, we appeal again to Remark 2.10 to deduce that p(•) never vanishes on [t, T ]. Since the map (x, p) → ∇ p H(x, p) is continuous for p = 0, we can pass to the limit in (5.4) and deduce that ẏ(s) = ∇ p H(y(s), p(s)) for all s ∈ [t, T ]. In conclusion, (y(•), p(•)) is a solution of the system in (5.1) with initial conditions y(t) = x, p(t) = -p x . This implies of course that ẏ(s) ∈ F (y(s)) for all s ∈ [t, T ]. Moreover, since V is continuous and y k (•) is optimal, we have

φ(y(T )) = lim k→∞ φ(y k (T )) = lim k→∞ V (t k , y k (t k )) = V (t, y(t)),
which means that y(•) is optimal for P(t, x).

The nondegeneracy condition ∂ + φ(z) = ∅ for all z ∈ R n that we have assumed above is verified, for instance, when φ is differentiable or semiconcave.

Remark 5.2. From the above proof it follows that, if the cost is supposed to be of class C 1 (R n ), then the pair (y(•), p(•)) in Lemma 5.1 satisfies ∇φ(y(T )) = -p(T ). Moreover, p is a dual arc associated to y. Now, fix (t, x) ∈ (-∞, T ) × R n . For any p = (p t , p x ) ∈ ∂ * V (t, x) {0}, we denote by R(p) the set of all trajectories y(•) that are solutions of (5.1)-(5.2), and optimal for P(t, x). The above lemma guarantees that the set-valued map R that associates with any p ∈ ∂ * V (t, x) {0} the set R(p) has nonempty values. Now let us prove that R is strongly injective. We will use the "difference set": Proof. Suppose to have two elements

∂ - x H(x, p) -∂ - x H(x, p) := {a -b : a, b ∈ ∂ - x H(x, p)}.
p i = (p i,t , p i,x ) ∈ ∂ * V (t, x) {0}, i = 1, 2, with p 1 = p 2 .
Note that the Hamilton-Jacobi equation implies that p 1,x = p 2,x if and only p 1 = p 2 . Furthermore, suppose that there exist two pairs (y(•), p i (•)), i = 1, 2 that are solutions of system (5.1) with p i (t) = p i,x and y(•) is optimal for P(t, x). Then, we get

ẏ(s) = ∇ p H(y(s), p 1 (s)) = ∇ p H(y(s), p 2 (s)) for all s ∈ [t, T ]. This implies that p i (s) ∈ N F (y(s)) ( ẏ(s)) , i = 1, 2 for all s ∈ [t, T ].
By (H3), the normal cone N F (y(s)) ( ẏ(s)) is a half-line. Recalling also that p i (i = 1, 2) never vanishes, it follows that there exists λ(s) > 0 such that p 2 (s) = λ(s)p

(R {0}) p ∩ ∂ - x H(x, p) -∂ - x H(x, p) = ∅ ∀p = 0. ( 5.6)
From (5.5) and (5.6) we obtain that λ(s) = 0 a.e. in [t, T ]. This gives that λ is constant. Moreover, since φ ∈ C 1 (R n ), we have that ∇φ(y(T )) = -p i (T ), i = 1, 2, which implies that λ = 1. But this yields p 1,x = p 2,x , which contradicts the inequality p 1 = p 2 . Hence, we can assert that the functions y i (•), i = 1, 2, are different.

Remark 5.4. Assumption (H4) is verified, for instance, when x → H(x, p) is differentiable, without any Lipschitz regularity of the map x → ∇ p H(x, p).

Example 5.5. The above theorem is false when φ / ∈ C 1 (R n ). Indeed, without such an assumption there could exist infinitely many reachable gradients at a point at which the optimal trajectory is unique. Let us consider the state equation in the one-dimensional space given by ẋ = u ∈ [-1, 1]. Let the cost function be defined by

φ(x) = x 2 sin 1 x + 3x if x = 0, 0 if x = 0.
This function is differentiable, with derivative φ ′ (x) = cos( 1 x ) + 2x sin( 1 x ) + 3 if x = 0, 3 if x = 0 which is discontinuous at zero because cos( 1 x ) oscillates as x → 0. Therefore, this function is differentiable but not of class C 1 (R). Moreover, ∂ * φ(0) = [START_REF] Aubin | Systems & Control: Foundations & Applications[END_REF][START_REF] Cannarsa | Some characterizations of optimal trajectories in control theory[END_REF]. Note that φ is strictly increasing. Thus, for any (t, x) ∈ [0, T ] × R, there exists a unique optimal control that is the constant one u ≡ -1, and so the unique optimal trajectory is x(s) = xs + t. The value function is V (t, x) = φ(x -T + t), and so it has the same regularity as the final cost φ. Summarizing, ∂ * V (t, x) = {(a, a) : a ∈ [2, 4]} at any point (t, x) such that x = Tt, but there exists a unique optimal trajectory starting from such points. Now let us consider the case when p = 0 ∈ ∂ * V (t, x). Theorem 5.6. Assume (SH), (H1) and suppose that φ ∈ C 1 (R n ). Let (t, x) ∈ (-∞, T ) × R n be such that 0 ∈ ∂ * V (t, x). Then there exists an optimal trajectory y : [t, T ] → R n for P(t, x) such that ∇φ(y(T )) = 0. Consequently, the corresponding dual arc is equal to zero.

Proof. Since 0 ∈ ∂ * V (t, x), we can find a sequence {(t k , x k )} such that V is differentiable at (t k , x k it follows that y is optimal for P(t, x). Furthermore, the sensitivity relation in Remark 3.4 holds true and so, recalling that V is differentiable at (t k , x k ), we have As applications of the above results we obtain the following corollaries.

-p k (t k ) = ∇ x V (t k , x k ) → 0. ( 5
Corollary 5.7. Under the same assumptions of Theorem 5.3, for every (t, x) ∈ (-∞, T ]×R n there exist at least as many optimal solutions of P(t, x) as elements of ∂ * V (t, x) .

Proof. Fix (t, x) ∈ (-∞, T ]×R n . By Lemma 5.1 and Remark 5.2, to every p = (p t , p x ) ∈ ∂ * V (t, x) {0} corresponds a pair of arcs (y, p) satisfying (5.1) and such that -p(t) = p x , y is optimal for P(t, x) and -p(T ) = ∇φ(y(T )). Moreover, since the arc p never vanishes, we have that ∇φ(y(T )) = 0. Theorem 5.3 implies that optimal solutions corresponding to distinct elements of ∂ * V (t, x) {0} are distinct. On the other hand, if 0 ∈ ∂ * V (t, x), then Thereom 5.6 yields the existence of an optimal trajectory y for P(t, x) such that 0 = ∇φ(y(T )). These facts give our claim.

Corollary 5.8. Assume (SH), (H1), φ ∈ C 1 (R n ) and suppose also that ∇φ(x) = 0 for all x ∈ R n . Then 0 ∈ ∂ * V (t, x) for all (t, x) ∈ (-∞, T ) × R n .

Corollary 5.9. Assume (SH), (H1), (H3), (H4) and let φ ∈ C 1 (R n ) ∩ SC(R n ). If V fails to be differentiable at a point (t, x) ∈ (-∞, T ) × R n , then there exist two or more optimal trajectories starting from (t, x).

Proof. Since V is semiconcave (see [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF]), if it is not differentiable at a point (t, x) ∈ (-∞, T ) × R n , then we can find two distinct elements p 1 , p 2 ∈ ∂ * V (t, x). If p 1 , p 2 are both nonzero, we can apply Theorem 5.3 to find two distinct optimal trajectories. If one of the two vectors is zero, for instance p 1 , then there exists at least an associated optimal trajectory y 1 (•) such that ∇φ(y 1 (T )) = 0 by Theorem 5.6, but for any optimal trajectory y 2 (•) associated to p 2 it holds that ∇φ(y 2 (T )) = 0 by Lemma 5.1 and Remark 2.10.

It might happen that two or more optimal trajectories actually start from a point (t, x) at which V is differentiable. However, if H ∈ C 1,1 loc (R n × (R n {0})), then it is well-know that such a behaviour can only occur when the gradient of V at (t, x) vanishes (see e.g. Theorem 7.3.14 and Example 7.2.10(iii) in [START_REF] Cannarsa | Semiconcave functions, Hamilton-Jacobi equations, and optimal control[END_REF]). More can be said in one space dimension as we explain below.

Example 5.10. When n = 1 it is easy to show that, if V is differentiable at some point (t 0 , x 0 ) with V x (t 0 , x 0 ) = 0, then there exists a unique optimal trajectory starting from (t 0 , x 0 ). Indeed, in this case, F (x) = [f (x), g(x)] for suitable functions f, g : R → R, with f ≤ g, such that -f and g are locally semiconvex. So, H(x, p) = f (x)p, p < 0, g(x)p, p ≥ 0.

(5.8)

Furthermore, since

  x(Tτ ) = x(Tτ ), we have that p(T ), x 1 (T )x(T ) = T T -τ ṗ(s), x 1 (s)x(s) ds + T T -τ p(s), ẋ1 (s) -ẋ(s) ds = (I) + (II).

  .21) Since arc p(•) never vanishes, the pair (x(•), p(•)) stays in the set where H is differentiable with respect to p. Thus, (4.21) is true for all t ∈ (Tτ , T ]. Second step. In this step we prove (4.4) in the whole interval [t 0 , T ]. Set Γ := {τ ∈ (0, Tt 0 ] : (4.4) holds true in (Tτ, T ]}.

  .22) for all t ∈ (T -τ m , T ] and for all y ∈ B(x(t), r 2 ). Moreover, since r 2 and c 2 are uniform with respect to time, (4.22) still holds true when t = Tτ m . So, p(Tτ m ) ∈ ∂ +,pr x V (Tτ m , x(Tτ m )). (4.23) Finally, consider the Mayer problem with final cost V (Tτ m , •) and time horizon Tτ m , that is, inf{V (Tτ m , y(Tτ m )) : ẏ ∈ F (y) a.e. in [t 0 , Tτ m ], y(t 0 ) = x 0 }.

Theorem 5 . 3 .

 53 Assume (SH), (H1), and suppose that φ is of class C 1 (R n ) and (H3) for each z ∈ R n , F (z) is not a singleton and has a C 1 boundary (for n > 1),(H4) R + p ∩ (∂ - x H(z, p) -∂ - x H(z, p)) = ∅ ∀p = 0 for all z ∈ R n .Then for any p 1 , p 2 ∈ ∂ * V (t, x) {0} with p 1 = p 2 , we have that R(p 1 ) ∩ R(p 2 ) = ∅.

  ) and lim k→∞ (t k , x k ) = (t, x), lim k→∞ ∇V (t k , x k ) = 0. Let y k (•) be an optimal trajectory for P(t k , x k ) and p k (•) be a dual arc. We extend y k and p k on [t -1, T ] as in the proof of Lemma 5.1. By Theorem 7.2.2 in [2], we can assume, after possibly passing to a subsequence, that y k (•) converges uniformly to y(•) which is a trajectory of our system on [t, T ]. Since φ(y(T )) = lim k→∞ φ(y k (T )) = lim k→∞ V (t k , x k ) = V (t, x),

. 7 )

 7 By (5.7),(2.15) and the Gronwall's inequality, we get that p k (T ) → 0 when k → ∞. We conclude that ∇φ(y(T )) = lim k→∞ ∇φ(y k (T )) = lim k→∞ -p k (T ) = 0.

  .7)Proof. First, recall that, thanks to Remark 2.10, p(t) = 0 for all t ∈ [t 0 , T ]. Hence, x(•) is the unique solution of the Cauchy problem

ẋ(s) = ∇ p H(x(s), p(s)) for all s ∈ [t, T ] , x(t) = x(t).

(3.8)

Let k > 0 be a Lipschitz constant for ∇ p H(•, p) on D r (x([t 0 , T ])) for p = 0. We claim that x h takes values in D r (x([t 0 , T ])) for all h ∈ B 0, re -k(T -t 0 ) . By contradiction, suppose that there exists s, t < s < T , such that |x h (s)x(s)| = r and |x h (s)x(s)| < r for all s ∈ [t, s). Then, by standard arguments based on Gronwall's lemma we conclude that

  T -t 0 ) |h| 2 + Adding up the previous relations, it follows that (3.7) holds true with c 1 := (Tt 0 )c ′ p ∞ e 2k(T -t 0 ) . The lemma is proved.Proof of Theorem 3.1. First note that estimate (3.3) is immediate for t = T . Let us observe that, in view of Remark 2.10, it holds that:

	Now recalling (2.16), (3.5) and (3.8), we get
		T
	(II) =	t	-p(s), ∇ p H(x h (s), p(s)) -∇ p H(x(s), p(s)) ds
			T
		=	(-H(x h (s), p(s)) + H(x(s), p(s))) ds.
		t

T t H (x h (s), p(s)) -H(x(s), p(s))) ds.

  .33) Let t ∈ (t 0 , T ) and (α, θ) ∈ R × R n be fixed. By Filippov's Theorem (see, e.g., [2, Theorem 10.4.1]), there exists a constant k such that, for any 0 < τ < 1, the initial value problem

	ẋ(s) ∈ F (x(s)) a.e. in [t + ατ, T ], x(t + ατ ) = x(t) + τ θ,	(3.34)
	has a solution, x τ (•), that satisfies the inequality
	x τ -x ∞ ≤ kτ.	(3.35)
	Hence, by the dynamic programming principle, (3.23), (2.9) and (3.35) we deduce that

  Thus, for k > k we have that p k (s) = 0 for all s ∈ [t k , T ] (see Remark 2.10), and the first inclusion in (5.3) becomes ẏk (s) = ∇ p H(y k (s), p k (s)) for all s ∈ [t k , T ]. that verifies the conclusions of the lemma. It is easy to prove that the sequences of functions {p k } k and {y k } k are uniformly bounded and uniformly Lipschitz continuous in [t -1, T ], using Gronwall's inequality together with estimates (2.15) and (SH)(iii), respectively. Hence their derivatives are essentially bounded. Therefore, after possibly passing to subsequences, we can assume that the sequence (y

(5.4)

Now, we extend y k and p k on [t -1, t k ) by setting y(s) = y(t k ), p(s) = p(t k ) for all s ∈ [t -1, t k ). The last point of the reasoning consists of proving that the sequence (y k (•), p k (•)), after possibly passing to a subsequence, converges to a pair (y(•), p(•)) k (•), p k (•)) converges uniformly in [t -1, T ] to some pair of Lipschitz functions (y(•), p(•)). Moreover, ṗk (•) converges weakly to ṗ

We will see that p(•) is in the set of differentiability of the map H(x, •) when p(T ) = 0. In that case, the second inclusion in (1.15) becomes ẋ(t) = ∇pH(x(t), p(t)) for all t ∈ [t0, T ].

This standard convention will be used throughout the paper.

(H2) holds with a constant c ′ on K if and only if F (x) satisfies the R-convexity property for all x ∈ K with radius R = (2c ′ ) -1 .

If (H2) holds, then ∇ p H(x, p) exists for all x ∈ K and p ∈ R n {0} and is Hölder continuous in x on K with exponent 1/2, uniformly for p ∈ R n {0}.

Acknowledgements

Partial support of this research by the European Commission (FP7-PEOPLE-2010-ITN, Grant Agreement no. 264735-SADCO), and by the INdAM National Group GNAMPA is gratefully acknowledged.

If x(•) is an optimal trajectory at (t 0 , x 0 ) and p(•) is a dual arc associated with x(•), then by Remark 3.4 we have that 0 = V x (t 0 , x 0 ) = -p(t 0 ). Therefore, 0 = p(t) for all t ∈ [t 0 , T ] by Remark 2.10. Thus, (5.8) and the maximum principle yield

(5.9)

Since f and g are both locally Lipschitz, x(•) is the unique solution of (5.9) satisfying x(t 0 ) = x 0 .


Wassim Hamidouche
email: wassim.hamidouche@insa-rennes.fr

Mickael Raulet

Olivier Déforges

PARALLEL SHVC DECODER: IMPLEMENTATION AND ANALYSIS

Keywords: HEVC, SHVC, parallel processing

The new Scalable High efficiency Video Coding (SHVC) standard is based on a multi-loop coding structure which requires the total decoding of all intermediate layers. The decoding complexity becomes then a real issue, especially for a real time decoding of ultra high video resolutions. A parallel processing architecture is proposed to reduce both the decoding time and the latency of the SHVC decoder. The proposed solution combines the high level parallel processing solutions defined in the HEVC standard with an extension of the frame-based parallelism. The latter solution enables the decoding of several spatial and temporal SHVC frames in parallel to enhance both decoding frame rate and latency. The wavefront parallel processing solution is used for more coarse level of granularity. The proposed hybrid parallel processing approach achieves a near optimal speedup and provides a good trade-off between decoding time, latency and memory usage. On a 6 cores Xeon processor, the parallel SHVC decoder performs a real time decoding of 1600p60 video resolution.

INTRODUCTION

The Scalable High efficiency Video Coding (SHVC) standard is the scalable extension of the HEVC standard [START_REF] Sullivan | Overview of the High Efficiency Video Coding (HEVC) standard[END_REF]. The SHVC standard is currently being developed by the ITU-T VCEG and by the ISO/IEC MPEG under a partnership known as the Joint Collaborative Team on Video Coding (JCT-VC). The objective behind this work is to define tools to provide temporal, spatial and quality (SNR) scalability. Since the temporal scalability is already enabled in HEVC with a hierarchical temporal prediction structure, SHVC concentrates on spatial and SNR scalability. Several scalable solutions [START_REF] Shi | Spatially Scalable Video Coding for HEVC[END_REF][START_REF] Helle | A Scalable Video Coding Extension of HEVC[END_REF][START_REF] Chen | Scalable Video Coding Extension for HEVC[END_REF][START_REF] Zhao | Inter-layer Intra Mode Coding for the Scalable Extension of HEVC[END_REF] were proposed as a response to the SHVC call for proposal [START_REF]Joint Call for Proposals on Scalable Video Coding Extensions of High Efficiency Video Coding (HEVC)[END_REF]. The approved approach is based on multi-loop decoding structure (i.e. all intermediate layers need to be decoded) and uses the same technologies of HEVC with an inter-layer prediction to improve the coding efficiency. This solution allows a gain of 20%-35% in terms of rate-distortion compared to a simulcast coding configuration. The SHVC encoder encodes the original video into L layers. The first layer repre-sents the base quality of the video, and decoding more layers allows to further enhance the temporal, spatial or SNR quality of the video. To decode the L th video layer, all intermediate layers (l = 1, ..., (L -1)) need to be fully decoded to perform inter-layer predictions. Moreover, in the case of spatial scalability, the decoded intermediate pictures are first up-sampled to match with the size of the upper layer picture. These extra operations considerably increase the complexity of the SHVC decoder compared to a single layer HEVC decoder. Therefore, SHVC decoding complexity becomes a real issue, especially to reach a real time decoding of ultra high video resolutions. In this paper we address the complexityrelated aspects of the SHVC decoder. A hybrid parallel processing architecture is proposed to decrease the decoding time and the latency of the SHVC decoder. The proposed architecture combines the high level parallel processing solutions defined in the HEVC standard with an extension of the framebased parallelism approach. This approach enables to decode several spatial and temporal SHVC frames in parallel to increase the decoding frame rate and reduce the frame latency. The high level parallel processing solutions, including wavefront, are used for more coarse level of granularity. The parallel SHVC decoder is based on the OpenHEVC software [START_REF]Open source HEVC decoder (OpenHEVC)[END_REF], which implements a conforming single layer HEVC decoder. The performance of the parallel SHVC decoder is evaluated on a computer fitter with a 6 cores Inter Xeon processor running at 3.2 Ghz. Experimental results show that the proposed solution performs a near optimal speedup and provides a good trade-off between decoding time, latency and memory usage. This paper is organized as follows. Section 2 gives a brief description of both HEVC and SHVC standards, including parallelization strategies in HEVC. Section 3 describes the parallel extension of the single layer OpenHEVC decoder. The SHVC decoder and the proposed hybrid parallel processing solution are presented in Section 4. The performance of the parallel SHVC decoder is assessed and discussed in Section 5

RELATED WORK

HEVC standard

The HEVC standard can reach the same subjective video quality as its predecessor H.264/AVC at about a half bitrate [START_REF] Ohm | Comparaison of the Coding Efficiency of Video Coding standards including High Efficiency Video coding (HEVC)[END_REF]. This gain is obtained thanks to new tools adopted in the HEVC standard, such as quadtree-based block partitioning, large transform and prediction blocks, accurate intra/inter predictions and the in-loop sample adaptive offset (SAO) filter. The HEVC frame is partitioned into Coding Tree Units (CTUs). Each contains one luma Coding Tree Block (CTB) and two chroma CTBs. Recursive subdivision of a CTU results in Coding Unit (CU) leaves with the corresponding Coding Blocks (CBs). The CU can be split into Prediction Units (PUs), a basic entity for intra and inter predictions, and recursively split into Transform Units (TUs), a basic entity for residual coding [START_REF] Sullivan | Overview of the High Efficiency Video Coding (HEVC) standard[END_REF]. The HEVC standard was designed with a particular attention to complexity, where several steps can be easily performed in parallel [START_REF] Chi | Parallel Scalability and Efficiency of HEVC Parallelization Approaches[END_REF][START_REF] Bossen | HEVC complexity and implementation analysis[END_REF]. Three high level parallel processing approaches, including independent slice, tile and wavefront, can be used in HEVC to simultaneously process multiple regions of a single picture. The frame can be partitioned into one or many slices, mainly to increase the bitstream robustness. The independent slices break the CABAC and the intra prediction dependencies and thus can be used for parallel encoding and decoding. The tile concept splits the picture into rectangular groups of CTBs, called tiles. As for slices, tiles break the coding dependencies at their boundaries, that each tile can be independently processed. However, slice and tile concepts have several disadvantages. Indeed, intra prediction limitation and resetting the CABAC probabilities decrease the coding performance in terms of rate distortion, especially for large number of tiles/slices per frame. Moreover, the in-loop filters cannot be performed in parallel at the tile/slice edges without additional control mechanism. The Wavefront Parallel Processing (WPP) solution splits the frame into CTB rows [START_REF] Clare | Wavefront parellel processing for HEVC Encoding and Decoding[END_REF]. In the WPP mode, the CABAC context is initialized at the start of each CTB row. The overhead caused by this initialization is limited since the CABAC context at each CTB row is initialized by the CABAC context state at the second CTB of the previous CTB row. As illustrated in Figure 1, the decoding of each CTB row can be carried out on separate threads with a minimum delay of two CTBs between adjacent CTB rows. Therfore, the wavefront dependencies require a delay of two CTBs between adjacent CTB rows, introducing parallelization inefficiency (not all threads are used when processing the start and the end of the frame) and requiring additional communication between threads decoding adjacent CTB rows. These three high level parallel processing solutions depend on the bitstream, and can be used only when the slice, tile or wavefront tools are enabled by the encoder. The frame-level parallelism allows to simultaneously process multiples frames, whatever the coding configuration, under the restriction that the motion compensation dependencies are satisfied [START_REF] Meenderinck | Parallel scalability of video decoders[END_REF]. The frame-based parallelism also suffers from a number of limitations. The performance of the frame-based parallelism solution strongly depends on the coding structure and the ranges of the motion vectors. Moreover, the frame-based parallelism improves the

Scalable SHVC standard

The SHVC standard aims to provide spatial and quality scalability with a simple and efficient coding architecture [START_REF]Joint Call for Proposals on Scalable Video Coding Extensions of High Efficiency Video Coding (HEVC)[END_REF]. All technologies defined in the HEVC standard are used in SHVC with an inter-layer prediction to further impove the rate-distortion performance compared to a simulcast coding configuration. For spatial scalability coding configuration with L layers, the SHVC encoder consists of L HEVC encoders, one for each layer. The Base Layer (BL) HEVC encoder (l = 1) encodes a downsampled version of the original video and feeds the HEVC encoder corresponding to the first (l = 2) Enhancement Layer (EL) with the decoded picture and its motion vectors (MVs). The L th HEVC encoder encodes the original video using the upsampled picture from the lower layer HEVC encoder (l = L -1) and its upscaled MVs as an additional reference picture for inter-layer predictions. The up-sampling operation is performed by a 8-tap interpolation filter for luma samples and a 4-tap filter for chroma samples [START_REF] Chen | Scalable High Efficiency Video Coding test model 3 (SHM 3)[END_REF]. The output of the L encoders are multiplexed to form a conforming SHVC bitstream. Therefore, the BL bitstream is HEVC conforming and can be decoded with any HEVC decoder. In this paper, the single layer OpenHEVC decoder is extended to support the wavefront parallel processing solution. The analytical speedup of the WPP solution is expressed following the number of decoding threads and the video parameters. Moreover, the proposed hybrid parallel processing solution is implemented under a software SHVC decoder. The performance of the parallel SHVC decoder is assessed in different decoding configurations. To the best of our knowledge, it is the first implementation of a real time SHVC decoder enabling a hybrid parallel processing solution.

PARALLEL SINGLE LAYER HEVC DECODER

OpenHEVC decoder

OpenHEVC is an open source implementation of the HEVC decoder. It is written in C programming language on the top of the FFmpeg library [START_REF]FFmpeg: Open source and cross-platform multimedia library[END_REF]. The source code is heavily optimized in Single Instruction Multiple Data (SIMD) methods, The architecture of the OpenHEVC decoder is based on a CTU. The decoder performs in a single pass all decoding steps at the CTU level. Figure 2 shows an overview of the OpenHEVC architecture. The hls decode row function decodes all CTUs of one row within the slice. It browses in raster scan the CTUs within the row and calls the recursive function hls coding tree to decode each CTU. This function browses in z-scan all CUs within the CTU and calls for each CU the hls coding unit function, performing one CU decoding. There are specific functions that handle the decoding of the prediction and the transform units, namely hls prediction unit and hls transform unit, respectively. Once all CUs within a CTU have been decoded, the deblocking filter (DF) and then the SAO filter are performed on the decoded CTU. However, when performing the DF of the current CTB, the right and the down CTB neighborhoods are not available (ie. not yet decoded). Therefore, the right and down edges of the current CTB are filtered when its right and down CTBs are being filtered, respectively. In this architecture, the DF and the SAO filters are delayed with one CTB and one CTB row for only the right and the down edges of a CTB, respectively. In terms of memory usage, the Open-HEVC decoder allocates two types of memory: local memory to hold informations used only at the level of the CTU, and global memory required to store informations at the picture and video sequence levels.

WPP extension in the OpenHEVC decoder

The WPP extension in the OpenHEVC architecture is straight forward. This is possible by running the hls decode row function on separate threads to decode several adjacent CTU rows in parallel. CABAC contexts are allocated.

Analytical performance of the WPP solution

The analytical speedup of the WPP solution represents the upper bound of its experimental performance. Let us consider x the number of CTB columns, y the number of CTB rows and d the delay in terms of CTB between two adjacent CTB rows required by the wavefront solution. The effective number of threads n used in the wavefront solution is given as follows:

n = min nb cpu threads, x d (1)
where d ∈ N + and nb cpu threads is the number of threads selected to decode the video sequence. The analytical speedup γ is derived as follows:

γ =    xy xy n +d(n-1) , if α = 0 xy x⌈ y n ⌉+d(α-1) , if α = 0 (2)
where x, y, n ∈ N + , and α = y mod n.

The speedup of the WPP solution is equal to the number of CTBs of the frame (xy) divided by the number of CTBs decoded by each thread plus the additional delay required by the wavefront approach. When the number of CTB rows is multiple of the number of decoding threads, the delay of the wavefront solution at the decoding of the last CTBs is equal to d(n -1). However, when the number of CTB rows is not multiple of the number of decoding threads, the delay at the end of the frame is equal to d(α -1). Figure 3 shows the analytical speedup of the WPP solution versus the number of threads for different video resolutions. We can notice that the WPP performance decreases for a large number of threads, where the additional delay considerably increases. Equation (2) does not consider the inactive threads waiting at the start and the end of decoding each frame. The waiting time of the inactive threads in terms of CTBs is computed as follows:

σ = d(n 2 -n), if α = 0 d/2(n 2 -n + α 2 -α) + bx -d/2(b 2 + b), if α = 0 (3)

REAL TIME AND PARALLEL SHVC DECODER

We first implemented the SHVC decoder under the Open-HEVC software. The SHVC decoder consists of L instances of the OpenHEVC decoder, one instance for each layer, with L the number of layers. Each HEVC decoder l (l = 1, .., L) decodes the corresponding layer, and the l th EL decoder, with l = 2, ..., L, has access to the picture and the MVs decoded by the lower layer decoder (l -1). Moreover, the EL decoder adds to its Decoded Picture Buffer (DPB) a new reference picture corresponding to the picture of the same temporal representation in the lower layer decoder. The inter-layer predictions are performed at the prediction unit level. Thus, the EL decoder copies the PU and the corresponding MVs from the lower layer decoder into its new reference picture. In the case of spatial scalability, the PU from lower decoder is first upsampled and its MVs upscaled before being copied into the inter-layer reference picture. Therefore, only the PUs used for inter-layer predictions are copied into the inter-layer reference picture, and upsampled in the case of spatial scalability. The OpenHEVC decoder performing the decoding of each SHVC layer was extended to support the high level parallel processing solutions, including the wavefront solution. Therefore, each layer can be decoded in parallel with the wavefront approach to improve both the decoding frame rate and the frame latency. To overcome with the wavefront solution limitations and increase the parallelization efficiency, a second level of parallelism (frame-based) is introduced to the SHVC decoder. The idea behind this hybrid approach is to decode several spatial and temporal frames in parallel (frame-based solution) and decode each frame in wavefront associated with a low number of threads. This enables to take (2, 2) with n the number of threads for the wavefront solution and m the number of threads decoding different frames at each layer advantage of the wavefront approach at its near optimal configuration (ie. number of threads is below 4, see Figure 3). Moreover, the inactive threads waiting for both WPP and motion compensation dependencies can be used to decode other frames waiting for available threads. Figure 4 illustrates the hybrid parallelism approach in the SHVC decoder decoding two spatial scalability layers (L = 2). Indeed, several spatial and temporal frames are decoded in parallel under the restriction that the motion compensation dependencies are satisfied.

The BL and the EL frames of the same temporal representation are simultaneously processed, which enhances both decoding frame rate and the SHVC frame latency. Since the inter-layer prediction is performed at the PU level, the BL and the EL frame can be simultaneously decoded with a control process to ensure that the PU used for inter-layer prediction is decoded at the BL decoder. The same communication process is used to decode two frames belonging to the same quality layer and different temporal representation to increase only the frame rate. This hybrid parallel processing solution combining the wavefront and the frame-based solutions in the SHVC decoder takes advantage of both solutions to improve the parallelism efficiency and reduce the decoding latency.

RESULTS AND ANALYSIS

Experimental configuration

The system and software configurations used to carry out the experiments are summarized in Table 1. We consider all video sequences of the SHVC common test conditions. [START_REF]SHVC Reference Software[END_REF] in two layers (L = 2) and two spatial scalability configurations: ×2 and ×1.5. The SHVC video sequences were coded in low delay coding configuration with enabling the wavefront feature where the delay between two adjacent CTB rows was set to 2 CTBs (ie. d = 2). The quantization parameter (QP) of the BL was set to 27 and 32, while the QP of the EL is equal to the BL QP minus 2. We consider n the number of decoding threads used for the wavefront solution, and m the number of thread used for the frame-based parallelism at each layer. To assess the performance of the hybrid parallel processing solution, we compare the performance of three decoding configurations: (n, m) ∈ {(6, 1), (1, 3), (2, 2)}. The SHVC decoder with the first configuration uses 6 concurrent threads for the wavefront parallelism. The second configuration decodes 3 BL and 3 EL frames in parallel. The third configuration enables the hybrid parallelism with 2 BL and 2 EL frames in parallel, and each frame uses 2 concurrent threads for the wavefront solution.

Results and discussions

Table 2 shows the bitrate performance of the SHVC encoder compared to a simulcast coding configuration for different video resolutions. The simulcast coding configuration consists in encoding the BL and the EL with two independent HEVC encoders. Therefore, the inter-layer prediction used in the SHVC standard enables in average a biterate gain up to 40% for 1080p video resolution and x1.5 spatial scalability. Figure 5 illustrates the speedup of the wavefront implementation in the proposed SHVC decoder. The wavefront implementation achieves a speedup near to the upper bound of the wavefront solution computed in equation ( 2), especially when the number of decoding threads is bellow 5. With using 6 threads, the performance of the proposed implementation slightly decreases to reach a speedup of 4.5 for 2160p video resolution, instead of the upper bound value of 5.5. This is because we use the maximum number of CPU cores. The decoder latency is assessed by the time required to decode one SHVC video frame. The wavefront solution performs the lowest latency with a decoding time per frame around 30 ms. In the wavefront mode, 6 concurrent threads are used to decode the CTU rows of the frame which enables a coarse level of granularity. The hybrid decoding configuration performs lower latency then the frame based configuration thanks to the two threads used for the wavefront decoding. In terms of memory usage, the wavefront configuration requires the minimum memory since only a copy of the local memory is allocated by thread. However, the frame-based parallelism allocates a new decoder for each thread, except the DPB memory which is shared between all threads decoding the same quality layer.

CONCLUSION

We investigated in this paper a hybrid parallel processing solution for a real time SHVC decoder. The hybrid parallelism combines the WPP solution with an extension of the framebased parallelism. Experimental results showed that the proposed solution performs near optimal speedup with a good trade-off between decoding time, latency and memory usage.

The SHVC decoder achieves on a 6 cores Xeon processor running at 3.2 Ghz the decoding of 1600p video resolution at 60 fps. The first end-to-end video demonstration using the proposed real time SHVC decoder within the GPAC player was presented in the 106 th MPEG meeting in Geneva [START_REF] Hamidouche | A scalable HEVC demonstration within GPAC player[END_REF].

Fig. 1 .

 1 Fig. 1. Principale of the wavefront solution

Fig. 2 .

 2 Fig. 2. Blocks diagram of the OpenHEVC decoder

Fig. 3 .

 3 Fig. 3. Analytical speedup of the WPP solution (CTB size = 64 and d = 2)

Fig. 4 .

 4 Fig. 4. Principle of the hybrid parallelism solution in the SHVC decoder: x2 spatial scalability, L = 2 and (n, m) = (2, 2) with n the number of threads for the wavefront solution and m the number of threads decoding different frames at each layer

Fig. 5 .

 5 Fig. 5. Speedup performance of the WPP solution in the SHVC decoder (BL QP =27)

  The delay in terms of CTU, noted d, required by the wavefront solution between two adjacent CTU rows is managed by an integer type array shared by all threads. The i th value of the array is used to count the number of decoded CTUs within the i th CTU row. Thus, the hls decode row function increments the related array value for each decoded CTU and decodes a new CTU only if the d next CTUs of the previous CTU row are decoded. The WPP extension requires an extra memory allocation. Each thread holds a copy of the local memory required to store informations of the CTU being decoded. Moreover, the memory of one CABAC context is allocated for each thread, and one extra CABAC context is required to save the context of the previous CTB row. Thus, if n threads are used for the decoding with the WPP solution, the memory of n copies of the local memory and (n + 1)

Table 1 .

 1 To show the decoder performance for larger video resolution, we added to the test sequences two 3840 × 2160 video sequences from the Configuration of the experiments STV High Definition Multi Format Test Set. All test video sequences were encoded with the SHVC reference software encoder

	System		Software
	Processor	Intel Xeon Compiler	GCC-4.6
		E5-1650	OS	Ubuntu 12.04
	ISA	X86-64	Kernel	3.5.0-34
	Clock frequency 3.2 GHz	OpenHEVC cff4b48a94
	Level 3 cache	12 MB	release	(based on HM11.0)
	Cores	6

Table 3

 3

	Configurations	BL + EL	BL+EL	Gain
	Resolution ratio (SHVC) (Simulcast) (%)
	1080p	×2	6401	1303	36
		×1.5	6432	11050	41
	1600p	×2	11950	17501	31
	2160p	×2	87052	135716	35

illustrates the performance of the three considered decoding configurations in terms of speedup, decoding frame rate, decoding time per frame and memory usage. The hybrid parallel processing solution achieves the highest speedup of 4.8 and 5 for ×2 and ×1.5 scalable configurations, respec-

Table 2 .

 2 Bit rate performance (Kbps) of the SHVC standard compared with a simulcast coding configuration (All QP) tively. The speedup of the wavefront parallelism ((n, m) = (6, 1)) is decreased by the wavefront limitations, especially for small video resolutions. The high speedup performance of the hybrid parallel processing solution considerably increases the decoding frame rate, which is in average around 70 frames per second (fps), instead of 48 fps and 40 fps for the wavefront and the frame-based parallelism configurations, respectively. The decoding frame rate performance of a simulcast configuration (only one HEVC decoder) is highlighted in bold font. The single layer HEVC decoder is almost two times faster then the SHVC decoder. In simulcast configuration, only the EL is decoded without the extra complexity of the SHVC decoder related to the upsampling and upscaling processes.

Table 3 .

 3 Performance of the SHVC decoder in different decoding configurations (All test video sequences and the DPB memory is not considered)

	Configurations	Decoding configurations
			(6, 1)	(1, 3)	(2, 2)
	Speedup	×2	3.33	2.95	4.8
		×1.5	3.6	2.75	5
	Decoding frame ×2	48	44	70
	rate (fps)	×1.5	48	40	69
		HEVC	99	74	116
	Decoding time ×2	32	187	90
	per frame (ms) ×1.5	29	169	78
	Memory usage ×2	16881 44193 30322
	(Ko)	×1.5	20340 54570 37240