Mathieu Claeys
email: mathieu.claeys@gmail.com

Jamal Daafouz
email: jamal.daafouz@univ-lorraine.fr

Didier Henrion
email: henrion@laas.fr

Modal occupation measures and LMI relaxations for nonlinear switched systems control *

This paper presents a linear programming approach for the optimal control of nonlinear switched systems where the control is the switching sequence. This is done by introducing modal occupation measures, which allow to relax the problem as a primal linear programming (LP) problem. Its dual linear program of Hamilton-Jacobi-Bellman inequalities is also characterized. The LPs are then solved numerically with a converging hierarchy of primal-dual moment-sum-of-squares (SOS) linear matrix inequalities (LMI). Because of the special structure of switched systems, we obtain a much more efficient method than could be achieved by applying standard moment/SOS LMI hierarchies for general optimal control problems.

Introduction

A switched system is a particular class of a hybrid system that consists of a set of dynamical subsystems, one of which is active at any instant of time, and a policy for activating and deactivating the subsystems. These dynamical systems are encountered in a wide variety of application domains such as automotive industry, power systems, aircraft and traffic control, and more generally the area of embedded systems. Switched systems have been the concern of much research, and many results are available for stability analysis and control design. They make evident the importance of orchestrating the subsystems through an adequate switching strategy, in order to impose global stability and/or performance. Interested readers may refer to the survey papers [START_REF] Decarlo | Perspectives and results on the stability and stabilizability of hybrid systems[END_REF][START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF][START_REF] Shorten | Stability criteria for switched and hybrid systems[END_REF][START_REF] Lin | Stability and stabilizability of switched linear systems: A survey of recent results[END_REF] and the books [START_REF] Liberzon | Switching in systems and control[END_REF][START_REF] Sun | Switched linear systems: control and design[END_REF] and the references therein.

In this context, these systems are generally controlled by intrinsically discontinuous control signals, whose switching rule must be carefully designed to guarantee stability and performance properties. As far as optimality is concerned, several results are available in two main different contexts.

The first category of methods exploits necessary optimality conditions, in the form of Pontryagin's maximum principle (the so-called indirect approaches), or through a large nonlinear discretization of the problem (the so-called direct approaches). The first contributions can be found in [START_REF] Branicky | A unified framework for hybrid control: model and optimal control theory[END_REF][START_REF] Hedlund | Optimal control of hybrid systems[END_REF][START_REF] Piccoli | Hybrid systems and optimal control[END_REF] where the problem has been formulated and partial solutions provided through generalized Hamilton-Jacobi-Bellman (HJB) equations or inequalities and convex optimization. In [START_REF] Riedinger | An optimal control approach for hybrid systems[END_REF][START_REF] Sussmann | A maximum principle for hybrid optimal control problems[END_REF][START_REF] Shaikh | On the hybrid optimal control problem: theory and algorithms[END_REF], the maximum principle is generalized to the case of general hybrid systems with nonlinear dynamics. The case of switched systems is discussed in [START_REF] Bengea | Optimal control of switching systems[END_REF][START_REF] Seatzu | Optimal control of continuous-time switched affine systems[END_REF][START_REF] Axelsson | Gradient descent approach to optimal mode scheduling in hybrid dynamical systems[END_REF]. For general nonlinear problems and hence for switched systems, only local optimality can be guaranteed , even when discretization can be properly controlled [START_REF] Xu | Results and perspectives on computational methods for optimal control of switched systems[END_REF]. The subject is still largely open and we are far from a complete and numericaly tractable solution to the switched optimal control problem.

The second category collects extensions of the performance indices H 2 and H ∞ originally developed for linear time invariant systems without switching, and use the flexibility of Lyapunov's approach, see for instance [START_REF] Geromel | Dynamic output feedback control of switched linear systems[END_REF][START_REF] Deaecto | Dynamic output feedback H ∞ control of switched linear systems[END_REF] and references therein. Even for linear switched systems, the proposed results are based on nonconvex optimization problems (e.g., bilinear matrix inequality conditions) difficult to solve directly. Sufficient convex Linear Matrix Inequality (LMI) design conditions may be obtained, yielding computed solutions which are suboptimal, but at the price of introducing a conservatism (pessimism) and a gap to optimality which is hard, if not impossible, to evaluate. Since the computation of this optimal strategy is a difficult task, a suboptimal solution is of interest only when it is proved to be consistent, meaning that it imposes to the switched system a performance not worse than the one produced by each isolated subsystem [START_REF] Geromel | Suboptimal switching control consistency analysis for switched linear systems[END_REF].

Despite the interest of these existing approaches, the optimal control problem is not globally solved for switched systems, and new strategies are more than welcome, as computationally viable design techniques are missing. The present paper aims at complementing this rich literature on switched systems with convex programming techniques from the optimal control literature. Indeed, it is a well-known fact [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF][START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF] that optimal control problems can be relaxed as linear programming (LP) problems over measure spaces. Despite some early numerical results [START_REF] Rubio | Control and Optimization: the linear treatment of nonlinear problems[END_REF], this approach was merely of theoretic interest, before the advent of tractable primal-dual moment-sum-of-squares (SOS) LMI hierarchies, also now called Lasserre hierarchies, see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] for an introduction to the subject. Most notably, [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] explores in depth the application of such a numerical method for general polynomial optimal control problems, where the control is bounded. By modeling control and trajectory functions as occupation measures, one obtains a convex LP formulation of the optimal control problem. This infinite-dimensional LP can be solved numerically and approximately with a hierarchy of convex finite-dimensional LMIs.

In this paper, we consider the problem of designing optimal switching rules in the case of polynomial switched dynamical systems. Classically, we formulate the optimal control switching problem as an optimal control problem with artificial controls being functions of time, each valued in the discrete set {0, 1}, and we relax it into a control problem with such controls now valued in the interval [0, 1]. In contrast with existing approaches following this relaxation strategy, see, e.g., [START_REF] Bengea | Optimal control of switching systems[END_REF][START_REF] Riedinger | Time optimal control of hybrid systems[END_REF], relying on the local Pontryagin maximum principle, our aim is to apply the global approach of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF]. We show that by specializing the convex objects for switched systems, one obtains a numerical method for which the number of modes driving the system enters linearly into the complexity of the problem, instead of exponentially. On the one hand, our approach follows the optimal control modeling framework. On the other hand, it exploits the flexibility and computational efficiency of the convex LMI framework. In contrast with most of the existing work on LMI methods, we have a guarantee of global optimality, in the sense that we obtain an asympotically converging (i.e., with vanishing conservatism) hierarchy of lower bounds on the achievable performance.

Organization of the paper

The paper is organized as follows. §2 constructs the generalized moment problem associated to the optimal control of switched systems, and details some conic duality results. Theses results are used in §3 to obtain an efficient numerical method based on the moment/SOS LMI hierarchy. §4 then outlines a simple method to extract candidate optimal trajectories from moment data. §5 gathers several useful extensions to the problem, kept separate from the main body of the article so as to ease exposition and notations. Finally, §6 illustrates the method with several examples.

Contributions

The contributions of this paper are as follows. On a theoretical level, a novel way of relaxing optimal control problems of switched systems is proposed, following [START_REF] Henrion | Optimal switching control design for polynomial systems: an LMI approach[END_REF]. The equivalence of this convex program with existing results in the literature [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF][START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF] is now rigorously proven. In addition, a full characterization of the dual conic problem as a system of relaxed HJB inequalities is given.

On a practical level, we present an easy to implement numerical method to solve the control problem, based on the LMI relaxations for optimal control [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF]. The specialized measure LP formulation allows for substantial computational gains over generic formulations, which we now characterize. To our knowledge, this is one of the few results, along with [START_REF] Claeys | Measures and LMIs for Impulsive Nonlinear Optimal Control[END_REF] and [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF], exploiting problem structure for more efficient LMI relaxations of control problems.

Preliminaries

Let M(X) denote the vector space of finite, signed, Borel measures supported on an Euclidean subset X ⊂ R n , equipped with the weak- * topology, see, e.g., [START_REF] Royden | Real analysis[END_REF] for background material. Let M + (X) denote the cone of non-negative measures in M(X). The support of µ ∈ M + (X), the closed set of all points x such that µ(A) > 0 for every open neighborhood A of x, is denoted by spt µ. For µ ∈ M(X), spt µ is the union of the supports of the Jordan decomposition of µ. For a continuous function f ∈ C(X), we denote by X f (x) µ(dx) the integral of f w.r.t. the measure µ ∈ M(X). When no confusion may arise, we note f, µ = f µ for the integral to simplify exposition and to insist on the duality relationship between C(X) and M(X). The Dirac measure supported at x * , denoted by δ x * , is the measure for which f, δ x * = f (x * ) for all f ∈ C(X). The indicator function of set A, denoted by I A (x), is equal to one if x ∈ A, and zero otherwise. The space of probability measures on X, viz., the subset of M + (X) with mass 1, µ = 1, is denoted by P(X).

For multi-index α ∈ N n , N being the set of natural numbers, and vector x ∈ R n , we use the notation x α := n i=1 x α i i . We denote by N n m the set of vectors α ∈ N n such that

n i=1 α i ≤ m. The moment of multi-index α ∈ N n of measure µ ∈ M + (X) is then defined as the real y α = x α , µ .
A multi-indexed sequence of reals (y α ) α∈N n is said to have a representing measure on X if there exists µ ∈ M + (X) such that y α = x α , µ for all α ∈ N n .

Let R[x] denote the ring of polynomials in the variables x ∈ R n , and let deg p denote the (total) degree of polynomial p.

A subset X of R n is basic semi-algebraic if it is defined as the intersection of finitely many polynomial inequalities, namely

X = {x ∈ R n : g i (x) ≥ 0, i = 1 . . . n X } with g i (x) ∈ R[x], i = 1 . . . n X .

Weak linear program 2.1 Problem statement

Consider the optimal control problem inf

σ T 0 l σ(t) (t, x(t)) dt s.t. ẋ(t) = f σ(t) (t, x(t)), x(0) = x 0 , x(T ) = x T , (t, x(t)) ∈ [0, T ] × X, σ(t) ∈ {1, 2, . . . , m}, (1)
where the infimum is over the sequence σ. The state x is a vector of n elements and the control consists of choosing, for almost all times, which of the m possible dynamics drives the system. Throughout this section, the following assumptions hold:

Assumption 1 Terminal time T , initial state x 0 and terminal state x T are given. State constraint set X is given and compact. Let K := [0, T ] × X. Functions f j : K → R n (dynamics), and l j : K → R, j = 1, . . . , m (Lagrangians) are given, continuous in all their variables, and Lipschitz continuous with respect to the state variable.

The integrand in the cost is called a Lagrangian, following the standard optimal control terminology, see e.g., [START_REF] Clarke | Functional analysis, calculus of variations and optimal control[END_REF]. Note that the above assumptions can be significantly weakened. For instance, mere measurability of the dynamics w.r.t. time, lower semi-continuity of the Lagrangian or unbounded state spaces when the Lagrangian is coercive are often considered in the calculus of variation literature. However, as §3 explores in depth, the question of the numerical representation of problem data is essential for rigorous global optimization. Up to our knowledge, only polynomials can offer such guarantees, and Assumption 1 is general enough to cover such an essential case.

Obviously, optimal control problem (1) can be equivalently written as

inf u T 0 m j=1 l j (t, x(t)) u j (t) dt s.t. ẋ = m j=1 f j (t, x(t)) u j (t) x(0) = x 0 , x(T ) = x T , (t, x(t)) ∈ K, u(t) ∈ U (2)
where the infimum is with respect to a time-varying vector u(t) which belongs for all t ∈ [0, T ] to the (nonconvex) discrete set U := {(1, 0, . . . , 0), (0, 1, . . . , 0), . . . , (0, 0, . . . ,

1)} ⊂ R m . (3)
The next sections explore the various ways this problem can be lifted/relaxed as a linear program over so-called occupation measures.

Remark 1 Section 5 gathers several extensions to problem (1) for which the present approach is applicable mutatis mutandis. This section is relegated at the end of the paper for ease of exposition.

Occupation measures

Simple examples (see for instance at the end of the paper) show that when measurable functions of time are considered for controls such as in (2), optimal solutions might not exist. This section summarizes several well-known concepts to regain compactness in the control. These tools will then be specialized in the next section for switched systems.

Definition 1 (Young measure) A Young measure is a time-parametrized family of probability measures ω(du|t) ∈ P(U) defined almost everywhere, such that for all continuous functions 1 v ∈ C(U), the function t → v, ω is Lebesgue measurable.

Young measures are also called generalized controls or relaxed controls, see for instance [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF]Part III]. Note that classical controls u(t), functions of time with values in U, are 1 Considering measures as a subset of distributions, those may be referred to as test functions a particular case of Young measures for the choice ω(du|t) = δ u(t) (du). Following the terminology of [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF], it is natural to relax (2) into the following "strong form"2 :

p * S = inf ω T 0 m j=1 l j (t, x(t))u j (t) dt s.t. ẋ = m j=1 f j (t, x(t))u j , ω(du|t) x(0) = x 0 , x(T ) = x T , (t, x(t)) ∈ K (4)
where the infimum is w.r.t. a Young measure ω(du|t) ∈ P(U). Note that there might be a strict relaxation gap, viz., p * S is strictly less than the infimum in problem (1), for ill-posed instances. It is not the purpose of this article to explore such a non-generic case, and we refer to the discussion in, e.g., [24, App. C] and the references therein on such occurrences. There are sufficient conditions guaranteeing the absence of such a gap, referred to as inward-pointing conditions, see for instance [START_REF] Frankowska | Filippov's and Filippov-Wazewski's Theorems on Closed Domains[END_REF].

An equivalent way of relaxing ( 2) is to relax the controls to belong, for all t ∈ [0, T ], to the (convex) simplex

conv U = {u ∈ R m : m j=1 u j = 1, u j ≥ 0, j = 1, . . . , m}. (5)
In other words, problem (4) on Young measures is equivalent to replacing U with conv U in problem [START_REF] Axelsson | Gradient descent approach to optimal mode scheduling in hybrid dynamical systems[END_REF]. In [START_REF] Bengea | Optimal control of switching systems[END_REF], problem (4) is called the embedding of problem (1), and it is proved that the set of trajectories of problem (1) is dense (w.r.t. the uniform norm in the space of continuous functions of time) in the set of trajectories of embedded problem (4). Note however that these authors consider the more general problem of switching design in the presence of additional bounded controls in each individual dynamics. To cope with chattering effects due to the simultaneous presence of controls and (initial and terminal) state constraints, they have to introduce a further relaxation of the embedded control problem. In this paper, we do not have controls in the dynamics, and the only design parameter is the switching sequence.

Notice that once a Young measure ω(du|t) is given in problem (4), the corresponding state trajectory is uniquely determined by

x(t) = x 0 + t 0 m j=1 f j (s, x(s))u j , ω(du|s) ds
and hence the following definition makes sense.

Definition 2 (Relaxed arc) A pair (x, ω) which is feasible, or admissible, for problem (4) is called a relaxed arc.

For optimization, strong problem (4) presents an essential first step, as sequential-compactness is regained, guaranteeing the existence of optimal solutions under the sole existence of a relaxed arc [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF]Th. 1.2]. For global optimization though, the nonlinear dependence of (4) on trajectories x(t) is problematic, and an additional generalization of Young measures must be introduced, capturing both controls and trajectories:

Definition 3 (Occupation measure) Given a relaxed arc (x, ω), its corresponding occupation measure is defined by

µ(A × B × C) := A I B (x(t))ω(C|t) dt
for all Borel subsets A, B, C of [0, T ], X and U, resp.

That is, occupation measures assign to each set A × B × C the total time "spent" on it by a relaxed arc (x, ω). An alternative, equivalent definition could be dµ(t, x, u) = δ x(t) (dx)ω(du|t)dt.

By construction, an occupation measure satisfies

v, µ = T 0 U v(t, x(t), u)ω(du|t) dt (6)
for all continuous test functions v ∈ C([0, T ]×X ×U). Indeed, by the Riesz representation theorem (see, e.g., [39, §21.5]), an occupation measure could alternatively be defined as the unique measure satisfying (6) for all continuous test functions (recall the hypothesis of compact supports).

Evaluating now a continuously differentiable test function along a trajectory and making use of ( 6) reveals the following lemma:

Lemma 1 Given a relaxed arc (x, ω), its corresponding occupation measure satisfies the following linear constraints for any test function

v ∈ C 1 (R × R n ): ∂v ∂t + ∂v ∂x • m j=1 f j u j , µ = v(T, x T ) -v(0, x 0 ). (7)
Note the use of a scalar product, denoted by a dot, between the gradient vector ∂v ∂x and the controlled dynamics. In [START_REF] Rubio | Control and Optimization: the linear treatment of nonlinear problems[END_REF], it is proposed then to relax strong problem (4) by optimizing over all Borel measures satisfying (7) instead of simply occupation measures, yielding the following "weak" problem:

p * W = inf µ m j=1 l j (t, x(t))u j (t), µ s.t. ∀v ∈ C 1 (K) : v(T, x T ) -v(0, x 0 ) = ∂v ∂t + ∂v ∂x • m j=1 f j u j , µ µ ∈ M + (K × U). (8)
Weak problem ( 8) is rigorously justified by the following essential result:

Theorem 1 There is no relaxation gap between optimal control problem (4) and measure LP (8), viz.,

p * S = p * W .
Proof: This result is not new, so its proof is only sketched. Obviously, direction p * S ≥ p * W is a simple consequence of Lemma 1 and the continuity of the cost. The other direction, more involved, is the core of [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF] and especially [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF]Theorem 2.3]. Synthetically, the authors use specialized Hahn-Banach type separation arguments to show that the admissible set for weak problem ( 8) is the closure of the convex hull of the set of occupation measures of the admissible solutions of (4). That is, one could interpret those results as a Krein-Milman theorem for optimal control problems, see e.g. [START_REF] Royden | Real analysis[END_REF]Chapter 14] for background on the Krein-Milman theorem.

Note that the use of relaxations and LP formulations of optimal control problems (on ordinary differential equations and partial differential equations) is classical, and can be traced back to the work by L. C. Young, Filippov, as well as Warga and Gamkrelidze, amongst many others. For more details and a historical survey, see, e.g., [18, Part III].

Modal occupation measures and primal LP

Occupation measures defined in §2.2 are supported on a subset of Euclidean space of dimension n + m + 1. As such, they prove to be challenging for practical numerical resolution when the size of the problem increases, a phenomenon known colloquially in the (dual) dynamic programming literature as the "curse of dimensionality".

For instance, the numerical approach of [START_REF] Rubio | Control and Optimization: the linear treatment of nonlinear problems[END_REF] proposes to consider a finite subset of the countably many linear constraints on µ given by [START_REF] Bonnard | Geometric and numerical methods in the contrast imaging problem in nuclear magnetic resonance[END_REF]. Then, as a consequence of Tchakaloff's theorem [29, Th. B.12], there exists an atomic measure with support included in the support of µ, and satisfying the truncated linear constraints exactly. By gridding the support of µ with Dirac measures of unknown masses, one can then approach weakly- * this atomic measure as the spatial resolution of the grid gets finer. This results in a finite-dimensional LP to solve, with a number O (1/∆ n+m+1 ) of unknowns, with ∆ the grid resolution. Therefore, for a fixed resolution, the size of the LP grows exponentially in the size of the state and control spaces.

Other examples suffering a similar fate are LMI relaxations as presented later on in §3, which the authors prefer over LP approximations for their greater rigor -most noticeably the guarantee of obtaining lower bounds and their better convergence properties, see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Section 5.4.2]. Indeed, as shown in §3.4, for a given relaxation order, the size of the semidefinite blocks in the LMIs also grows exponentially with the dimension of the underlying space.

For finite-dimensional optimization problems, structural properties of the problem can be exploited to define equivalent LPs using more measures, but of smaller dimensions, see [START_REF] Lasserre | Convergent SDP-relaxations in polynomial optimization with sparsity[END_REF]. This allows for much faster numerical resolution. Motivated by these savings, we now introduce specialized occupation measures to satisfy much the same goal for the optimal control of switched systems:

Definition 4 (Modal occupation measures) The j-th modal occupation measure µ j (dt, dx) ∈ M + (K) associated with occupation measure µ as in Def. 3, is defined as

µ j (A × B) := A B U u j dµ(t, x, u),
for all Borel subsets A, B of [0, T ], X, resp.

In words, modal occupation measures are the projections on K = [0, T ] × X of the first moments of the occupation measure defined in §2.2 w.r.t. the controls. For each Borel subset of K, each modal occupation measure therefore specifies the time spent by the pair (t, x(t)) on each mode. As a consequence, Def. 4 implies the following specialization of Lem. 1 for switched systems:

Corollary 1 Given a relaxed arc (x, ω), its corresponding modal occupation measures satisfy the following linear constraints:

m j=1 ∂v ∂t + ∂v ∂x • f j , µ j = v(T, x T ) -v(0, x 0 ) (9)
for all test functions v ∈ C 1 (K).

Proof: Notice that by definition of U, the occupation measure satisfies

∂v ∂t , µ = ∂v ∂t • m j=1 u j , µ .
The corollary is then the immediate application of Def. 4 and Fubini's theorem.

Corollary 1 naturally points to the following alternative weak problem for switched systems:

p * = inf (µ 1 ,...,µm) m j=1 l j , µ j s.t. ∀v ∈ C 1 (K) : v(T, x T ) -v(0, x 0 ) = m j=1 ∂v ∂t + ∂v ∂x f j , µ j µ j ∈ M + (K), j = 1, . . . , m (10)
where the minimization is w.r.t. the vector of modal occupation measures (µ 1 , . . . , µ m ).

This is rigorously justified by the following:

Theorem 2 There is no relaxation gap between measure LP (8) and measure LP (10), viz.,

p * = p * W Proof: We first show p * ≤ p * W .
Consider an admissible measure µ for [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF]. Then, by Cor. 1, there exists an admissible vector (µ 1 , . . . µ m ) satisfying [START_REF] Bressan | Introduction to the mathematical theory of control[END_REF]. As the cost can be treated in an analogous fashion, this shows that any admissible solution for [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] is also admissible for [START_REF] Branicky | A unified framework for hybrid control: model and optimal control theory[END_REF] with the same cost, hence p * ≤ p * W . For the reverse inequality, consider now a vector (µ 1 , . . . , µ m ) admissible for [START_REF] Branicky | A unified framework for hybrid control: model and optimal control theory[END_REF], and define

μ := m j=1 µ j . (11)
By construction, each µ j is absolutely continuous with respect to μ, such that by the Radon-Nikodým Theorem [39, §18.4], there exists a non-negative, measurable function ūj (t, x) such that µ j = ūj μ. Injecting this back in [START_REF] Cassandras | Optimal control of a class of hybrid systems[END_REF] shows that, in addition, m j=1 ūj = 1, μ-almost everywhere. Define now µ ∈ M + (K × U), with U as in [START_REF] Barvinok | A Course in Convexity[END_REF], such that

dµ(t, x, u) := m j=1 ūj (t, x)δ 1 (du j |t, x) dμ(t, x), such that by definition U u j dµ(t, x, u) = ūj (t, x) dμ(t, x),
where the last two equations are understood in a weak sense. Working out the weak dynamics of (10) leads then to:

m j=1 ∂v ∂t + ∂v ∂x • f j , µ j = m j=1 ∂v ∂t + ∂v ∂x • f j ūj , μ = ∂v ∂t + m j=1 ∂v ∂x • f j ūj , μ (12)
= ∂v ∂t + m j=1 ∂v ∂x • f j u j , µ .
As the cost can be treated in a similar manner, this concludes p * ≥ p * W , hence the proof.

Theorem (2) fulfills the objective laid at the beginning of this section. Indeed structured LP [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] involves m modal occupation measures supported on spaces of dimension n + 1, instead of a single occupation measure on a space of dimension n+m+1 as in unstructured LP (8).

HJB inequalities and dual LP

Before investigating the practical implications on LMI relaxations of structured measure LP [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF], we explore its conic dual. This is an interesting result in its own right for socalled "verification theorems" which supply necessary and sufficient conditions in the form of more traditional HJB inequalities. In addition, practical numerical resolution of the LMI relaxations by primal/dual interior-point methods [START_REF] Mosek Aps | The MOSEK optimization software[END_REF] implies that a strengthening of this dual will be solved as well, as shown later on in §3.3.

In this section, it is first shown that the solution of ( 10) is attained whenever an admissible solution exists. Then, the dual problem of [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF], in the sense of conic duality, is presented. This leads directly to a system of subsolutions of HJB equations. Although, the cost of this problem might not be attained, it is however shown that there is no duality gap between the conic programs.

First of all, we establish that whenever the optimal cost of ( 10) is finite, there exists a vector of measures attaining the value of the problem:

Lemma 2 If p * is finite in problem [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF], there exists an admissible (µ * 1 , . . . , µ * m ) attaining the infimum, viz., such that m j=1 l j , µ * j = p * .

Proof: We first show that the mass of each measure is bounded. This is true for each µ j , since test function v(t, x) = t imposes m j=1 1, µ j = T . Then, following Alaoglu's theorem [39, §15.1], the unit ball in the vector space of compactly supported measures is compact in the weak- * topology. Therefore, any sequence of admissible solutions for [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] possesses a converging subsequence. Since this must be true for any sequence, this is true for any minimizing sequence, which concludes the proof. Now, remark that (10) can be seen as an instance of a conic program, called hereafter the primal, in standard form (see for instance [START_REF] Barvinok | A Course in Convexity[END_REF]):

p * = inf zp z p , c p s.t. A z p = b, x p ∈ E + p ( 13
)
where

• decision variable z p := (µ 1 , . . . , µ m ) belongs to vector space E p := M(K) m equipped with the weak- * topology;

• the cost c := (l 1 , . . . , l m ) belongs to vector space F p := C(K) m equipped with the strong topology;

• •, • p : E p × F p → R
is the duality bracket given by the integration of continuous functions with respect to Borel measures, since E p = F ′ p , with the prime denoting the topological dual;

• the cone E + p is the non-negative orthant of E p ; • the linear operator A :

E p → C 1 (K) ′ is given by z p → Az p = m j=1 L j µ j where L j is the adjoint operator of L ′ j : C 1 (K) → C(K) defined by v → L ′ j v := ∂v ∂t + ∂v ∂x • f j ;
• right hand side b := δ (T,x T ) (dt, dx) -δ (0,x 0 ) (dt, dx) belongs to vector space

E d := C 1 (K) ′ .
Lemma 3 The conic dual of LP problem (10) is given by

d * = sup v v(T, x T ) -v(0, x 0 ) s.t. l j -L ′ j v ≥ 0, ∀ (t, x) ∈ K, j = 1 . . . m, v ∈ C 1 (K). ( 14
)
Proof: Following standard results of conic duality (see [START_REF] Anderson | Linear programming in infinite-dimensional spaces: theory and applications[END_REF] or [START_REF] Barvinok | A Course in Convexity[END_REF]), the conic dual of ( 13) is given by

d * = sup z d b, z d d s.t. c -A ′ z d ∈ C + (K) m , z d ∈ F d (15)
where

• decision variable z d := v belongs to vector space F d := C 1 (K);

• the (pre-)dual cone is

C + (K) m , i.e., E + p is dual to C + (K) m ; • •, • d : E d × F d → R
is the appropriate duality pairing between E d and F d .

The lemma just details this dual problem.

Once the duality relationship established, the question arises of whether a duality gap occur between linear problems [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] and [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF]. The following theorem discards such a possibility:

Theorem 3 There is no duality gap between primal LP (10) and dual LP (14): if there is an admissible vector for (10), then

p * = d * .
Proof: One can show, following [1, Th. To prove closure, one may show that, for any sequence of admissible solutions (z

(n)
p ) n∈N , all accumulation points of ( z

(n) p , c p , A z (n) p ) n∈N belong to R. Note that Lemma 2 establishes that any sequence (z (n)
p ) n∈N has a converging subsequence. Therefore, all that is left to show is the weak- * continuity of A, hence of each L j . Following [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], this can be shown by noticing that each L ′ j is continuous for the strong topology of C 1 (K), hence for its associated weak topologies. Operators L ′ j , hence A, are therefore weakly- * continuous, and each sequence ( x

(n) p , c p , Ax (n) p ) n∈N converges in R, which concludes the proof.
Note that what is not asserted in Th. 3 is the existence of a continuous function for which the optimal cost is attained in dual problem [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF]. Indeed, it is a well-known fact that value functions of optimal control problems, to which v is closely related, may not be continuous, let alone continuously differentiable. However, there does exist an admissible vector of measures for which the optimal cost of primal [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] is attained (whenever there exists an admissible solution), following Lemma 2. This gives practical motivations for working in a purely primal approach on measures, as the dual problem will be solved anyway as a side product, see in the later sections of this article.

We close this section by detailing how dual problem [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF] can nonetheless be used analytically as a "verification theorem", following the discussion of [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF] for the unstructured case, that is following the dual of (10) instead.

Denote by τ j the time subset for which the j-th mode is "active":

τ j := sptπ t µ j , (16)
where π t µ j is the projection, or marginal of µ j on the time axis, viz., the unique measure such that

v(t), π t µ j = K v(t) dµ j (t, x)
for all continuous test functions v and j = 1, . . . , m. If an admissible control u(t) is piecewise-continuous, then obviously τ j := T 0 I {e j } (u(t)) dt, where e j is the j-th unit vector of R m . Note however that the intersection of several of the τ j might be of positive Lebesgue measure. In this case, relaxed controls can only be weakly approximated by fast oscillating sequences of classical controls. In the language of differential inclusions, this consists of realizing a control in the convexified vector field but not belonging to the original vector field.

Corollary 2 Let (x, ω) be a relaxed arc, and let the intervals τ j be computed as in [START_REF] Deaecto | Dynamic output feedback H ∞ control of switched linear systems[END_REF] from their occupation measures. Then there exists a sequence (v n ) n∈N ∈ C 1 (K) admissible for [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF], such that

lim n→∞ τ j l j (t, x(t)) -L ′ j v n (t, x(t)) dt = 0, j = 1 . . . m,
if and only if (x, ω) is a globally optimal solution of optimal control problem (4).

Proof: This corollary explicits weak duality (via the complementarity condition z * p , c -A ′ z * d p = 0) if z * p and z * d are optimal for their respective problems, and exploits Lem. 2 guaranteeing the existence of an optimal z * p . The advantage of such specialized optimality certificates for switched systems over the general case is that the test needs only to be checked on a mode-by-mode basis. This is particularly true if mode-dependent constraints are introduced, see §5.2.

LMI relaxations

This section outlines the numerical method to solve [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] in practice, by means of primaldual moment-SOS LMI relaxations. This is done by restricting the problem data to be polynomial, so that occupation measures can be equivalently manipulated by their moments for the problem at hand, see §3.1. Then, this new infinite-dimensional problem is truncated so as to obtain in §3.2 a convex, finite-dimensional relaxation, with dual described in §3.3. Finally, §3.4 shows how the structural properties of (10) improves the computational load of each of these relaxations in comparison to unstructured relaxations, as could be derived from [START_REF] Branicky | A unified framework for hybrid control: model and optimal control theory[END_REF].

In the remainder of the paper, the standing Assumption 1 is therefore strengthened as follows:

Assumption 2 All functions are polynomial in their arguments:

l j , f j ∈ R[t, x], j = 1, . . . , m.
In addition, set K = [0, T ]×X is basic semi-algebraic, viz., it is defined as the conjunction of finitely many polynomial inequalities

K = {(t, x) ∈ R × R n : g i (t, x) ≥ 0, i = 1, . . . , n K } with g i ∈ R[t,
x], i = 1, . . . , n K . Let g 0 (t, x) denote the polynomial identically equal to one. In addition, it is assumed that one of the g i enforces a ball constraint on all variables, which is possible w.l.g. since K is assumed compact (see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Th. 2.15] for slightly weaker conditions).

Moment LP

Given a sequence y = (y α ) α∈N n , let L y : R[x] → R be the Riesz linear functional

f (x) = α f α x α ∈ R[x] → L y (f ) = α f α y α .
Define the localizing matrix of order d associated with sequence y and polynomial g(x) =

γ g γ x γ ∈ R[x] as the real symmetric matrix M d (g y) whose entry (α, β) reads [M d (g y)] α,β = L y g(x) x α+β (17) = γ g γ y α+β+γ , ∀α, β ∈ N n d . (18)
In the particular case that g(x) = 1, the localizing matrix is called the moment matrix.

The construction of the LMI associated with problem (10) can now be stated. Its decision variable is the aggregate sequence of moments y = (y 1 , y 2 , . . . , y m ) where each y j = (y j,β ) β∈N n+1 is the moment sequence of measure dµ j (t, x) for j = 1, 2, . . . , m, i.e.,

y j,β = v β (t, x), µ j (19)
for the particular choice of test function

v β (t, x) := t β 0 x β 1 1 x β 2 2 • • • x βn n , β ∈ N n+1 . (20)
As each term of the cost of ( 10) is polynomial by assumption, they can be rewritten as

m j=1 β∈N n+1 c j,β y j,β = m j=1 L y j (l j ).
That is, vector (c j,β ) β contains the coefficients of polynomials l j expressed in the monomial basis. Similarly, the weak dynamics constraints of (10) need only be satisfied for countably many polynomial test functions, since the measures are supported on compact subsets of R n+1 . Hence the weak dynamics defines a linear constraint between moments of the form

m j=1 β∈N n+1 a j,α,β y j,β = b α = v α (T, x T ) -v α (0, x 0 ) (21)
where coefficients a j,α,β can be deduced by identification from

β∈N n+1 a j,α,β y j,β = L y j (L ′ j v α ), α ∈ N n+1 . (22)
Finally, the only nonlinear constraints are the convex LMI constraints for measure representativeness, i.e., constraints on y such that [START_REF] Frankowska | Filippov's and Filippov-Wazewski's Theorems on Closed Domains[END_REF] holds for all j = 1, . . . , m and β ∈ N n+1 . Indeed, it follows from Putinar's theorem [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]Theorem 3.8] that the sequence of moments y has a representing measure defined on a set satisfying Assumption 2 if and only if M d (g i y) 0 for all d ∈ N and for all polynomials g i defining the set, i = 0, 1, . . . , n K , and where A 0 stands for matrix A positive semidefinite, i.e., with nonnegative real eigenvalues.

This leads to the problem:

p * ∞ = inf y m j=1 β∈N n+1 c j,β y j,β s.t. m j=1 β∈N n+1 a j,α,β y j,β = b α , α ∈ N n+1 , M d (g i y j ) 0, i = 0 . . . n K , j = 1 . . . m, d ∈ N. ( 23
)
Theorem 4 Measure LP (10) and infinite-dimensional LMI problem (23) share the same optimum:

p * = p * ∞ .
For the rest of the paper, we will therefore use p * to denote the cost of measure LP [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] or LMI problem (23) indifferently.

Moment LMI hierarchy

The final step to reach a tractable problem is relatively obvious: infinite-dimensional LMI problem ( 23) is truncated to its first few moments.

To streamline exposition, first notice in LMI ( 23) that M d+1 (•) 0 implies M d (•) 0, such that when truncated, only the constraints of highest order must be taken into account. Now, let d 0 ∈ N be the smallest integer such that all Lagrangians, dynamics and constraint monomials belong to N n+1 2d 0 . This is the degree of the so-called first relaxation. For any relaxation order d ≥ d 0 , the decision variable is now the vector (y j,α ) α with α ∈ N n+1 2d , made of the first n+2d+1 n+1 moments of each measure µ j . Then, define the index set

Nn+1 2d := α ∈ N n+1 : deg L ′ j v α ≤ 2d, j = 1, . . . , m ,
viz., the set of monomials for which test functions of the form (20) lead to linear constraints of appropriate degree. By assumption, this set is finite and not empty -the constant monomial always being a member.

Then, the LMI relaxation of order d is given by

p * d = inf
Notice that for each relaxation, we get a standard LMI problem that can be solved numerically by off-the-shelf software. In addition, the relaxations converge asymptotically to the cost of the moment LP:

Theorem 5 For increasing relaxation orders d, the hierarchy of finite-dimensional LMI relaxations (24) yields an asymptotically converging monotonically non-decreasing sequence of lower bounds on the values of measure LP (10) and infinite-dimensional LMI problem (23

) , i.e. p * d 0 ≤ p * d 0 +1 ≤ • • • ≤ p * ∞ = p * .
Proof: By construction, observe that j > i implies p * d 0 +j ≥ p * d 0 +i , viz., the sequence p * d is monotonically non-decreasing. Asymptotic convergence to p * follows from [29, Theorem 3.8] as in the proof of Theorem 4. Therefore, by solving the truncated problem for ever greater relaxation orders, we obtain a monotonically non-decreasing sequence of lower bounds to the true optimal cost.

SOS LMI hierarchy

As for the measure LP of §2, the moment LMI relaxations detailed in the previous section possess a conic dual. In this section, we show that this dual problem can be interpreted as a polynomial SOS strengthening of the dual outlined in §2.4. The exact form of the dual problem is an essential aspect of the numerical method, since it will be solved implicitly whenever primal-dual interior-point algorithms are used for solving the moment LMI hierarchy of §3.2.

Let S n be the space of symmetric n × n real matrices. One can show (see, e.g., [29, §C]) that, for A, B ∈ S n , A, B := trace AB is a duality bracket S n × S n → R, and that {A ∈ S n : A 0} defines a convex cone of S n . In problem [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF], let us define the matrices

A i,β ∈ S n+d+1 n+1
satisfying the identity

M d (g i y) = β A i,β y β
for every sequence (y β ) β and i = 0, 1, . . . , n K .

Proposition 1 The conic dual of moment LMI problem (24) is given by the SOS LMI problem sup

z,Z α∈ Nn+1 2d b α z α s.t. α∈ Nn+1 2d a j,α,β z α + n K i=0 A i,β , Z i,j = c j,β , β ∈ N n+1 2d , Z i,j 0, i = 0, 1, . . . , n K , j = 1, . . . , m. (25)
Proof: Replacing the equality constraints in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] as two inequalities, it is easy to see that the moment relaxation can be written as an instance of LP [START_REF] Claeys | Reconstructing trajectories from the moments of occupation measures[END_REF], whose dual is given symbolically by [START_REF] Claeys | Measures and LMIs for Impulsive Nonlinear Optimal Control[END_REF]. Working out the details leads to the desired result, using for semi-definite constraints the duality bracket as explained earlier.

The relationship between ( 25) and ( 14) might not be obvious at a first glance. Denote by Σ[z] the subset of R[z] that can be expressed as a finite sum of squares of polynomials. Then a standard interpretation (see, e.g., [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]) of ( 25) in terms of such objects is given by the next proposition.

Proposition 2 LMI problem (25) can be stated as the following polynomial SOS strengthening of problem [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF]:

sup v(T, x T ) -v(0, x 0 ) s.t. l j -L ′ j v = n K i=0 g i s i,j , j = 1, . . . , m (26)
where the maximization is w.r.t. the vector of coefficients z of polynomial v(t, x) = α∈ Nn+1 2d z α v α (t, x) and the vectors of coefficients of polynomials s i,j ∈ Σ[t, x], deg g i s i,j ≤ 2d.

Proof: By ( 21), the cost of ( 26) is equivalent to [START_REF] Henrion | Mean squared error minimization for inverse moment problems[END_REF]. Then multiply each scalar constraint (indexed by α) by v α as given by [START_REF] Geromel | Dynamic output feedback control of switched linear systems[END_REF], and sum them up. By definition, α c j,α v α = l j , and similarly, β a j,α,β z α v α = L ′ j v α . The conversion from the semi-definite terms to SOS exploits their well-known relationship (e.g., [29, §4.2]) to obtain the desired result, by definition [START_REF] Decarlo | Perspectives and results on the stability and stabilizability of hybrid systems[END_REF] of the localizing matrices. Prop. 2 specifies in which sense "polynomial SOS strengthenings" must be understood: positivity constraints of ( 14) are enforced by SOS certificates, and the decision variable of ( 14) is now limited to polynomials of appropriate degrees.

Finally, the following result states that no numerical troubles are expected when using classical interior-point algorithms on the primal-dual LMI pair [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Henrion | Mean squared error minimization for inverse moment problems[END_REF].

Proposition 3 The infimum in primal LMI problem ( 24) is equal to the supremum in dual LMI problem [START_REF] Henrion | Mean squared error minimization for inverse moment problems[END_REF], i.e., there is no duality gap.

Proof: By Assumption 2, one of the polynomials g i in the description of set K enforces a ball constraint. The corresponding localizing constraint M d (g i y j ) 0 then implies that the vector of moments y is bounded in LMI problem [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF]. Then to prove the absence of duality gap, we use the same arguments as in the proof of Theorem 4 in Appendix D of [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF].

Computational complexity

This section details rough estimates on the numerical gains expected by employing modal occupation measures in LMI relaxations as opposed to the more generic method developed in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF].

Following the standing assumptions, the computational complexity of solving an LMI relaxation of order d with p occupation measures supported on a space of dimension n + m + 1 (time, states, controls) is dominated by p LMI constraints of size m (the moment matrices of the occupation measures) in n variables (the moment vectors of the occupation measures), with

n = n + m + 2d + 1 n + m + 1 , m = n + m + d + 1 n + m + 1 .
A standard primal-dual interior-point algorithm to solve this LMI at given relative accuracy ǫ > 0 (duality gap threshold) requires a number of iterations (Newton steps) growing as O(p

1 2 m1
2 ) log ǫ, see, e.g., [START_REF] Ben-Tal | Lectures on modern convex optimization: analysis, algorithms, and engineering applications[END_REF]Section 6.6.3]. In the real model of computation (for which each addition, subtraction, multiplication, division of real numbers has unit cost), each Newton iteration requires no more than O(n 3 ) + O(pn 2 m2 ) + O(pn m3 ) operations. When solving a hierarchy of simple LMI relaxations as described above, the accuracy ǫ is fixed, the number of states n and controls m are fixed the number p of measures is fixed, and the relaxation order d varies, such that O(n) = O( m) = O(d 4(n+m+1) ) and the dominating term in the complexity estimate grows in O(p Therefore, an LMI relaxation of an optimal switching control problem with n states and m controls will be solved in O(d formulation of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] and O(m 3 2 d 9 2 (n+1) ) when solved with structured formulation [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF]. That is a n+1 n+m+1 reduction of the polynomial rate at which the CPU time grows with relaxation orders. This back-of-the-envelope estimation is slightly conservative in practice, as shown in §6.2. Note that the same analysis as performed with the reported computation times of [START_REF] Bonnard | Geometric and numerical methods in the contrast imaging problem in nuclear magnetic resonance[END_REF] or [START_REF] Sager | Efficient upper and lower bounds for global mixedinteger optimal control[END_REF] reveals a similar underestimation of actual computation gains by applying the method described in this paper. As seen in these examples, those gains are substantial and justify the practical use of the modal occupation measures for switched systems.

Trajectory extraction

This section presents a method for extracting approximate optimal trajectories from moment data.

As presented so far, the method provides a converging sequence of lower bounds to the value of the control problem. This already provides a valuable tool to the user, allowing to certify as globally optimal local solutions found by other means such as a local solver or heuristics -or even reject unsound candidate solutions, see §6.3. In addition, comparing lower bounds with the value of an admissible solution, when they do not match, allows to easily quantify the maximal gain that may be achieved by investing more numerical efforts for that particular problem.

As useful as these may prove, it seems intuitive that much more than the cost could be extracted from moment data, especially at sufficiently high relaxation orders. In this section, we show that optimal controls and trajectories can indeed be inferred. The focus here is not on obtaining very precise estimates of the optimal solution, as this would require an impractically large number of test functions in the weak ODE constraints. In addition, estimates of arbitrary high precision can already be obtained routinely from local optimal control solvers (see, e.g., BOCOP [START_REF] Bonnans | Bocop -A collection of examples[END_REF]), if suitably initialized. Therefore, what is only needed from the moment data is a sensible approximation of the globally optimal solution(s), to be then simply refined by local methods.

Consider the trajectory x(t) which must be reconstructed on [0, T ] from partial moment sequence L y j (t α x β ) α+|β|≤2r , j = 1 . . . m. As a consequence of (1), see [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF]Cor. 1.4], optimal solutions {µ j } are supported on the graph of optimal trajectories. Therefore, one possible strategy for reconstructing x(t) is to construct an approximate support on a discretization of [0, T ] × X from the partial moment data. We propose a specialization for switched systems -needed for recovering the modal duty cycles -of the method developed in [START_REF] Claeys | Reconstructing trajectories from the moments of occupation measures[END_REF]. As in this reference, we assume that the optimal pair (u * (t), x * (t)) is unique for ease of exposition. We also assume for the same reason that the state space is unidimensional, as the outlined procedure could be trivially repeated for each component of a multidimensional state space. Fix a mesh resolution ε. Denote then by X ε a mesh supported on finitely many points, such that for all x ∈ X, there exists

x i ∈ X ε such that |x i -x| ≤ ε. Let T ε denote the analogous discretization of [0, T ]. It is proposed in [15, Th. 3] to solve the program min μj L y j (t α x β ) -t α x β , μj s.t. μj ∈ M + (T ε × X ε ), (27)
to obtain the best discrete approximation μj of the partial moment sequence {y j }. Indeed, this can be recast as a simple finite-dimensional, linear program, since measures in M + (T ε × X ε ) can be parametrized by a discrete set of weights, each assigned to an atom supported on T ε × X ε . The approximate trajectory way points are simply deduced from the support of the optimal solution of ( 27), viz., from the non-zero atomic weights.

This simple procedure could be repeated for each modal measure µ j in order to reconstruct the full trajectory. Active modes along the trajectory are then deduced by inspecting the relative modal weights at each atom. However, this naive approach proves to be very imprecise in practice, since modes are deduced from solutions of independent optimization problems (one for each measure). In particular, the sum of all modal measures must disintegrate as (as plugging test functions of time only in (8) reveals):

m j=1 µ j = ζ(dx|t) dt, (28)
where ζ is a probability measure on X define almost-everywhere on [0, T ]. However, the discrete version of this property is not guaranteed with independent solving of ( 27), so that duty cycles can hardly be reconstructed. This observation leads directly to the following alternative program:

min μ1 ,...,μm m j=1 L y j (t α x β ) -t α x β , μj s.t. m j=1 |Xǫ| k=1 μj {(t i , x k )} = (∆t) i , i = 1, . . . , |T ǫ |, μj ∈ M + (T ε × X ε ), (29)
where (∆t) i is the length of the ith cell, containing t i ∈ T ǫ , of a given partition of [0, T ]. In [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF], we have done nothing else that to couple the modal reconstruction by constraining the discretization of ζ(dx|t i ) to be a probability measure. When the solution of the optimal control problem is unique, it is then possible to approximate the value of x * (t) at the time nodes via

x * (t i ) ≈ m j=1 |Xǫ| k=1 μj {(t i , x k )} x k (∆t) i ,
and the duty cycles via

d * j (t k ) ≈ |Xǫ| k=1 μj {(t i , x k )} (∆t) i .
To show that a relaxation has converged, we use those way-points to hot start a numerical method, see the examples in §6. If the cost of the local method agrees with some tolerance to the relaxation cost, we then terminate the moment hierarchy and validate the local solution as globally optimal. In practice, and in accordance with the analysis of §3.4, problems with state-space smaller than 6 can be usually solved with a globality gap of a few percent at most. The method may still be applied to larger problems; For some instances, one may still solve the problem, whereas on some others, the method simply provide a lower bound on the cost.

Extensions

Several standard extensions of our results are now presented.

Free/distributed initial state

The approach can easily take into account a free initial state and/or time, by introducing an initial occupation measure µ 0 ∈ M + ({0} × X 0 ), with X 0 ⊂ R n a given compact set, such that for an admissible starting point (t 0 , x(t 0 )),

v, µ 0 = v(t 0 , x(t 0 )), (30)
for all continuous test functions v(t, x) of time and space. That is, in weak problem [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF], one replaces some of the boundary conditions by injecting [START_REF] Lasserre | Convergent SDP-relaxations in polynomial optimization with sparsity[END_REF] and making µ 0 an additional decision variable. In dual [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF], this adds a constraint on the initial value and modifies the cost.

Similarly, a terminal occupation measure µ T can be introduced for free terminal states and/or time. Note that injecting both [START_REF] Lasserre | Convergent SDP-relaxations in polynomial optimization with sparsity[END_REF] and its terminal counterpart in [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] requires the introduction of an additional affine constraint to exclude trivial solutions, e.g., 1, µ 0 = 1 so that µ 0 is a probability measure. In dual problem [START_REF] Claeys | Moment LMI approach to LTV impulsive control[END_REF], this introduces an additional decision variable.

More interestingly, the initial time may be fixed w.l.g. to t 0 = 0, but only the spatial probabilistic distribution of initial states is known. Let ξ 0 (dx) ∈ P(X 0 ) be the measure whose law describes such a distribution. Then, the additional constraints for [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] are

v, µ 0 = X 0 v(0, x) ξ 0 (dx).
As remarked in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], this changes the interpretation of LP [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF] to the minimization of the expected value of the cost given the initial distribution. See also [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] for the Liouville interpretation of the LP as transporting measure ξ 0 along the optimal flow.

Additional constraints

In measure LP [START_REF] Candès | Towards a mathematical theory of superresolution[END_REF], each modal occupation measure is supported on the same set K. This simply translates the fact that state constraints are mode-independent. However, nothing prevents the use of specific mode constraints by defining m sets {K j } j=1,...,m .

In unstructured LP [START_REF] Branicky | A unified framework for hybrid control: model and optimal control theory[END_REF], these would be specified by constraining the support of µ to m j=1 {e j } × K j , where e j is the unit vector in R m whose j-th entry is 1. Then, in the proof of Th. 2, for direction p * ≤ p * W , it is easy to see that this implies that each µ j is supported on K j . For the reverse direction, one can define w.l.g. the support of μ to be K := ∪ m j=1 K j by extending that of each µ j to K and setting µ j (K \ K j ) = 0. Then µ has the expected support.

A second class of constraints that can be easily accounted for by the method are a finite number of integral constraints of the form

T 0 h k σ(t) (t, x(t)) dt ≤ e k , k = 1, . . . , n i (31)
with given h k j ∈ R[t, x], j = 1, . . . , m and e k ∈ R, k = 1, . . . , n i . Indeed, rewriting the constraint in the equivalent formalism of (2) and using modal occupation measures as in Def. 4, [START_REF] Liberzon | Basic problems in stability and design of switched systems[END_REF] becomes

m j=1 h k j , µ j ≤ e k . (32)
That is, in moment problem [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF], whose first relaxation order may need to be updated in function of the degrees of each h k j , each of the n i integral constraints simply appears as an additional linear constraint. The interest of treating these integral constraints explicitly (instead of rewriting them as additional states to fit in the rigid formalism of ( 1)) is obvious from §3.4 in terms of computational load. Conversely, some translational-invariant problems might strongly benefit in replacing selected states by integral constraints, see, e.g., [START_REF] Sager | Efficient upper and lower bounds for global mixedinteger optimal control[END_REF].

Wider class of dynamical systems

First note that additional drift terms, viz., dynamics of the form ẋ = f 0 + m j=1 f j u j , fit easily within the framework of problem (1) by adding the drift term to each mode dynamics.

Secondly, in a related fashion, affine-in-the-control problems with polytopic control sets more general that the box described in (5) can also be handled by the formalism presented in this paper. Indeed, the problem is equivalent to controlling (with relaxed objects -see section §2) the system with modes associated with vertices of the control polytope.

Finally, dynamics of the form f j (t, x, u j ), parametrized by a mode-dependent measurable control u j (t), can be incorporated into the presented formalism by combining the approach in this paper with that of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF]. However, mode-dependent states, where the size of the state-space varies for each given mode change and/or whose meaning is mode-dependent, must be incorporated by extending those states to all modes with a null vector field.

It is an open question whether a more elegant approach can be incorporated into the framework of this paper.

Open-loop versus closed-loop

In problem (1), the control signal is the switching sequence σ(t) which is a function of time: this is an open-loop control, similarly to what was proposed in [START_REF] Claeys | Measures and LMIs for Impulsive Nonlinear Optimal Control[END_REF] for impulsive control design. One could also want to constrain the switching sequence to be an explicit or implicit function of the state, i.e., σ(x(t)), a closed-loop control signal. In this case, each occupation measure, explicitly depending on time, state and control, may be disintegrated as dµ(t, x, u) = ξ(dt | t, u)ω(du | t)dt, and we should follow the framework described originally in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF].

Switching and impulsive control

We may also combine switching control and impulsive control if we extend the system dynamics to

dx(t) = m k=1 f k (x(t)) u(t) dt + p j=1 g j (t)ν j (dt),
which must be understood in a weak sense. Here, g j are given continuous vector functions of time and ν j are signed measures to be found, jointly with the switching signal u(t). Whereas modal occupation measures are restricted to be absolutely continuous w.r.t. the Lebesgue measure of time, impulsive control measures ν j can concentrate in time. For example, for a dynamical system dx(t) = g(t)ν(dt), a Dirac measure ν(dt) = δ s enforces at time t = s a state jump x + (s) = x -(s)+g(s). In this case, to avoid trivial solutions, the objective function should penalize the total variation of the impulsive control measures, see [START_REF] Claeys | Measures and LMIs for Impulsive Nonlinear Optimal Control[END_REF].

Examples

In this section, we show several examples to illustrate the method. The first example illustrates the fact that the infimum is not attained even in the simplest instances of optimal control problem (1). The second example is the constrained double integrator example of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF]. The final two examples are taken from [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF], where they are solved by a local optimization method dedicated for switched systems. These last examples highlight how our method can complement more traditional approaches.

All moment relaxations were built with the GloptiPoly toolbox [START_REF] Henrion | Gloptipoly 3: Moments, optimization and semidefinite programming[END_REF] and solved via the Mosek semi-definite solver [START_REF] Mosek Aps | The MOSEK optimization software[END_REF], interfaced through Yalmip [START_REF] Löfberg | Yalmip : A toolbox for modeling and optimization in Matlab[END_REF].

y 2,α = 1 2 1 1 2 t α dt = 2 -2 -α 4 + 4α
and they can be compared with the following moment vectors obtained numerically at the 7th LMI relaxation: We observe that the computed moments closely match the exact optimal moments, so that the approximate control law extracted from the computed moments will be almost optimal.

Double integrator

We revisit the double integrator example with state constraint studied in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], formulated as the following optimal switching problem:

p * = inf T s.t. ẋ(t) = f σ(t) (x(t)), x(0) = (1, 1), x(T ) = (0, 0) x 2 (t) ≥ -1, ∀t ∈ [0, T ]
where the infimum is w.r.t. a switching sequence σ : [0, T ] → {1, 2} with free terminal time T ≥ 0 and affine dynamics

f 1 := x 2 -1 , f 2 := x 2 1 .
We know from [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] that the optimal sequence consists of starting with mode 1, i.e., u 1 (t) = 1, u 2 (t) = 0 for t ∈ [0, 2], then chattering with equal proportion between mode 1 and 2, i.e., u 1 (t) = u 2 (t) = 1 2 for t ∈ [2, 5 2 ] and then eventually driving the state to the origin with mode 2, i.e., u 1 (t) = 0, u 2 (t) = 1 for t ∈ [ 5 2 , 7 2 ]. Here too the infimum p * = 7 2 is not attained for problem (1), whereas it is attained with the above controls for problem (4).

In Table 2 we report the lower bounds p * d on the optimal value p * obtained by solving LMI relaxations (24) of increasing orders d, rounded to 5 significant digits. We also indicate the number of variables n (i.e., total number of moments) of each LMI problem, as well as the zeroth order moment of each occupation measure (recall that these are approximations of the time spent on each mode). We observe that the values of the lower bounds and the masses stabilize quickly to the optimal values p * = 7 2 , y 1,0 = 5 2 , y 2,0 = 5 4 . We carried out a comparison of computational times required for solving the unstructured generic LMI relaxations of [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] versus their structured modal counterpart, for relaxation orders 1 to 7. The computational gains induced by using modal occupation measures follow the expected exponential improvement, with an exponent of about 1.7, better than the 4 3 predicted by the asymptotic analysis of §3. and where the infimum is w.r.t. a switching sequence σ(t) but also a classical control u(t), consistently with the extension sketched in §5.3. The lower bounds and computation times are given in Tab. 3. We also report the cost of a direct, local, optimal control methods as implemented in BOCOP [START_REF] Bonnans | Bocop -A collection of examples[END_REF] via embedding (4), and hot started with the method of §4.

As one can see, the costs are in close agreement, and we can numerically certify the local solutions as globally optimal. We also used VSDP [START_REF] Jansson | VSDP: a Matlab software package for verified semidefinite programming[END_REF] to strengthen the semi-definite bounds, so as to compute verified lower bounds on the cost of a relaxation via rigorous interval arithmetic. The lower bound for the third order relaxation could be certified to the significant figures presented in Tab. 3. The disagreement with the lower cost reported in [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF] is due to numerical round-off issues in the execution of their local method. In fact, integrating finely the solution reported in [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF] leads the a candidate arc whose cost is above our certified lower bound.

Double tank problem

We consider the double tank problem of [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF]:

p * = inf T 0
2(x 2 (t) -3) dt s.t. ẋ1 (t) = c σ(t) -x 1 (t) ẋ2 (t) = x 1 (t) -x 2 (t), x(0) = (2, 2) ′ σ ∈ {1, 2}, T = 10, with data c 1 = 1, c 2 = 2 and where the infimum is w.r.t. a switching sequence σ(t). By introducing the lifts ℓ i = √ x i , algebraically constrained as ℓ 2 i = x i , ℓ i ≥ 0, the problem is easily recast with polynomial data. Table 4 reports the relaxation costs of our method along with the cost of BOCOP, hot-started by the moment data. Again, agreement is reached quickly. Note that the cost is here strictly better than the one reported in [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF], which is stuck in a local but not global minimum. This adverse behavior is of course inherent to any local optimization scheme, and shows the interest of methods which allow to obtain decent starting point to initialize them. Obviously, such a pass with a local method is still necessary to obtain very precise numeric solutions, and our general framework allows to combine the best of the global and local worlds.

Quadrotor

For our last example, we take the quadrotor example considered in [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF]:

p * = inf
f 2 = g sin x 3 (t) g cos x 3 (t)-g -Lu(t) I

, f 3 = g sin x 3 (t) g cos x 3 (t)-g Lu(t) I [START_REF] Mosek Aps | The MOSEK optimization software[END_REF] and where the infimum is w.r.t. a switching sequence σ(t) but also a classical control u(t), consistently with the extension sketched in §5.3. We turn this problem into one with polynomial data by considering another parametrization of the attitude x 3 belonging to SO(2), namely by replacing x 3 with ℓ 1 := cos x 3 and ℓ 2 := sin x 3 , who must then satisfy the ODE l1 = -ℓ 2 ẋ3 ,

l2 = ℓ 1 ẋ3 . ( 36
)
The problem has however too high of a dimension to hope to obtain tight bounds systematically, with 7 states/lifts, 1 control and time (see the analysis in §3.4). Nonetheless, for this specific example, the bounds presented in Tab. 5 show convergence in two relaxations only, since the local minimum obtained with BOCOP is very close to the bound obtained at the relaxation of order d = 3, solved in about 7 minutes on our desktop PC. Note that the relaxation of order d = 4, involving n = 98670 moments, would still be attainable with modern machines, at the expense of a full day of computations. Finally, also note that the solution is again better than the local minimum reported in [START_REF] Vasudevan | Consistent approximations for the optimal control of constrained switched systems-part 2: An implementable algorithm[END_REF].

  3.10] (see also the exposition in [3, §4]), that the closure of the cone R := ( z p , c p , A z p ) : z p ∈ E + p belongs to R × E d . Note that the weak- * topology is implicit in the definition of E d , and the closure of R should be understood in such a weak sense.

  α,β y j,β = b α , α ∈ Nn+1 2d M d (g i y j ) 0, i = 0, . . . , n K , j = 1, . . . , m.

9 2

 9 (n+m+1) ), which clearly shows a strong dependence on the number of state and control variables.

computed y 1 =

 1 (0.74996 0.31246 0.18746 0.13277 • • • ) , exact y 1 = (0.75000 0.31250 0.18750 0.13281 • • • ) , computed y 2 = (0.25004 0.18754 0.14588 0.11723 • • • ) , exact y 2 = (0.25000 0.18750 0.14583 0.11719 • • • ) .

6. 3

 3 Switched LQRWe consider the problemp * = inf T 0 0.01 u 2 (t) dt + 3 i=1 (x i (T ) -1) 2 s.t. ẋ(t) = A x(t) + B σ(t) u(t), x(0) = (0, 0, 0), u(t) ∈ U = [-20, 20], σ ∈ {1, 2, 3},

1 =

 1 . ẍ = f σ(t) , x(0) = (0, 1, 0), ẋ(0) = (0, 0, 0), u(t) ∈ U = [0, 10 -3 ], σ(t) ∈ {1, 2, 3}, T = 7.5,(33)with data M = 1.3, L = 0.3050, I = 0.0605, g = 9.8, andf sin x 3 (t) M (u(t)+M g) cos x 3 (t) M(u(t)+M g)-g 0 ,

Table 2 :

 2 [START_REF] Bengea | Optimal control of switching systems[END_REF]. Lower bounds p * d on the optimal value p * obtained by solving LMI relaxations of increasing orders d; n is the number of variables in the LMI problem; y j,0 is the approximate time spent on each mode j = 1, 2.

	d	p * d	n	y 1,0	y 2,0
	1 2.5000 30 1.7500 0.75000
	2 3.2015 105 2.1008 1.1008
	3 3.4876 252 2.2438 1.2438
	4 3.4967 495 2.2484 1.2484
	5 3.4988 858 2.2494 1.2494
	6 3.4993 1365 2.2496 1.2497
	7 3.4996 2040 2.2498 1.2498

Table 3 :

 3 Lower bounds p * d and number of variables n of the LMI problem in function of relaxation order d for the problem of §6.3. The value found by hot starting BOCOP with our method is also shown.

	d	p * d	n
	1	0.0000 62
	2	4.4886 322
	3	4.7265 1092
	4	4.7298 2904
	5	4.7304 6578
	. . .
	BOCOP 4.7304

Table 4 :

 4 Lower bounds p * d and number of variables n of the LMI problem in function of relaxation order d for the problem of §6.4. The value found by hot starting BOCOP with our method is also shown.

Table 5 :

 5 Lower bounds p * d and number of variables n of the LMI problem in function of relaxation order d for the problem of §6.5. The value found by hot starting BOCOP with our method is also shown.

"Strong" is opposed here to the "weak" problem to be defined shortly after.

(n+m+1) ) operations when solved with the general

Acknowledgments:

This work benefited from discussions with Milan Korda, Jean-Bernard Lasserre and Luca Zaccarian.

This work with partly supported by project 13-06894S of the Grant Agency of the Czech Republic and by the UK Engineering and Physical Sciences Research Council under Grant EP/G066477/1.

Chattering

Consider the scalar (n = 1) optimal control problem (1):

where the infimum is w.r.t. a switching sequence σ : [0, 1] → {1, 2} and

In Table 1 we report the lower bounds p * d on the optimal value p * obtained by solving LMI relaxations [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] of increasing orders d, rounded to 5 significant digits. We also indicate the number of variables n (i.e., total number of moments) of each LMI problem, as well as the zeroth order moment of each occupation measure (recall that these are approximations of the time spent on each mode). We observe that the values of the lower bounds and the masses stabilize quickly. In this simple case, it is easy to obtain analytically the optimal switching sequence: it consists of driving the state from x(0) = 1 2 to x( 12 ) = 0 with the first mode, i.e., u 1 (t) = 1, u 2 (t) = 0 for t ∈ [0, 1 2 [, and then chattering between the first and second mode with equal proportion so as to keep x(t) = 0, i.e., u

Because of chattering, the infimum in problem (1) is not attained by an admissible switching sequence. It is however attained in the convexified problem (4).

The optimal moments can be obtained analytically

t α dt = 2 + 2 -α 4 + 4α ,


Joël Penhoat
email: joel.penhoat@orange-ftgroup.com

Karine Guillouard
email: karine.guillouard@orange-ftgroup.com

Tayeb Lemlouma
email: tayeb.lemlouma@univ-rennes1.fr

Mikaël Salaun
email: mikael.salaun@univ-rennes1.fr

Analysis of the Implementation of Utility Functions to Define an Optimal Partition of a Multicast Group

Keywords: Handover, Multicast group partition, Resource optimization, User's context, Utility function I

As the optimal use of network resources is a major issue for telecoms operators, we started works aiming to, firstly, improve the utilization of network resources by transmitting the IP packets in multicast when possible, secondly, to adapt the format of the data transmitted in multicast to take into account the context of the members of the multicast group, and thirdly to preserve the Quality of Service when a member of the multicast group moves from a radio network to another radio network. The paper shows, through a scenario, how our work will improve the utilization of the resources and then describes our approach.

INTRODUCTION

The optimization of the use of the resources of the networks is a major issue for a telecoms operator because it allows him to reduce his operational expenditure (OPEX). In particular, the improvement of the use of the resources of the radio spectrum is necessary as showed in a study [START_REF]Report of the Spectrum Efficiency Working Group[END_REF] led in 2002 by Federal Communications Commission (FCC). This study showed that in a frequency band the rate of use of the radio resources could vary between 5% and 85%.

According to us, the solutions that aim to optimize the use of the network resources must be implemented in each level of the TCP/IP stack. Moreover, interactions must exist among each solution implemented in each level of the stack, i.e. the optimization is based on cross-layer solutions. In the PHY and MAC layers, the Cognitive Radios [START_REF] Fette | Cognitive Radio Technology[END_REF] are designed to improve the use of the radio spectrum resources by exploiting the radio resources vacated by their owners. In 2004, the FCC has asked the IEEE to implement the Cognitive Radios in the frequency range 54 -698 MHz [START_REF]Notice of Proposed Rule Making[END_REF]. The IEEE P802.22 standard [START_REF]IEEE Draft Standard for Information technology Telecommunications and information exchange between systems Local and metropolitan area networks Specific requirements Part 22.1: Standard to Enhance Harmful Interference Protection for Low Power Licensed Devices Operating in TV Broadcast Bands[END_REF] meets this demand by allowing the use of vacant TV channels by radio equipments operating without radio licenses. In the IP layer, the multicast transmission of data [START_REF] Deering | IETF Network Working Group: RFC 1112[END_REF] is a known technique for improving the use of the resources in an IP network because it reduces the number of IP packets transmitted over a network when several receivers must receive the same data. In the transport layer, numerous studies have improved the throughput of TCP by taking into consideration the physical characteristics of the networks. For example, the TCP Westwood protocol [START_REF] Mascolo | End-to-End Bandwidth Estimation in TCP to Improve Wireless Link Utilization[END_REF] improves the throughput of a TCP connection when the IP packets are transmitted over a radio network.

Our study focuses on the improvement of the use of the resources of networks at the IP level by implementing multicast transmissions when the services asked by the users can be transmitted in multicast. During a multicast transmission, all the members of a multicast group (i.e. the users) receive the data in the same format because a multicast transmission does not take into account the heterogeneity of the receivers (mobile phones, laptops, smartphones, tablets), the heterogeneity of the radio networks (GSM, Wi-Fi, WiMAX ...), or the diversity of the profiles of the members of the group (engineer, accountant, student …). The diversity of the receivers, radio networks, or the profiles of the users, are elements that characterize the context of a user. In the article, we use the definition of Abowd et al [START_REF] Abowd | Towards a Better Understanding of Context and Context-Awareness[END_REF] to define the context of a user. Figure 1 illustrates a scenario in which the members of a multicast group G have different contexts. In addition, as the members of the group may be mobile, their contexts vary during the transmission because they can connect themselves to wireless networks having different characteristics, for example during a handover between a Wi-Fi network transmitting in multicast the IP packets and an Universal Mobile Telecommunications System (UMTS) network transmitting in unicast the IP packets. So, the three objectives of our work are, firstly, to improve the utilization of the resources of the networks by transmitting in multicast the IP packets when possible, secondly, to adapt the format of the data transmitted in multicast to take into account the context of the members of the multicast group, and thirdly to preserve the Quality of Service (QoS) when a user moves from one radio network to another radio network.

The structure of the article is the following. The second section describes a scenario showing the interest of our works for the telecoms operators. The third section makes an inventory of the works that take into account the context of the users during a multicast transmission and analyzes their loopholes; then the fourth section presents our approach to implement our three objectives. Finally, the fifth section concludes the article and exposes our future works.

II. DESCRIPTION OF A SCENARIO ESTABLISHING A SYNERGY BETWEEN UNICAST AND MULTICAST NETWORKS

In this section we describe a scenario that could improve the utilization of the resources of the radio networks of a telecoms operator by establishing a synergy between unicast and multicast networks. In our scenario, eight persons, Anatole, Antoine, Bernard, Bertrand, Alice, Bénédicte, Catherine, and Isabelle, take part in a video-conference. The video-conference is made up of a Voice over IP (VoIP) flow and a Video flow. The Video flow is encoded with a Scalable Video Codec [START_REF] Schwarz | International Organisation For Standardisation ISO/IEC JTC1/SC29/WG11 Coding of Moving Pictures and Audio[END_REF] that splits the flow into several sub-flows. Our scenario consists of six stages. In the first stage (Figure 2), Anatole and Antoine receive the VoIP flow on a fixed phone and the Video flow on a video-projector. In the third stage (Figure 4), Bernard moves. His smartphone, initially connected to the MBMS network, connects itself to the Wi-Fi network. The VoIP and Video flows are transmitted in multicast over the Wi-Fi network that uses IPv6 addresses. In the fourth stage (Figure 5), Bernard, who has a laptop with a Wi-Fi interface, decides to take part in the videoconference via his laptop. Having connected his laptop to the Wi-Fi network, he turns off his smartphone and takes part in the video-conference via his laptop. In the fifth stage (Figure 6), the operator who manages the MBMS network notices that the smartphone of Alice is the only device connected to this network. As the smartphone of Alice has a MBMS interface and a Wi-Fi interface, the operator decides that Alice will take part in the video-conference via the Wi-Fi interface of her smartphone without decreasing her QoS. At the end of this operation the resources of the MBMS network are no longer used. In the last stage of our scenario (Figure 7), Antoine, who has a laptop with a Wi-Fi interface and an E-UTRAN interface, moves. After having turned on his laptop, he receives the VoIP and Video flows via two different interfaces: the VoIP flow is received in unicast via the E-UTRAN interface, while the Video flow is received in multicast via the Wi-Fi interface.

The six stages of our scenario show that a synergy between IPv4/IPv6 unicast radio networks and IPv4/IPv6 multicast radio networks is possible and could interest a telecoms operator. But its implementation raises many questions. Here is a non-exhaustive list of questions. Knowing that the contexts of the members of the multicast group are different, in what format the server should send the data when the IP packets carrying the data are transmitted in multicast? Knowing that the structure of the multicast group may change over time, as we see by comparing the structure of the multicast group between the first and the sixth stage, how to adapt the format of the transmitted data to reflect these changes? Knowing that the users are mobile, what are the criteria for selecting a radio network during a handover? Figure 7. A scenario describing a synergy between multicast and unicast networks (sixth stage)

III. IDENTIFICATION AND ANALYSIS OF THE EXISTING

WORKS

In this section we identify and analyze the works taking into account the context of the users in a multicast transmission. The first works date from the 1990s. In 1996, McCann et al [START_REF] Mccanne | Receiver-driven Layered Multicast[END_REF] have proposed to split a multicast group according to the throughput that the terminals of the users can receive. The data flow to be transmitted is encoded in several layers, each layer being transmitted with a certain throughput. The first layer, called the base layer, is necessary to decode the flow, whereas the other layers are used to improve the QoS of the received flow. The QoS of a user is better if the number of layers decoded by his terminal is higher. Each layer is associated with a subgroup of the partition of the multicast group. The subscription to one or several subgroups is made with the Receiver-driven Layered Multicast (RLM) protocol: the terminal of a user chooses to subscribe to one or several subgroups, i.e. to receive one or several layers, according to its decoding capabilities and the available bandwidth in the network. In 2000, Yang et al [START_REF] Yang | Optimal Partitioning of Multicast Receivers[END_REF] defined a utility function [START_REF] Anand | Foundations of Rational Choice Under Risk[END_REF] in the terminal of each user by taking as parameter the throughput received by the terminal. The optimum of the utility function is reached when the throughput received by the terminal is equal to the throughput that it would receive if it was alone in the group. Then, having defined a utility function for each subgroup making up a partition of the multicast group, they mathematically demonstrated that there is a partition, among all the possible partitions, whose sum of the extremums of the utility functions of the subgroups making up the partition is bigger than the sum of the extremums of the utility functions of the subgroups of the other partitions. This partition, which is the optimal partition, is obtained by a centralized process. Several works redefined the utility function implemented in the terminals by Yang et al [START_REF] Yang | Optimal Partitioning of Multicast Receivers[END_REF]: Maimour et al [START_REF] Maimour | A RTT-based Partitioning Algorithm for a Multi-rate Reliable Multicast Protocol[END_REF] modified the function by taking a parameter easier to get than the throughput, namely the transmission delay between the source emitting the flow of IP packets and each terminal; then Yousefi' zadeh et al [START_REF] Yousefi' Zadeh | Layered Media Multicast Control (LMMC): Rate Allocation and Partitioning[END_REF] chose a utility function continuously differentiable to reduce the complexity of the calculations to realize to obtain the optimal partition. In 2003, Li et al [START_REF] Li | Multirate Video Multicast over the Internet: An Overview[END_REF] showed that the consideration of the context of the users during a transmission of a video flow in multicast requires a video source having a method of transmission capable of transmitting the flow with various throughputs. Having established a taxonomy of the various methods of transmission of a video flow, they compared the three methods (stream replication, cumulative layering, noncumulative layering) implemented in the processes of partition of a multicast group. From the years 2005, several projects aim to take into account the context of the users in the multicast architectures: in 2008, the C-Mobile project [START_REF] Santos | Multicast/broadcast network convergence in next generation mobile networks[END_REF] defines a MBMS architecture that takes into account the context of the users; then in 2009, the C-Cast project [START_REF] Antoniou | Architecture for Context-Aware Multiparty Delivery in Mobile Heterogeneous Networks[END_REF] defines methods for collecting and analyzing the contexts in a multicast architecture.

In the works that we identified, a centralized process calculates the optimal partition from a utility function implemented in each terminal. However, other entities could also implement a utility function: the operators managing networks, the suppliers of a service … Each entity can have its own criteria to define an optimal partition. For example, an operator can define a single multicast group to improve the use of his networks, whereas the users will prefer to define a number of subgroups equal to the number of users for improving the consideration of the contexts of each user. When several entities take part in the partition process, what partition to choose among those proposed by every entity? Who chooses the partition? Furthermore, in the identified works, the mobility of the users is little studied. The analysis of the mobility requires the following definition. During a handover, when a terminal disconnects itself from a network, this network is called outgoing network; when it connects itself to a new network, this network is called incoming network. The analysis of the existing studies shows two issues. During a handover, what incoming network to choose? Who chooses the network? According to Zdarsky [START_REF] Zdarsky | Handover In Mobile Communication Networks: Who is In Control Anyway[END_REF], the user chooses the incoming network, while according to Antoniou et al [START_REF] Antoniou | Architecture for Context-Aware Multiparty Delivery in Mobile Heterogeneous Networks[END_REF], it is the operator managing the network that chooses the incoming network. To take into account the diverse objectives of the entities participating in the selection process, Suciu et al [START_REF] Suciu | Assessing the Handover Approaches for Heterogeneous Wireless Networks[END_REF] proposed a method called Hierarchical and Distributed Handover (HDHO), and analyzed a scenario composed of three entities, namely a content provider, an operator managing networks, and a user. The objective of the content provider is to choose an incoming network offering a QoS adapted to the flow to be transmitted. The objective of the operator is to choose the least loaded network for transmitting the flow of the content provider. The objective of the user is to choose a network offering the best QoS/Cost ratio for receiving the flow.

It is important to notice that the mobility of a user can cause a new partition of the multicast group due to the variation of the number of the terminals connected to the outgoing and incoming networks. Conversely, a new partition can cause the mobility of one or more users as shown in the fifth stage of the scenario described in the second section. The works that we identified do not address the interactions that can exist between the partition process of a group and the selection process of an incoming network.

IV. PRESENTATION OF OUR APPROACH

In this section we present our approach to implement our three objectives. The first two objectives seem contradictory. Indeed, the more the number of members in a multicast group is higher, the better the use of network resources. But the more the number of members in a multicast group is higher, the more it will be difficult to take into account the variety of the contexts of the users. It is thus necessary to find a compromise between, on one hand, the multicast transmission of the IP packets and, on the other hand, the consideration of the contexts of the users. Our approach aims at defining several entities that will divide the multicast group into several subgroups according to the context of the users. Three entities, namely the content provider, the operator managing the networks, and the users, are involved in the partition process. The objectives of the three entities are the following ones. The objective of the content provider is to encode his content into one or more different formats according to the encoding processes available on his servers (objective 1); the objective of the operator is to transmit the data in multicast when the multicast transmission is possible and when the consumption of the resources of networks during a multicast transmission of data towards N users is lower than the consumption of the resources of networks during a unicast transmission of data towards N users (objective 2); the objective of the users is to receive the data in a format adapted to their context (objective 3).

The implementation of the third objective is made with the HDHO method. The three entities participating in the selection process of an incoming network are the content provider, the operator managing the networks, and the users. The objective of the content provider is to choose an incoming network offering a QoS adapted to the flow to be transmitted (objective 4). The objective of the operator is to choose the least loaded network for transmitting the flow of the content provider (objective 5). The objective of the user is to choose a network offering the best QoS/Cost ratio for receiving the flow (objective 6). Since our approach is based on the definition of three entities, each with their goals, we must specify how these three entities interact among them to split the multicast group and to select an incoming network during a handover. By referring to the works of Suciu et al [START_REF] Suciu | Assessing the Handover Approaches for Heterogeneous Wireless Networks[END_REF], we chose the Free Conflict method, the Compromise and Negotiation method, and the Team Enforced method for implementing these interactions.

Since the mobility of a user can cause a new partition of the group and as a new partition can cause the mobility of one or more users, the partition process and the selection process interact among them. The interaction between the two processes is described by the heuristic presented in Figure 8. During a handover, the end of the selection process triggers the beginning of the partition process. At each iteration of the partition process, the operator managing the network can initiate a handover of one or more users to meet its objective. The selected networks must not degrade the QoS of the users. Currently we are working on the modules composing the heuristic and we reflect on the way to integrate our approach in a MBMS architecture. Figure 9 shows a possible integration. The objectives of the content provider, namely the objectives 1 and 4, can be implemented in the Broadcast Multicast Service Center (BM-SC) and in the Gateway GPRS Support Node (GGSN). The objectives of the operator, namely the objectives 2 and 5, can be implemented in the GGSN and in the Radio Network Controller (RNC). The objectives of the user, namely the objectives 3 and 6, can be implemented in the user's terminal.

V. CONCLUSION

As the optimization of the use of the resources of the networks is a major issue for telecoms operators, we initiated works that aim to, firstly, improve the use of the resources of the networks by transmitting the IP packets in multicast when it is possible, secondly, adapt the format of the data transmitted in multicast to take into account the context of the users, and thirdly preserve the Quality of Service when a user moves from a radio network towards another radio network. After having shown, through a scenario, how our work would allow to establish a synergy between multicast and unicast networks, we analyzed the works taking into account the context of the users during a multicast transmission. The analysis revealed three loopholes: the terminals of the users are the only entities that participate in the partition process; the mobility of the users is little studied; the listed works do not tackle the interactions that can exist between the partition process and the selection process. Our work, that takes into account these shortcomings, aims to, firstly, define the entities involved in the partition process and the selection process, secondly, define the objectives of these entities, thirdly, define the partition algorithm according to the objectives of each entity, fourthly, define the interaction between the partition process and the selection process. When these four steps will be made, we will model the partition process and the selection process with OPNET®.

Figure 1 .

 1 Figure 1. Multicast transmission in a heterogeneous context

Figure 2 .

 2 Figure 2. A scenario describing a synergy between multicast and unicast networks (first stage) The VoIP flow is transmitted in unicast over a UMTS network that uses IPv4 addresses. The Video flow is transmitted in unicast over an Evolved Universal Terrestrial Radio Access Network [9] that uses IPv6 addresses. The Evolved Universal Terrestrial Radio Access Network is noted E-UTRAN in the figure 2. Bernard, Bertrand and Alice receive the VoIP and Video flows on their smartphones. The VoIP and Video flows are transmitted in multicast over a Multimedia Broadcast Multicast Service network [10] that uses IPv4 addresses. The Multimedia Broadcast Multicast Service network is noted MBMS in the figure 2. Bénédicte, Catherine and Isabelle receive the VoIP and Video flows on their Personal Computers. The VoIP and Video flows are transmitted in multicast over a Wi-Fi network that uses IPv6 addresses. In the second stage (Figure 3), Bertrand moves.

Figure 3 .

 3 Figure 3. A scenario describing a synergy between multicast and unicast networks (second stage)

Figure 4 .

 4 Figure 4. A scenario describing a synergy between multicast and unicast networks (third stage)

Figure 5 .

 5 Figure 5. A scenario describing a synergy between multicast and unicast networks (fourth stage)

Figure 6 .

 6 Figure 6. A scenario describing a synergy between multicast and unicast networks (fifth stage)

Figure 8 .

 8 Figure 8. Heuristic describing the interaction between the selection process and the partition process

Figure 9 .

 9 Figure 9. Integration of our approach in a MBMS architecture