Edouard Pauwels

Didier Henrion

Jean-Bernard Lasserre

Positivity certificates in optimal control

We propose a tutorial on relaxations and weak formulations of optimal control with their semidefinite approximations. We present this approach solely through the prism of positivity certificates which we consider to be the most accessible for a broad audience, in particular in the engineering and robotics communities. This simple concept allows to express very concisely powerful approximation certificates in control. The relevance of this technique is illustrated on three applications: region of attraction approximation, direct optimal control and inverse optimal control, for which it constitutes a common denominator. In a first step, we highlight the core mechanisms underpinning the application of positivity in control and how they appear in the different control applications. This relies on simple mathematical concepts and gives a unified treatment of the applications considered. This presentation is based on the combination and simplification of published materials. In a second step, we describe briefly relations with broader literature, in particular, occupation measures and Hamilton-Jacobi-Bellman equation which are important elements of the global picture. We describe the Sum-Of-Squares (SOS) semidefinite hierarchy in the semialgebraic case and briefly mention its convergence properties. Numerical experiments on a classical example in robotics, namely the nonholonomic vehicle, illustrate the concepts presented in the text for the three applications considered.

Introduction 1.Context

In the context of understanding and reproducing human movements and more generally in motion control, there has recently been a growing interest in using optimal control to model and account for the complexity of underlying processes [START_REF] Arechavaleta | An optimality principle governing human walking[END_REF][START_REF] Chittaro | On inverse optimal control problems of human locomotion: stability and robustness of the minimizers[END_REF][START_REF] Friston | What is optimal about motor control?[END_REF][START_REF] Laumond | Optimality in robot motion: optimal versus optimized motion[END_REF][START_REF] Majumdar | Convex Optimization of Nonlinear Feedback Controllers via Occupation Measures[END_REF][START_REF] Mombaur | From human to humanoid locomotionan inverse optimal control approach[END_REF][START_REF] Puydupin-Jamin | A convex approach to inverse optimal control and its application to modeling human locomotion[END_REF][START_REF] Todorov | Optimality principles in sensorimotor control[END_REF]. The question of the validity of this approach is still open and the interface between optimal control and human locomotion is an active field of research.

The so-called weak formulation of optimal control problem has a long history in the control community [START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF][START_REF] Hernández-Hernández | The linear programming approach to deterministic optimal control problems[END_REF][START_REF] Friston | What is optimal about motor control?[END_REF], see also [9, Part III] for a detailed historical perspective. This approach comes with a rich convex duality structure [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF], one side of which involves functional non negativity constraints. This type of constraints constitutes the focus of this paper.

In general, functional positivity constraints are not tractable computationally. Advances in semialgebraic geometry on the representation of positive polynomials [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] have allowed to construct provably convergent hierarchies of sums-of-squares approximations to this kind of intractable constraints when the problem at hand only involves polynomials [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF][START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]. Based on semidefinite programming [START_REF] Vandenberghe | Semidefinite programming[END_REF], these approximations provide a new perspective on infinite dimensional linear programs and functional non negativity constraints, along with tractable numerical approximations. Application of these hierarchies in control lead to the design of new methods to address control problems with global-optimality guaranties [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Parrilo | Semidefinite programming relaxations and algebraic optimization in Control[END_REF][START_REF] Henrion | Solving nonconvex optimization problems -How Glop-tiPoly is applied to problems in robust and nonlinear control[END_REF][START_REF]Positive polynomials in control[END_REF][START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF].

Content

This paper is a tutorial which focuses on the application of infinite dimensional conic programming approach to control problems. This constitutes a very relevant tool for the human locomotion and humanoid robotics research communities. Indeed the sums-ofsquares (SOS) hierarchy provides a systematic numerical scheme to solve related practical control problems. We will illustrate the power of this approach by focusing on three such particular problems, namely:

• region of attraction approximation.

• direct optimal control.

• inverse optimal control. The infinite dimensional linear programming approach combined with its associated SOS hierarchy of approximations has been applied to these problems in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF][START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF]. All in all, the contents of this paper is not new and is merely based on existing materials from the control and sums-of-squares approximations literature. The purpose of the paper is to reveal and highlight a few simple mechanisms and ideas that constitute a common denominator of all these applications.

Being concerned with accessibility to a broad audience, we deliberately hide important aspects of the approach. In particular, we focus on functional positivity constraints (one side of a coin in this approach) because we think that this is the most accessible way to present a general intuition regarding the weak formulation of optimal control problems. Another reason is that this simple notion of positivity allows to provide very strong sub-optimality certificate stemming from elementary mathematics. Other facets of the same problem (the other side of the coin described in the dual of the infinite-dimensional linear program), including conic duality and details about the weak formulation of control problems on occupation measures, are only briefly mentioned in a second step with very few details. Indeed, this material is often perceived as more technical and less accessible from a mathematical point of view. Although we do not emphasize much the moment relaxation approximation and its relation with occupation measures, it would provide a more complete picture to speak about the moment-SOS hierarchy (instead of the SOShierarchy) because each semidefinite program of the SOS-hierarchy of approximations of functional positivity constraints has a dual (also a semidefinite program) which deals with "moments" of occupation measures. We mention this point only briefly and invite the reader interested in more details about these aspects to consult the existing literature.

Organization of the paper

The optimal control problem and its value function are introduced in Section 2. In Section 3, we introduce functional positivity constraints which involve surrogate value functions. We discuss implications of these types of constraints in the context of optimal control, and in particular we describe how they relate to the approximation of the value function. This constitutes a general and flexible core result that is useful in the control applications that we consider. Section 4 illustrates the concept in several control problems dealing with (i) the approximation of region of attraction, (ii) optimal control and (iii), inverse optimal control. Finally, Section 5 discusses connections with the optimal control literature and additional aspects of the approach that we do not describe explicitly. We also briefly describe how the sums-of-squares hierarchy of approximations can be implemented and discuss convergence issues.

Optimal control and value function 2.1 Notations and preliminaries

If A is a subset of R n , C(A) denotes the space of continuous functions from A to R while C 1 (A) denotes the space of continuously differentiable functions from A to R. Let X ⊆ R d X and U ⊆ R d U denote respectively the state and control spaces, both supposed to be compact. The system dynamics is given by a continuously differentiable vector field f ∈ C 1 (X × U ) d X . Terminal state constraints are represented by a given compact set X T ⊆ X. Given all the above ingredients one may define admissible trajectories in the context of optimal control. We will use the following definition.

Definition 1 (Admissible trajectories) Consider an initial time t 0 ∈ [0, 1] and a pair of functions (x, u) from [t 0 , 1] to R d X and R d U respectively. This pair constitutes an admissible trajectory if it has the following properties:

• u is a measurable function from [t 0 , 1] to U . • For any t ∈ [t 0 , 1], x(t) = x 0 + t t 0 f (x(s), u(s))ds. • x(1) ∈ X T .
Given x 0 ∈ X, denote by traj t 0 ,x 0 the set of such admissible trajectories starting at time t 0 with x(t 0 ) = x 0 . Note that the second property implies that x is differentiable almost everywhere as a function of t, with ẋ(t) = f (x(t), u(t)) for almost all t ∈ [t 0 , 1].

The class of admissible trajectories constitutes the decision variables of an optimal control problem.

Optimal control and value function

An optimal control problem consists of minimizing a functional over the set of admissible trajectories. The functional has a specific integral form involving a continuous Lagrangian l ∈ C(X × U ) and a continuous terminal cost l T ∈ C(X T ). Given an initial time t 0 ∈ [0, 1] and a starting point x 0 ∈ X, consider the infimum value:

v * (t 0 , x 0 ) := inf 1 t 0 l(x(t), u(t))dt + l T (x(1)) s.t. (x, u) ∈ traj t 0 ,x 0 (OCP)
of the functional over all admissible trajectories. It is a well defined value that only depends on t 0 and x 0 and v * : [0, 1] × X → R ∪ {+∞} is called the value function associated with the optimal control problem.

Note that the constraints in (OCP) ensure that we only consider admissible trajectories starting from x 0 at t 0 , and therefore if traj t 0 ,x 0 is empty then v * (t 0 , x 0 ) = +∞.

Bounds on the value function

The value function introduced in (OCP) can be a very complicated object. The existence of minimizing sequences, the question of the infimum being attained and the regularity of v * are all quite delicate issues. In this section we show that functional positivity constraints that are expressible in a simple form lead to powerful approximation results. In addition, and remarkably, a striking feature of these results is that their proof arguments are elementary. We now focus on the description of these constraints while their origin and connection with control theory are postponed to Section 5.

Global lower bounds

We let "•" denote the dot product between two vectors of the same size. For a given function v ∈ C 1 ([0, 1] × X), consider the following positivity conditions:

l(x, u) + ∂v ∂t (x, t) + ∂v ∂x (x, t) • f (x, u) ≥ 0 ∀(x, u, t) ∈ X × U × [0, 1] (1)
l T (x) -v(T, x) ≥ 0 ∀x ∈ X T .
Note that these conditions are indeed functional positivity constraints since both of them must hold for all arguments in certain sets. How to ensure or approximate such conditions in practical situations is discussed in Section 5.3. We focus for the moment on the consequences of condition (1) in terms of control, the following proposition being an elementary, yet powerful example.

Proposition 1 (Global lower bound on the value function)

If v ∈ C 1 ([0, 1] × X)
satisfies condition (1) then v(t 0 , x 0 ) ≤ v * (t 0 , x 0 ) for any x 0 ∈ X and t 0 ∈ [0, 1].

Proof : Fix x 0 ∈ X and t 0 and consider the set traj t 0 ,x 0 of admissible trajectories starting at x 0 at time t 0 as described in Definition 1. If this set is empty then v * (t 0 , x 0 ) = +∞. Since v is continuous on a compact set, it is bounded and hence finite at (t 0 , x 0 ) which ensures that v(x 0 , t 0 ) ≤ v * (x 0 , t 0 ). If traj t 0 ,x 0 is not empty, consider an arbitrary but fixed admissible trajectory (x, u) : [t 0 , 1] → X × U which satisfies all the requirements of Definition 1 with x(t 0 ) = x 0 . Combining admissibility with the first condition in (1) yields:

l(x(t), u(t)) + ∂ ∂t [v(t, x(t))] = l(x(t), u(t)) + ∂v ∂t (t, x(t)) + ∂v ∂x (t, x(t)) • ẋ(t) = l(x(t), u(t)) + ∂v ∂t (t, x(t)) + ∂v ∂x (t, x(t)) • f (x(t), u(t)) ≥ 0, for almost all t ∈ [t 0 , 1].
Integrating between t 0 and 1, and using non negativity of the first term, we obtain

1 t 0 l(x(t), u(t)) dt + v(1, x(1)) -v(t 0 , x 0 ) ≥ 0.
Combining with the second condition in (1) yields

v(t 0 , x 0 ) ≤ 1 t 0 l(x(t), u(t)) dt + l T (x(1)).
Since (x, t) was arbitrary among all admissible trajectories, this inequality is still valid if we take the infimum in the right hand side, which coincides with the definition of v * in (OCP), and the proof is complete.

Proposition 1 provides a sufficient condition to obtain global lower bounds on the value function v * . A remarkable property of this condition is that it does not depend explicitly on v * . In particular, condition (1) does not depend explicitly on regularity properties of v * or on the existence of optimal trajectories in (OCP). Furthermore, they are expressed in a relatively compact form and the proof arguments are elementary.

Local upper bounds

We now turn to upper bounds on the value function v * of problem (OCP). First, observe that if the set of admissible trajectories is empty in (OCP) then v * (t 0 , x 0 ) = +∞. Hence upper bounding v * using a continuous function only makes sense when the set of admissible trajectories is not empty. Therefore such upper bounds depend on admissible trajectories and only hold in a certain "local sense". In particular, global upper bounds do not exist in general, whence the local characteristic for the type of bounds derived in this section. We introduce the following notation Definition 2 (Domain of the value function) Denote by V ⊂ [0, 1] × X the domain of v * , that is, the subset of [0, 1] × X on which v * takes finite values,

V := {(t 0 , x 0 ) ∈ [0, 1] × X : traj t 0 ,x 0 = ∅}
Consider a fixed pair (t 0 , x 0 ) ∈ V and a fixed admissible trajectory (x, u) ∈ traj t 0 ,x 0 , starting at x 0 at time t 0 . For a given ≥ 0, the following conditions are a counterpart to the positivity condition in [START_REF] Arechavaleta | An optimality principle governing human walking[END_REF].

l(x(t), u(t)) + ∂v ∂t (t, x(t)) + ∂v ∂x (t, x(t)) • f (x(t), u(t)) ≤ 2 , for almost all t ∈ [t 0 , 1] (2) l T (x(T )) -v(1, x(1)) ≤ 2 .
They can be used to obtain the following upper approximation result.

Proposition 2 (Local upper bound on the value function) Let (t 0 , x 0 ) ∈ V be fixed. Let (x, u) ∈ traj t 0 ,x 0 be an admissible trajectory starting at x 0 at time

t 0 . Assume that v ∈ C 1 ([0, 1] × X) satisfies condition (2) for a given > 0. Then v * (t, x(t)) ≤ v(t, x(t)) + for all t ∈ [t 0 , 1].
In addition, if v satisfies condition (1) then (x, u) is at most sub-optimal for problem (OCP): feasible with objective value at most greater than the optimal value.

Proof : Following similar integration arguments as in the proof of Proposition 1, using the first part of condition (2) yields:

1 t l(x(s), u(s)) ds + v(1, x(1)) -v(t, x(t)) ≤ (1 -t) 2 ≤ 2 , ∀ t ∈ [t 0 , 1],
and combining with the second part of condition (2),

1 t l(x(s), u(s)) ds + l T (x(1)) ≤ l T (x(1)) -v(1, x(1)) + v(t, x(t)) + 2 ≤ v(t, x(t)) + , for all t ∈ [t 0 , 1].
As the left hand side is an upper bound on v * (t, x(t)), the first statement follows. In addition, if condition ( 1) is satisfied then we can use Proposition 1 at (t, x(t)) to obtain:

1 t l(x(s), u(s)) ds + l T (x(1)) ≤ v * (t, x(t)) + .
In particular, letting t = t 0 in the previous relation yields that (x, u) is at most -suboptimal for problem (OCP).

Again, a remarkable property of condition [START_REF] Athans | Optimal control. An introduction to the theory and its applications[END_REF] is that it depends neither on the regularity of v * nor on the existence of optimal trajectories and still provides powerful sub-optimality certificates. Note that Proposition 2 characterizes properties of v * only along the specific chosen trajectory, whence the name "local" for this type of bounds.

Applications in control

In this section, we consider applications in control and show how conditions ( 1) and ( 2) can be used to solve control problems.

The general methodology is to use conditions ( 1) and ( 2) as constraints in combination with additional constraints and linear objective functions depending on the application.

The reason why this is relevant and produces valid practical methods comes from the connection with Propositions 1 and 2. Depending on the problem at hand, definition of objective functions or addition of constraints allow to provide a systematic numerical scheme to solve the control problems we consider: approximating the region of attraction of a controlled system, solving optimal control and inverse optimal control problems, provided that they are described with polynomials and semi-algebraic sets (see also Section 5.3). All the material of this section is based on reformulation and simplification of the work presented in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF].

Region of attraction

The region of attraction is a subset of the domain of the value function, V in Definition 2, corresponding to a fixed initial time t 0 . In other words, we are looking for the set X 0 of initial conditions, x 0 , for which there exists an admissible trajectory starting in state x 0 at a given time t 0 .

Definition 3 (Region of attraction) The region of attraction at time t 0 , denoted by X 0 ⊂ X, is the set that satisfies

X 0 = {x 0 ∈ X : traj t 0 ,x 0 = ∅} ,
where traj t 0 ,x 0 is the set of admissible trajectories as given in Definition 1. Following Definition 2, we have

{t 0 } × X 0 = V ∩ {t 0 } × X.
This exactly corresponds to the situation where l = 0 and l T = 0 in (OCP). Indeed, in this case, v * becomes the indicator of X 0 (equal to 0 on X 0 and +∞ otherwise) and the optimal control problem is a feasibility problem.

Condition (1) becomes

∂v ∂t (x, t) + ∂v ∂x (x, t) • f (x, u) ≥ 0 ∀(x, u, t) ∈ X × U × [0, 1] (3) v(T, x) ≤ 0 ∀x ∈ X T
and Proposition 1 has the following consequence.

Corollary 1 If v ∈ C 1 ([0, 1] × X) satisfies condition (3) then v(x 0 , t 0 ) ≤ 0 for any x 0 ∈ X 0 .
Corollary 1 states that X 0 is contained in the zero sublevel set of v whenever v satisfies condition (3). However this is not sufficient to have a good approximation of X 0 and condition (3) is not strong enough to distinguish between accurate and rough sublevel set approximations of this type. In order to sort out accurate candidates v, a possibility is to search among all functions which satisfy condition (3) an "optimal" one, e.g., in the sense that it should be as much as possible greater than 0 outside of X 0 . Following [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF], we introduce an additional decision variable w ∈ C(X). We will construct an optimization problem which ensures that w is non positive on X 0 and as close as possible to 1 on X \X 0 . This can be obtained by combining Corollary 1 with additional positivity constraints and a linear objective function. The following problem is a reformulation of problem ( 16) in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF]. sup

v,w X w(x)dx s.t. 0 ≤ ∂v ∂t + ∂v ∂x • f 0 ≤ -v(T, •) w(•) ≤ v(•, t 0 ) w ≤ 1. (4)
In problem (4), the first to constraints are exactly condition (3) and corollary 1 ensures that v(•, t 0 ) ≤ 0 on X 0 . Therefore, the third constraint ensures that w ≤ 0 on X 0 . The last constraint combined with the objective function allow to "choose" w as close as possible to 1 on X \X 0 . In general the supremum in (4) is not attained, but any candidate solution w, is such that its zero sublevel contains X 0 and remains close to it in a certain sense. Indeed it what shown in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] that the supremum in ( 4) is equal to the volume of X 0 and this quantity can be approximated by hierarchies of semidefinite approximations which we describe in Section 5.

Optimal control

In this section, we fix t 0 and x 0 . As described in Section 3, condition (1) provides a global lower bound on v * . However, the family of functions v which satisfy this condition is too large. For example, if l ≥ 0 and l T ≥ 0, then v = 0 satisfies condition (1) and does not provide much insight regarding solutions of (OCP). Therefore, one should design a way to choose lower bounds of specific interest. In the (direct) optimal control problem, one is interested in the value v * (t 0 , x 0 ). Hence an informal approach is to choose among all v that satisfy condition (1) one for which v(t 0 , x 0 ) is close to v * (t 0 , x 0 ). Note that under condition (1) we already have v(t 0 , x 0 ) ≤ v * (t 0 , x 0 ) and hence it is sufficient to look for a function v such that v(t 0 , x 0 ) is as large as possible. This leads to the following optimization problem. sup

v v(t 0 , x 0 ) s.t. 0 ≤ l + ∂v ∂t + ∂v ∂x • f 0 ≤ l T (•) -v(T, •). (5)
In general the supremum is not attained. Furthermore, for most reasonable practical situations, the value of the problem is exactly v * (t 0 , x 0 ), providing a valid conceptual solution to the optimal control problem.

At this point a remark is in order. Solutions of problem (5) allow to approximate from below the value function v * . In this respect they provide solutions of (OCP) because of their relations to v * which is the value of specific interest. However, this approach does not give access to an optimal trajectory which achieves this optimal value. Indeed, without further assumptions, the existence of such an optimal trajectory is not guaranteed. In order to compute optimal trajectories, further conditions are required in combination with additional methods to search for optimal trajectories. When such a method is available, it is always possible to combine it with solutions of (5) by using condition (2) and Proposition 2 to certify the sub-optimality of the computed trajectory.

Inverse optimal control

In inverse optimal control the situation is somewhat reversed compared to direct optimal control. The Lagrangian is unknown but we are given a set of trajectories that should be optimal with respect to the unknown Lagrangian. So the goal is to find a Lagrangian for which the given trajectories are optimal. In Figure 1, we display an informal description of this problem and its relation with the direct optimal control problem in the framework of positivity certificates. Briefly, the main goal is to infer a cost function (a Lagrangian) which can generate a set of given trajectories through an optimality process. The applications of this are twofold:

• Provide a tool for applications in which one assumes the existence of an optimality process behind decisions.

• Provide a modeling tool which could allow to summarize and reproduce the behaviour of observed systems.

In the rest of this section, we fix an admissible trajectory (x, u) starting from x 0 ∈ X 0 at time 0. We suppose that the state trajectory x as well as the control trajectory u are given and we look for candidate Lagrangians. The whole methodology naturally extends to an arbitrary number of trajectories. Actually, the higher the number of trajectories, the better and the more (physically) meaningful is the characterization of the candidate Lagrangian that we are looking for. However for clarity of exposition, the approach is better understood when we consider a single given trajectory.

In order to provide a solution to the inverse problem, we combine conditions (1) and ( 2). The relevance of doing this comes from Proposition 2 which provides a sub-optimality certificate. In addition, we enforce l T = 0 in order to simplify the problem and avoid the multiplication of non identifiabilities. Among all potential certificates we look for the one that provides the smallest sub-optimality gap as described in Proposition 2. This leads to the following optimization problem.

System description: f, X, U, X Output: Lagrangian l Figure 1: Direct optimal and inverse optimal control flow chart. The dynamical system is described through the dynamics f , the state constraint set X, control constraint set U and terminal state constraint set X T which are all given. We emphasize that the Lagrangian and the trajectories have symmetric roles for the direct and inverse problems.

In particular, the output of the inverse problem is a Lagrangian.

inf

,l,v s.t. 0 ≤ l + ∂v ∂t + ∂v ∂x • f 0 ≤ l T (•) -v(T, •) 2 ≥ l(x(t), u(t)) + ∂v ∂t (t, x(t)) + ∂v ∂x (t, x(t)) • f (x(t), u(t)) ∀t ∈ [0, 1] 2 ≥ l T (x(T )) -v(1, x(1)). ( 6
)
By Proposition 2, if l is a Lagrangian part of a feasible solution ( , l, v) for problem [START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF], then the trajectory (x, u) is -sub-optimal for problem (OCP) with Lagrangian l. In other words, every feasible solution ( , l, v) of ( 6) provides us with an -sub-optimality certificate for the trajectory (x, u). However, this is not sufficient. Indeed, problem (6) always admits the trivial solution (0, 0, 0) and it turns out that this solution is also valid from a formal point of view. Indeed, every admissible trajectory is optimal for the trivial null Lagrangian, and therefore, from the point of view of inverse optimality, the null Lagrangian is a valid (but not satisfactory) solution. To avoid trivial Lagrangians, additional constraints on l are needed. We will settle upon problem [START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF] as it highlights the main mechanism behind positivity in inverse optimal control and invite the reader to see [START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF] for further discussions and more details about application in practical situations.

Duality, Hamilton-Jacobi-Bellman, SOS reinforcement and convergence

The results presented so far without much context elements are related to principles which have a long history in optimal control theory. In this section we mention a few of them and we also comment on how to use these results in practical contexts through the SOS hierarchy.

Occupation measures

The constraints imposed in ( 1) have a conic flavor as they combine linear operators and positivity constraints. The space of continuous functions that are nonnegative on a given set form a convex cone. This cone admits a (convex) dual cone, see [4, Chapter IV] for a description of conic duality in Banach spaces. Representation results of Riesz type ensure that this dual cone can be identified with that of nonnegative measures on the same set.

As is classical for duality in convex optimization:

• To the inequality constraints appearing in the conic optimization problem (1) are associated nonnegative dual variables in the dual conic optimization problem, and

• to the variables appearing in (1) are associated constraints on these dual variables.

The constraints in the dual problem describe a transport equation satisfied by the dual variables, more precisely the transport along the flow followed by admissible trajectories in Definition 1. These dual variables are called "occupation measures", see e.g. [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF] for an accurate description.

In other words, the dual counterpart of condition (1) allows to formally work with generalized trajectories instead of classical ones. Whence the name "relaxation" for this approach. Equivalently, one speaks of "weak formulation" of the optimal control problem (OCP) because the differential equation is replaced by a weaker constraint (the transport equation for occupation measures). One main benefit of working with weak formulations is that the question of attaining the infimum is solved, at least from a theoretical point of view, under weak conditions, e.g. compactness of the sets X and X T ). However, the relaxed problem is not equivalent to the original problem, and its optimal value may be smaller. But for most reasonable practical situations, there is no relaxation gap and the optimal values of both problems are the same [START_REF] Vinter | Convex duality and nonlinear optimal control[END_REF][START_REF] Vinter | The equivalence of strong and weak formulations for certain problems in optimal control[END_REF]. Although the use of occupation measures is much less popular than classical differential equations in the engineering community, it is classical in Markov processes and ergodic dynamical systems. Furthermore, understanding this dual aspects is crucial in the framework of positivity constraints that we describe.

Hamilton-Jacobi-Bellman equation

Conditions ( 1) and ( 2) have the same flavor and structure as the well known Hamilton-Jacobi-Bellman (HJB) sufficient optimality conditions (see e.g. exposition in [START_REF] Athans | Optimal control. An introduction to the theory and its applications[END_REF]). In fact, if we combine (1) with ( 2) with = 0, we recover exactly the same condition. This provides a certificate of optimality for a given trajectory. However, this condition is not necessary. Indeed if the value function v * is not smooth (which is the case in most practical situations) then it is not possible to fulfill this condition in the classical sense.

Whence the use of a relaxed condition involving > 0 that measures how far we are from the true optimality condition. Another possible workaround is the use of the elegant viscosity solution concept to define "solutions" of HJB equation [START_REF] Bardi | Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations[END_REF]. This involves a lot more sophisticated mathematical machinery, far beyond the scope of this paper.

SOS reinforcement

Finally, conditions (1) and ( 2) are actually positivity constraints for functions. Moreover, all the examples presented in Section 4 consist of combining these constraints with additional constraints of the same type and linear objective functions. In full generality this type of constraints is not amenable to practical computation. In order to be able to use the results of this paper to actually solve control problems, involving some practical "algorithm", we need to enforce more structure on the objects we manipulate. A now widespread approach is to work with the following assumption.

Assumption 1 The dynamics f , the Lagrangian l and the terminal cost l T are polynomials. Constraints set X, U and X T are compact basic semi-algebraic sets.

Recall that a closed basic semi-algebraic set G can is defined by inequalities involving a finite number of polynomials g 1 , . . . , g q ∈ R [X]:

G = {x : g i (x) ≥ 0, i = 1, . . . , q} . (7)
Given a family of sum-of-squares (SOS) polynomials p 0 , p 1 , . . . , p q , hence nonnegative, it is direct to check that the following polynomial P in Putinar form

P = p 0 + q i=1 p i g i , (8)
is nonnegative on G. Checking whether a given polynomial is a SOS reduces to solving a semidefinite program and is thus amenable to efficient practical computation [START_REF] Vandenberghe | Semidefinite programming[END_REF]. Actually dedicated software tools exist [START_REF] Löfberg | Pre-and post-processing sum-of-squares programs in practice[END_REF]. Hence under Assumption 1, if v is a polynomial then Condition 1 can be enforced by semidefinite constraints. This is of course an approximation and in fact the SOS constraints [START_REF] Chittaro | On inverse optimal control problems of human locomotion: stability and robustness of the minimizers[END_REF] are stronger than the original positivity constraints, whence the name "reinforcement". But a counterpart of this approximation is that it is amenable to practical computation on moderate size problems which is not the case for general positivity constraints. Figure 2: Sublevel set outer approximations (light red, larger) to the region of attraction X 0 (dark red, smaller) for different degrees of the SOS reinforcement. This was originally published in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF].

Conic convex duality also holds for semidefinite programs. In the present context of control, the dual variables associated with the SOS reinforcement of condition (1) are "moments" of the occupation measures discussed in Section 5.1. Hence the SOS approximation actually bears the name moment-SOS approximation, see [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] for a comprehensive treatment.

Convergence

The positivity certificate in equation ( 8) describes a family of nonnegative polynomials over the set G involving a family of SOS polynomials {p i } q i=0 . By increasing the degree allowed for these SOS polynomials p i , one provides a hierarchy of increasing families of polynomials nonnegative on G. A relevant issue is:

What happens when we let the degrees of the SOS polynomials {p i } q i=0 defining this hierarchy goes to infinity?

This issue is related to the question of the representation of nonnegative polynomials on compact basic semi-algebraic sets. Fortunately, powerful results from real algebraic geometry state that it is enough to work with certificates of the form of (8) [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF]. This usually translates in global convergence results: replacing nonnegativity constraint in condition (1) by their SOS reinforcement and letting the degree of the SOS polynomials go to infinity is, in some sense, equivalent to the intractable constraints in condition [START_REF] Arechavaleta | An optimality principle governing human walking[END_REF]. Applications of sufficient conditions to represent positive polynomials date back to [START_REF] Lasserre | Global optimization with polynomials and the problem of moments[END_REF] in static optimization and to [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] in optimal control; see also [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF][START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF] for a more recent overview. This methodology can be used for all the control problems described in Section 4 to provide converging hierarchies of semidefinite approximations [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF], see also [START_REF] Henrion | Optimization on linear matrix inequalities for polynomial systems control[END_REF] for a detailed overview.

Numerical illustration

In this section we briefly describe numerical results obtained when applying the SOS reinforcement techniques of Section 5.3 to the abstract optimization problems of Section 4. We choose a simple but non trivial nonlinear system: Brockett's integrator. This system is of importance in humanoid robotics since it is equivalent to the nonholonomic Dubbins vehicle [START_REF] Souères | Shortest paths synthesis for a car-like robot[END_REF], a model of human walking [START_REF] Arechavaleta | An optimality principle governing human walking[END_REF], up to a change of variable [START_REF] Devon | Kinematic and dynamic control of a wheeled mobile robot[END_REF]. The numerical results presented here relate to free terminal time optimal control problem, which is different from the fixed terminal time setting considered in this work. They still illustrate most important aspects of these simulations. Indeed, most of the ideas presented in Sections 3 and 4 have direct equivalent in the free terminal time setting. In a nutshell, the terminal time in (OCP) is not fixed to be 1 but is a decision variable of the problem. In this case, the value function v * as well as its lower approximations v can be chosen to be independent of time. The numerical examples of this section were originally presented in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF][START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF][START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF]. All these examples were computed by combining the abstract infinite dimensional optimization problems of Section 4 with the SOS reinforcement techniques of Section 5.3.

Brockett's integrator

Brockett's integrator is a 3-dimensional nonlinear system with two dimensional control. We set X = {x ∈ R 3 : x ∞ ≤ 1}, U = {u ∈ R 2 : u 2 ≤ 1} and we let X T be the origin in R 3 . The dynamics of the system are given by

f (x, u) =   u 1 u 2 u 1 x 2 -u 2 x 1   , (9)
where the subscripts denote the corresponding coordinates. All the following examples are related to the minimum time to reach the origin under the previous dynamical constraints.

The value function of this problem is known and described in [5, Theorem 1.36 and 1.41] and the corresponding optimal control is computed in [27, Corollary 1]. In what follows, T (x) denotes the optimal time to reach the origin, starting at initial state x under the dynamical constraints (9).

Region of attraction

For this application, the final time is set to 1 and initial time is set to 0. The region of attraction described in Section 4 is the set X 0 of initial states for which there exists a feasible trajectory reaching the origin in time less or equal to 1. In other words, it 6) and the constant Lagrangian (normalized between 0 and 1). Epsilon error (eps) corresponds to the value of in [START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF]. The Lagrangian is looked for among all 3-variate polynomials of degree up to 4. These results were originally presented in [START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF].

consists of the set of initial states x, for which T (x) ≤ 1. This quantity is computable explicitly [START_REF] Beals | Hamilton-Jacobi theory and the heat kernel on Heisenberg groups[END_REF]. Combining the formulation in equation ( 4) with the SOS reinforcement technique described in Section 5.3, we get sublevel sets which are outer approximations of X 0 . This is represented in Figure 2 which compares the true region of attraction and its outer approximation in R 3 .

Minimum time direct optimal control

For the direct optimal control problem, we are interested in the value of the optimal time T (x). Following [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], we combine the formulation in [START_REF] Beals | Hamilton-Jacobi theory and the heat kernel on Heisenberg groups[END_REF] with the SOS reinforcement technique described in Section 5.3. As a result, we get a lower approximation of the optimal time T (x). This is illustrated in Table 1 for different initial conditions: x 1 = 1 and x i ∈ {1, 2, 3}, i = 2, 3. As expected, we obtain lower bounds on the optimal time which is known analytically. For these examples, the approximation is reasonably accurate.

Inverse optimal control

In this example, we are interested in recovering the minimum time Lagrangian (constant) from optimal trajectories which reach the origin in minimal time under dynamical constraints [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF]. These trajectories can be computed analytically [START_REF] Prieur | Robust optimal stabilization of the Brockett integrator via a hybrid feedback[END_REF]. As outlined in Figure 1, the trajectories constitute an input of the inverse problem and the output is a Lagrangian function. In order to find this function, we follow the work of [START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF] which combines the abstract problem in (6) with SOS reinforcement techniques described in Section 5.3 and additional constraints. We emphasize that the problem of Lagrangian identification is much less well posed than the direct optimal control problem and that accuracy of solutions highly depend on prior information about expected Lagrangians. In [START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF], it is shown that the success of such a procedure requires careful normalization and prior knowledge enforcement (sparsity through a regularization term). We do not describe the details of the procedure here and refer to [START_REF] Pauwels | Inverse optimal control with polynomial optimization[END_REF][START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF] for more details. This formulation includes a regularization parameter denoted by λ. Figure 3 presents measures of inverse optimality accuracy, (the value of in ( 6)), and estimation accuracy (a distance to the constant Lagrangian, the true Lagrangian of minimum time optimal control), for various values of this parameters. The input is made of optimal time trajectories and Figure 3 illustrates that the original Lagrangian can be recovered with a reasonable inverse optimality accuracy for some values of the regularization parameter close to 1.

Figure 3 :

 3 Figure3: Error versus a regularization parameter λ for the inverse optimal control problem. Estimation error (est) is a measure of distance between a candidate solution computed with (6) and the constant Lagrangian (normalized between 0 and 1). Epsilon error (eps) corresponds to the value of in[START_REF] Chesi | LMI Techniques for Optimization Over Polynomials in Control: a Survey[END_REF]. The Lagrangian is looked for among all 3-variate polynomials of degree up to 4. These results were originally presented in[START_REF] Pauwels | Linear conic optimization for inverse optimal control[END_REF].

Table 1 :

 1 Brockett's integrator, comparison of exact optimal time and SOS reinforcement. This was originally published in[START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF].

	SOS reinforcement.	Optimal time.
	1.7979 2.3614 3.2004 1.8257 2.3636 3.2091
	2.3691 2.6780 3.3341 2.5231 2.6856 3.3426
	2.8875 3.0654 3.5337 3.1895 3.1008 3.5456

IRIT, Université de Toulouse, Toulouse, France.

LAAS-CNRS, Université de Toulouse, CNRS, Toulouse, France.

Faculty of Electrical Engineering, Czech Technical University in Prague, Prague, Czech Republic.

Acknowledgements

This work was partly supported by project 16-19526S of the Grant Agency of the Czech Republic, project ERC-ADG TAMING 666981,ERC-Advanced Grant of the European Research Council and grant number FA9550-15-1-0500 from the Air Force Office of Scientific Research, Air Force Material Command.