Mathieu Claeys

Didier Henrion

Martin Kružík

Semi-definite relaxations for optimal control problems with oscillation and concentration effects

Converging hierarchies of finite-dimensional semi-definite relaxations have been proposed for state-constrained optimal control problems featuring oscillation phenomena, by relaxing controls as Young measures. These semi-definite relaxations were later on extended to optimal control problems depending linearly on the control input and typically featuring concentration phenomena, interpreting the control as a measure of time with a discrete singular component modeling discontinuities or jumps of the state trajectories. In this contribution, we use measures introduced originally by DiPerna and Majda in the partial differential equations literature to model simultaneously, and in a unified framework, possible oscillation and concentration effects of the optimal control policy. We show that hierarchies of semi-definite relaxations can also be constructed to deal numerically with nonconvex optimal control problems with polynomial vector field and semialgebraic state constraints.

Introduction

This paper is devoted to a numerical method for solving optimal control problems which may exhibit concentrations and/or oscillations. Such problems naturally appear in many applications, for instance in controlling space shuttles, in impulsive control theory, see e.g. [START_REF] Blaquière | Impulsive optimal control with finite or infinite time horizon[END_REF], [START_REF] Bryson | Applied optimal control theory[END_REF], or [START_REF] Getz | Optimal control systems with state variable jump discontinuities[END_REF].

A typical example how concentration effects enter a minimization problem is the following: inf 1 0 (t -1/2) 2 |u(t)| dt s.t. ẏ = u, y(0) = 0, y(1) = 1, y ∈ W 1,1 (0, 1), u ∈ L 1 (0, 1), [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF] where u is a control living in the Lebesgue space of square integrable functions L 2 (0, 1), y is the corresponding state living in the Sobolev space W 1,1 (0, 1) of functions whose (distributional) derivative belongs to the Lebesgue space of integrable functions L 1 (0, 1), and the dot denotes time derivative.

Roughly speaking, an optimal control must here balance between transfering the state from 0 to 1 and remaining constant "as much as possible". Therefore, the optimal state should switch between two constants. As the function t → (t -1/2) 2 attains its minimum on [0, 1] at t = 1/2, it is desirable to switch from zero to one in a vicinity of t = 1/2. Having this in mind, it is easy to check that in problem (1) the infimum is zero but it cannot be attained. Changing suitably the weight function t → (t -1/2) 2 , the jump point can appear anywhere in [0, 1], and in particular, also on the boundary.

Concentrations do not have to occur only at isolated points, but they can be smeared out along the whole interval. This can be demonstrated on the following problem: inf 1 0 u(t) 2 1 + u(t) 4 + (y(t) -t) 2 dt s.t. ẏ = u, y(0) = 0, y ∈ W 1,1 (0, 1), u ∈ L 1 (0, 1), u ≥ 0.

(2)

Here, the cost favors instantaneous controls of null or very large magnitude, while averaging out to 1. The infimum of (2) is 0. Indeed, consider the control

u k (t) = k if t ∈ [ l k -1 2k 2 , l k + 1 2k 2 ] 0 otherwise
where k ∈ N is large enough and 1 ≤ l ≤ k -1. The corresponding state then reads y k (t) = t 0 u k (s) ds. An easy calculation shows that with this sequence (y k , u k ) k∈N the cost in problem (2) can approach zero as closely as desired, so that the infimum is zero, while there is obviously no minimizer.

In this paper, we propose a numerical method for solving those types of problems in a unified framework. The high-level methodology we follow is now familiar [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Claeys | Measures and LMIs for non-linear optimal impulsive control[END_REF]:

• First, a suitable relaxed concept of control is assumed, so as to guarantee the existence of minimizers under sufficiently broad assumptions.

• Second, as the problem still depends non-convexly on trajectories, whether via dynamics, constraints or the cost, suitable variants of occupation measures are introduced, so as to lift the optimization problem as a linear program over a measure space.

• Finally, if problem data are polynomial, directly or via algebraic lifts, this linear program can be solved via the paraphernalia of moment-sum-of-squares semidefinite programming relaxations (moment-SOS relaxations for short).

For problems with bounded controls, which may give rise to fast oscillations, appropriate relaxed concepts of controls were developed decades ago, by the likes of Young [START_REF] Young | Lectures on the calculus of variations and optimal control theory[END_REF], Fillipov, Warga, Gamkrelidze [START_REF] Gamkrelidze | Principles of optimal control theory[END_REF] and many others, see e.g. [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF]Part III]. The equivalence between the relaxed control problem and the measure LP was then proven in [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], see also [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF]. More recently, [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] proposed to solve this linear program via moment-SOS relaxations. For unbounded controls entering affinely in the problem, which may give rise to concentration effects, various weak concepts of solution have been proposed, where the control is now a measure of time [START_REF] Neustadt | Optimization, a moment problem and nonlinear programming[END_REF][START_REF] Gamkrelidze | Principles of optimal control theory[END_REF] in the simplest case, with more intricate cases requiring appropriate graph completions [START_REF] Bressan | On differential systems with vector-valued impulsive controls[END_REF] to ensure well-posedness of the relaxed program. Variants of occupation measures were then introduced [START_REF] Claeys | Measures and LMIs for non-linear optimal impulsive control[END_REF][START_REF] Claeys | Mesures d'occupation et relaxations semi-définies pour la commande optimale[END_REF] so as to solve the problem via moment-SOS relaxations, optimizing also w.r.t. all possible graph completions.

For unbounded controls entering non-linearly in the control problem, minimizing sequences may give rise to both oscillation and concentration phenomena. DiPerna and Majda [START_REF] Diperna | Oscillations and concentrations in weak solutions of the incompressible fluid equations[END_REF] have introduced measures allowing to capture the limit of admissible control sequences. Those results were then used in [START_REF] Kružík | Optimization problems with concentration and oscillation effects: relaxation theory and numerical approximation[END_REF] as the basis of a numerical method to solve unconstrained, convex (in the trajectories) problems. In this paper, we introduce appropriate occupation measures to relax this class of problem as a linear program over measures, and develop the subsequent moment-SOS relaxations resulting from this formulation. This allows to attack non-convex problems, and as importantly for practical applications, handle state constraints seamlessly.

Contribution

The method of moments has already been used in relaxations of optimal control problems with oscillations in [START_REF] Lasserre | Nonlinear optimal control: numerical approximation via moments and LMI relaxations[END_REF] and then [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] using occupation measures and moment-SOS techniques. See also [START_REF] Meziat | An alternative approach for non-linear optimal control problems based on the method of moments[END_REF] and its calculus of variations counterpart [START_REF] Meziat | Coarse-convex-compactification approach to numerical solution of nonconvex variational problems[END_REF] which do not use occupation measures but time-dependent moments and hence time-discretization, and which do not account for state constraints. Occupation measures and moment-SOS techniques were then used in [START_REF] Claeys | Measures and LMIs for non-linear optimal impulsive control[END_REF][START_REF] Claeys | Mesures d'occupation et relaxations semi-définies pour la commande optimale[END_REF] to cope with concentrations. In this paper, these techniques are extended (to our best knowledge for the first time) for optimal control problems with oscillations and concentrations. As a by-product, we describe explicitly how compactification techniques can be used to deal numerically with non-compact sets in the moment-SOS approach to optimal control.

Organization of the paper

The paper is organized as follows. Section 2 introduces the problem and recalls key results about DiPerna-Majda measures. Section 3 develops the primal linear program on measures, and also present its Hamilton-Jacobi Bellman dual. Section 4 details how this primal-dual pair can be solved via moment-SOS relaxations and semidefinite programming. Section 5 presents several extensions to the approach, relegated to this section for clearer exposition. Finally, 6 presents several relevant examples.

Notations

Let M(X) denote the vector space of finite, signed, Radon measures supported on an Euclidean subset X ⊂ R n , equipped with the weak-star 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). 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 use the duality bracket notation f, µ = f µ for the integral to simplify exposition and to insist on the duality relationship between C(X) and M(X) on compact 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, the subset of M + (X) with mass 1, µ = 1, is denoted by P(X).

Let T := [t 0 , t f ] denote a time interval, with t f > t 0 ≥ 0. We use standard notation for Lebesgue and Sobolev spaces, i.e. L p (T ; R m ) and W 1,1 (T ; R m ). Due to nonreflexivity of W 1,1 (T ; R m ) we are forced to enlarge the space of states (trajectories) to BV (T ; R m ), the space of functions of bounded variations on T . However, the standard definitions of the BV space does not take into account of jumps of function values at the boundary of the interval [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF] as it is typically defined on an open set. Nevertheless, we can choose a small ε > 0 and extend any absolutely continuous function y ∈ W 1,1 (T ; R m ) to (t 0 -ε; t f + ε) such that this extension ỹ satisfies ỹ(t) = y(0) for t ∈ [t 0 -ε; t 0 ) and ỹ(t) = y(t f ) for t > t f . Then we define BV (T ; R m ) as the set of restrictions to T of the weak-star (in the sense of BV) closure of the set {ỹ : y ∈ W 1,1 (T ; R m )}. In fact, this definition coincides with the so-called Souček space W 1,µ (T ; R m ) introduced in [START_REF] Souček | Spaces of functions on domain Ω, whose k-th derivatives are measures defined on Ω[END_REF] and used e.g. in [START_REF]Relaxation in optimization theory and variational calculus[END_REF].

For multi-index α ∈ N n and vector x ∈ R n , we use the notation x α := n i=1 x α i i for a monomial. 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 (z α ) α∈N n is said to have a representing measure on X if there exists µ ∈ M + (X) such that z α = 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 of R n is basic semi-algebraic if it is defined as the intersection of finitely many polynomial inequalities, namely {x ∈ R n :

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

Preliminaries

DiPerna-Majda measures

As the motivating examples reveal, the infimum of the optimal control problems might not be attained. For that reason, we have to construct a suitable locally compact convex hull of the Lebesgue spaces [START_REF]Relaxation in optimization theory and variational calculus[END_REF]. As already mentioned, we will use a special extension proposed by DiPerna and Majda [START_REF] Diperna | Oscillations and concentrations in weak solutions of the incompressible fluid equations[END_REF][START_REF] Kružík | On the measures of DiPerna and Majda[END_REF][START_REF] Roubíček | Adaptive approximation algorithm for relaxed optimization problems In Proceedings of "Fast Solutions of Discrete Optimization Problems[END_REF].

Let S m-1 denote the unit sphere in R m and let

R = v ∈ C b (R m ) : ∃ v 0 ∈ C b (R m ), v 1 ∈ C(S m-1 ), c ∈ R : lim |u|→∞ v 0 (u) = 0, v(u) = c + v 0 (u) + v 1 u |u| |u| p 1 + |u| p (3)
denote the complete separable subring of the ring C b (R m ) of bounded continuous functions on R m . The corresponding compactification of R m , denoted γR m , is then homeomorphic with the unit ball or equivalently the simplex in R m . This means that every v ∈ R admits a uniquely defined continuous extension on γR m (denoted then again by v without any misunderstanding) and conversely, for every v ∈ C(γR m ), the restriction on R m lives in R.

Let σ ∈ M + (T ), and let L ∞ w (T, σ; M(γR m )) denote the Banach space of all weakly σ-measurable 1 σ-essentially bounded mappings from T to the set of Radon measures M(γR m ) on γR m . Let U(T, σ; γR m ) denote the subset of L ∞ w (T, σ; M(γR m )) consisting of the mappings ν : t → ν(du|t) such that ν(du|t) is a probability measure on γR m for σ-almost all t ∈ T . DiPerna and Majda [START_REF] Diperna | Oscillations and concentrations in weak solutions of the incompressible fluid equations[END_REF] showed that, given a bounded sequence (u k ) k∈N in L p (T ; R m ), 1 ≤ p < +∞, there exists a subsequence (denoted by the same indices) and a measure η ∈ M + (T × γR m ) such that for any h 0 ∈ C(T × γR m ),

lim k→∞ T h(t, u k (t))dt = T γR m h 0 (t, u)dη(t, u) , (4)
where h(t, u) = h 0 (t, u)(1 + |u| p ). DiPerna-Majda measures are precisely all the measures M + (T × γR m ) that are attainable in the sense of (4) by some sequence in L p (T ; R m ).

For our purposes, it will be convenient to disintegrate a DiPerna-Majda measure η ∈ M + (T × γR m ) as a product of a time marginal σ ∈ M + (T ) and a state conditional ν ∈ U(T, σ; γR m ), i.e. η(dt, du) = ν(du|t)σ(dt).

By this, we mean that for any h 0 ∈ C(T × γR m ),

lim k→∞ T h(t, u k (t))dt = T γR m h 0 (t, u)ν(du|t)σ(dt), (5)
where h is related to h 0 as before. We say that such a pair (σ, ν) ∈ M(T ) × Y(T, σ; γR m ) is attainable by a sequence (u k ) k∈N ⊂ L p (T ; R m ). The set of all attainable pairs (σ, ν) is denoted by DM p (T ; R m ).

Given (σ, ν) ∈ DM p (T ; R m ) we denote by (σ, ν) the norm of total variation, i.e. the mass of the measure η(dt, du) := ν(du|t)σ(dt) ∈ M + (T × γR m ).

Control relaxations

We consider the following class of optimal control problems: minimize T l(t, y, u)dt

s.t. ẏ = f (t, y, u), y(0) = y 0 , y ∈ W 1,1 (T ; Y ), u ∈ L p (T ; R m ), ( 6
)
where Y is a given subset of R m . For this section and the next, we make the following integrability and growth conditions on the Lagrangian and dynamics:

Assumption 1 Lagrangian l(t, y, u) := a(t, y, u) + b(t, u) and dynamics f (t, y, u) := c(t, y, u) + d(t, u) are such that a : T × Y × R m → R is a Carathéodory function 2 , c : T × Y × R m → R n is a Carathéodory function, and b : T × R m → R is continuous, while satisfying max(|a(t, y, u)|, |c(t, y, u)|) ≤ α 1+ε (t) + β(|y| 1/ε + |u| p/(1+ε) ), ( 7
) b 0 ∈ C(T ; R),
where b 0 (t, u) := b(t, u)/(1

+ |u| p ), ( 8
) |c(t, y, u)| ≤ (α 1 (t) + β|u| p )(1 + |y|), (9) |a(t, y 1 , u) -a(t, y 2 , u)| ≤ (α 1 (t) + β|y 1 | 1/ε + β|y 2 | 1/ε + β|u| p/(1+ε) )|y 1 -y 2 |, (10) |c(t, y 1 , u) -c(t, y 2 , u)| ≤ (α 1 (t) + β|y 1 | 1/ε + β|y 2 | 1/ε + β|u| p/(1+ε) )|y 1 -y 2 |, (11) d 0 ∈ C(T ; R n ),
where

d 0 (t, u) := d(t, u)/(1 + |u| p ), (12) a
(t, y, u) + b(t, u) ≥ δ|u| p , (13)
with some ε > 0, δ ≥ 0, β ∈ R, α q ∈ L q (T ).

Note that if δ = 0 in (13), we must slightly adapt the discussion in the paper by bounding the set of admissible controls in L p (T ; R m ). This will result in an additional linear constraint in the measure LP and the moment relaxations, as explained in Section 5. Moreover, we really can admit only measurability in the first variables of a and c. The reason is their growth in the control variable which is smaller than p, namely at most p/(1 + ε).

As shown in [START_REF] Kružík | Optimization problems with concentration and oscillation effects: relaxation theory and numerical approximation[END_REF], DiPerna-Majda measures allow for the following relaxation of ( 6), which we refer to the "strong" problem (by opposition to a weak problem to defined later on):

minimize

T γR m l(t, y(t), u) 1 + |u| p ν(du|t)σ(dt) s.t. y(τ ) = y(t 0 ) + τ t 0 γR m f (t, y(t), u) 1 + |u| p ν(du|t)σ(dt), τ ∈ T, y ∈ BV (T ; R m ), (σ, ν) ∈ DM p (T ; R m ), (14)
where the differential equation is now expressed in integral form.

The natural embedding

i : L p (T ; R m ) → DM p (T ; R m ) u → (σ, ν) := ((1 + |u(t)| p )dt, δ u(t) (du|t)) (15)
establishes readily that ( 14) is really an extension of ( 6). In fact, the following two assertions justify that ( 14) is actually a legitimate relaxation of ( 6), see [START_REF] Kružík | Optimization problems with concentration and oscillation effects: relaxation theory and numerical approximation[END_REF] for proofs.

Proposition 1 Let (7)-( 9), [START_REF] Diperna | Oscillations and concentrations in weak solutions of the incompressible fluid equations[END_REF], and (12) be valid. Assume Y = R m and a fixed initial condition

y 0 ∈ R m . For k ∈ N, let y k solve ẏk = f (t, y k , u k ), y k (t 0 ) = y 0 , (16)
and let the sequence (u k ) k∈N attain (σ, ν) in the sense of (5). Then y k → y weakly star in BV(T ; R m ) and y k (t f ) → y(t f ), with y uniquely defined by

y(τ ) = y 0 + τ t 0 γR m f (t, y(t), u) 1 + |u| p ν(du|t)σ(dt), τ ∈ T. (17)
Hence, we can define a map π : DM p (T ; R m ) → BV (T ; R m ) such that π(σ, ν) = y where y is a solution to [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF].

Proposition 2 Let (7)-( 13) be valid. Assume Y = R m , a fixed initial condition y 0 and a free final state. Then the infimum in the original problem (6) is equal to the infimum in the strong problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF], which is attained. Moreover, every solution (σ, ν) ∈ DM p (T ; R m ) to the strong problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] is attainable in the sense of (5) by a minimizing sequence for the original problem (6), and, conversely, every minimizing sequence for the original problem (6) contains a subsequence converging in the sense of (5) to a solution of the strong problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF].

Remark 1 If we consider an additional constraint on state trajectories, i.e. y(t) ∈ Y for some compact Y ⊂ R n , Proposition 2 does not hold anymore in general. Indeed, consider (1), our first example in the introduction, with Y = {0, 1}. Then the infimum of ( 6) is infinity because the admissible set of states is empty, while the infimum of ( 14) is zero. Different boundary conditions and/or an explicit bound on the norm of the control might yield a similar relaxation gap. On the other hand, we know that if y ∈ BV (T ; R m ) is an optimal state (a solution) then y ∈ L ∞ (T ; R m ). Therefore, there is a closed ball B(0, R) in R m centered at the origin and of radius R which contains y. Therefore, taking Y := B(0, R) for R > 0 large enough, it is always possible to obtain a solution on the whole R m .

Proposition 1 establishes uniqueness of the Cauchy problem for the relaxed differential equation. This motivates the following handy definition for the remainder of the paper.

Definition 1 (Relaxed arc) A triplet (σ, ν, y) is called a relaxed arc for strong problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] if (σ, ν) ∈ DM p (T ; R m ) and y ∈ BV (T, Y ) satisfy [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF], as well as the boundary conditions of [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF].

We can readily prove the following result:

Proposition 3 Assume that there is a relaxed arc (σ, ν, y) for problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] such that (σ, ν) ≤ c for some c > 0. If y ∈ Y for every solution ẏ = c(t, y, u) + d(t, u), y(t 0 ) = y 0 where u ∈ L p (T ; R m ) is such that i(u) ≤ c then the corresponding relaxation result holds as in Proposition 2.

Weak linear program

This section constructs a weak linear program for relaxing optimal control problem (6), and explicits its dual. For ease of exposition, we assume that both boundary conditions in [START_REF] Bressan | On differential systems with vector-valued impulsive controls[END_REF] are prescribed (see Section 5 on how to relax this assumption). We also assume that Y is compact, since this is required anyway in the next section for manipulating measures by their moments. Finally, we assume δ > 0 in Assumption 1, so that we do not need to explicitly handle a bound on the L p norm of the control (see Section 5 again for how such a constraint would modify the discussion below).

Measure LP

We now define occupation measures based on DiPerna-Majda measures, in much the same way occupation measures can be constructed from Young measures, see e.g. [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF][START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF]. Problem [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] has relaxed control (σ, ν) as decision variables, both measures, but also the state trajectory y, considered now as a function of bounded variation. As such, the problem is not fully expressed as a linear program on measures, and cannot yet be solved by our moment-SOS approach. In this subsection, we therefore embed [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] into such a linear program, via an appropriate space-time reparametrization of the solution during the possible jumps. First of all, notice that the ODE of strong problem ( 14) is a measuredriven differential equation. Let σ = σ C + σ D denote the Lebesgue decomposition of measure σ, with its continuous (absolutely or singularly w.r.t. the Lebesgue measure) part σ C and its discrete part σ D supported on at most countably many points of J := (t j ) j∈N ⊂ T . When σ is continuous, so is the state trajectory y. When it is discrete, one may construct a properly defined space-time reparametrization of the state trajectory "during" the jumps, see [START_REF] Motta | Space-time trajectories of nonlinear systems driven by ordinary and impulsive controls[END_REF][START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF][START_REF] Dykhta | Hamilton-Jacobi inequalities in control problems for impulsive dynamical systems[END_REF]:

Definition 2 (Space-time reparametrization) A function y ∈ BV (T ; R n ) is a solu- tion to the ODE in (14) if it satisfies y(τ + ) = y(t - 0 ) + τ t 0 γR m f (t, y(t), u) 1 + |u| p ν(du|t) σ C (dt) + s∈J∩[t 0 ,τ ] y(s + ) -y(s -)
where y(s + ) and y(s -) are boundary conditions of the following ODE:

ẏs (t) = γR m f (s, y s (t), u) 1 + |u| p ν(du|t), t ∈ [0, σ D ({s})] y s (0) = y(s -), y s (σ D ({s})) = y(s + ) ( 18
)
with y s a fictitious state that evolves "during" the jump at s ∈ J.

Here y(t ± ) represent left and right limits of y(t), and we implicitly extend y(t) by a constant function outside of the interval T should jump discontinuities arise at its boundaries. Note that during jumps, we follow for the rest of the paper the convention that the state y s remains in Y , that is, we forbid arbitrarily fast violations of the state constraints during jumps. Given Proposition 1, the mere definition of relaxed control (σ, ν) guarantees the uniqueness of y, and hence of the space-time reparametrization as well. The reason to introduce Definition 2 is therefore not motivated by a desire for a well-defined concept of trajectory as in impulsive optimal control, but as a necessary step for defining an appropriate concept of occupation measure. Indeed, fix an admissible relaxed arc (σ, ν, y) and its associated space-time reparametrization (y s ) s∈J , and define a measure

ξ(B|u, s) = δ y(s) (B) if s / ∈ J σ({s}) 0 I B (ys(t)) σ({s}) dt if s ∈ J (19)
for any Borel set B ⊂ Y , where I B (y) denotes the indicator function equal to 1 if y ∈ B and 0 otherwise. Note that the normalization by σ({s}) ensures that ξ(B|s) is a probability measure. The notation ξ(dy|u, s) indicates that ξ is a conditional probability measure depending on control u (through the DiPerna-Majda measure (σ, ν)) and time s.

Definition 3 (Occupation measure) The occupation measure µ ∈ M + (T × Y × γR m ) associated to a given admissible relaxed arc (σ, ν, y) is defined by

dµ(t, y, u) := ξ(dy|u, t) ν(du|t) σ(dt) (20)
The following essential property reveals that the ODE in [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF] gives rise to linear constraints:

Proposition 4 Let µ be the occupation measure associated to admissible relaxed arc (σ, ν, y). Then for all test functions v(t, y) ∈ C 1 (T × Y ) it holds:

∂v ∂t 1 1 + |u| p + ∂v ∂y f (t, y, u) 1 + |u| p , µ = v(t f , y(t + f )) -v(t 0 , y(t - 0 )). ( 21
)
Proof : By the chain rule in BV ([1, Th. 3.96]), differentiating such test functions along the admissible trajectory leads to

v(t f , y(t + f )) -v(t 0 , y(t - 0 )) = T dv(t, y(t)) = T ∂v ∂t (t, y(t)) dt :=a 1 + T ∂v ∂y (t, y C (t)) dy C (t) :=a 2 + s∈J v(s, y(s + )) -v(s, y(s -)) :=a 3 (22)
where y C denotes the continuous part of the Lebesgue decomposition of y w.r.t. time. By [START_REF] Blaquière | Impulsive optimal control with finite or infinite time horizon[END_REF]

with v = g = 1, dt = γR m 1 1+|u| p ν(du|t) σ(dt)
, so that the first term is equal to

a 1 = ∂v ∂t (t, y) 1 1 + |u| p , µ . (23)
By Definition 3 and the fact that dy(t) = γR m 1 1+|u| p ν(du|t) σ(dt), the second term is equal to

a 2 = ∂v ∂y f (t, y, u) 1 + |u| p , µ C , (24)
where µ C is the continuous part of the Lebesgue decomposition of µ w.r.t. time. Finally, the last term can now be evaluated along graph completions using [START_REF] Henrion | Gloptipoly 3: Moments, optimization and semidefinite programming[END_REF]:

a 3 = s∈J σ({s}) 0 dv(t) = s∈J σ({s}) 0 γR m ∂v ∂y (s, y s (t)) f (s, y s (t), u) 1 + |u| p ν(du|s) dt = s∈J Y γR m ∂v ∂y (s, y) f (s, y, u) 1 + |u| p ξ(dy|u, s) ν(du|s) σ({s}) = ∂v ∂y f (t, y, u) 1 + |u| p , µ D , (25)
where µ D is the discrete part of the Lebesgue decomposition of µ w.r.t. time. Since µ = µ C + µ D , this concludes the proof.

Proposition 4 suggests to relax strong problem ( 14) as a linear program on measures, called hereafter the "weak" problem:

p * W = inf µ l(t, y, u) 1 + |u| p , µ s.t. ∂v ∂t 1 1 + |u| p + ∂v ∂y f (t, y, u) 1 + |u| p , µ = v(t f , y(t + f )) -v(t 0 , y(t - 0 )), ∀v ∈ C 1 (T × Y ) µ ∈ M + (T × Y × γR m ). ( 26
) Obviously, p * W is smaller than or equal to the infimum of [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF]. Note that it is conjectured that the values actually agree, as is the case for bounded controls, see [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]. In the next section, ( 26) is further relaxed to obtain a finite-dimensional, tractable problem. The absence of a relaxation gap is then simply tested a posteriori by observing that the finite-dimensional solution converges to a solution of [START_REF] Bressan | On differential systems with vector-valued impulsive controls[END_REF]. See also the examples in Section 6.

Dual conic LP

Before investigating the practical implications on semi-definite relaxations of measure LP [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[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 Hamilton-Jacobi-Bellman (HJB) inequalities. In addition, practical numerical resolution of the semidefinite programming (SDP) relaxations by primal/dual interior-point methods [START_REF] Sturm | Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones[END_REF] implies that a strengthening of this dual will be solved as well, as shown in Section 4.4.

In this section, it is first shown that the solution of ( 26) is attained whenever an admissible solution exists. Then, the dual problem of [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF], in the sense of conic duality, is presented. This leads directly to a HJB-type inequality. Although, the value 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 value of ( 26) is finite, there exists a vector of measures attaining the value of the problem:

Lemma 1 If p *
W is finite in problem [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF], there exists an admissible µ attaining the infimum, viz. such that l 1+|u| p , µ = p * W .

Proof : Observe that by coercivity of the cost, the mass of µ is bounded. Following Alaoglu's theorem [31, §15.1], the unit ball in the vector space of compactly supported measures is compact in the weak star topology. Therefore, any sequence of admissible solutions for (26) 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 (26) 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 * W = inf xp x p , c p s.t. A x p = b, x p ∈ E + p ( 27
)
with decision variable x p := µ ∈ E p := M(T × Y × γR m ), and cost c := l 1+|u| p ∈ F p := C(T × Y × γR m ). The notation x p , c p refers to the duality between E p and F p . The cone E + p is the non-negative orthant of E p . The linear operator A :

E p → [C 1 (T × Y )] ′ is the adjoint operator of A ′ : C 1 (T × Y ) → C(T × Y × γR m ) defined by v → A ′ v := ∂v ∂t 1 1 + |u| p + ∂v ∂y f (t, y, u) 1 + |u| p . ( 28
)
The right hand side is b :

= δ (t f ,y(t f )) (dtdy) -δ (t 0 ,y(t 0 )) (dtdy) ∈ E d := [C 1 (T × Y )] ′ .
Lemma 2 The conic dual of (26) is given by

d * = sup v v(t f , y(t f )) -v(t 0 , y(t 0 )) s.t. l(t,y,u) 1+|u| p -A ′ v(t, y) ≥ 0, ∀ (t, y, u) ∈ T × Y × γR m , v ∈ C 1 (T × Y ). (29)
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 ( 27) is given by

d * = sup x d b, x d d s.t. c -A ′ x d ∈ F + p , x d ∈ E d (30)
where decision variable Once the duality relationship established, the question arises of whether a duality gap may occur between linear problems [START_REF]Relaxation in optimization theory and variational calculus[END_REF] and [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF]. The following theorem discards such a possibility: Theorem 1 There is no duality gap between (29) and (26): if there is an admissible vector for (29), then

x d := v ∈ F d := C 1 (T × Y )
p * W = d * . (31)
Proof : Following [2, Th. To prove closure, one may show that, for any sequence of admissible solutions (x k p ) k∈N , all accumulation points of ( x k p , c p , A x k p ) k∈N belong to C. Note that Lem. 1 establishes that any sequence (x k p ) k∈N has a converging subsequence. Therefore, all that is left to show is the weak-star continuity of A. Following [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], this can be shown by noticing that A ′ is continuous for the strong topology of C 1 (T × Y ), hence for its associated weak topologies. Operators A is therefore weakly-star continuous, and each sequence ( x k p , c p , Ax k ) k∈N converges in C, which concludes the proof.

Note that what is not asserted in Theorem 1 is the existence of a continuously differentiable function for which the optimal cost is attained in dual problem [START_REF]Relaxation in optimization theory and variational calculus[END_REF]. Indeed, it is a wellknown 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 ( 26) is attained (whenever there exists an admissible solution), following Lem. 1. This furnishes practical motivations for approaching the problem via its primal on measures, as the dual problem will be solved anyway as a side product, see the later sections of this article.

Corollary 1 Let µ be admissible for [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF]. Then, there exists a sequence (v k ) k∈N ∈ C 1 (T × Y ), with each element admissible for [START_REF]Relaxation in optimization theory and variational calculus[END_REF] and such that lim k→∞ l(t, y, u)

1 + |u| p -Av k , µ = 0, ( 32
)
if and only if µ is a solution of [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF].

Proof : This corollary exploits weak duality via the complementarity condition

lim k→∞ x * p , c -A ′ x k d p = 0 if x *
p is optimal for the primal and x k d is minimizing for the dual, and exploits Lem. 1 guaranteeing the existence of an optimal x * p . This last corollary implies easy sufficient conditions for global optimality of the original and strong problem:

Corollary 2 Let u(t) be admissible for (6), resp. (σ, ν) be admissible for [START_REF] Gaitsgory | Linear programming approach to deterministic infinite horizon optimal control problems with discounting[END_REF]. Let µ be their corresponding occupation measure. If there exists a sequence (v k ) k∈N ∈ C 1 (T × Y ) satisfying the conditions of Cor. 1, then u(t) is globally optimal for (6), resp. (σ, ν) is globally optimal for (14).

Semidefinite relaxations

This section outlines the numerical method to solve [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF] in practice, by means of primaldual moment-SOS relaxations. First, the problem is transformed to avoid explicitly handling γR m . Then, when problem data is restricted to be polynomial3 , occupation measures can be equivalently manipulated by their moments for the problem at hand. Then, this new infinite-dimensional problem is truncated so as to obtain a convex, finite-dimensional relaxation (see Section 4.3). Finally, we present a simple approach to reconstruct approximate trajectories from moment data, if more than the globally optimal cost is needed.

In the remainder of the paper, we make the following standing assumptions: Assumption 2 All functions are polynomial in their arguments:

l, f ∈ R[t, y, u]. (33)
In addition, set Y is basic semi-algebraic, that is, defined by finitely many polynomial inequalities

Y = {y ∈ R n : g i (y) ≥ 0, i = 1, . . . , n Y } ( 34
)
with g i ∈ R[y], i = 1, . . . , n Y .
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 Y is assumed compact (see [START_REF] Lasserre | Positive polynomials and their applications[END_REF]Th. 2.15] for slightly weaker conditions).

Equivalent problem on compact sets

Set γR m prevents the definition of moments of the form u α , µ , since not all such polynomials are members of R. In addition, manipulating very large quantities is bound to pose numerical issues. To overcome this difficulty, we use the fact that γR m is homeomorphic to the unit ball or a simplex in R m , see [START_REF] Kružík | Optimization problems with concentration and oscillation effects: relaxation theory and numerical approximation[END_REF]. We leverage this necessary transformation to also remove the rational dependence in the control in [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF].

For precisely this last practical reason, we consider specifically the p-norm when expressing |u| as well as in the definition of B m , the unit ball in R m . Define the mapping

q : γR m → B m u → u (1 + |u| p ) 1 p (35)
with inverse

q -1 : B m → γR m w → w (1 -|w| p ) 1 p . ( 36
)
As both q and q -1 are continuous, q defines a proper homeomorphism. Define now the pushforward measure

γ(A × B × C) := µ(A × B × q -1 (C)) (37)
for every Borel subsets A, B, C respectively in T , Y , B m .

Finally, introduce the additional lifting variable

w 0 := 1 - m i=1 |w i | p 1/p .
This variable is easily constrained algebraically if, for instance, p is even, since constraints w 0 ≥ 0 and w p 0 = 1-m i=1 w p i uniquely determine w 0 . For clarity of exposition, we assume for the rest of the section that p is even, while common alternative cases are simply worked out in some examples in Section 6.

With these hypotheses in mind, notice that for multi-index α ∈ N m such that |α| ≤ p,

u α 1 + |u| p p , µ = w p-|α| 0 w α , γ . ( 38
)
That is, by homogenizing (with respect to the control) polynomials via the new variable w 0 , and using push-forward measure [START_REF] Young | Lectures on the calculus of variations and optimal control theory[END_REF], problem (26) may be reformulated as:

p * W = inf γ l(t, y, w), γ s.t. ∂v ∂t w p 0 + ∂v ∂y f , γ = v(t f , y(t f )) -v(t 0 , y(t 0 )) ∀v ∈ C 1 (T × Y ) γ ∈ M + (G) (39)
after defining

G := T × Y × W, W := (w 0 , w) ∈ [0, 1] × B m : w 0 ≥ 0, w p 0 = 1 - m i=1
w p i and where l and f are the homogenizations by w 0 with respect to the control of each term of resp. l and f . That is, we multiply each of these terms by an appropriate power of w 0 so that their degree with respect to the extended controls (w 0 , w) is equal to p.

Notice that (39) is a measure LP with purely polynomial data. Indeed, it is easy to see that the support G of γ can be described as a semi-algebraic set:

G = (t, y, w) ∈ R 1+n+1+m : g i (t, y, w) ≥ 0, i = 1, . . . , n G . ( 40
)
For ease of exposition (in the definition of moment matrices below), we also enrich the algebraic description of G with the trivial inequality g 0 (t, y, w) := 1 ≥ 0. In addition, again for ease of exposition, we formally consider equality constraints as two inequality constraints. Finally, without loss of generality since G is bounded, we make the following Assumption 3 One of the polynomials in the definition of set G in (40) has the form g i (t, y, w) := r -(t, y, w) 2 2 for a sufficiently large constant r.

Equivalent moment problem

This subsection details how measure LP (39) can be solved by an appropriate hierarchy of semidefinite programming (SDP) relaxations, since it possesses polynomial data.

We first rewrite (39) in terms of moments. Recall that the moment of degree α ∈ N n of a measure µ(dx) on X ⊂ R n is the real number4

z α = x α , µ . (41)
Then, given a sequence z = (z α ) α∈N n , let ℓ z : R[x] → R be the linear functional

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

γ g γ x γ ∈ R[x] as the real symmetric matrix M d (g y) whose entry (α, β) reads [M d (g z)] α,β = ℓ z g(x) x α+β (43) = γ g γ z α+β+γ , ∀α, β ∈ N n d . (44)
In the particular case that g(x) = 1, the localizing matrix is called the moment matrix. As a last definition, a sequence of reals z = (z α ) α∈N n is said to have a representing measure if there exists a finite Borel measure µ on X, such that relation (41) holds for every α ∈ N n .

The construction of the moment problem associated with (39) can now be stated. Its decision variable is the sequence of moments (z β ) β∈N 1+n+1+m of measure γ, where each moment is given by z β := e β , γ , β ∈ N 1+n+1+m , where e β are polynomials of R[t, y, w] defining its monomial basis5 :

e β := t β 1 y β 2 1 • • • y β n+1 n w β n+2 0 w β n+3 1 • • • w β 1+n+1+m m , β ∈ N 1+n+1+m . (45)
As each term of the cost of (39) is polynomial by assumption, they can be rewritten as

β∈N n+1+m+1 c β z β = ℓ z ( l). ( 46
)
That is, vector (c β ) contains the coefficients of polynomial l expressed in monomial basis (45).

Similarly, the weak dynamic constraints of (39) need only be satisfied for countably many polynomial test functions v ∈ R[t, y], since the measure γ is supported on a compact subset of R 1+n+1+m . Therefore, for the particular choice of test function

v α (t, y) := t α 1 y α 2 1 • • • y α n+1 n , α ∈ N 1+n , (47)
the weak dynamics define linear constraints between moments of the form

β∈N 1+n+1+m a α,β z β = b α := v α (t t , y(t f )) -v α (t 0 , y(t 0 )) (48)
where coefficients a α,β can be deduced by identification with

β∈N 1+n+1+m a α,β z β = ℓ z ( ∂v α ∂t w p 0 + ∂v α ∂y f (t, y, w)), α ∈ N 1+n . (49)
Finally, the only nonlinear constraints are the convex semidefinite constraints for measure representativeness. Indeed, it follows from Putinar's theorem [START_REF] Lasserre | Positive polynomials and their applications[END_REF]Theorem 3.8] that the sequence of moments z has a representing measure defined on a set G satisfying Assumption 3 if and only if M d (g i z) 0 for all d ∈ N and for all polynomials g i defining the set, where 0 means positive semidefinite.

This leads to the problem:

p * ∞ = inf z β∈N 1+n+1+m c β z β s.t. β∈N 1+n+1+m a α,β z β = b α , α ∈ N 1+n , M d (g i z) 0, i = 0, 1, . . . , n G , d ∈ N. (50)
Theorem 2 Measure LP (39) and infinite-dimensional SDP (50) share the same optimum:

p * W = p * ∞ . (51)
For the rest of the paper, we will therefore use p * W to denote the cost of measure LP (39) or infinite-dimensional SDP (50) indifferently.

Moment hierarchy

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

To streamline exposition, first notice in (50) that M d+1 (•) 0 implies M d (•) 0, such that when truncated, only the semidefinite constraints of highest order must be taken into account. Now, let d 0 ∈ N be the smallest integer such that all criterion, dynamics and constraint monomials belong to N 1+n+1+m 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 finitedimensional vector (z α ) α with α ∈ N Then, the SDP relaxation of order d is given by

p * d = inf z β∈N 1+n+1+m 2d c β z β s.t. β∈N 1+n+1+m 2d a α,β z β = b α , α ∈ N1+n 2d , M d (g i z) 0, i = 0, 1, . . . , n G . (52)
Notice that for each relaxation, we obtain a standard finite-dimensional SDP that can be solved numerically by off-the-shelf software. In addition, the relaxations converge asymptotically to the cost of the moment LP: Therefore, by solving the truncated problem for ever greater relaxation orders, we will obtain a monotonically non-decreasing sequence of lower bounds to the true optimal cost.

Theorem 3 p * d 0 ≤ p * d 0 +1 ≤ • • • ≤ p * ∞ = p * W . (53

SOS hierarchy

As for the measure LP of Section 3.1, the moment 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 sum-of-squares (SOS) strengthening of the dual outlined in Section 3.2. 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 methods are used for the moment hierarchy of Section 4.3.

Let S n be the space of symmetric n × n real matrices equipped with the inner product A, B := trace AB for A, B ∈ S n . In problem (52), let us define the matrices A i,β ∈ S 1+n+1+m+d 1+n+1+m

satisfying the identity

M d (g i z) = β A i,β z β ( 54
)
for every sequence (z β ) β and i = 0, 1, . . . , n G .

Proposition 5 The conic dual of moment SDP (52) is given by the SOS SDP

sup x,X α∈ N1+n 2d b α x α s.t. α∈ N1+n 2d a α,β x α + n G i=0 A i,β , X i = c β , β ∈ N 1+n+1+m 2d , X i ∈ S 1+n+1+m+d 1+n+1+m , X i 0, i = 0, 1, . . . , n G , x α ∈ R, α ∈ N1+n 2d . (55)
Proof : Replacing the equality constraints in (52) as two inequalities, moment relaxation (52) can be written as an instance of linear program [START_REF] Roubíček | Adaptive approximation algorithm for relaxed optimization problems In Proceedings of "Fast Solutions of Discrete Optimization Problems[END_REF], whose dual is given symbolically by [START_REF] Motta | Space-time trajectories of nonlinear systems driven by ordinary and impulsive controls[END_REF]. Working out the details leads to the desired result, using for semidefinite constraints the duality bracket as explained earlier.

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

Proposition 6 Semidefinite problem (55) can be stated as the following polynomial SOS strengthening of problem (29):

sup v(t f , y(t f )) -v(t 0 , y(t 0 )) s.t. l - ∂v ∂t w p 0 - ∂v ∂y f = n G i=0 g i s i , (56)
where the maximization is w.r.t. the vector of coefficients x of polynomial

v(t, y) = α∈ Nn+1 2d x α v α (t, y),
and the vectors of coefficients of polynomials

s i ∈ Σ[t, y, w], deg g i s i ≤ 2d, i = 0, . . . , n G .
Proof : By (48), the cost of ( 56) is equivalent to (55). Then multiply each scalar constraint (indexed by β) by monomial e β in definition (45), and sum them up. By definition, β c β e β = l. Notice also that β α a α,β x α e β = ∂v ∂t w p 0 + ∂v ∂y f . The conversion from the semidefinite terms to the SOS exploits their well-known relationship (e.g. [23, §4.2]) to obtain the desired result, by definition (43) of the localizing matrices. Prop. 6 specifies in which sense "polynomial SOS strengthenings" must be understood: positivity constraints of problem6 (29) are enforced by SOS certificates, and the decision variable of ( 29) 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 semidefinite pair (52-55).

Proposition 7

The infimum in primal problem (52) is equal to the supremum in dual problem (55), i.e. there is no duality gap.

Proof : By Assumption 2, one of the polynomials g i in the description of set Y enforces a ball constraint, and so does the ball constraint on W and the representation of the intervals. The corresponding localizing constraints M d (g i z)

0 then implies that the vector of moments z is bounded in semidefinite problem (52). 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].

Approximate solution reconstruction

Solving the hierarchy of primal/dual problems (52)/(55) simply yields a monotonically non-decreasing and converging sequence of lower bounds on the relaxed cost p * W . If actual trajectories and/or controls must also be reconstructed, additional computations must be carried out, since this information is encoded within the moments and the dual polynomial certificates.

We follow the simple strategy proposed in [START_REF] Claeys | Reconstructing trajectories from the moments of occupation measures[END_REF], which is well-suited to recover discontinuous trajectories. In this framework, a grid G ǫ of G is fixed, such that set G ǫ has finite cardinality and dist(z, G ǫ ) ≤ ǫ for all z ∈ G. Then, one seeks to minimize the distance between the truncated moment sequence of a measure supported on G ǫ , and the moments returned by any of the relaxations. The supremum norm is particularly interesting, since it corresponds to the truncation of the weak star norm on measures. Because G ǫ has finite cardinality, this optimization problem is a simple finite-dimensional linear program to solve with the atomic weights as decision variables. Obviously, as ǫ is decreased and the relaxation order is increased, those atomic measures approximate closely the moments of the global optimal occupation measure (assuming its uniqueness), and good approximation of controls and trajectories can be recovered. If high precision is required, those may later be refined by applying any local optimization technique, or by simply working out necessary optimality conditions based on the observed solution structure. Finally, note that to circumvent the exponential growth in the dimension of G of the computational method entails, one can simply identify one coordinate (state or control) at a time, by simply considering moments of time and that coordinate. Then, one only needs to grid the projection of G on a 2-dimensional grid, which is well within reach of current mid-scale LP solvers.

Extensions

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

v, µ 0 = v(t 0 , y(t 0 )), (57)
for all continuous test functions v(t, y) of time and space. That is, in weak problem (39), one replaces some of the boundary conditions by injecting (57) and making µ 0 an additional decision variable. In dual [START_REF]Relaxation in optimization theory and variational calculus[END_REF], this adds a constraint on the initial value of v and modifies the cost.

Similarly, a terminal occupation measure µ f can be introduced for free terminal states and/or time. Note that injecting both (57) and its terminal counterpart in (39) 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]Relaxation in optimization theory and variational calculus[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 ξ ∈ M + (Y 0 ) be the probability measure whose law describes such a distribution. Then, the additional constraints for (39) are v, µ 0 = Y 0 v(0, y) ξ(dy).

As remarked in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], this changes the interpretation of LP (39) 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 the probability ξ along the optimal flow.

Finally, integral constraints can be easily taken into account in our framework. For instance, if δ = 0 in Assumption 1, it is essential to add a constraint of the type T |u(t)| p dt ≤ u max in [START_REF] Bressan | On differential systems with vector-valued impulsive controls[END_REF], with u max a given bound on the norm of the control. This results in problem [START_REF] Miller | Impulsive control in continuous and discretecontinuous systems[END_REF] in additional linear constraint |u| p 1+|u| p , µ ≤ u max , hence in an additional scalar decision variable in the various dual problems.

Examples

This section presents several examples of the approach. Practical construction of the semidefinite relaxations were implemented via the GloptiPoly toolbox [START_REF] Henrion | Gloptipoly 3: Moments, optimization and semidefinite programming[END_REF], and solved numerically via SeDuMi [START_REF] Sturm | Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones[END_REF]. In this case, one can avoid the use of lift variable w 0 , since with the positivity constraint on u, we have simply w 0 = 1 -w 1 . Measure LP (39) is then expressed as inf γ,µ 1 Because we started with a cost rational in the control, there remains a rational expression in (62) despite the change of variables introduced in Section 4.1. This rational term can then treated by introducing the lifting variable r = (1-w) 3 w 2 (1-w) 4 +w 4 , constrained algebraically via the equation r((1 -w) 4 + w 4 ) = (1 -w) 3 w 2 .

Solving the problem with GloptiPoly leads at the fourth relaxation leads to moments of the form ℓ z (t k ) k∈N = (2.0026, 1.0026, 0.6692, 0.5026, 0.4026, 0.3359, . . .), ℓ z (w k ) k∈N = (2.0026, 1.0026, 1.0012, 0.9999, 0.9985, 0.9972, . . .) to be compared with the moments of the known optimal solution t k , γ * k∈N = (2.0000, 1.0000, 0.6667, 0.5000, 0.4000, 0.3333, . . .), w k , γ * k∈N = (2.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, . . .). The trajectory reconstructed with the method of Section 4.5 is given in Fig. 2. The reconstructed solution agrees with the true optimal solution. defined accordingly to the constraints in the optimal control problem. The trajectory reconstructed from moments of the 6th relaxation is reported back on Fig. 3, with a relaxation cost of p * 6 = 0.824. From this, it is easy to infer a candidate optimal trajectory involving an impulse of ≈ 0.273 at t = 0, followed by an impulse of ≈ -0.227 at t ≈ 0.318, followed by a control in feedback form of u = y 1 /(2y 2 + 1) to steer around the obstacle, followed by a free coasting arc. This admissible policy has a cost of ≈ 0.846, which, given the relaxation cost, strongly suggests its global optimality.

Weierstrass' example

Consider the optimal control problem inf (65)

Note the lack of coercivity in the cost integrand for t = 0, so that the standing Assumptions 1 are not met. Following [START_REF] Stein | Princeton lectures on analysis III. Real analysis: measure theory, integration, and Hilbert spaces[END_REF]Section 5.4] a minimizing sequence for this problem is

u k (t) = k if -1 k ≤ t ≤ 1 k , 0 otherwise. ( 66
)
Note however that lim k→∞ 1 -1

(u k (t)) 2 dt → ∞, such that the infimum cannot be attained by a DiPerna-Majda measure.

Solving the LP problem (39) with GloptiPoly leads to numerical issues, as the mass of γ grows without bounds at each relaxation, as expected. We are currently investigating suitable analytical and numerical frameworks to cope with this problem. However, if one introduces an additional L 2 norm on the control, the problem becomes tractable by our approach. The new optimal minimizing sequence will obviously be different from (66).

  and (pre-)dual cone F + p is the positive orthant of F p . The notation b, x d d refers to the duality between E d and F d . The lemma just details this dual problem.

  3.10] (see also the exposition in [3, § 4]), it is enough to show that the weak-star closure of the cone C := ( x p , c p , A x p ) : x p ∈ E + p belongs to R×E d .

)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 * W follows from [23, Theorem 3.8].

Figure 1 :

 1 Figure 1: Reconstruction trajectory for Example 6.1.

( 1 -

 1 w) 3 w 2 (1 -w) 4 + w 4 + (1 -w) (y 1 -t) 2 , γ s.t. ∂v ∂t (1 -w) + ∂v ∂y w, γ = v(1, •), µ 1 -v(0, y(0)), ∀v ∈ R[t, y] γ ∈ M + ([0, 1] 3 ), µ 1 ∈ M + (R)(62)

Figure 3 :

 3 Figure 3: Reconstruction trajectory for the example of Ex. 6.3.

u 1 - 1 t 2 u 2

 112 dt s.t. ẏ = u y(-1) = -1, y(1) = 1 u ∈ L 2 ([-1, 1]), u(t) ≥ 0.

This means that for any w ∈ R, the mapping t ∈ T → γR m w(u)ν(du|t) ∈ R is σ-measurable in the usual sense.

This means that a(t, •, •) : Y × R m → R is continuous for almost every t ∈ T and a(•, y, u) : T → R is measurable for all y and u.

This class of functions can cover a lot of cases in practice, see for instance the example in Section 6.2.

Most references on the subject use y instead of z for moments, but we reserve this symbol for trajectories in this paper.

This choice purely for ease of exposition, for numerical reasons other bases may be more appropriate, e.g. Chebyshev polynomials.

More exactly, the dual of (39), which is straightforward to explicit from[START_REF]Relaxation in optimization theory and variational calculus[END_REF] and map[START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF].

Obviously, we could make a simple substitution to make the problem affine in the control and use the more efficient relaxations of[START_REF] Claeys | Measures and LMIs for non-linear optimal impulsive control[END_REF]. This example is really to showcase the flexibility of our method.

Acknowledgment

This research was supported by a project between the Academy of Sciences of the Czech Republic (AV ČR) and the French Centre National de la Recherche Scientifique (CNRS) entitled "Semidefinite programming for nonconvex problems of calculus of variations and optimal control". The first author was also supported by the United Kingdom Engineering and Physical Sciences Research Council under Grant EP/G066477/1.

Simple impulse

We consider optimal control problem (1), our first motivating example. The unique solution is to apply an impulse of unit amplitude at t = 1 2 , such that minimizing sequences in L 2 tend weakly to the Dirac measure. Therefore, the optimal DiPerna-Majda measure is given by

The problem is rewritten as the measure LP (39), with 7 w 0 := 1 -w 2 1 algebraically constrained in the description of our semi-algebraic measure support G as w 2 0 = 1 -w 2 1 and w 0 ≥ 0:

Recall in particular that u = ∞ if and only if w 0 = 0. Solving the problem with GloptiPoly leads at the fifth relaxation to moments of the form ℓ z (t k ) k∈N = (2.0000, 1.0000, 0.5833, 0.3750, 0.2625, 0.1979, . . .), ℓ z (w k ) k∈N = (2.0000, 1.0101, 1.0000, 0.9943, 0.9903, 0.9873, . . .)

to be compared with the moments of the known optimal solution:

t k , γ * k∈N = (2.0000, 1.0000, 0.5833, 0.3750, 0.2625, 0.1979, . . .), w k , γ * k∈N = (2.0000, 1.0000, 1.0000, 1.0000, 1.0000, 1.0000, . . .).

Finally, Figure 1 shows the reconstructed trajectory using the method outlined in Section 4.5. The solution agrees with the true solution, even during the jump.

Smeared impulses

We consider now optimal control problem (2), our second motivating example. This sequence tends weakly to the DiPerna-Majda measure given by

with optimal trajectory given by y(t) = t.

Non-convex problem

We consider now a simplified planar orbital rendezvous problem constrained in a nonconvex domain:


Ismael Hernandez-Carrasco

J Sudre

Veronique Garcon

Hussein Yahia

Boris Dewitte

Christoph Garbe

Serena Illig

Ivonne Montès

A Paulmier

I Dadou

Validation of inferred high resolution ocean pCO2 and air-sea fluxes with in-situ and remote sensing data

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Titre: Validation of inferred super-resolution ocean pCO2 and air-sea CO2 fluxes with insitu and remote sensing data a) Introduction Submesocale activity is being recognized as of primary importance in global ocean processes such as for instance the precise determination of GHGs exchanges between the ocean and the atmosphere. The scarcity of oceanographic cruises and the lack of available satellite products for GHG concentrations at high resolution prevent from obtaining a global assessment of their spatial variability at small scales. In this ESA Oceanflux project, the teams are making use of non-linear signal processing methods for inferring super-resolution maps (pixels resolution: 4kms) of CO2 fluxes by setting up a novel methodology based on the determination of an optimal multiresolution analysis computed from singularity exponents associated to Sea Surface Temperature (SST), chlorophyl concentration and low resolution CO2 fluxes. The multiresolution analysis makes use of (MERIS, MODIS AVW-MERGED and GSM-MERGED products. We present validation experiments using in-situ boat campaigns data colocalized with the generated high resolution products. Validation has been performed in Benguela OMZ region. b) Method SIngularity exponents are important non-linear and multiscale characteristics of turbulent data [1, 2, 3]. They can be used to set up optimal inference across the scales of complex signals [START_REF] Yahia | Garçon Motion analysis in oceanographic satellite images using multiscale methods and the energy cascade Pattern Recognition[END_REF]. In this work, seasonal regression coefficients are computed from ROMS simulation outputs. We have been using globcolour merged products (AVW and GSM) for ocean colour to: increase the number of points in the ocean pCO2 field, to get more intersections for a wider validation for in-situ pCO2. We have also made comparison of inferred pCO2 from Globcolour with those from MERIS. In AVW CHL_a values are weighted by the relative error for each sensor on the simple averaging. In GSM we use fully normalized water leaving radiances.

c) Results

The validation analysis shows that values of superresolution pCO2 are closer to insitu pCO2 when we use merged ocean color (closer with GSM globcolour) . Analysis of the PDFs of pCO2 values show good agreement between inferred pCO2 and CarbonTracker (better for merged products). From singularity spectra analysis we obtain that the merged products improve the representation of the transition fronts (binomial cascade behaviour at small values of the singularity exponents).

d) Discussion & Conclusion

The methodology introduced in the ESA Oceanflux proposal is able to derive super resolution maps of GHGs fluxes validated by in-situ boat campaigns with excellents results which in particular are outperforming the outputs of simulation models such as CarbonTracker: not only the resolution, but the data itself is closer to in-situ data. As a consequence, the methodology presented in the ESA Oceanflux will serve as a tool for better quantitative evazluation of GHGs fluxes betwwen the ocean and the atmosphere. Bibliography

  [1] I. Hernandez-Carrasco, J. Sudre, V. Garçon, H. Yahia, B. Dewitte, C. Garbe, S. Illig, I. Montès, I. Dadou, A. Paulmier, A. Butz Inference of super-resolution ocean pCO2 and air-sea CO2 fluxes from non-linear and multiscale processing methods