Rene Lopez Flores
email: rene.lopezflores@ensiacet.fr.

Stéphane Negny

Jean Pierre Belaud

Jean-Marc Le Lann

Collective intelligence to solve creative problems in conceptual design phase

Keywords: Collective intelligence, Computer Aided Innovation, Conceptual design, Problem resolution, Innovation process;

Introduction

In the industrial field, innovation represents a key element for economic success. Although there is not a consensus about its definition, it is possible to describe innovation as the implementation of a new or significantly improved product (goods or services), process, marketing method, organizational method in business practices or workplace organization that gives significant advantages to a firm on a market. In order to put into practice this concept, it is In industry, there is an interest in the collective resolution of creative problems found on the phase of conceptual design. In this work we introduce an information-based software framework for collaboration in the problem resolution process. This framework proposes the implementation of techniques from the collective intelligence research field in combination with the systematic methods provided by TRIZ theory. Both approaches are centered in the human aspect of the innovation process, and are complementary. While collective intelligence focuses on the intelligence or behavior that emerges in collaborative work, the TRIZ theory is centered in the individual's capacity to solve problems. The framework's objective is to improve the individual creativity provided by TRIZ method and tools, with the value created by the collective contributions. This work aims to expand the horizon in the field of computer aided innovation (CAI), to the next evolutionary step called Open CAI 2.0.

Peer-review under responsibility of the Scientific Committee of TFC 2011, TFC 2012, TFC 2013 and TFC 2014 -GIC necessary to define a process that allows to lead from an idea or a need, up to a product in the marketplace; going through different phases such as design, production and marketing. In this paper we mainly focus on product and process innovation.

As reported by Dieter [START_REF] Dieter | Engineering design: a materials and processing approach[END_REF], design is a critical phase because the decisions taken in this stage could affect up to 80% of the total manufactured product cost. But product design is not a single activity; instead it is the organization of different activities forming together the product design process. In general this process involves the following phases: (a) starting decision, (b) preliminary design, (c) detailed design and final design.

It is acknowledged that conceptual design (first part in preliminary design) is perhaps the most creative, and difficult phase to achieve. In this paper we introduce the elements for a framework, which is still under development, to enhance the creativity of the participants in the conceptual design phase. The core idea of this framework is to combine the use of collective intelligence, a systematic methodology for problem solving and the functionality that the Web as a platform provides, in order to propose an environment for enhancing creativity through social collaboration.

Creative conceptual design

According to Wang et al. [START_REF] Wang | Collaborative conceptual design-state of the art and future trends[END_REF], conceptual design is perhaps the most important task in product design. Dieter [START_REF] Dieter | Engineering design: a materials and processing approach[END_REF] identifies this phase as the one that involves the most uncertainty, requires the most creativity and the coordination of different agents. To deal with these creative efforts, engineers use different methods, either by manual or computational means.

In [START_REF] Shai | Creative conceptual design: Extending the scope by infused design[END_REF], the authors appoint the importance of using strategies for improving creativity in conceptual design. According to [START_REF] Belleval | Modele de conception a base de reseau de contradictions. Le cas de la conception des microsatelites au cnes[END_REF], creative conceptual design has the following characteristics: (a) the statement of an unresolved and poorly defined problem, (b) the problem has a number of contradictions, (c) the achievement of a new solution, (d) and finally the construction of new knowledge. Usually to solve inventive problems or generate ideas in conceptual design, engineers use traditional methods such as: concept-knowledge theory, brainstorming, and trialerror. Nevertheless, these methods have certain drawbacks: randomness, the lack of systematization and the relay on individual talent. From a systematic perspective, innovation can be addressed through a controllable and creative thinking method. To remove existing barriers in traditional methods, the Theory of Inventive Problem Solving (TRIZ) gathers a set of methods and concepts to systematize innovation. Compared to other methods, the advantage of TRIZ is that it is a heuristic based on scientific knowledge and the study of millions of patents [START_REF] Savransky | Engineering of Creativity: Introduction to TRIZ Methodology of Inventive Problem Solving[END_REF].

Collective design approaches

The high interdisciplinary in conceptual design involves collaboration from different agents (e.g. customers, designers and engineers). In this context, information and communication technologies provide the space for information exchange and creative interaction [START_REF] Yannou | Management des hommes, des projets et des informations[END_REF]. For example, in [START_REF] Wang | Collaborative conceptual design-state of the art and future trends[END_REF] Wang et al. proposed a paradigm shift in conceptual design to adopt a more pragmatic and aggressive approach through collaboration. In their proposition artificial intelligence and information technologies are the support and impulse for collaboration.

For Nieto and Santamaría [START_REF] Nieto | The importance of diverse collaborative networks for the novelty of product innovation[END_REF], collaboration with suppliers, clients and research organizations have a positive impact on the novelty of innovation. Nieto and Santamaría also suggest the integration and the management of internal and external knowledge to improve the levels of innovativeness and competitiveness. Therefore, collaborative innovation enables to access to external sources of technological knowledge and skills. Nevertheless, the collaborative aspect in innovation not only represents a paradigm shift in the conceptualization of the innovation process, but also requires the support of collaborative technologies [START_REF] Standing | How can organizations use wikis for innovation?[END_REF], [START_REF] Hüsig | Open CAI 2.0' -Computer Aided Innovation in the era of open innovation and Web 2.0[END_REF].

Figure 1 describes the development of the tools to support collaborative innovation. It is possible to identify the change from the use of stand-alone applications to the use of technologies and techniques enhancing social interactions. Moreover, this evolution implies the emergence of "weak ties" between different participants. According to Caseau [START_REF] Caseau | Processus et Entreprise 2.0 -Innover par la collaboration et le Lean management[END_REF], weak ties are important in a company because they allow the collaboration of employees whom normally are not in contact, as well as promoting collective intelligence. Recently, two major changes are driving the evolution in CAI tools. The first one is the technologic aspect based on the advantages that the Web 2.0 offers as a platform. The second one is the management strategy known as the Open Innovation paradigm [START_REF] Chesbrough | Open innovation: The new imperative for creating and profiting from technology[END_REF], which consists in opening the innovation process to the participation of external actors and the inclusion of external knowledge. In this scenario, Hüsig and Kohn propose the concept Open CAI 2.0 as the next evolutionary step on CAI development [START_REF] Hüsig | Open CAI 2.0' -Computer Aided Innovation in the era of open innovation and Web 2.0[END_REF]. They define Open CAI 2.

as "a category of CAItools that use technologies following the Web 2.paradigm to facilitate open innovation methods in order to open access of organizations to a large audience of external actors and enable them to interact in different activities of the innovation process".

The framework discussed in this paper is a prototype following the principles of an "Open CAI 2.0 tool". The main focus of our work lies in the adoption of a systematic innovation process that integrates the capitalization of previous experiences in a collaborative environment. Gathering collective intelligence is considered in this framework as the key element to overcome the obstacles created by the individual cognitive limits typical of a creative activity as it is the preliminary design.

Collective intelligence in the industrial field

Collective intelligence (CI) has existed since humans started to bring together intellectual efforts to develop specific tasks. Nowadays, industries start to focus on immaterial elements to define the firm value (i.e. brand portfolio, employee's life quality, intelligence emotional). From these elements, collective intelligence is a kind of intelligence that emerges from the synergy of individual creative efforts when a cognitive task (e.g. collaborative innovation) takes place [START_REF] Yannou | Management des hommes, des projets et des informations[END_REF]. This synergy is important in new product development because in order to reduce timeto-market and to improve the success possibilities of a product, the innovation process should not depend on the skills of one person.

According to Zara [START_REF] Zara | Le management de l'intelligence collective: vers une nouvelle gouvernance[END_REF], the challenge of collective intelligence and knowledge management is how to improve the collective efforts in order to be better than individual efforts. Zara defines collective intelligence as "the capacity to join intelligence and knowledge to achieve a common objective". Collective intelligence takes a new dimension with the incorporation of the computers. For example, the Center for Collective Intelligence at the MIT works developing systems to connect people and computers so that collectively they act more intelligent [START_REF] Leimeister | Collective Intelligence[END_REF]. In another example, Innocentive is presented as a platform that connects people with innovation problems to solution providers around the world, with the aim to unleash human creativity to solve problems that matter to business and society [START_REF] Allio | CEO interview: the InnoCentive model of open innovation[END_REF].

Social Web

The discussion about collective intelligence leads to consider the social behavior involved. The Web 2.0 as a platform improves the performance of human interactions, creating new services known as social networks. According to Caseau [START_REF] Caseau | Processus et Entreprise 2.0 -Innover par la collaboration et le Lean management[END_REF], a social network is a graph that represents the interaction between actors. In the graph the nodes are the actors and the edges are the interactions.

It is possible to face the challenges that collective intelligence imposes on the innovation process by using social networks. In fact, Social Networks allow interaction of different users who do not know each other; giving rise to the network effect phenomenon [START_REF] Esteban-Gil | SocialBROKER: A collaborative social space for gathering semantically-enhanced financial information[END_REF]. One particular case of social networks is the Collaborative Innovation Networks (COINs). Gloor [START_REF] Gloor | Swarm Creativity: Competitive Advantage through Collaborative Innovation Networks[END_REF] defines COIN as "a cyber-team of self-motivated people with a collective vision, enabled by the Web to collaborate in achieving a common goal by sharing ideas, information, and work."

Relying on the sharing and cooperation architecture provided by Web 2.0 technologies, it is feasible to deploy applications using collective intelligence techniques. The model in Figure 2 represents the users' interactions to gather collective intelligence from a Web application. The application should aggregate the content in models. The aggregation allows to learn from other users contributions. Finally, the user rates or recommends relevant content.

A new framework for improving conceptual design using collective intelligence

The techniques that were integrated in our framework to improve creativity in conceptual design are focus on harnessing the kind of collective intelligence that emerges from a Web 2.0 application [START_REF] Alag | Collective Intelligence in Action[END_REF].

Figure 3 introduces the way in which our framework's core is organized, and Table 1 generally describes each level. During operation, the different process stages are executed following an asynchronous pattern, namely, each user works on the data separately within a shared resolution space, and the activities assigned to different members are achieved at distinct times. The framework objective is to integrate different aspects in order to: gather collective intelligence, support collaborative work and implement a problem resolution process. A more detailed explanation of each level is presented below.

Model TRIZ-CBR

The model TRIZ-CBR [START_REF] Robles | Case-based reasoning and TRIZ: A coupling for innovative conception in Chemical Engineering[END_REF] organizes the innovation process to assist users in the resolution of technical or physical contradictions. This model considers the integration of the TRIZ tools and the Case-Based Reasoning (CBR) technique in order to provide a resolution process. The resolution process is capable to guide creativity to generate innovative solutions, at the same time that it stores, indexes and reuses knowledge in order to accelerate the innovation process. The framework functionality is presented in the Figure 4 using a Unified Modeling Language (UML) diagram. The resolution process starts when the user creates an entity called project. A project is used for structuring all the information aspects concerned with the process. Once the project edited the user has access to the options in order to update any of the project characteristics through dialog components.

The functionality follows a process based on the model TRIZ-CBR. The stages that compose this process are: Problem analysis, Contradiction formulation, Knowledge capitalization and Solution documentation. For example, Figure 5 presents the dialog box to make the description about the problematic situation. The description for each option in the framework is presented next.

Problem analysis: According to TRIZ theory, when using contradiction matrix, the user should do an analysis with the single purpose to generate, infer, complete and collect information about the problematic situation. Guided by different TRIZ tools, this section is divided in four stages: General description, System description, Resources identification and Ideal Final Result (IFR).

Contradiction formulation:

The contradiction is one of the central and most important concepts in TRIZ classic concepts; it is defined as the condition in which two demands or requirements of a system are mutually exclusive but must be assosiated to achieve the same objective [START_REF] Altshuller | 40 Principles: TRIZ Keys to Innovation[END_REF]. The implementation of this tool, based on a model proposed by Altshuller and Clarke in [START_REF] Altshuller | 40 Principles: TRIZ Keys to Innovation[END_REF], is with the aim of assisting the user to identify and document the contradiction. Once the user identifies and saves the contradiction, the next step is a query in the knowledge database.

Knowledge capitalization:

In this option the user accesses the knowledge database. This database stores previous cases which have been solved either as a success or a failure. For its development, we have used the concepts of a CBR [START_REF] Watson | Applying Case-Based Reasoning: Techniques for Enterprise Systems[END_REF] and it is implemented using jCOLIBRI library [START_REF] Recio-Garía | Ontology based CBR with jCOLIBRI[END_REF]. After retrieval with a specific similarity measure and the Nearest Neighbour Algorithm, the system gives a list of most similar cases ranked in order of importance. Then, two options are possible for printing all the information related with the case (e.g. General description). Finally, when there is not a similar case the user follows a sub-process in order to solve the contradiction from scratch using the TRIZ resolution principles.

Documentation of solution:

The last step in the process of problem resolution is documenting the solution. In this stage the user describes in the best possible way the achieved solution. This section is organized in three stages: proposed solution, implementation and details about involved resources. Finally, when a user confirms a solution certain step of the framework generates and stores a new case in the CBR database in order to the coverage of the problem space but also to update the knowledge in the database.

Collaboration support

In the study of innovation through collaboration, the process -as a conceptual object or tool-has a central role because it arranges the activities and actors.

The collaboration process that we propose is centered in the aspects to allow different actors cooperate within a common environment that controls information integrity. These aspects are:

To provide tools in order to facilitate the communication among users. The coordination of activities performed by users. To allow users collaboration to create, edit and share projects. To allow the creation of collaboration groups. To ensure information integrity and keeping the progress tracking.

The actors involved in the process are: the project owner, the project collaborator and the mutual exclusion control.

The Figure 6 is a model in Business Process Model and Notation (BPMN) to describe the collaboration process. In certain way, the project owner is who has more control in the management of a project. After the project creation, he is responsible to create collaboration groups and share the project. Then, to share the project is through an invitation generated by the project owner. In the task "Edit project", the user access to the innovation process described in section 3.1. In the edition, the collaborator accesses the same options to modify the project as the project owner. When a user edits a project the mutual exclusion control blocks the project resource in order to maintain information integrity. The mutual exclusion finishes when the user ends the edition, or by the mutual exclusion control when the timer is over. Then, the project resource is released.

Collecting intelligence in collaborative innovation

In the conception of our platform, we consider the relation between the problem formulator and the community as follow: a social relationship and a conceptual relationship (see Figure 7). The social relationship appears when a user collaborates with other users to solve a problem. The conceptual relationship emerges when users create elements that we call "knowledge components". The knowledge components are the content users create either by using TRIZ methods or by using domain knowledge to implement a particular solution. The use of tags and reviews enrich the knowledge components as well as they help to create the conceptual relations. The model in Figure 7 considers the user's capacity to learn from their interactions and contributions in a form of feedback (reviews).

The architecture of participation is not enough to harness the intelligence from the collective effort in a Web application. In addition, Figure 7 presents the mechanisms to implement collective intelligence that we identified from [START_REF] Robles | Case-based reasoning and TRIZ: A coupling for innovative conception in Chemical Engineering[END_REF]. The mechanisms to improve our platform are: tagging, cloud navigation, reviews, and building user profile. Tagging: There are two possibilities to generate the tags: manually or by a process of tags extraction. In the manual option, the user introduces the tags or annotations to add metadata in problematic situation analysis to describe the project. In Figure 5 is possible to appreciate the option for manual tagging. The automatic process for tag extraction, as proposed in [START_REF] Esteban-Gil | SocialBROKER: A collaborative social space for gathering semantically-enhanced financial information[END_REF], is based on the typical steps involved in text analysis (Tokenization, Normalization, Elimination of Stop words and Stemming) from free-text fields.

It is worth mentioning that functionality for gathering collective intelligence is not completed. There is a work in process; nevertheless aspects about this development are pointed out in perspectives.

Conclusion and Perspectives

Conclusion

Our findings suggest that to achieve a real collaborative innovation in an open context, it is necessary to overcome several barriers, in this paper some of them have been tackled: social interaction, knowledge management and the definition of an innovation process based on problem resolution. A solution that integrates these elements using the Web 2.0 platform was described.

The concepts from collective intelligence introduced in this article expose the possibilities to improve participant's creativity in the phase of conceptual design. The collective intelligence provides a way to expose knowledge that is otherwise hidden in a collective environment. For example, bubbling up interesting content or dynamic content classification.

In order to develop a more complete platform, it is necessary to take advance of the most recent approaches provided by information technologies to master knowledge management in collaborative environments. Semantic technologies seem to provide powerful and practical mechanisms to develop this functionality. This work is not free from limitations. One drawback is that the success for the framework depends on the interest and participation of the actors involved. By considering this limitation, we develop an important effort to take into consideration guidelines for usability and collaboration within Web 2.0 applications.

Finally, it is required the validation through the internet or an intranet network. This validation will be realized in a case related with the process engineering domain.

Perspectives

Although the contradiction matrix is an important tool, its utilization is not easy and relies on the user's skills. This limitation could be overcome using an automatic method in order to scan free-text and find the specific technical parameters to formulate the contradiction [START_REF] Tuson | A Method for Facilitating Inventive Design Based on Semantic Similarity and Case-Based Reasoning[END_REF].

In relation to the work in progress, we intend to develop missing functionality about collective intelligence. However, it is possible to present some of the characteristics expected.

Firstly, incorporate tag clouds. This component helps the user to make a rapid search using the tags concepts generated manually by the users or the process for tags extraction.

Secondly, provide review functionality. The reviews are useful to quantify the quality of the content generated by the users. In the platform the reviews are focused on problem solutions, and they could be of two types: textual and rating. Both kinds allow the users to provide an instant feedback about the solution's relevance. The rating option has an advantage over the textual review because the information provided is quantifiable and used directly.

And lastly, create a user profile. The importance to build a user profile is because it allows the framework to provide more relevant and personalized information. Our framework proposes to generate the profile base on the content user generates and the social interactions. The use of TRIZ tools and domain knowledge via tag extraction are the base to build a profile of concepts. The collaborations between the user and the community are the base to build the social profile. For example, in [START_REF] Stankovic | Finding Co-solvers on Twitter, with a Little Help from Linked Data[END_REF] the authors propose to use the social profile to find possible collaborators for a particular project in a recommendation system.

Figure 1 .

 1 Figure 1. Evolution of collaborative innovation IT-support

Figure 2 .

 2 Figure 2. Model of Collective Intelligence[START_REF] Alag | Collective Intelligence in Action[END_REF]

Figure 3

 3 Figure 3 Framework core components

Figure 4

 4 Figure 4 Framework functionality

Figure 5

 5 Figure 5 Problematic situation dialog

Figure 6

 6 Figure 6 Collaboration process

Figure 7

 7 Figure 7 Architecture of participation for gathering collective intelligence

Table 1

 1 Level characteristics

Acknowledgements

This work is sponsored by the Mexican National Council for Science and Technology (CONACyT) and the Government of France through the French embassy in Mexico.


Swann Marx

Tillmann Weisser

Didier Henrion

Jean Bernard Lasserre

A moment approach for entropy solutions to nonlinear hyperbolic PDEs *

Keywords: nonlinear partial differential equation, convex optimization, moments and positive polynomials

We propose to solve polynomial hyperbolic partial differential equations (PDEs) with convex optimization. This approach is based on a very weak notion of solution of the nonlinear equation, namely the measure-valued (mv) solution, satisfying a linear equation in the space of Borel measures. The aim of this paper is, first, to provide the conditions that ensure the equivalence between the two formulations and, second, to introduce a method which approximates the infinite-dimensional linear problem by a hierarchy of convex, finite-dimensional, semidefinite programming problems. This result is then illustrated on the celebrated Burgers equation. We also compare our results with an existing numerical scheme, namely the Godunov scheme.

Introduction

This paper is concerned with the numerical study of scalar nonlinear hyperbolic conservation laws, a partial differential equation (PDE) which model numerous physical phenomena such as fluid mechanics, traffic flow or nonlinear acoustics [START_REF] Dafermos | Hyperbolic conservation laws in continuum physics[END_REF], [START_REF] Whitham | Linear and nonlinear waves[END_REF]. The existence and uniqueness of solutions to the associated Cauchy problem crucially depends on the flux and the initial condition [START_REF] Kružkov | First order quasilinear equations in several independent variables[END_REF]. Even if the solution is unique, its numerical computation is still a challenge -in particular when the solution has a shock, i.e., a discontinuity. Existing schemes based on discretization such as [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] suffer from numerical dissipation: the shock is smoothened in the numerical solution and cannot be represented accurately. In fact, sometimes the exact location of the shock is of crucial interest for applications. Note however that some existing numerical schemes are able to capture shocks in the case where the conservation laws under consideration are linear, see e.g. [START_REF] Després | Contact discontinuity capturing schemes for linear advection and compressible gas dynamics[END_REF].

In contrast to existing methods, a distinguishing feature of the numerical scheme presented in this paper is to not rely on discretization; it computes the solution in a given time-space window globally. From such a solution, the location of the shock at a given time can be computed up to the limits of machine precision. In our opinion this is a major advantage when compared to other numerical methods.

Measure-Valued Solutions While PDEs are usually understood in a weak sense, DiPerna proposed an even weaker notion of solution, so-called measure-valued solutions (mv solutions for short) [START_REF] Diperna | Measure-valued solutions to conservation laws[END_REF], which are based on Young measures, i.e. time and/or space dependent probability measures. Young measures have originally been introduced in the context of calculus of variations and optimal control, where the velocity or more generally the control is relaxed from being a function of time to being a timedependent probability measure on the control space, see e.g. [12, Part III] for an overview. Similarly, DiPerna introduced mv solutions to conservation laws as measures on the solution space, now depending on time and space.

Naturally, every weak solution gives rise to a mv solution when identifying a solution y(t, x) with the Young measure δ y(t,x) (dy). We say then that the mv solution is concentrated on (the graph of) the solution. In this paper, we are focusing on a setup where both weak and mv solutions are unique (hence identical). In this case, both solutions coincide via the identification just mentioned. Note however that our approach also applies without any change to situations where the mv solution is not concentrated, e.g., because of an initial condition that is not concentrated either.

In order to ensure uniqueness we rely on the notion of entropy solutions which has been extended to entropy mv solutions. Entropy is a concept from thermodynamics that makes reference to the fact that differences in physical systems, e.g., the densities of particles in a room, tend to adjust to each other. It is well-known that the entropy solution of a scalar nonlinear hyperbolic conservation law is unique. For the generalized situation things are more involved. However under suitable assumptions on the initial condition entropy, uniqueness of mv solutions can be proved.

Recently there has been an increasing interest in numerical schemes to compute mv solutions for hyperbolic conservation laws with non concentrated initial conditions [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF][START_REF] Feireisl | Convergence of finite volume schemes for the Euler equations via dissipative measure-valued solutions[END_REF]. Existing numerical schemes apply standard discretization methods to compute sufficiently many trajectories according to the distribution of the initial condition and recover the moments of the mv solution by considering limits of the trajectories. In contrast to this our approach directly computes the moments of the mv solution. Therefore in some sense this work is in the opposite direction. We compute moments to recover trajectories in the case where the initial condition and the solution are concentrated.

Generalized Moment Problem The key idea underlying the approach is to consider mv solutions as solutions to a particular instance of the Generalized Moment Problem (GMP) which is an infinite-dimensional optimization problem on appropriate spaces of measures, and where both the cost and the (possibly countably many) constraints are linear in the moments of the respective measures. Lasserre [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF] showed that the GMP can be approximated as closely as desired by solving a hierarchy of convex semidefinite programs (SDP) of increasing size, provided that the data of the GMP are semi-algebraic; that is, the measures are supported on basic semi algebraic compact sets (i.e. bounded sets defined by finitely many polynomial inequalities and equations) and the involved functions are polynomial or semi-algebraic functions (i.e. functions whose graphs are semi-algebraic sets). The duals to these SDPs are linear problems on polynomial sums of squares (SOS). Therefore this hierarchy of SDP relaxations is called the moment-SOS (sums of squares) hierarchy. By now, many problems from different fields of mathematics, including optimal control of ordinary differential equations [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], have been reformulated as particular instances of the GMP and then approximated or solved by the moment-SOS hierarchy. This paper is in the line of these former contributions. That is, (i) the mv solutions are viewed (or formulated) as solutions of a particular instance of the GMP, and (ii) the moments of mv solutions are approximated as closely as desired by solving a moment-SOS hierarchy.

Any optimal solution of each semidefinite relaxation at step d in the hierarchy provides information about the mv solution in the form of a sequence of its (approximated) moments, up to degree d; the higher is d the better is the approximation of its moments. As we restrict to measures with compact support, they are fully characterized from knowledge of the complete sequence of their moments. Interestingly, it is worth noting that in [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF] it was already pointed out that the statistical moments of mv solutions are precisely the quantities of interest.

Contribution To the best of our knowledge, this work seems to be the first contribution where nonlinear PDEs are addressed without time-space domain discretization and using convex optimization with a proof of convergence. An original early attempt to compute mv solutions of nonlinear wave equations with linear programming was reported in [START_REF] Rubio | Nonlinear theory of generalized functions[END_REF], also in the presence of controls. In [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], the authors apply to moment-SOS hierarchy to solve optimal control problems of ordinary differential equations, and it was shown in [START_REF] Henrion | Linear conic optimization for nonlinear optimal control[END_REF] that it provides a sequence of subsolutions converging in norm to the viscosity solution of the Hamilton-Jacobi-Bellmann PDE, a particular nonlinear hyperbolic equation. In [START_REF] Mevissen | Moment and SDP relaxation techniques for smooth approximations of problems involving nonlinear differential equations[END_REF], nonlinear PDEs are discretized into large-scale sparse polynomial optimization problems, in turn solved with the moment-SOS hierarchy. More recently, bounds on functionals of solutions were obtained with SOS polynomials for nonlinear PDEs arising in fluid dynamics in [START_REF] Chernyshenko | Polynomial sum of squares in fluid dynamics: a review with a look ahead[END_REF] and for the nonlinear Kuramoto-Sivashinsky PDE in [START_REF] Goluskin | Bounds on mean energy in the Kuramoto-Sivashinsky equation computed using semidefinite programming[END_REF]. These works, however, focus only on the dual SOS problems, and they provide bounds with no convergence guarantees. They do not exploit the primal formulation of the problem on moments, which we believe to be crucial for convergence analysis. In the recent work [START_REF] Fjordholm | On the computation of measured-valued solutions[END_REF], the authors compute mv solutions for the equations of compressible and incompressible inviscid fluid dynamics, with the help of discretization algorithms based on Monte Carlo methods. Even more recently, in [START_REF] Brenier | Solution by convex minimization of the Cauchy problem for hyperbolic systems of conservation laws with convex entropy[END_REF] the author has proposed a convex formulation for the classical solution to nonlinear hyperbolic PDEs and he proves that the entropy solution to the Burgers equation might be recovered also via this optimization problem. However, this paper does not provide a numerical scheme. In the concurrent work [START_REF] Korda | Moments and convex optimization for analysis and control of nonlinear partial differential equations[END_REF], the authors propose to use the moment-SOS hierarchy in a much more general setting of a controlled polynomial PDE. However, at that level of generality, there is no proof that the numerical scheme will converge to an appropriate solution of the PDE. For more references on previous attempts to use convex optimization for solving and controlling PDEs, the reader is referred to the introduction of [START_REF] Korda | Moments and convex optimization for analysis and control of nonlinear partial differential equations[END_REF].

Outline This paper is organized as follows. Section 2 introduces different notions of solutions for scalar conservation laws and provides some links between these notions. Section 3 introduces the Moment-SOS hierarchy, proves that the mv solution framework can be written as an instance of the GMP, and explains how one may interpret the moment solutions. The focus of Section 4 is on a numerical study of the Burgers equation. Finally, Section 5 collects some concluding remarks and further research issues to be addressed.

Notation If X is a topological space, let C (X ) resp. C 0 (X ) resp. C 1 c (X ) denote the space of functions on X that are continuous resp. continuous and vanishing at infinity resp. continuously differentiable with compact support. For p ≥ 1, the Lebesgue space L p (X ) consists of functions on X whose p-norms are bounded. The set of signed resp. positive Borel measures is denoted M (X ) resp. M (X ) + . The set of probability measures on X is denoted by P(X ) and it consists of elements µ ∈ M (X ) + such that µ(X ) = 1. The measure λ X ∈ P(X ) denotes the normalized Lebesgue measure on X . Given a vector w = (w 1 . . . w n ), we denote by R[w] the ring of real multivariate polynomials in the variables w 1 , . . . , w n .

Notions of solutions

We start with a brief overview of different notions of solutions to scalar polynomial PDEs. For details, we refer to [START_REF] Dafermos | Hyperbolic conservation laws in continuum physics[END_REF] for weak solutions and [START_REF] Málek | Weak and measure-valued solutions to evolutionary PDEs[END_REF] for measure-valued solutions. The aim of this section is to give a clear link between these two concepts of solutions.

Weak and entropy solutions

In order to study mv solutions, it is instructive to revisit the classical concept of weak solutions first. Consider therefore the Cauchy problem

∂y ∂t (t, x) + ∂f (y) ∂x (t, x) = 0, (t, x) ∈ R + × R, (1a)
y(0, x) = y 0 (x), x ∈ R, (1b)
where (1a) is a scalar hyperbolic conservation law with f ∈ C 1 (R) and (1b) provides an initial condition y 0 ∈ L 1 (R) ∩ L ∞ (R). Note that (1a) encompasses, among others, the well-known Burgers equation if one sets f (y) = 1 2 y 2 . Even if the initial condition y 0 is smooth, solutions to (1) might be discontinuous (see [11, p. 143] for the case of the Burgers equation). Solutions to this problem are hence usually understood in the following weak sense.

Definition 1 (Weak solution). A function y ∈ L ∞ (R + × R) is a weak solution to (1) if, for all test functions ψ 1 ∈ C 1 c (R + × R), it satisfies R + R ∂ψ 1 (t, x) ∂t y(t, x) + ∂ψ 1 (t, x) ∂x f (y(t, x)) dx dt + R ψ 1 (0, x)y 0 (x) dx = 0. (2)
In general, weak solutions to (1) are not unique. However it can be shown (see e.g. [START_REF] Kružkov | First order quasilinear equations in several independent variables[END_REF]) that among all possible weak solutions, only one has a physical meaning. This solution is called the entropy solution and can be characterized as follows.

Definition 2 (Entropy pair/entropy solution). (i) A pair of functions η, q ∈ C 1 (R)

is called an entropy pair for (1a) if η is strictly convex and q = f η .

(ii) A weak solution y ∈ L ∞ (R + × R) of (1) is an entropy solution if, for all entropy pairs and all non-negative test functions

ψ 2 ∈ C 1 c (R + × R), it satisfies R + R ∂ψ 2 ∂t η(y) + ∂ψ 2 ∂x q(y) dx dt + R ψ 2 (0, x)η(y 0 )(x) dx ≥ 0. ( 3
)

Measure-valued solutions

Generally, regularity results of conservation laws are obtained from regularized conservation laws

∂ ∂t y ε + ∂ ∂x f (y ε ) -ε ∂ 2
∂x 2 y ε = 0, where ε > 0 is a fixed parameter. Then one studies the limit of solutions y ε as ε goes to 0 and tries to retrieve some of regularity properties of the latter equation for the conservation law. However, on the one hand, regularized solution y ε may or may not converge to a weak solution y of (1). This is due to a lack of reflexivity of the space L ∞ . On the other hand, regularized solutions y ε necessarily converge to a measure-valued (mv) solution. This notion builds upon the concept of a Young measure. Definition 3 (Young measure). A Young measure on a Euclidean space X is a map µ : X → P(R), ξ → µ ξ , such that for all g ∈ C 0 (R) the function ξ → R g(y)µ ξ (dy) is measurable.

Later, mv solutions have also proved to be useful in the study of problems more general than [START_REF] Brenier | Solution by convex minimization of the Cauchy problem for hyperbolic systems of conservation laws with convex entropy[END_REF], where the initial condition (1b) is replaced by a Young measure parametrized in space (see e.g. [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF] and the references therein). The generalized problem is to find a Young measure µ (t,x) which satisfies the following Cauchy problem:

∂ t µ (t,x) , y + ∂ x µ (t,x) , f (y) = 0, (t, x) ∈ R + × R, (4a)
µ (0,x) = σ 0 , x ∈ R, (4b)
where •, • denotes integration of a measure µ ∈ M (R) against a function g ∈ C (R):

µ, g := R g(y)µ(dy).
In (4) the measure σ 0 is a given Young measure on R, and f is a continuously differentiable function on R. The conservation law (4a) has to be understood in the sense of distributions, i.e.:

Definition 4 (Measure-valued solution). A Young measure is a measure-valued (mv) solution to (4) if, for all test functions

ψ 1 ∈ C 1 c (R + × R), it satisfies R + R ∂ψ 1 (t, x) ∂t µ (t,x) , y + ∂ψ 1 (t, x) ∂x µ (t,x) , f (y) dx dt + R ψ 1 (0, x) σ 0 , y dx = 0. (5)
Note that the weak solution y has been replaced by a time-space parametrized probability measure µ supported on the range of y. Whereas a weak solution is requested to satisfy (2), only averages of the mv solution are considered in [START_REF] Dahl | Extending the conic optimizer in MOSEK with semidefinite cones[END_REF]. It is easy to see that every weak solution induces a mv solution via the canonical embedding y(t, x) → δ y(t,x) . As in the case of weak solution, an entropy condition is needed in order to select solutions with a physical meaning. Quite in analogy to entropy solutions, entropy mv solutions are defined as follows.

Definition 5 (Entropy measure-valued solution). An mv solution µ is an entropy mv solution to (4) if, for all entropy pairs (η, q) and all non-negative test functions

ψ 2 ∈ C 1 c (R + × R), it satisfies R + R ∂ψ 2 (t, x) ∂t µ (t,x) , η + ∂ψ 2 (t, x) ∂x µ (t,x) , q dx dt + R ψ 2 (0, x) σ 0 , η dx ≥ 0. ( 6
)
Remark 1. Again it is straightforward to see that entropy solutions are entropy mv solutions via the canonical embedding y(t, x) → δ y(t,x) . However, as demonstrated on an example in [15, p. 775], in contrast with entropy solutions, entropy mv solutions are not necessarily unique.

We have seen that the concept of mv solutions is weaker than the concept of weak solutions. Hence mv solutions are a relaxation of weak solutions: every weak solution is also an mv solution, but the set of mv solutions can be larger than the set of weak solutions. However, the following result states that considering mv solutions is not a relaxation. To be more precise, when the initial measure in (4b) is concentrated on (the graph of) the initial condition in (1b), then the entropy mv solution to ( 4) is unique and concentrated on (the graph of) the (unique) entropy solution to (1).

Theorem 1 (Concentration of the entropy mv solution). Let C be the Lipschitz constant of the function f . Let y be an entropy solution and µ be an entropy mv solution to [START_REF] Brenier | Solution by convex minimization of the Cauchy problem for hyperbolic systems of conservation laws with convex entropy[END_REF]. Then, for all T ≥ 0 and all r ≥ 0, it holds

|x|≤r µ (t,x) , |y -y(T, x)| dx ≤ |x|≤r+CT σ 0 , |y -y 0 (x)| dx. (7)
In particular, if σ 0 = δ y 0 (x) , then µ (t,x) = δ y(t,x) for all t ∈ [0, T ] and all x such that |x| ≤ r.

Remark 2. The proof of Theorem 1 is similar to the one provided in [START_REF] Kružkov | First order quasilinear equations in several independent variables[END_REF] and it is postponed to Appendix A. It is based on the doubling variable strategy, using the following family of entropy pairs:

η v (y) = |y -v|, q v (y) = sign(y -v)(f (y) -f (v)) (8)
parametrized in v ∈ R. In [START_REF] Lax | Shock waves and entropy[END_REF], it has been proved that linear combinations of these entropy pairs, together with the convex hull of linear functions, generate all entropy pairs. In other words, to prove Theorem 1 for every entropy pair it is enough to consider the entropy pairs [START_REF] Demoulini | Weak-strong uniqueness of dissipative measure-valued solutions for polyconvex elastodynamics[END_REF]. Moreover, note that initially the doubling variable strategy has been used to prove uniqueness of the solution to scalar nonlinear conservations laws. The main drawback is that the entropy solution has to satisfy this inequality for all convex pairs. However for the specific case of the Burgers equation, it is shown in [START_REF] Delellis | Minimal entropy conditions for Burgers equation[END_REF] and [START_REF] Panov | Uniqueness of the solution of the Cauchy problem for a first order quasilinear equation with one admissible strictly convex entropy[END_REF] that one may consider only one convex pair.

An emphasis on compact sets

In practice, one computes or approximates the solution on compact subsets, so let

T := [0, T ], X := [L, R] (9)
be the respective domains of time t and space x, for fixed (but arbitrary) constants T, L, R. After scaling, we assume without loss of generality that T = R -L = 1. Note that the entropy inequality induces a stability property:

y(t, •) L ∞ (X) ≤ y 0 L ∞ (R) , ∀t ≥ 0 ( 10
)
Y := [y, ȳ], (11)
where the bounds y := ess inf x∈R y 0 (x) and ȳ := ess sup x∈R y 0 (x) depend on the initial condition. On T × X, the polynomial hyperbolic equations given in (1) reads:

   ∂y ∂t + ∂f (y) ∂x = 0, (t, x) ∈ T × X, y(0, x) = y 0 (x), x ∈ X. (12)
Definition 6 (Entropy solution on compact sets). A weak solution y is an entropy solution to [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF] if, for all test functions

ψ 1 ∈ C 1 (R + × R), it satisfies T X ∂ψ 1 ∂t y + ∂ψ 1 ∂x f (y) dxdt + X ψ 1 (0, x)y 0 (x)dx - X ψ 1 (T, x)y(T, x)dx + T ψ 1 (t, L)y(t, L)dt - T ψ 1 (t, R)y(t, R)dt = 0 (13)
and, for all convex pairs (η, q) and all non-negative test functions

ψ 2 ∈ C 1 (R + × R), it satisfies T X ∂ψ 2 ∂t η(y) + ∂ψ 2 ∂x q(y) dxdt + X ψ 2 (0, x)η(y 0 )(x)dx - X ψ 2 (T, x)η(y(T, x))dx + T ψ 2 (t, L)q(y(t, L))dt - T ψ 2 (t, R)q(y(t, R))dt ≥ 0. ( 14
)
As we work on compact sets, the test functions do not have to vanish at infinity. However new terms y(t, R) and y(t, L) now appear. Related to this notion of solutions on compact sets, we also have a similar definition for mv entropy solution.

Definition 7 (Measure-valued entropy solution on compact sets

). A Young measure µ : (t, x) ∈ T × X → µ (t,x) ∈ P(Y) is an entropy measure-valued solution to (12) if, for all test functions ψ 1 ∈ C 1 (T × X), it satisfies T X ∂ψ 1 ∂t µ (t,x) , y + ∂ψ 1 ∂x µ (t,x) , f (y) dx dt + X ψ 1 (0, x) σ 0 , y dx - X ψ 1 (T, x) σ T , y dx + T ψ 1 (t, L) σ L , f (y) dt - T ψ 1 (t, R) σ R , f (y) dt = 0 (15)
and, for all convex pairs (η, q) and all non-negative test functions

ψ 2 ∈ C 1 (T × X), it satisfies T X ∂ψ 2 ∂t µ (t,x) , η(y) + ∂ψ 2 ∂x µ (t,x) , q(y) dx dt + X ψ 2 (0, x) σ 0 , η(y) dx - X ψ 2 (T, x) σ T , η(y) dx + T ψ 2 (t, L) σ L , q(y) dt - T ψ 2 (t, R) σ R , q(y) dt ≥ 0, ( 16
)
where σ 0 , σ T , σ L resp. σ R are Young measures supported on T, X, T resp. X.

Remark 3 (Imposing constraints on the boundary). To ensure concentration of µ (t,x) on the graph of the solution to (13)-( 14), in addition to the condition σ 0 = δ y 0 (x) , one may impose conditions on the boundary measures σ L and/or σ R . In practice, one knows the initial condition in an interval larger than X and so one is able to impose σ L and/or σ R . The width of this interval depends on the Lipschitz constant of the flux, T , L and R. As an illustrative example, consider the case where the initial condition is positive and the flux is strictly convex. By the classical method of characteristics, if the initial condition y 0 is positive then so is the solution y for all t ≥ 0. In particular if f is strictly convex we only need to impose knowledge at the left of the box X. Therefore σ L has to be known for all t ∈ T, and σ R is unconstrained. We refer to [START_REF] Leveque | Numerical methods for conservation laws[END_REF] for a more precise discussion on the choice of the boundary constraint.

A convex optimization approach for mv solutions on compact sets

In the latter section, we introduced mv solutions for scalar hyperbolic equations. Note that measures are fully characterized by their moments on compact sets, see e.g. [24, p. 52]. This means in particular that moments are the quantities of interest. The aim of this section is to express formulations ( 15)-( 16) as constraints on the moments, to explain how one can compute numerically these moments thanks to the moment-SOS hierarchy. We also show how one can interpret these moments in the case where the initial measure is concentrated.

Moment constraints for the entropy mv solution

Let ν ∈ M (K) + , with K := T×X×Y. In the following, we derive moment constraints that will imply that ν can be desintegrated as follows dν(t, x, y) = dt dx dµ (t,x) (dy) [START_REF] Goluskin | Bounds on mean energy in the Kuramoto-Sivashinsky equation computed using semidefinite programming[END_REF] or, equivalently,

ν = λ T λ X µ (t,x) , ( 18
)
where µ is an entropy mv solution satisfying [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF] and [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF]. In [START_REF] Goluskin | Bounds on mean energy in the Kuramoto-Sivashinsky equation computed using semidefinite programming[END_REF] the measure ν is called an occupation measure and the Young measure µ is its conditional measuring y given t and x. We also need to introduce the following time boundary measures dν 0 (t, x, y) := δ 0 (dt) dx σ 0 (dy), dν T (t, x, y) := δ T (dt) dx σ T (dy) [START_REF] Handelman | Representing polynomials by positive linear functions on compact convex polyhedra[END_REF] whose supports are K 0 := {0}×X×Y and K T := {T }×X×Y respectively. Similarly, we introduce the following space boundary measures.

dν L (t, x, y) := dt δ L (dx) σ L (dy), dν R (t, x, y) := dt δ R (dx) σ R (dy) (20)
whose supports are given by K L := T × {L} × Y and K R := T × {R} × Y respectively. First, to ensure that the marginal of ν with respect to t and x is the Lebesgue measure on T × X, it suffices to impose that:

K t α 1 x α 2 dν(t, x, y) = T×X t α 1 x α 2 dt dx, α ∈ N 2 . ( 21
)
In a similar manner, we can enforce the respective marginal of the boundary measures to be products of an Dirac measure and the Lebesgue as follows

K 0 0 α 1 x α 2 dν 0 (t, x, y) = X 0 α 1 x α 2 dx, α ∈ N 2 , ( 22
)
K T T α 1 x α 2 dν T (t, x, y) = X T α 1 x α 2 dx, α ∈ N 2 , ( 23
)
K L t α 1 L α 2 dν L (t, x, y) = T t α 1 L α 2 dt, α ∈ N 2 (24)
and

K R t α 1 R α 2 dν R (t, x, y) = T t α 1 R α 2 dt, α ∈ N 2 . (25)
Next, we aim at proving that ( 15) and ( 16) can also be expressed by moment constraints. We split the exposition into two steps: the first one deals with [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF], while the second deals with (16).

First step: enforcing (15) by moment constraints

Lemma 1. Let φ α 1 (t, x, y) := t α 1 x α 2 y and φ α 2 (t, x, y) := t α 1 x α 2 f (y) for α ∈ N 2 . Linear constraint (15) is equivalent to K ∂φ α 1 ∂t + ∂φ α 2 ∂x dν + K 0 φ α 1 dν 0 - K T φ α 1 dν T + K L φ α 2 dν L - K R φ α 2 dν R = 0 (26) for all α ∈ N 2 .
Proof of Lemma 1 Since T × X is a compact set, as a consequence of the Stone-Weierstrass theorem, we can restrict the test functions to ψ 1 = t α 1 x α 2 for α ∈ N 2 to enforce [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF]. 2 9

Second step: enforcing (16) by moment constraints

As noticed in Remark 2, the entropy inequality is satisfied for all convex pairs (η, q) if and only it is satisfied for all Kruzkhov entropies given in [START_REF] Demoulini | Weak-strong uniqueness of dissipative measure-valued solutions for polyconvex elastodynamics[END_REF]. To express [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] as moment constraints, we are faced with two issues: first, taking into account an uncountable family of functions parametrized by v ∈ Y and, second, the absolute value function v → |v| is not a polynomial. To deal with the uncountable family of functions, we introduce v as a new variable. To treat the absolute value, we double the number of measures.

More precisely, we define the Borel measures ϑ + , ϑ -whose supports are defined as follows

K + := spt(ϑ + ) = {(t, x, y, v) ∈ K × Y : y ≥ v}, K -:= spt(ϑ -) = {(t, x, y, v) ∈ K × Y : y ≤ v}.
Similarly, we define the time boundary measures ϑ + 0 , ϑ - 0 , ϑ + T and ϑ - T with the following supports

K + 0 := spt(ϑ + 0 ) = {(t, x, y, v) ∈ K 0 × Y : y ≥ v}, K - 0 := spt(ϑ - 0 ) = {(t, x, y, v) ∈ K 0 × Y : y ≤ v}, (27)
and

K + T := spt(ϑ + T ) = {(t, x, y, v) ∈ K T × Y : y ≥ v}, K - T := spt(ϑ - T ) = {(t, x, y, v) ∈ K T × Y : y ≤ v}. (28)
Finally, let us define the space boundary measures ϑ + L , ϑ - L , ϑ + R and ϑ - R with the following supports

K + L := spt(ϑ + L ) = {(t, x, y, v) ∈ K L × Y : y ≥ v} K - L := spt(ϑ - L ) = {(t, x, y, v) ∈ K L × Y : y ≤ v} (29)
and

K + R := spt(ϑ + R ) = {(t, x, y, v) ∈ K R × Y : y ≥ v}, K - R := spt(ϑ - R ) = {(t, x, y, v) ∈ K R × Y : y ≤ v}. (30)
We are now in position to state the following lemma.

Lemma 2 (Recovering all Kruzkhov entropies). Assume that

ϑ + + ϑ -= ν ⊗ λ Y , (31)
ϑ + 0 + ϑ - T = ν 0 ⊗ λ Y , ϑ + T + ϑ - T = ν T ⊗ λ Y , (32)
ϑ + L + ϑ - L = ν L ⊗ λ Y , ϑ + R + ϑ - R = ν R ⊗ λ Y . (33)
Then, ( 16) is equivalent to

K + θ(v) ∂ψ 2 ∂t (y -v) + ∂ψ 2 ∂x (f (y) -f (v)) dϑ + + K - θ(v) ∂ψ 2 ∂t (v -y) + ∂ψ 2 ∂x (f (v) -f (y)) dϑ - + K + 0 θ(v)ψ 2 (0, x)(y -v)dϑ + 0 + K - 0 θ(v)ψ 2 (0, x)(v -y)dϑ - 0 - K + T θ(v)ψ 2 (T, x)(y -v)dϑ + T - K - T θ(v)ψ 2 (T, x)(v -y)dϑ - T + K + L θ(v)ψ 2 (t, L)(f (y) -f (v))dϑ + L + K - L θ(v)ψ 2 (t, L)(f (v) -f (y))dϑ - L - K + R θ(v)ψ 2 (t, R)(f (y) -f (v))dϑ + R - K - R θ(v)ψ 2 (t, R)(f (v) -f (y))dϑ - R ≥ 0, (34)
for all nonnegative functions θ ∈ C (Y).

Note that from the Stone-Weierstrass Theorem, the constraints ( 31), ( 32) and ( 33) can be expressed as moment constraints: (31) holds if and only if, for all α ∈ N 4 ,

K + ∪K - t α 1 x α 2 y α 3 v α 4 d(ϑ + + ϑ -)(t, x, y, v) = K t α 1 x α 2 y α 3 dν(t, x, y) Y v α 4 dv (35)
and similarly for [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] and [START_REF] Rubio | Nonlinear theory of generalized functions[END_REF].

Proof of Lemma 2: For conciseness, we focus only on the first two term in [START_REF] Whitham | Linear and nonlinear waves[END_REF]. The terms considering the boundary measures can be treated similarly. Let us prove that if for all nonnegative functions θ ∈ C 1 (Y) and all nonnegative functions ψ 2 ∈ C 1 (T×X),

K + θ(v) ∂ψ 2 ∂t (y -v) + ∂ψ 2 ∂x (f (y) -f (v)) dϑ + + K - θ(v) ∂ψ 2 ∂t (v -y) + ∂ψ 2 ∂x (f (v) -f (y)) dϑ -= K + ∪K - θ(v) ∂ψ 2 ∂t |y -v| + ∂ψ 2 ∂x sign(y -v)(f (y) -f (v)) d(ϑ + + ϑ -) ≥ 0 (36)
then the following inequality holds, for all test functions ψ 2 ∈ C 1 (T×X) and all v ∈ Y:

T×X×Y ∂ψ 2 ∂t |y -v| + ∂ψ 2 ∂x sign(y -v)(f (y) -f (v))dν ≥ 0. ( 37
)
First, observe that (31) implies that

K + ∪K - θ(v) ∂ψ 2 ∂t |y -v| + ∂ψ 2 ∂x sign(y -v)(f (y) -f (v)) d(ϑ + + ϑ -) = Y θ(v) T×X×Y ∂ψ 2 ∂t |y -v| + ∂ψ 2 ∂x sign(y -v)(f (y) -f (v)) dν dv. (38)
Then, since (36) holds for any nonnegative functions θ, and y -v = |y -v| on spt(ϑ + ) (resp. v -y = |y -v| on spt(ϑ -)),

T×X×Y ∂ψ 2 ∂t |y -v| + ∂ψ 2 ∂x sign(y -v)(f (y) -f (v)) dν ≥ 0. ( 39
)
2

In order to express [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] as moment constraints, it remains to prove that the functions ψ 2 and θ can be replaced by suitable polynomials. Here, in contrast with the first step, where the functions ψ 1 were unconstrained, the functions ψ 2 and θ have to be nonnegative. To address this issue, we again use positivity certificates from real algebraic geometry.

Lemma 3. Let φ +,α 1 (t, x, y, v) := t α 1 (T -t) α 2 (x -L) α 3 (R -x) α 4 (v -y) α 5 (ȳ -v) α 6 (y -v), φ -,α 1 (t, x, y, v) := t α 1 (T -t) α 2 (x -L) α 3 (R -x) α 4 (v -y) α 5 (ȳ -v) α 6 (v -y), φ +,α 2 (t, x, y, v) ::= t α 1 (T -t) α 2 (x -L) α 3 (R -x) α 4 (v -y) α 5 (ȳ -v) α 6 (f (y) -f (v)), φ -,α 2 (t, x, y, v) := t α 1 (T -t) α 2 (x -L) α 3 (R -x) α 4 (v -y) α 5 (ȳ -v) α 6 (f (v) -f (y)) ( 40
)
for α ∈ N 6 . Then, ( 16) is equivalent to

K + ∂φ +,α 1 ∂t + ∂φ +,α 2 ∂x dϑ + + K - ∂φ -,α 1 ∂t + ∂φ -,α 2 ∂x dϑ - + K + 0 φ +,α 1 dϑ + 0 + K - 0 φ -,α 1 dϑ - 0 - K + T φ +,α 1 dϑ + T - K - T φ -,α 1 dϑ - T + K + L φ +,α 2 dϑ + L + K - L φ -,α 2 dϑ - L - K + R φ +,α 2 dϑ + R - K - R φ -,α 2 dϑ - R ≥ 0 (41)
for all α ∈ N 6 .

Proof of Lemma 3:

The proof relies on a result of real algebraic geometry. Again, invoking the Stone-Weierstrass Theorem, in [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] we can restrict the test functions ψ 2 and θ to be polynomials. To enforce their positivity, we use Handelman's Positivstellensatz [START_REF] Handelman | Representing polynomials by positive linear functions on compact convex polyhedra[END_REF] that implies that

ψ 2 (t, x) = α 1 ,α 2 ,α 3 ,α 4 ∈N 4 c ψ 2 α t α 1 (T -t) α 2 (x -L) α 3 (R -x) α 4 , θ(v) = α 5 ,α 5 ∈N c θ α (v -y) α 5 (ȳ -v) α 6 (42)
with finitely many positive real coefficients c ψ 2 α , c θ α . Now, (41) implies that

α∈N 6 c ψ 2 α c θ α K + ∂φ +,α 1 ∂t + ∂φ +,α 2 ∂x dϑ + + K - ∂φ -,α 1 ∂t + ∂φ -,α 2 ∂x dϑ - + K + 0 φ +,α 1 dϑ + 0 + K - 0 φ -,α 1 dϑ - 0 - K + T φ +,α 1 dϑ + T - K - T φ -,α 1 dϑ - T + K + L φ +,α 2 dϑ + L + K - L φ -,α 2 dϑ - L - K + R φ +,α 2 dϑ + R - K - R φ -,α 2 dϑ - R ≥ 0, (43)
which, by linearity of the integrals and the derivatives, recovers (34) for ψ 2 and θ given in (42). Consequently, by Lemma 2, (34) implies that (16) holds. 2

Remark 4. Note that the measure defined in (17) is similar to the occupation measure introduced in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], which deals with optimal control of nonlinear finite-dimensional systems. This notion has been further used in many other contexts, as for instance the computation of region of attraction [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF]. Therefore, the formulation given in (15)-( 16) might be instrumental to solve other problems than computing numerically the solution of scalar hyperbolic PDE.

The next section aims at showing that a moment formulation can be numerically solved thanks to the moment-SOS hierarchy and SDP.

The Generalized Moment Problem and its relaxations

Roughly speaking, the Generalized Moment Problem (GMP) is an infinite-dimensional linear optimization problem on finitely many Borel measures ν i ∈ M (K i ) + whose supports are contained in given sets K i ⊆ R n i , with i = 1, . . . , k and n i ∈ N. That is, one is interested in finding measures whose moments satisfy (possibly countably many) linear constraints and which minimize a linear criterion. In full generality, the GMP is intractable, but if all K i are basic semi-algebraic sets and the integrands are polynomials (semi-algebraic functions are also allowed1 ), then one may provide an efficient numerical scheme to approximate as closely as desired any finite number of moments of optimal solutions of the GMP. It consists of solving a hierarchy of semidefinite programs2 of increasing size. Convergence of this numerical scheme is guaranteed by invoking powerful results from Real Algebraic Geometry (essentially positivity certificates).

Let h i ∈ R[w i ] and h i,k ∈ R[w i ] be polynomials in the vector of indeterminates w i ∈ R n i and let b k be real numbers, for finitely many i = 1, 2, . . . , N and countably many k = 1, 2, . . .. The GMP is the problem

ρ := inf ν N i=1 K i h i dν i s.t. N i=1 K i h i,k dν i b k , k = 1, 2, . . . ν i ∈ M (K i ) + , i = 1, . . . , N. (44)
Entropy mv solution as a GMP In the scalar hyperbolic case, the measures ν i under consideration are ν, ν T , ν 0 , ν R , ν L and all the measures we have introduced when transforming the Kruzkhov inequality into moment constraints. The sets K i correspond to T, X and Y. Finally, the polynomials h i,j are given in (26) (conservation law) (41) (entropy inequality), (35) (Kruzhkov entropies), and (21-25) (boundary measures).

We may also define an objective functional

K hdν + K 0 h 0 dν 0 + K T h T dν T + K L h L dν L + K R h R dν R , ( 45
) with h, h 0 , h T , h L , h R ∈ R[t, x, y].
If σ 0 = δ y 0 (x) with y 0 an initial condition in ( 13)-( 14) and, in addition, if one imposes suitable boundary measures as exposed in Remark 3, then this objective functional is not especially useful to recover the entropy mv solution of scalar hyperbolic PDE, since the corresponding Young measure is concentrated as a consequence of Theorem 1: there is nothing to be optimized. However, with such an objective functional, one can compute quantities of interest such as the energy of the solution. Moreover, our aim is to relax the GMP in order to solve it numerically and, then, this objective functional might be helpful to accelerate the convergence of the corresponding relaxations. We refer to Section 4 for more discussions about the choice of objective functionals for the Riemann problem of the Burgers equation.

Finally where the measures defined in ( 31)-( 33) and related to the Kruzkhov entropies are considered as implicit variables.

From measures to moments Instead of optimizing over the measures in problem (46), we optimize over their moments. For simplicity and clarity of exposition, we describe the approach in the case of a single unknown measure ν, but it easily extends to the case of several measures. So consider the simplified GMP:

ρ = inf ν K hdν s.t. K h k dν b k , k = 1, 2, . . . ν ∈ M (K) + . (47)
The moment sequence z = (z α ) α∈N n of a given measure ν ∈ M (K) + is defined by

z α = K w α dν, α ∈ N n (48)
where

w α = w α 1 1 • . . . • w αn n .
Conversely, given a sequence (z α ) α∈N n , if (48) holds for some ν ∈ M (K) + we say that the sequence has the representing measure ν. Recall that measures on compact sets are uniquely characterized by their moments; see e. p α w α . Next, integration of p with respect to a measure ν involves only finitely many moments:

K p dν = K α∈N n d p α w α dν = α∈N n d p α K w α dν = α∈N n d p α z α .
Next, define a pseudo-integration with respect to an arbitrary sequence z ∈ R N n by:

z (p) := α∈N n p α z α (49)
and z is called the Riesz functional. Moment sequences can be characterized via the Riesz functional:

Theorem 2 (Riesz-Haviland [24, Theorem 3.1]). Let K ⊆ R n be closed. A real sequence z is the sequence of some measure ν supported on K if and only if z (p) ≥ 0 for all p ∈ R[w] nonnegative on K.

Assuming that K is closed, we can reformulate the GMP (47) as a linear problem on moment sequences. Consider the optimization problem:

ρ * = inf z z (h) s.t. z (h k ) b k , k = 1, 2, . . . z (p) ≥ 0, for all p ∈ R[w] nonnegative on K. ( 50
)
By Theorem 2, the two formulations ( 50) and (47) are equivalent. Of course problem (50) is still numerically intractable.

The second and last step to approximate GMPs numerically consists of replacing the cone of polynomials nonnegative on K by a more tractable cone. This is where one exploits the fact that K is basic semi-algebraic set.

From nonnegative polynomials to sums of squares Characterizing nonnegativity of polynomials is an important issue in real algebraic geometry. Let K be a basic semi-algebraic set, i.e.:

K = {w ∈ R n : g 1 (w) ≥ 0, . . . , g m (w) ≥ 0}. ( 51
)
for some polynomials g 1 , . . . , g m ∈ R[w], and assume that K is compact. In addition assume that one of the polynomials, i.e. the first one, is g 1 (w) := N -n i=1 w 2 i for some N ∈ N sufficiently large 3 . For notational convenience we let g 0 (w) := 1.

Remark 5. Note that the compact sets T, X and Y which are defined in the latter section can be expressed as basic semi-algebraic compact sets. Indeed, one has

T = {t ∈ R : t(T -t) ≥ 0}, X = {x ∈ R : (x-L)(R-x) ≥ 0}, Y = {y ∈ R : (y-y)(ȳ-y) ≥ 0}. ( 52
)
Recall that a polynomial s ∈ R[w] is a sum of squares (SOS) if there are finitely many polynomials q 1 , . . . , q r such that s(w) = r j=1 q j (w) 2 for all w. The following result due to Putinar [START_REF] Putinar | Positive polynomials on compact semi-algebraic sets[END_REF] is crucial to approximate (50) numerically.

Theorem 3 (Putinar's Positivstellensatz). If p > 0 on K then p = m j=0 s j g j for some SOS polynomials s j ∈ R[w], j = 0, 1, . . . , m.

By a density argument, checking nonnegativity of z on polynomials nonnegative on K can be replaced by checking nonnegativity only on polynomials that are strictly positive on K and hence on those that have an SOS representation as in Theorem 3.

Next, for a given integer d, denote by Σ[w] d ⊂ R[w] the set of SOS polynomials of degree at most 2d, and define the cone Q(g) ⊂ R[w] by: d) be the vector of monomials of degree at most d. For instance, for n = 2 and d = 3,

Q d (g) :=    m j=0 σ j g j : deg(σ j g j ) ≤ 2d, σ j ∈ Σ[w], j = 0, 1, . . . , m    (53) and observe that Q d (g) ⊂ Q d+1 (g) consist of polynomials positive on K for all d. Let v d := (w α ) |α|≤d ∈ R[w] s(
v d = (1 w 1 w 2 w 2 1 w 1 w 2 w 2 2 w 3 1 w 2 1 w 2 w 1 w 2 2 w 3
2 ). For j = 0, 1, . . . , m, let d j denote the smallest integer larger than or equal to deg(g j )/2, let M d-d j (g j z) denote the real symmetric matrix linear in z corresponding to the entrywise application of z to the matrix polynomial g j v d-d j v T d-d j . For j = 0, i.e., g 0 = 1, this matrix is called moment matrix. It turns out that z (g j q 2 ) ≥ 0 for all q ∈ R[w] d if and only if M d-d j (g j z) 0 where the inequality means positive semidefinite. Therefore checking whether z is nonnegative on Q d (g) reduces to checking whether M d-d j (g j z) 0 for j = 0, 1, . . . , m, which are convex linear matrix inequalities in z.

Moment-SOS hierarchy The following finite-dimensional semidefinite programming (SDP) problems are relaxations of the moment problem (50):

ρ * d = inf z z (h) s.t. z (h k ) b k , deg(h k ) ≤ 2d, k = 1, 2, . . . M d-d j (g j z) 0, j = 0, 1, . . . , m (54)
and they are parametrized by the relaxation order d.

Theorem 4 (Convergence of the moment-SOS hierarchy [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]). Assume there is some M > 0 and k ∈ N such that z (h k ) ≤ b k implies z (1) < M . Then:

(i) The semidefinite relaxation (54) has an optimal solution z d = (z d α ), ρ d ≤ ρ d+1 and lim d→∞ ρ d = ρ * ;

(ii) If (50) has a unique minimizer z * , then

lim d→∞ z d α = z * α , ∀ α ∈ N n . ( 55
)
A proof is provided in [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF], but, for clarity, we recall the steps and the arguments used to obtain the result.

Proof of Theorem 4: Let z := (z α ) α∈N n 2d be a feasible solution of (54). From M d-d 1 (g 1 z)

0 we obtain

n i = 1 z (w 2 i ) ≤ N z 0 ,
and in particular z (w 2 i ) ≤ N z 0 , i = 1, . . . , n. By iterating one also obtains (w 2d i ) ≤ N d z 0 , i = 1, . . . , n. Moreover, combining with M d (z) 0, from [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]:

|z α | ≤ max z 0 , max i=1,...,n z (w 2d i ) =: τ d , ∀α ∈ N n 2d .
This inequality together with the fact that z (1) = z 0 is bounded implies that the moment sequence z is uniformly bounded. Then, the feasible set of (54) is closed, bounded, and hence compact. Hence (54) has an optimal solution z d .

Next, for a given d, let z d be an optimal solution to (54) and complete z d with zeros to make it an infinite sequence indexed by α ∈ N n . Then define:

ẑd α := z d α τ k , ∀α ∈ N n ; 2k -1 ≤ |α| ≤ 2k; k = 1, . . . , d. (56)
By construction, |ẑ d α | ≤ 1, for all α ∈ N n and therefore ẑd becomes an element of the unit ball B 1 of the Banach space ∞ of bounded sequences, equipped with the sup-norm. Since ∞ is the topological dual of 1 , by the Banach-Alaoglu theorem [2, Theorem 3.16], B 1 is weak star (sequentially) compact. Hence there exists ẑ ∈ B 1 and a subsequence {d k } ⊂ N such that ẑd k → ẑ for the weak star topology σ( ∞ , 1 ). In particular, for every α ∈ N n , lim k→∞ ẑd k α = ẑ α . Since τ k is bounded for all k = 1, . . . , d, using (56) in the other direction, there exists

z * = (z * α ) α∈N n such that lim k→∞ z d k α = z α , ∀α ∈ N n . (57)
The pointwise convergence (57) implies M d (g j z ) 0 for j = 0, 1, . . . , m. Hence by Theorem 3, z * has a representing measure ν supported on K. In particular, from (57),

z (h k )
b k for all k = 1, 2, . . . which proves that ν is a feasible solution of (47). In addition,

ρ ≥ lim k→+∞ ρ d k = K hdν ≥ ρ , (58)
which proves that ν is an optimal solution of (47). Finally, if (47) has a unique minimizer ν then ν = ν and the convergence (57) holds for the whole sequence, which yields (55). This concludes the proof. 2

Remark 6 (Extension to several measures). Theorem 4 extends naturally to the GMP (44) with finitely many measures. A more detailed discussion is provided in [24, Section 4.5.2 p. 88].

Convergence of the relaxations of (46) Problem (46) can be approximated by a hierarchy of semidefinite relaxations as mentioned in Remark 6. Moreover observe that the mass of all measures appearing in (46) is bounded, because their marginals with respect to time and/or space are Lebesgue. Indeed, for instance, T×X×Y dν = T×X×Y dt dx µ (t,x) (dy) = 1, where we have used the fact that µ is a Young measure.

Then, according to Remark 6 and Theorem 4, optimal solutions of the moment-SOS hierarchy (54) (adapted to the present context) converge to optimal solutions of (46) as d goes to infinity, in the sense of (55). In particular, one may extract the mv solution of [START_REF] Fjordholm | Construction of approximate entropy measure-valued solutions for hyperbolic systems of conservation laws[END_REF] and even obtain the entropy solution of ( 13)-( 14), provided that σ L and/or σ R and σ 0 are concentrated.

Interpretation of the moment solutions

An optimal solution z d at step d of the moment-SOS hierarchy of relaxations (54) adapted to the GMP (46), consists of finite sequences of approximate moments, one for each unknown measure of (46). If one is interested in statistical properties of the mv solution such as its mean or its variance, the moments provide the perfect information, at least for sufficiently large d. However, if one is rather interested in properties of the graph of the entropy solution, a post processing step is required.

An inverse problem Recovering the graph of the solution {(t, x, y(t, x)) : t ∈ T, x ∈ X} ⊂ T × X × Y from the moments of the measure ν = λ T λ X δ y(t,x) is an inverse problem whose detailed study is out of the scope of this paper, see e.g. [START_REF] Claeys | Reconstructing trajectories from the moments of occupation measures[END_REF] in the context of controlled ODEs. However, we briefly outline here one possible strategy with a formal justification. It turns out that it works surprising well in all our examples of the Burgers equation with or without shock.

Let w = (t, x, y) and z α = T×X×Y w α dν denote the vector of moments of ν. For any polynomial p ∈ R[w] d with vector of coefficients p in the monomial basis, it holds

p M d (z)p = p 2 dν.
Consequently, if p is in the kernel of M d (z), we have that

T×X×Y p 2 dν = 0.
In other words, the support of the measure is contained in the zero level set of every polynomial (whose vector of coefficients is) in the kernel of the moment matrix. However, this inclusion can be strict in some cases. Therefore we propose to also consider polynomials corresponding to small eigenvalues. Let us explain this now:

Since the moment matrix is positive semidefinite, it has a spectral decomposition

M d (z) = P EP (59)
where P is an orthonormal matrix whose columns are denoted p i , i = 1, 2, . . . and satisfy p i p i = 1 and p i p j = 0 if i = j, and E is a diagonal matrix whose diagonal entries are eigenvalues e i+1 ≥ e i ≥ 0 of the moment matrix. Each column p i is the vector of coefficients in the monomial basis of a polynomial p i ∈ R[w], so that

p i M d (z)p i = p 2 i dν = e i .
The following result shows that the measure is concentrated on a sublevel set of an SOS polynomial constructed from the spectral decomposition of the moment matrix. which holds since ν is a probability measure and p sos is non-negative. Lemma 4 justifies the following algorithm, which extracts from a grid the values at which the polynomial p sos is small:

Input moment matrix M d (z) of measure ν = λ T λ X δ y(t,x)
, small real > 0, grid points (t i , x j , y k ) i,j,k=1,...,N ⊂ T × X × Y;

Step 1 Compute spectral decomposition (59) of M d (z) and construct SOS polynomial p sos in (60) with the largest number of terms r such that r i=1 e i < ;

Step 2 For each i, j, k = 1, . . . , N , evaluate p i,j,k := p sos (t i , x j , y k );

Step 3 For each i, j = 1, . . . , N , let y i,j := y k * where k * := arg min k p i,j,k ;

Output Approximation (y i,j ) i,j=1,...,N ⊂ Y of y(t, x) at grid points (t i , x j ) i,j=1,...,N ⊂ T × X.

The computational burden is modest: an eigenstructure decomposition at Step 1, and grid point evaluations of polynomial p sos at Step 2.

The Riemann problem for the Burgers equation

For a numerical illustration, we consider the classical Riemann problem (see e.g., [START_REF] Evans | Partial differential equations[END_REF]) for a Burgers equation. In particular, we choose the flux

f (y) = 1 4 y 2 .
The Riemann problem to this conservation law is a Cauchy problem with the following initial condition, piecewise constant with one point of discontinuity:

y 0 (x) = l if x < 0, r if x > 0,
where l, r ∈ R. The solution to the Riemann problem depends strongly on the values of l and r. In particular:

1. If l > r, the shock at the initial condition spreads along the characteristics.

2. If l < r, the solution is not necessarily unique. The entropy condition allows to select the right solution, which is known as a rarefaction wave.

Both cases are interesting from a numerical point of view for their own reasons. In general, the first case is difficult to tackle because of the discontinuity. In general, numerical schemes based on discretization tend to smoothen out the shock. Indeed, recovering numerically the exact point of discontinuitiy is a challenge for these schemes.

In the second case the solution is continuous, but not necessarily unique. For the Burgers equation, it has been shown that one single entropy condition is sufficient to guarantee uniqueness of the solution [START_REF] Delellis | Minimal entropy conditions for Burgers equation[END_REF]. To the best of our knowledge, there is no Table 1: Approximation of y(0.75, x) with Godunov and GMP.

such that the scheme stays stable. In Table 1, we display the obtained values from this approach on an interval around the shock. We can see the typical behaviour of shock smoothing. In contrast, the values obtained by our GMP approach exactly represent the position of the shock.

Rarefaction waves

Now let l = 0 and r = 1. As it has been noticed before, with such an initial condition, entropy conditions are crucial to select the right solution, i.e., the solution with a good physical meaning. The analytical entropy solution corresponding to this example is

y(t, x) =    0 x ≤ 0, 2x t 0 ≤ x ≤ t 2 , 1 x ≥ t 2 . (62)
Numerically implementing all entropy pairs of Kruzkhov is possible (as seen in Section 3.1), but heavy. It is known that the entropy η(y) = y 2 provides all necessary information to make the entropy solution unique for Burgers equation [START_REF] Delellis | Minimal entropy conditions for Burgers equation[END_REF]. Then, instead of using all Kruzkhov pairs, we propose the following family of entropies in this example:

η k (y) = y k , ∀k ∈ N (63)
and the corresponding polynomial functions q k . Note that η is strictly convex on Y = [0, 1]. In particular, we do not have to split the measures in [START_REF] Godunov | A difference method for numerical calculation of discontinuous solutions of the equations of hydrodynamics[END_REF] into two measures, since there is no absolute value appearing in (63). It is neither necessary to introduce a lifting variable as was discussed in Section 3.1. Finally, we define the sum over all entropy constraints as an objective function to be maximized. Solving the relaxation of order d = 6 (i.e. moments of degree up to 12), we obtain the following moments for the marginal on y:

(z 0,0,k ) k=0,1,... = (1.0000, 0.3750, 0.3333, 0.3125, 0.3000, 0.2917, 0.2857, 0.2812, . . .) which, again up to numerical accuracy, coincide with the moments of the actual analytic entropy solution. Applying the algorithm from Section 3.3 with = 10 -6 yields a polynomial p sos with r = 48 terms in the approximate kernel of the moment matrix of size 84, and the approximated solution represented on Figure 2.

Conclusion

In this paper, we have provided a new method to solve scalar polynomial hyperbolic partial differential equations. This method relies on the moment-SOS hierarchy sur-veyed in [START_REF] Lasserre | Moments, positive polynomials and their applications[END_REF]. More precisely, we have proved that the truncated moments associated to the measure-valued solution formulation converge to the Dirac measure concentrated on entropy solution to the scalar polynomial solution. we believe that all the arguments of our paper extend to the case of a spatial variable x of dimension greater than one.

The idea of solving linear problems on measures to solve nonlinear differential equation is not new. In the context of nonlinear ordinary differential equations (ODEs), the linear problems involved measures called occupation measures. Roughly speaking, occupation measures allow to measure the time spent by a graph of the trajectory of the ODE in a given subset of the state space. Provided that the nonlinearities considered are polynomial, one can transform the nonlinear ODE into a linear moment problem, in turn solved numerically with the moment-SOS hierarchy, see [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] and the survey [START_REF] Henrion | Linear conic optimization for nonlinear optimal control[END_REF]. Therefore, the current paper can be seen as an extension to (uncontrolled) PDEs of the results provided in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] for (controlled) ODEs.

This opens many further research lines. For example:

• One of the most interesting aspect of the notion of very weak solution is the linear formulation on measures of nonlinear differential equations. Such formulations have been useful to solve many problems appearing in the ODE framework, such as optimal control [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF] or approximation of region of attraction [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF]. The challenge was to prove that the measure formulation was not a relaxation of the original nonlinear problem. For the hyperbolic conservation law studied in our paper, we have used entropy inequalities for that purpose. We are wondering whether it is possible to extend these techniques to the case of other nonlinear PDEs.

• A class of other nonlinear PDEs could be parabolic ones. One of the interest of these equations is that they regularize the solution, whatever is the initial condition. Therefore, as it is done for ODEs in [START_REF] Lasserre | Nonlinear optimal control via occupation measures and LMI relaxations[END_REF], it might be possible to define test functions depending on the solution to the parabolic equation and then define an occupation measure associated to the latter. This together with the relaxed control theory surveyed in [START_REF] Fattorini | Infinite dimensional optimization and control theory[END_REF] might be instrumental to solve optimal control problem for nonlinear parabolic equations.

• The Burgers equation is irreversible. Roughly speaking, given a terminal condition y(T, x) with T > 0, there exists a continuum of initial conditions yielding y(T, x), see e.g., [START_REF] Gosse | Filtered gradient algorithms for inverse design problems of one-dimensional Burgers equation[END_REF]. Such a continuum can be described with measures and, hence, our linear formulation might be useful to solve such inverse problems, extending to PDEs what was developed in [START_REF] Henrion | Convex computation of the region of attraction of polynomial control systems[END_REF] for ODEs.

Acknowledgement: The authors would like to thank Matthieu Barreau for his help with the Godunov numerical scheme and Sylvain Ervedoza for all the interesting and encouraging discussions. This work also benefited from feedback from Yann Brenier, Bruno Després, Maxime Herda, Milan Korda, Ondřej Kreml and Josef Málek.

A Proof of Theorem 1

The proof is divided into two steps. The first step consists in proving that v can be replaced by y(t, x) or µ (t,x) , y . The second step aims at proving the contraction inequality given in [START_REF] Delellis | Minimal entropy conditions for Burgers equation[END_REF]. In each step, a special choice of test function is done in order to prove the result.

• First step: Doubling variable

Let us consider the entropy pair given in [START_REF] Demoulini | Weak-strong uniqueness of dissipative measure-valued solutions for polyconvex elastodynamics[END_REF]. For all (s, z) ∈ R + × R, we choose v = y(s, z), where y is an entropy solution to (12):

T 0 R ∂ψ ∂t µ (t,x) , |y -y(s, z)| + ∂ψ ∂x µ (t,x) , sign(y -y(s, z))(f (y) -f (y(s, z)) dx dt + R ψ(0, x) σ 0 , |y -y(s, z)| dx - R ψ(T, x) µ (t,x) , |y -y(s, z)| dx. (64)
Similarly, for all (s, z) ∈ R + × R, we set v = µ (t,x) , y in (3) and use the fact that µ is a probability measure:

as ε goes to 0.

• Second step: Contraction inequality

Given two positive values r ∈ R and T ∈ R + , let us choose ϕ as follows:

ϕ(t, x) = θ ε (t)∆ ε (t, x), (t, x) ∈ R + × R (82)
where From this latter equation, one can conclude the proof when ε goes to 0. Indeed, the left hand side of the inequality can be bounded as follows:

θ ε (t) :=          1 t ≤ T, T -t ε T ≤ t ≤ T + ε, 0 t ≥ T + ε, (83) and
1 ε T +ε T R ∆ ε (t,

  g. [24, p. 52]. Let N n d := {α ∈ N n : |α| ≤ d}, where |α| := n i=1 α i , and s(d) := n+d d . A vector p := (p α ) α∈N n d ∈ R s(d) is the coefficient vector (in the monomial basis) of a polynomial p ∈ R[w] with d = deg(p) expressed as p = α∈N n deg(p)

Lemma 4 (

 4 Concentration inequality). Let r ∈ N and β > 0. Then ν({w : p sos (w) ≤ γ}) ≥ 1 -β. The proof of Lemma 4 follows readily from the inequality ν({w : p sos (w) > γ}) ≤ p sos dν γ = β

Figure 1 :

 1 Figure 1: Approximation of the solution y(t, x) obtained with our GMP approach, in the case of a shock. x 0.1850 0.1855 0.1860 0.1865 0.1870 0.1875 0.1880 0.1885 Godunov 0.9999 0.9991 0.9936 0.9580 0.7647 0.2724 0.0123 0.0000 GMP 1.0000 1.0000 1.0000 1.0000 1.0000 0.0000 0.0000 0.0000

Figure 2 :

 2 Figure 2: Approximation of the solution y(t, x) obtained with our GMP approach, in the case of a rarefaction wave.

  ,x) , |y -y(s, z)| + ∂ψ ∂z µ (t,x) , sign(y -y(s, z))(f (y) -y(s, z)) ds dz+ R ψ(0, z) µ (t,x) , |y -y 0 (z)| dz ≥ 0.(65)Let us choose ψ := ψ(t, x, s, z). Thanks to the two latter inequalities, one hasR + R R + R ∂ψ ∂s + ∂ψ ∂t µ (t,x) , |y -y(s, z)| + ∂ψ ∂z + ∂ψ ∂x µ (t,x) , sign(y -y(s, z))(f (y) -f (y(s, z))) ds dz dx dt + R R ψ(t, x, 0, z) µ (t,x) , |y -y 0 (z)| dz dx + R R ψ(0, x, s, z) σ 0 , |y -y(s, z)| dz dx ≥ 0.(66) Let ρ ε ∈ C 1 (R) satisfy R ρ ε (s)ds = 1. (67)For all ϕ ∈ C

  can prove that, for any continuous function φ := φ(x, z) x, z) -φ(x, x))dt ds → 0 as ε → 0. (80) Finally, using (69) and (70), the equation (66) converges toR + R ∂ϕ ∂t µ (t,x) , |y -y(t, x)| + ∂ϕ ∂x µ (t,x) , sign(y -y(t, x))(f (y) -f (y(t, x))) dx dt + R ϕ(0, x) σ 0 , |y -y 0 (x)| dx ≥ 0,

∆∆∆

  ε (t, x) := r + C(T -t), r + C(T -t) -|x| ε r + C(T -t) ≤ |x| ≤ r + C(T -t) + ε, 0 |x| ≥ r + C(T -t) + ε(84)where C denotes the Lipschitz constant of the function f . Differentating θ ε with respect to t yields∂θ ε (t) (T -t) ≤ |x| ≤ r + C(T -t) + ε, 0 |x| ≥ r + C(T -t) + ε,(86)Finally, differentiating ∆ ε with respect tox yields ε r + C(T -t) ≤ |x| ≤ r + C(T -t) + ε, 0 |x| ≥ r + C(T -t) + ε. ε (t, x) µ (t,x) , |y -y(t, x)| dt dx --t)≤|x|≤r+C(T -t)+ε µ (t,x) , |y -y(t, x)| dt dx -1 ε R + r+C(T -t)≤|x|≤r+C(T -t)+ε sign(x) µ (t,x) , sign(y -y(t, x))(f (y) -f (y(t, x))) dt dx + R ϕ(0, x) σ 0 , |y -y 0 (x)| dx ≥ 0. (88)Note that one has sign(x) µ (t,x) , sign(y -y(t, x))(f (y) -f (y(t, x))) ≤ C µ (t,x) , |y -y(t, x)| . ε (t, x) µ (t,x) , |y -y(t, x)| dt dx ≤ R ϕ(0, x) σ 0 , |y -y 0 (x)| dx.

∆µ

  that, for any t ∈ [T, T + ε] and any |x| ≤ r + ε, one hasr + C(T -t) -|x| ε ε (t, x) µ (t,x) , |y-y(t, x)| dt dx ≤ 1 ε T +ε T |x|≤r+ε µ (t,x) , |y -y(, x)| dt dx. (t,x) , |y -y(, x)| dt dx → |x|≤r σ T , |y -y(T, x)| dx as ε → 0. (93) Similarly, one can prove that R ϕ(0, x) σ 0 , |y -y 0 (x)| dx → |x|≤r+CT σ 0 , |y -y 0 (x)| dx as ε → 0. (94) Finally, it yields, for all positive values T and r |x|≤r σ T , |y -y(T, x)| dx ≤ |x|≤r+CT σ 0 , |y -y 0 (x)| dx.(95)This concludes the proof of Theorem 1.

  see e.g.[START_REF] Dafermos | Hyperbolic conservation laws in continuum physics[END_REF] Theorem 6.2.4]. Since y 0 is bounded in L ∞ , it follows from the maximum principle [6, Theorem 6.3.2] that y(t, .) is bounded in L ∞ for all t ≥ 0. Hence, we can consider that y takes values in the following compact set

  , one is able to define a GMP describing entropy mv solution:

	inf ν, ν T , ν L and/or ν R (45) (objective functional)
	s.t.	(26) (conservation law),
		(41) (entropy inequality),
		(35) (Kruzhkov entropies),
		(21 -25) (boundary measures),
		ν ∈ M (K)

+ (occupation measure), ν T ∈ M (K T ) + (time boundary measure), ν L ∈ M (K L ) + (space boundary measure), and/or ν R ∈ M (K R ) + (space boundary measures) (46)

  1 c (R + × R), one defines ψ as follows (t,x) , |y -y 0 (x)| dx ≥ 0. , up to a change of variable, one has, for any continuous function φ := φ(t, s) -φ(t, t))dt ds → 0 as ε → 0.

	We aim at proving that
										ρ ε		t -s ε	→ δ(t -s) as ε → 0,	(71)
	and									ρ ε			x -z ε	→ δ(x -z) as ε → 0,	(72)
	so that we will have, thanks to (69) and (70)
	R + R	∂ϕ ∂t	µ (t,x) , |y -y(t, x)| +	∂ϕ ∂x	µ (t,x) , sign(y -y(t, x))(f (y) -f (y(t, x)) dx dt
	+		R	ϕ(0, x) µ (73)
	Noticing that, for a fixed t > 0,
														2	R	1 2ε	ρ	t -s ε	ds = 2,	(74)
							R R	1 ε	ρ		t -s ε	φ(t, s)dt ds = 2
																(76)
	Therefore, for any positive value k, it follows that
	R + R +	1 ε	ρ	t -s 2ε		φ(t, s) -φ(t, t)dt ds ≤M ε	R |t-s|≤2ε,|s|≤k,|t|≤k	1 ε	ρ	t -s 2ε	dt ds
																≤4M ε k.
																(77)
	Note that
															M ε → 0 as ε → 0.	(78)
	Hence,
				R + R +	1 ε	ρ			t -s 2ε	(φ(t, s)
				ψ(t, x, s, z) =	1 ε 2 ρ ε		t -s 2ε	ρ ε	x -z 2ε	ϕ	t + s 2	,	x + z 2	.	(68)
	Therefore
				∂ ∂t ψ	ψ +	∂ ∂s ψ		=	1 ε 2	∂ϕ ∂t	t + s 2	,	x + z 2	ρ ε	x -z 2ε	ρ ε	t -s 2ε	(69)
	and
				∂ ∂x ψ	+	∂ ∂z ψ		=	1 ε 2	∂ϕ ∂x	t + s 2	,	x + z 2	)ρ ε	x -z 2ε	ρ ε	t -s 2ε	.	(70)

thenR φ(t, t)dt. (

75

)

Since φ is continuous and lies in a compact set, then it is uniformly continuous. Therefore, one has |t -s| ≤ 2ε ⇒ |φ(t, s) -φ(t, t)| ≤ M ε .

  x) µ (t,x) , |y -y(t, x)| dt dx

	≤	1 ε	T +ε T	|x|≤r+ε	r + C(T -t) -|x| ε	µ (t,x) , |y -y(t, x)| dt dx
	≤	1 ε	T +ε T	|x|≤r+ε

r + C(T -t) -|x| ε µ (t,x) , |y -y(t, x)| dt dx.

A semi-algebraic function is a function whose graph is a semi-algebraic set, i.e. it is described by finitely many polynomial inequalities and equations.

A semidefinite program is a particular class of a convex conic optimization problem that can be solved numerically efficiently.

This condition is slightly stronger than asking K to be basic semi-algebraic compact. However, the inequality N -n i=1 w 2 i ≥ 0 can always be added as a redundant constraint to the description of a basic semi-algebraic compact set.

This work was partly funded by the ERC Advanced Grant Taming and by project 16-19526S of the Grant Agency of the Czech Republic.

similar result for the uniqueness of entropy mv solutions for Burgers equation with concentrated initial data, except for classical solutions [START_REF] Demoulini | Weak-strong uniqueness of dissipative measure-valued solutions for polyconvex elastodynamics[END_REF].

We present numerical results for both cases. We are going to consider l, r ∈ {0, 1}. Following the discussion yielding [START_REF] Evans | Partial differential equations[END_REF], we can assume that the solution takes values only in Y = [0, 1]. The time-space-window on which we consider the solution is T

]. Further note that, from the initial condition, we can derive that y(t, L) = l, ∀t ∈ T.

Moreover, due to positivity of y, the solution on T × X does not depend on the initial condition for x > 1 2 . Remark on the significance of the numerical results upfront We need to emphasize that these experiments are by no means conclusive. Our implementation is based on the Matlab interface Gloptipoly3 [START_REF] Henrion | Gloptipoly 3: moments, optimization and semidefinite programming[END_REF] and the SDP solver of MOSEK [START_REF] Dahl | Extending the conic optimizer in MOSEK with semidefinite cones[END_REF]. The purpose of the numerical examples is to show that our framework actually works in practice and with a proper implementation might actually provide an alternative to schemes based on discretization.

Shock waves

Let l = 1 and r = 0. As it has been noticed before, with such an initial condition the solution is discontinuous, for all t > 0. The unique analytical solution corresponding to this initial condition is

As an objective function, we choose the default implemented in Gloptipoly, which minimizes the trace of the moment matrix. Since the trace is the convex envelope of the rank on the set of matrices with norm less than one, this is likely to cause early convergence of the moment-SOS hierarchy: low rank solutions correspond to measures supported on sets of zero Lebesgue measure. As in this case the marginal of ν with respect to y is supported on {0, 1} we expect this criterion to be appropriate to accelerate convergence. Indeed, for d = 6 (i.e. moments of degree up to 12) we end up with the following moments for y:

(z 0,0,k ) k=0,1,... = (1.0000, 0.6250, 0.6250, 0.6250, 0.6250, . . .) which correspond (up to numerical accuracy) exactly with the moments of the analytic solution.

Localizing the shock In order to approximate the solution from our approximated moments we follow the path lined out in Section 3.3. Applying our algorithm with = 10 -6 yields a polynomial p sos with r = 54 terms in the approximate kernel of the moment matrix of size 84, and to the approximated solution represented on Figure 1.

As already mentioned the computed moments can be used in order to approximate the location of the shock at some given time t. Here we will take t = 0.75, consequently the shock is located at exactly x = 0.1875. We used a standard Godunov scheme (we refer to [START_REF] Leveque | Numerical methods for conservation laws[END_REF] for more details) to compute the solution up to this time. For space discretization, we took a mesh size of 0.0005 and a consistent discretization in time