Virginie Fresse
email: virginie.fresse@univ-st-etienne.fr

Catherine Combes
email: catherine.combes@univ-st-etienne.fr

Belhassen Hatem

Hubert

Mathematical models applied to on-chip network on FPGA for resource estimation

Keywords: Design Space Exploration, NoC dimensioning, FPGA, mathematical modeling, resource estimation

One main challenge of prototyping a SoC (System on Chip) on FPGA (Field Programmable Gate Array) is to tune at best the communication architecture according to the task graph of an application and the available resources of the chosen FPGA. The exploration of the potential design candidates is time consuming, tedious and does not scale. The sheer number of parameters leads to a wide design space that cannot be explored in a limited time.

The aim of this paper is to identify mathematical models applied to NoC to estimate FPGA resources. Mathematical models are obtained from a database containing a set of observed results. Using the database, the Pearson's correlation coefficient and the variable clustering are used to set the most appropriate variables and constants. The mathematical models are obtained and then validated with a set of experimental results. The validation shows that the error rate between observed results and the analytically estimated results is less than 5%. The designer can therefore tune the NoC in shorter exploration time.

I. INTRODUCTION

Systems On Chip (SoC) using Network on Chip (NoC) are the most appropriate systems for real time embedded applications. The SoC is a set of hardware or software IPs (Intellectual Properties) connected to the NoC. NoCs are emerging communication structures as they provide high bandwidth and high scalability with low power. In the design of SoC, the number and type of IPs are extracted from the algorithm. Signal and image processing algorithms are mainly described as a graph with functions and flow related to data or control dependencies. In most cases, one function is considered as an IP in the SoC. The flows between functions are implemented by means of the communication structure (NoC). According to the number of IPs, the communication structure is tuned. Tuning the NoC consists in selecting appropriate parameters of the NoC. The number of parameters and their associated values are high. Exploring all appropriate solutions is an intensive time process because of the sheer number of parameters required for the NoC. The designer selects the NoC without exploring all candidates, gaining significant time in the development process but the chosen solution is not always optimal. The Field Programmable Gate Array (FPGA) devices are widely used for prototyping systems. FPGA can be used to emulate the NoC performances within a fast design space exploration cycle. The performance metrics on FPGA are timing (bandwidth, latencies), area and energy consumption. Emulation gives precise timing and power evaluations in a shorter cycle compared to simulation [START_REF] Genko | A Complete Network-On-Chip Emulation Framework[END_REF]. Emulation on FPGA is not suitable for area estimation. Each NoC candidate has to be synthesized then placed and routed to obtain the number of resources required. Area estimation can be explored after either the synthesis or the place and route process. These processes are time consuming. With large size of FPGA, this process can run for several hours for one NoC candidate. Therefore it is not possible to synthesize all candidates to evaluate the number of resources required. Area estimation is important in order to find architectural solutions that: 1) suit to the target FPGA 2) correspond to application requirements 3) provide efficient timing results. The aim of this work is to provide a methodological framework based on mathematical modeling. The identified models help the designer to select the appropriate NoC candidates from a restricted number of implementation with FPGA and algorithm constraints. The contribution of this paper is to show the feasibility of creating a mathematical model for sizing a NoC on FPGA. This model was validated by a comprehensive set of experimentations. It guarantees a reduction of time necessary to the design space exploration (DSE) of NoC in the field of signal and image processing.

The paper is organized into 9 sections. Related works are given in section 2. The design space exploration of NoC on FPGA including basis elements (NoC, FPGA, application and devices) is detailed in section 3. The methodological framework is described in section 4. The development of the mathematical models is presented in section 5. Validation of both experiments XP1 and XP2 for different sizes of NoC on a set of FPGAs are described in section 6. The impact of the synthesis optimization goals is studied in section7. The limitations of the models are in section8. Conclusion and future works are in section 9.

II. RELATED WORKS

NoCs have emerged as efficient scalable and low power communication structures for many-core SoC (System On Chip including several hundred or thousands of cores). Many NoCs are designed for FPGA devices [START_REF] Moraes | HERMES: an Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF][3][4] and application-specific NoC design flows are proposed [START_REF] Sahu | A survey on application mapping strategies for Network On Chip design[END_REF]. In the design flow, the application described as a task graph is mapped to the topology graph. The topology graph is the NoC structure with all parameters already specified. These design flows do not explore the design space of the NoC. Design space explorations for the NoC are mainly based on power consumption and timing [START_REF] Genko | A Complete Network-On-Chip Emulation Framework[END_REF][5] [START_REF] Bhat | Energy models for network on Chip Components[END_REF][7] [START_REF] Jena | System Level approach to NoC Design Space exploration[END_REF]. ORION is a tool designed for fast and accurate power and area model on Integrated Circuit (IC) [START_REF] Kahng | ORION 2.0: a fast and accurate NoC power and area model for early stage design space exploration[END_REF]. The tool explores the area occupied (mm2) and the power (mW) by the NoC used on 65 nm chips when routers and links increase. The 3D Tezzaron design flow also explores the 3D NoC to reduce the area of the chip and interconnects on ASIC to optimize power [START_REF] Jena | System Level approach to NoC Design Space exploration[END_REF]. A system level approach is proposed to explore the NoC design space with an objective to minimize the energy consumption and link bandwidth (timing). These works concern power and timing evaluation for ASIC. NOCDEX is a tool to evaluate the impact of various options on area, number of cycles and execution time on FPGA [START_REF] Li | NOCDEX: Network on Chip Design Space Exploration Through Direct Execution and Options Selection Through Principal Component Analysis[END_REF]. The tool evaluated the number of cycles according to the number of slices and the maximum frequency for a cascade NoC with 4 masters and 4 slaves. Power models at different abstraction levels have also been proposed for a variety of networks in the past. Models for resource estimation of the NoC on FPGA have not been fully explored yet. A power area analysis of NoCs in FPGAs has been proposed in [START_REF] Binesh Marvasti | A power-area analysis of NoCs in FPGAs[END_REF]. The analysis is based on the analysis of power and area of the router for the 4×4 torus topology. This work only considers the routing blocks, no any others blocks or routing. The number of links varies according to the position of the router so that it has a huge impact of the total number of resources. It is necessary to analyze the global structure to obtain a precise model depending on the topology. We propose to explore the design space of NoCs to estimate the area metric on FPGA. Explorations are constrained by the target FPGA and the data flow graph from the application.

III. DESIGN SPACE EXPLORATION OF NOC ON FPGA

Design Space Exploration (DSE) refers to the activity of exploring design alternatives prior to implementation [START_REF] Kang | An approach for effective Design Space Exploration[END_REF]. The challenge of DSE is to explore the sheer size of the design space and to find the best candidates. Typically a large system has billions of possibilities as parameters of NoCs are abundant. The designer must select the topology, the number of nodes, the size of flits, the commutation mode, the routing algorithm, the size of buffers and many other parameters. Enumerating every point of the design space is prohibitive and is time consuming [START_REF] Villamon | Design Space Exploration for Networks on Chip[END_REF]. Moreover, the exploration of NoC candidates on FPGA is huge as the number of FPGAs is high. The portfolio of Xilinx company includes six FPGA families (Spartan, Artix, Kintex, Kintex Ultrascale, Virtex and Virtex ultrascale) [START_REF][END_REF]. Each family has around hundreds of devices. The estimation of resources for each NoC candidate on each FPGA device is long. Observed resources are obtained from a synthesis process whose time depends on the size of the NoC (29 minutes for a medium size and several hours for a large size). Exploring all points on the design space can take several weeks.

The methodological framework proposed is based on the following elements described below:

• The NoC structure, • The FPGA devices.

A. Network On Chip (NoC)

NoC are communication structures proposed as a solution for the communication challenge. NoC architecture is composed of several basic elements depicted in Fig. 1 : • Network Interface (NI): it enables PE (Processing Element) to communicate with routing node they are connected to. • Routing node (or switch): according to the routing algorithm, the switch sends packets to the appropriate link in the network. • Links: connect the routing switches together or switches to NI. • Processing Element: these units correspond to various modules of SoC, such as IP blocks, memories, processors. Basic elements for the NoC structure.

Many topologies can be considered for NoC structures: mesh (a), torus, ring (b), tree (c)…. The mesh topology is the most appropriate for FPGA devices (as depicted in Fig. 1). The following work uses mesh-based NoC but the framework can be extended to others. One PE sends messages to another PE through the NoC.

Messages are compacted and divided into packets, which are divided into parts of the size of a flit. Flits (Flow Control Units) can be classified based on their position inside the packets as header, tail or payload.

B. FPGA

An FPGA (Field Programmable Gate Array) is a programmable logic device used in various applications requiring rapid prototyping of digital electronics (telecommunication, image processing...). Modern FPGAs are now able to host processors cores as well as several IP blocks to perform efficient prototyping of embedded systems. However, the designer can obtain, after the synthesis process, a prevision of FPGA resources. Resources are LUT (Look Up Table ), MLUT (Memory LUT), FF (Flip Flop), Buffers and I/O (Input and Ouput). The resource allocation is given in the postsynthesis report. This allowance depends on CLB (Configurable Logic Block) that define the internal architecture of the FPGA.

IV. METHODOLOGICAL FRAMEWORK

A. Description

The objective is to mathematically model the relation between the input configuration of the NoC and material resources used without going through the step of synthesis. So we have to identify links between NoC input variables and the FPGA resources used for the NoC (LUT, MLUT, FF). The variables considered in the mathematical models are:

• n 1 : the number of routers in the X-axis.

• n 2: the number of routers in the Y-axis.

• n 3: the depth of buffer.

• n 4: the size of flit.

Other inputs of the NoC are set (i.e. are constants) such as routing algorithm, flow control and the number of virtual channels (for the use of the credit based control flow).

Methodological framework

The methodological framework is proposed in Fig 2 . The results obtained are the number of LUT, MLUT and FF extracted from each synthesis process. They are stored in a database. The number of synthesis should be enough to get a full set of observed results. As long as the database is not complete, synthesis of the NoC according to variables are repeated.

Then, from the complete database of observed results, data analysis is done to obtain links between variables and LUT, MLUT, FF. In the first experiment, variables are (n 1 , n 2 ). In the second experiment, variables are (n 1 , n 2 , n 4 ).

In the first and second experiment, once the learning set is done, several steps are involved. Starts by analyzing data, deducing mathematical models, estimating resources, synthesizing additional NoC configurations on the same FPGA used on the learning set or synthesizing existing data base Noc sizes on different FPGAs, then calculating the relative error between observed and estimated resources, at the end, if the error rate is less than 6%, models are validated.

B. Context of XP1

The NoC used in the following experiments is the NoC Hermes. It was developed by the Catholic University of Rio Grande do Sul, in Porto Alegre, Brazil [START_REF] Moraes | HERMES: an Infrastructure for Low Area Overhead Packet-switching Networks on Chip[END_REF]. This NoC is based on a 2D Mesh switch. The main components of this infrastructure are the Hermes switch and IP cores (Fig 3 . ). The Hermes switch has routing control logic and five bi-directional ports. All ports contain input buffers for provisional storage of information.

NoC synthesis for XP1

The objective is to find f k (n 1 , n 2 ) which corresponds to the identification of Nb k (number of resources k) for input constants (n 3 : buffer depth {32} and n 4 : size of flit {16}) and input variables (n 1 : number of routers in the X-axis {3..16} and n 2 : number of routers in the Y-axis {3..8}).

C. Context of XP2

The NoC used in the following experiments is also the NoC Hermes. The objective of this second experiment is to find g k (n 1 , n 2 , n 4 ) which corresponds to the identification of Nb k (number of resources k) for input constants (n 3 : buffer depth {32} and input variables (n 1 : number of routers in the Xaxis {3..16} and n 2 : number of routers in the Y-axis {3..8}and n 4 : size of flit {16, 32, 64}). The context of the second experiment is depicted in Fig 5. NoC synthesis for XP2 V. MATHEMATICAL MODELING Before defining the mathematical models, the analysis of data is achieved to define the most appropriate variables and the order of resources.

A. Data analysis

The aim is to identify from the data analysis links between input variables (n 1 , n 2, n 4 ) and FPGA resources LUT, MLUT and FF. The variable n 3 is not considered as the buffer depth remains always identical. This is due to the different kind of memory blocks that are used according to the NoC: the number does not change, only the type (i.e. the size of the block). The Pearson's correlation coefficient is first observed to measure the strength of a linear association between two variables (Table 3). There is a strong correlation between the observed resources.

While analyzing similarities between groups, the strongest correlation is between FFs and LUTs (0.992). There are also strong correlations between MLUT and LUT, and also FF and MLUT.

There is also a strong correlation (lesser but significant) between n 1 × n 2 and the number of FF and LUT. One unexpected correlation is the correlation (in blue) between n 1 × n 2 and the FPGA resources: 0.64 with MLUT, 0.88 with FF and 0.882 with LUT. This correlation is higher than the correlations between the FPGA resources and n 1 or n 2 . It is also observed that n 1 has a higher correlation with FPGA resources than n 4 and n 2 . The impact of the size of flits is higher than the number of nodes in Y, but lower than the number of nodes in X.

But it is also possible to cluster variables in terms of their correlations. Two variables have a pair of values for each sample, and measures of distance and dissimilarity between these two column vectors can be considered. The similarity between variables is measured: this can be in the form of correlation coefficients or other measures of association. The result of a cluster analysis is a binary tree, or dendrogram, with n-1 nodes. The branches of this tree are cut at a level of similarities obtained in our case by using correlation.

A strong correlation indicates a high degree of similarity. A weak correlation indicates a low degree of similarity. Similarities are depicted in Table 4 and the corresponding dendrogram is presented in Figure 6. Similarities between the variables.

B. Mathematical models for XP1

As the number of routers is n 1 multiplied by n 2 , the relation between MLUT observed and (n 1 , n 2 ) must be considered.

dividing the number of MLUT observed per (n 1× n 2 ) is necessary to find those links between the number of MLUTs and one

The phenomenon is illustrated in Fig 7 . This figure shows 14 classes of measures corresponding to the 14 variations of n 1 . And from a class to another there is a translation on horizontal and vertical axis. The curves show that a is almost a constant value around 5.63 and b varies. Approaching b by a polynomial trendline allows us to deduce the corresponding formula:

Variation of coefficients a and b

, = × × . × -+ -. × + . × + .
(

) 1
The strong correlation between MLUT and both LUT and FF is extracted in the previous section (Data Analysis). Therefore a coefficient to express LUT and FF according to f MLUT can be found (table 5). With the chosen coefficients, f LUT and f FF become:

LUT (n 1 , n 2 ) = 12× f MLUT (n 1 , n 2 ) (2) f FF (n 1 , n 2 ) = 4 × f MLUT (n 1 , n 2 ) (3)
Regarding to f MLUT (n 1 , n 2 ) given in equation (1).

C. Mathematical models for XP2

The purpose of this second experiment is to express g k (n 1 , n 2 , n 4 ) = coeff kij *f k (n 1 , n 2 ). The size of flits is changed from 16 to 32 and the impact on the number of resources is analyzed. The number of resources changes according to the type of resources. There is one specific coefficient for MLUT (the value is 2), for LUT (the value is 1.477) and for FF (the value is 1.833) in this case. According to the configuration of the size of flits from i to j, all coefficients called Coeff kij are different (see table 7 and table 8). The coefficient for MLUT, called Coeff MLUTij, is respectively 2 and 1.88 for flits (i=16 to j=32) and for flits (i=32 to j=64). This phenomenon is identical for k=FF and k=LUT.

VI. VALIDATION

The validation is first done on results extracted from FPGA already used. Then other implementations with random sizes of NoCs and different size of flits are done to validate the models.

A. Validation of XP1 with different sizes of NoC on a Virtex7 FPGA

To validate our models, random NoC architectures are selected. Varying the number of routers (n 1 , n 2 ), synthesizing and comparing with analytically estimated results gives the error rates illustrated in Fig 9 .  There are three classes of error rates. The first class is for n 1 = 3, and n 2 = {3..8}. The error rate is 4.20% for the number of MLUTs, 4.33% for FFs and 2.51% for LUTs. The maximum error rate for the first class is less than 5%. The second class is for n 1 = 4 and n 2 = {3..8}. The error rate for the number of MLUTs is 1.42%, 1.49% for FFs and 0.46% for LUTs. The maximum error rate for the second class is less than 2%. The third and last class is for n 1 = {5..16} and n 2 = {3..8}. The error rate for the number of MLUTs is between [-0.65%, 0.47%], for the number of FFs it is between [-0.83%, 0.45%] and for LUTs it is between [-0.66%, 1.63%]. Error rates corresponding to f k for k = FF, LUT, MLUT Therefore, it is possible to estimate the number of resources for small sizes of NoC with an error rate less than ±5% (first class). The error rates for the third class are less than ±2%. This third class concerns large NoC having an important synthesis time. These error rates indicate that the number of estimated resources is near to post synthesis results.

B. Validation of XP2 with different sizes of NoC on a Virtex7 FPGA

The mathematical model validation is then done on previously unused FPGAs. The error rate between observed results and estimated is analyzed and presented in The error rate for a size of flit from 16 to 32 is around -6% for small size of NoCs. This error rate decrease to less than 4% for bigger sizes of NoC. This indicates that the analytically estimated results are a little bit bigger than the results obtained after synthesis (synthesized results) for small sizes of NoC. The analytically estimated results are smaller than synthesized results for bigger sizes of NoCs. For any cases, the error rate is low and the analytically estimated results are close to synthesized results. This phenomenon is identical when the size of flits changes from 16 to 64. The error rate is a little bit higher for smaller size of NoC (around -7%) and bigger size of NoC. This error rate remains fairly good.

C. Validation using different FPGA devices

To validate the experiments, three architectures of NoC varying the number of switches (n 1 ; n 2 ) were selected by drawing lots. Their sizes are {(7; 4), (11; 12), (5; 11)}. Then 20 FPGA from the 326 FPGA available in Vivado 2012.3 were selected randomly. The FPGA available on Vivado are distributed as follows {194 Virtex7, 92 Kintex 7 and 40 Artix7}. After synthesizing on the 20 different FPGAs, the number of resources is the same for each size of NoC. Fig. 12 depicts that the error rates vary from -0.5% to 1.2%. This result suggests that the mathematical models can correctly estimate the numbers of MLUTs, LUTs and FFs for XILINX families.

VII. IMPACT OF SYNTHESIS OPTIONS

The objective is to analyze the impact of the synthesis options. The options concern the area or speed optimization with three optimization efforts (normal, high and fast) for the Xilinx Synthesis Tool (XST). 6 combinations (Table 9) can be considered when synthesizing the NoC. The NoC used is the Hermes NoC. The routing algorithm is identical to the previous experiments (XY), the mesh topology too. The depth of buffer and the size of flit are 16. The main difference concerns the flow control. The previous flow control was credit based with 2 virtual channels. The flow control is now replaced by the handshake protocol. The environment used for the experiments is Xilinx ISE 14.7. The synthesis is done with two sizes of NoC (7×7 and 14×14) on the Virtex 7 FPGA (VC707 evaluation platform). The optimization efforts have not impact on the number of FFs and MLUTs when optimizing the area. The normal and high efforts give the same number of FFs. The fast optimization effort modifies the number of LUTs. This can be considered insignificant as it only represents 0.32% of added LUTs for the 14×14 and 0.2% for the 7×7. For the speed optimization goal, the number of resources is identical for the normal and high options. The fast option changes the number of FFs and LUTs. In the fast mode, 22% and 11% added LUTs are required for the 7×7 and the 14×14. Therefore, the number of MLUTs does not depend on the synthesis options. The number of FFs remains identical for 5 synthesis options. There are only 14 more FFs for the 14×14 NoC using the fast area option. This is not significant compared to the 38 710 FF used. The only main difference lies in the number of LUTs used. This analyze confirm the methodology proposed in section V. Mathematical models are proposed to first estimate the number of MLUTs (f MLUT ) according to the input variables. Then the number of FFs (f FF ) and LUTs (f LUT ) are extracted according to the number of MLUTs (f MLUT ) .

To extract mathematical models, the optimization goal must be wisely selected. According to the previous results, the normal area mode should be selected. This mode gives the same result as the high optimization goal with a shorter synthesis time and it gives better results (fewer resources) than the fast optimization level.

As the resource results are similar for the normal and high optimization goals, the mathematical model can be defined from the normal mode using the area optimization.

VIII. LIMIT OF THE MODELS

The mathematical models are extracted from a specific NoC with variables and constants. In the previous experiments and the correlation analysis, 3 variables are extracted and other parameters are used as constants. The depth of buffer (variable n 3 ) became a constant as it has no impact on the number of resources. Other parameters were first considered as constant to restrict the number of variables.

In this section, 2 other variables are considered: the routing algorithm (n 5 ) and the flow control (n 6 ).

The experiments conducted on the Hermes NoC with different routing algorithms (semi adaptive and determinist routing algorithm) show that such algorithms do not have any impact on the number of resources (7 lines are overlapped). Fig. 15 depicts the number of FFs according to the routing algorithms and for different sizes of NoC. This behavior is identical for LUTs and MLUTs. The routing algorithm (n 5 ) is then considered as a constant when building the mathematical model. This is true for these kinds of routing algorithms. The use of more sophisticated algorithms can lead to more added resources. In this case, n 5 will be considered as a variable used to build the mathematical model). A comparison between both flows is done in the table 10 (the number of added resources for the credit based compared to the handshake. The resources for the handshake are extracted from the mathematical models. The resources for the virtual channel are obtained from the synthesis of the NoC. The number of FFs is 2.3 more for the virtual channel than the handshake for both sizes of NoC, 2.44 more for the LUTs and 1.5 more for the MLUTS.

Table 10. Ratio of resources between both types of flow for two sizes of NoC (credit based/handshake).

The exploration of the NoC should also consider the control flow (variable n 6 ). Changing the flow control leads to define coefficients for each type of resource from the initial model as it has been done for n 4 .

IX. CONCLUSION AND FUTURE WORK

In this paper, the feasibility to identify mathematical models for exploring the NoC on FPGA devices has been shown. The number of FPGA resources (LUT, MLUT and FF) can be estimated using these models and without experiments. The designer can explore the entire design space to find the most appropriate candidate in shorter time. The time saving is significant as the exploration with mathematical models takes only few minutes and with experiments takes few days. The designer can also explore all FPGA candidates without increasing the exploration time. Mathematical models for a new NoC structure (topologies, flow control…) should be based on the analysis of the correlation of NoC variables and FPGA resources and also the correlation of Pearson 2-2. These analysis leads to select the input variables and the input constants. Input data can be one parameter or a combination of parameters. These analysis help the designer to order the Nb k (number of resources k) for input constants and variables. The mathematical models obtained can estimate the number of resource with the lowest error rate. Future work is to define the impact of the variable n 6 in the mathematical model and to analyze these models for other topologies.

Fig 1 .

 1 Fig 1.

Fig 2 .

 2 Fig 2.

Fig 3 .

 3 Fig 3. The Hermes NoC and its switch architecture. The platform is the VC707 Evaluation Platform with a Virtex 7 XC7 VX485 FPGA (containing 303,600 LUTs, 130,800 MLUTs, and 607,200 FF, registers and IO…). The experiments are carried out within the Atlas tool and then VIVADO 2012.3 as depicted in Fig 4. The synthesis tool is the XST tool (Xilinx Synthesis Tool).

  Fig 4.

  Fig 5.

Fig 7 .

 7 Fig 7. Number of MLUTs divided per (n 1 ×n 2 ) Approaching each class by logarithmic trendlines (a logarithmic trendline is the best-fit curved line) confirms that MLUT observed /(n 1 ×n 2 ) can be written as: (a × LN(n 2 -2) + b) and there is provided the values of a and b in Fig 7.

  Fig 8.

  Fig 9.

  Fig 14. and Fig 11.

Fig 10 .Fig 11 .

 1011 Fig 10. Rate error of XP2 model for f k when the size of flit 16-> 32

Fig 12 .

 12 Fig 12. Error rate of the model for f k on different FPGA

Fig 13 .

 13 Fig 13. Synthesis times for the 6 combinations of the 14×14 Hermes NoC.

Fig 14 .

 14 Fig 14. Number of FFs for different sizes of Hermes NoC using different routing algorithms.The experiments are conducted for the flow control (n 6 ) using two types: the handshake and the credit based with 2 virtual channels, in Fig 15.The number of resources significantly changes according to the flow control.

Fig 15 .

 15 Fig 15. Number of resources according to the flow control.

Table 3 .

 3 Pearson's correlation coefficient.

		n 4	n 2	n 1	FF	LUT	MLUT
	n 2	0.17
	n 1	-0.157 -0.0237
	FF	0.364	0.509 0.531
	LUT	0.460	0.503 0.467 0.992
	MLUT 0.627	0.463 0.339 0.932 0.971
	n 1 × n 2 -0.056 0.462	0.68 0.88 0.821	0.643

Table 4 .

 4 Table of similarities in the melting step

	Group number	Number of	Similarities between the
		variables	group of variables
	1	6	99.58
	2	5	98.53
	3	4	94.00
	4	3	84.00
	5	2	81.35
	6	1	75.46

  They are illustrated in the table of similarities in the melting step (Table4). 6 groups are extracted. The first group (with a 99.58 similarity) has 6 variables. The second group is extracted for a similarity degree above 98.53. This group contains 5 variables. It indicates that two variables, FF and LUT, have a small distance. The last group contains one variable only. The FPGA resources (LUT, FF and MLUT) are strongly correlated to (n 1 × n 2 ) as the similarity degree is 94 (cf Table4, group number 3). So, models are carried out with the variable called n 1 ×n 2 instead of considering two independent variables n 1 and n 2 . The mathematical models are first based on the number of MLUTs as the correlation is lower. The mathematical models are also studied from n 1 × n 2 as this variable has the highest degree of similarities compared to n 1 only or n 2 only.

	94.00.

Table 5 . Coefficients to express FF, LUT according to MLUT

 5

		Coefficient	Coefficient	Coefficient
		FF/MLUT	LUT/MLUT	LUT/FF
	Average	3.9632	12.2779	0.32281
	Median	3.9626	12.3027	0.32184
	Standard deviation	0.0049	0.1243	0.00363
	Min	3.9442	11.9239	0.31789
	Max	3.9737	12.4518	0.33327
	(Min+ Max)/2	3.95899	12.1878	0.32558
	Coefficient chosen	4	12	1/3

Table 6 .

 6 Coefficient k for flit from size 16 to 32

	k = MLUT	k = LUT	k = FF
	i= 16	i= 16	i= 16
	j=32	j= 32	j= 32
	Coeff MLUT 16 32 = 2	Coeff LUT 16 32 = 1.477	Coeff FF 16 32 = 1.833
	Then, for n 4 =16 ->32
	g

MLUT (n 1 , n 2 , n 4 ) = 2*f MLUT (n 1 , n 2 )

	(4)
	and
	g LUT (

n 1 , n 2 , n 4 ) = 1.477*f LUT (n 1 , n 2 )

	(5)
	and
	g FF (

n 1 , n 2 , n 4 ) = 1.833*f FF (n 1 , n 2 )

  Table7 and table 8 illustrate different coefficients while varying the size of flits (16, 32 and 64).

	(6)

Table 7 .

 7 Coefficient k regarding the size of flits (from i to j). Coeff MLUT 16 64 = 3.66 Coeff LUT 16 64 = 2.437 Coeff FF16 64 = 2.01

	k = MLUT	k = LUT	k = FF
	i= 16	i= 16	i= 16
	j=64	j=64	j= 64

Table 8 .

 8 Coefficient k regarding the size of flits (from i to j). Coeff MLUT 32 64 = 1.88 Coeff LUT 32 64 = 1.64 Coeff FF 32 64 = 1.05

	k = MLUT	k = LUT	k = FF
	i= 32	i= 32	i= 32
	j=64	j=64	j= 64

Table 9 .

 9 Synthesis options in XST (with ISE 14.7)The synthesis times for the size 14×14 are depicted in Fig 14.The fastest time is obtained with the fast mode. The normal optimization goal ensures faster synthesis than the high optimization goal.

	4,00%
	2,00%
	0,00%
	-4,00% -2,00%	48 48 48 96 48 48 48 24 24 24 24 96 96 96
	-6,00%
	-8,00%

Error rates Flits 16 -> 64

	FF -Error Lut -Error Mlut -Error
	Combinations	Optimization Goal Optimization Effort
	1	Speed	Normal
	2	Speed	High
	3	Speed	Fast
	4	Area	Normal
	5	Area	High
	6	Area	Fast

Table 10

 10 and table11give the number of resources for respectively the area and resources optimizations.

Table 10 .

 10 Number of resources according to the area optimization goal.

Table 11 .

 11 Number of resources according to the speed optimization goal.

ACKNOWLEDGMENT

Funding for this project was provided by a grant from la region Rhone-Alpes.


Piermarco Cannarsa
email: cannarsa@mat.uniroma2.it

AND Antonio Marigonda
email: antonio.marigonda@univr.it

Khai T Nguyen

OPTIMALITY CONDITIONS AND REGULARITY RESULTS FOR TIME OPTIMAL CONTROL PROBLEMS WITH DIFFERENTIAL INCLUSIONS

Keywords: . 2010 Mathematics Subject Classification. 34A60, 49J15 proximal normal vectors, differential inclusions, time optimal control, semiconcave functions

We study the time optimal control problem with a general target S for a class of differential inclusions that satisfy mild smoothness and controllability assumptions. In particular, we do not require Petrov's condition at the boundary of S. Consequently, the minimum time function T (•) fails to be locally Lipschitz-never mind semiconcave-near S. Instead of such a regularity, we use an exterior sphere condition for the hypograph of T (•) to develop the analysis. In this way, we obtain dual arc inclusions which we apply to show the constancy of the Hamiltonian along optimal trajectories and other optimality conditions in Hamiltonian form. We also prove an upper bound for the Hausdorff measure of the set of all nonlipschitz points of T (•) which implies that the minimum time function is of special bounded variation.

Introduction

In this paper we study the time optimal control problem for the differential inclusion [START_REF] Albano | Singular gradient flow of the distance function and homotopy equivalence[END_REF] ẋ(t) ∈ F (x(t)), for a.e. t > 0, x(0) = x 0 ∈ R n , with a given closed target set S ⊆ R n . The dynamics is described by a set-valued Lipschitz continuous function F : R n ⇒ R n , whose values are assumed to be compact, convex and nonempty.

For each trajectory of (1) starting from x 0 , i.e., for each absolutely continuous function y x 0 (•) ∈ AC([0, +∞[; R n ) satisfying ẏx 0 (t) ∈ F (y x 0 (t)) for a.e. t > 0 and y x 0 (0) = x 0 , we set θ(y x 0 (•)) := inf{t ≥ 0 : y x 0 (t) ∈ S}, with the convention inf ∅ = +∞. The minimum time function is defined by T (x 0 ) := inf {θ(y x 0 (•)) : y x 0 (•) is a trajectory of (1) with y x 0 (0) = x 0 } .

When finite, T (x 0 ) represents the minimum time needed to steer the point x 0 to the target S following the trajectories of [START_REF] Albano | Singular gradient flow of the distance function and homotopy equivalence[END_REF]. The study of the regularity of T (•) is a central problem in optimal control theory, and the literature offers a huge choice of papers on such a topic. In particular, starting from the seminal paper [START_REF] Cannarsa | Convexity properties of the minimum time function[END_REF], the regularity property of T (•) called semiconcavity was extensively studied and used to deduce new optimality conditions. Roughly speaking, semiconcavity amounts to the local Lipschitz continuity of T (•) plus a uniform exterior sphere condition for the hypograph of T (•). Using these geometric properties, one can derive further regularity results for T (•), such as BV estimates for T (•) and ∇T (•), the existence of Taylor's expansion of order two around a. e. point, and bounds for the singular sets of T . We refer to [START_REF]Hamilton-Jacobi equations, and optimal control[END_REF] for an introduction to semiconcave functions. Semiconcavity (and semiconvexity) results, however, rely essentially on a strong controllability assumption-the so-called Petrov condition-which is actually equivalent to the local Lipschitz continuity of T . When this assumption is removed, T (•) may fail to be semiconcave, but it still retains the external sphere property of the hypograph (or epigraph). In [START_REF] Colombo | Some new regularity properties for the minimal time function[END_REF], for parameterized linear multifunctions, the epigraph of T (•) was proved to satisfy a strong external sphere condition, which is called positive reach property in the sense of Federer (also known, in literature, as ϕ-convexity or proximal smoothness). The regularity properties of the class of functions whose epigraph has positive reach turned out to be comparable with the properties of semiconcave/semiconvex functions, we refer to [START_REF] Colombo | Differentiability properties for a class of nonconvex functions[END_REF] for details.

The above geometric approach was also generalized to the nonlinear case: in [START_REF] Colombo | On the structure of the minimum time function[END_REF], the positive reach property of the hypograph of T (•) was obtained replacing Petrov's condition by the assumption that the normal cone to the hypograph is pointed (i.e., contains no lines). Without such an assumption, in [START_REF] Khai | Hypographs satisfying an external sphere condition and the regularity of the minimum time function[END_REF], the hypograph of T (•) was proved to satisfy a weaker external sphere condition. In the same paper, it was shown that such a condition yields essentially the same regularity properties as in the case when the hypograph has positive reach.

The study of the singular set for T (•), beyond the semiconcave case, was performed in [START_REF]Singularities for a class of non-convex sets and functions, and viscosity solutions of some Hamilton-Jacobi equations[END_REF] for the positive reach case, in [START_REF] Khai | Rectifiability of siguralities of non-lipschitz functions[END_REF] for the weak external sphere property, and in [START_REF] Marigonda | Some regularity properties for a class of upper semicontinuous functions[END_REF] for a further generalized case. In all these papers the structure of the singular set was analyzed, providing upper bounds for the Hausdorff measure of such a set. Lower estimates were obtained in [START_REF] Albano | Singular gradient flow of the distance function and homotopy equivalence[END_REF] and [START_REF] Colombo | SBV regularity for minimum time function[END_REF].

So far, all the results in the above papers were proved for a state equation given in the form of a smooth C 1,1 -parameterized multifunction. The smoothness of the parameterization was a crucial issue to gain semiconcavity estimates, and was extensively used in all its generalizations as well. Note that, although a Lipschitz multifunction always posseses a Lipschitz parameterization (see, for instance, [START_REF] Aubin | Set-Valued Analysis[END_REF]), it is still an open problem to find conditions for such a parameterization to be smooth. This motivates a separate study of the minimum time problem for differential inclusions. The first result in this direction is due to [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF], where the semiconcavity of the value function of the Mayer problem for system (1) was proved. Instead of searching for a smooth parametrization of F (•), the main idea of [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF] is to use the smoothness of the Hamiltonian associated with system (1), defined by

(2) H(x, p) = sup v∈F (x) p, v , (x, p) ∈ R n × R n .
This approach was extended in [START_REF] Cannarsa | The dual arc inclusion with differential inclusions[END_REF] to the study of the minimum time function, still in the semiconcavity framework. A further step to extend this kind of analysis beyond semiconcavity, was performed in [START_REF] Cannarsa | Exterior sphere condition and time optimal control for differential inclusions[END_REF], which can be seen as the counterpart of [START_REF] Colombo | On the structure of the minimum time function[END_REF] and [START_REF] Khai | Hypographs satisfying an external sphere condition and the regularity of the minimum time function[END_REF] for differential inclusions, proving the external sphere property enjoyed by hypo T under milder controllability assumptions.

The main tool used in our analysis is the dual arc inclusion (see [START_REF] Cannarsa | The dual arc inclusion with differential inclusions[END_REF]), i.e., the natural nonsmooth counterpart of the Hamiltonian system associated with the problem, that is,

(3) ẋ(t) = ∇ p H(x(t), p(t)), -ṗ(t) ∈ ∂ x H(x(t), p(t)).
If the trajectory x(•) starting from x 0 at t = 0 is optimal, then the above system admits a solution when coupled with a terminal condition for p(T (x 0 )) that turns out to be a proximal inner normal to the target set S at x = x(T (x 0 )).

In this paper, we prove two results for system [START_REF] Aubin | Set-Valued Analysis[END_REF]: in the first one, we state that the superdifferentiability of the minimum time function T (•) along an optimal trajectory is completely determined by the value of the Hamiltonian at the endpoint (x(T (x 0 )), p(T (x 0 ))). More precisely, if we are able to find a nontrivial proximal inner normal to the target S at the endpoint x = x(T (x 0 )) such that the value of the Hamiltonian computed at this inner normal at x is nonzero, then the p-part of the solution of (3) yields a continuous selection of ∂ P T along the trajectory x(•). In particular, we have that

∂ P T (x(t)) = ∅ for all t ∈ [0, T (x 0 )].
Due to the presence of horizontal normals to hypo T , the nonsmoothness of T (•) propagates similarly along the flow of an optimal trajectory: indeed we show that, if the value of the Hamiltonian computed at this inner normal at x is zero, then the same p-part of the solution yields a continuous selection of ∂ ∞ T along the optimal trajectory. So, once again,

∂ ∞ T (x(t)) = ∅ for all t ∈ [0, T (x 0 )].
The second result of this paper, which is a consequence of the above propagation of superdifferentiability, is concerned with the constancy of the Hamiltonian along optimal trajectories, which somewhat resembles the classical case. In order to prove this result, we use the fact that the value of the Hamiltonian, at the terminal point of an optimal trajectory, computed at a suitable inner normal, yields the existence of a supergradient of T , or of an horizontal supergradient of T , at all points of the trajectory. This fact forces the value of the Hamiltonian, along the solution of the dual arc inclusion, to be identically 1 in the former cases, and 0 in the latter.

A partial converse of the above result, i.e., a sufficient condition for optimality, is also established in the case of superdifferentiability. We show that, if we have a solution of the generalized characteristic system

ẋ(t) = ∇ p H(x(t), p(t)), -p(t) ∈ ∂ P T (x(t)),
along which the Hamiltonian is constantly equal to 1, then the x-part of the solution is actually an optimal trajectory. The last part of the paper is devoted to the study of SBV regularity of the minimum time function, which guarantees that the singular part of the distributional gradient of T (•) has no Cantor component-a property that has several applications to the calculus of variations (see, e.g., [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF]). Actually, the result we prove is slightly stronger than just establishing the SBV regularity of T (•). Indeed, Theorem 4.6 ensures that, if the subset of ∂S at which H vanishes for a nontrivial choice of inner normals is small enough, then there are few optimal trajectories along which the normal cone to hypo T has an horizontal part. So, at most points, ∂ P T (x) is bounded and T (•) turns out to exhibit a Lipschitz behaviour.

The paper is structured as follows: in Section 2 we fix the notation, and recall definitions and preliminaries from nonsmooth analysis, expecially concerning differential inclusions. In Section 3, we discuss our standing assumptions and recall some useful results from [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF], while Section 4 is devoted to the main results of the paper and the analysis of some of their consequences.

Preliminaries and notation

Our ground space will be the Euclidean space R n . Definition 2.1. Let Ω, K, and S be, respectively, an open, closed, and any subset of R n , let x = (x 1 , . . . , x n ) and y = (y 1 , . . . , y n ) be points of R n , let r > 0, and let k ≥ 0 be an integer. We denote by:

x, y := Also, C k (Ω) stands for the space of all f : Ω → R with continuous derivatives up to order k, C k b (Ω) collects the functions of C k (Ω) with bounded derivatives of order k, and C k c (Ω) the ones with compact support. If π K (y) = {ξ}, i.e. it is a singleton, we will identify the set π K (y) with its unique element and write π K (y) = ξ. The characteristic function χ S :

R d → {0, 1} of S is defined as χ S (x) = 1 if x ∈ S and χ S (x) = 0 if x / ∈ S. Definition 2.2. Let X be a vector space. A set C ⊆ X is convex if for every x 1 , x 2 ∈ C, λ ∈ [0, 1], we have that λx 1 + (1 -λ)x 2 ∈ C.
If S ⊆ X is a set, the smallest (with respect to inclusion) convex set which contains S is called the convex hull of S and it is defined as

co S := C∈F (S) C,
where F (S) := {C ⊆ X : C ⊇ S and C is convex}. We have that S = co S iff S is convex.

Definition 2.3. Let X be a vector space and f : X → R ∪ {±∞} be a function.

We recall the definitions of

dom f := {x ∈ X : f (x) ∈ R}, the domain of f ; epi f := {(x, β) ∈ X × R : x ∈ dom f, β ≥ f (x)}, the epigraph of f ; hypo f := {(x, α) ∈ X × R : x ∈ dom f, α ≤ f (x)}, the hypograph of f .
If X is a topological vector space, we say that f is lower semicontinuous (shortly: l.s.c.) if epi f is closed in X × R with respect to the product topology on X × R, i.e.

lim inf y→x f (y) ≥ f (x).
A function g is called upper semicontinuous (shortly u.s.c.) if -g is l.s.c.

U ⊆ X, V ⊆ Y , a function f : U → V is said to be a Lipschitz continuous function (f ∈ Lip(U)) if there exists C > 0, called a Lipschitz constant, such that for every x 1 , x 2 ∈ U f (x 1 ) -f (x 2 ) Y ≤ C x 1 -x 2 X . A function f : U → V is called locally Lipschitz continuous (f ∈ Lip loc (U)) if it is Lipschitz continuous on every compact subset of U. Given x ∈ X, we say that f : X → Y is Lipschitz continuous at x if there exists a neighborhood U of x in X such that f : U → Y is Lipschitz continuous.
We recall the following classical result on regularity of Lipschitz functions holding for spaces of finite dimensions: Theorem 2.5 (Rademacher's Theorem). Let X be a Banach space of finite dimension, let U ⊆ X be open, and let f : U → R be a locally Lipschitz function. Then f is differentiable almost everywhere with respect to Lebesgue measure.

Definition 2.6 (BV functions).

Let Ω be an open subset of R n , u ∈ L 1 (Ω). We say that u is a function of bounded variation in Ω and write u ∈ BV (Ω) if there exist Radon measures µ 1 , . . . , µ n on Ω such that

Ω u(x)∂ x i ϕ(x) dx = - Ω ϕ(x)dµ i (x), for all ϕ ∈ C 1 c (Ω).
The vector-valued measure

Du := (µ 1 , . . . , µ n ) is called the distributional (full) gradient of u. We say that u ∈ BV loc (Ω) if u ∈ BV (Ω ′ ) for every bounded open subset Ω ′ of Ω.
We now recall a few notions related to functions of bounded variation, referring the reader to [START_REF] Ambrosio | Functions of bounded variation and free discontinuity problems[END_REF] for more details. If u ∈ BV , then Du can be decomposed into an absolutely continuous part w.r.t. the Lebesgue measure, herafter denoted by ∇u dx or ∇u, and a singular part, D s u. One can further introduce the jump part of D s u, Ju, taking the restriction of D s u to the set of all points of Ω at which u has no approximate limit. Then, the difference D s u -Ju is the so-call Cantor part of D s u, labeled D c u. Finally, we say that u ∈ BV loc (Ω) is a special function of locally bounded variation, and we write u ∈ SBV loc (Ω), if the Cantor part D c u vanishes.

Proposition 2.7 (Proposition 4.2 in [4]). Let u ∈ BV (Ω). Then u ∈ SBV (Ω) if and only if D s u is concentrated on a Borel set of σ-finite H n-1 measure. Thus, u ∈ SBV (Ω) if it vanishes outside a countably H n-1 -rectifiable set. Definition 2.8 (Proximal normals). Let S be a closed subset of R n . A vector v is called a proximal normal to S at x ∈ S if there exists σ = σ(v, x) ≥ 0 such that (4) v, y -x ≤ σ y -x 2 , for every y ∈ S.
The set of all proximal normals to S at x will be denoted by N P S (x). Given ρ > 0, we say that v ∈ N P S (x) is realized by a ball with radius ρ if one can take

σ = v 2ρ in (4). Observe that x ∈ N P Q (x) if and only d Q (x+λv) = λ v for some λ > 0. Moreover, if v ∈ N P S (x)
is realized by a ball with radius ρ, then B(x + ρv, ρ) ∩ S = ∅. Remark 2.9. We recall that, when S is convex, we can take σ = 0 in the above definition. Hence, the proximal normal cone at x reduces to the normal cone in the sense of convex analysis, namely the set of vectors v ∈ R n such that v, yx ≤ 0 for all y ∈ S. Definition 2.10 (External sphere condition). Let S ⊂ R n be closed and let θ : ∂S →]0, ∞[ be continuous. We say that S satisfies the θ-external sphere condition if for every x ∈ ∂S, there exists a nonzero vector v ∈ N P Q (x) which is realized by a ball of radius θ(x).

We say that a closed subset Q of R n satisfies the θ-internal sphere condition if and only if R n \ Q satisfies the θ-external sphere condition. Definition 2.11 (Proximal supergradients). Let f : R n → [-∞, +∞] be an upper semicontinuous function. For every x ∈ dom(f ), we denote by ( 5)

∂ P f (x) . = ξ ∈ R n : (-ξ, 1) ∈ N P hypo(f ) (x, f (x)
) , the set of proximal supergradients of f at x, and by ( 6)

∂ ∞ f (x) . = ξ ∈ R n : (-ξ, 0) ∈ N P hypo(f ) (x, f (x)) . the set of horizontal proximal supergradients of f at x. We recall that, if f is Lipschitz continuous at x, then ∂ ∞ f (x) is empty. The converse in general is false. Definition 2.12 (Support function). Let C ⊆ R n be nonempty. The support func- tion σ C : R n →]0, +∞] is defined as σ C (p) = sup v∈C p, v . It can be proved that σ C (p) = σ co C (p).
Let Ω be an open subset of R n , let x 0 ∈ Ω, and let f : Ω → R be Lipschitz continuous at x 0 . Definition 2.13 (Clarke's generalized gradient). We define Clarke's generalized gradient of f at x 0 by setting

∂f (x) = co v ∈ R n : ∃{y i } i∈N ⊂ Ω s.t. f is differentiable at y i , y i → x 0 ∇f (y i ) → v .
We now recall the definition and some properties of semiconcave functions, referring the reader to [START_REF]Hamilton-Jacobi equations, and optimal control[END_REF] for further properties and characterizations. Let Ω be an open subset of R n and let c ∈ R. Definition 2.14 (Semiconcave functions). We say that f : Ω → R is semiconcave in Ω with semiconcavity constant c 0 > 0 if f is continuous and, for every

x 1 , x 2 ∈ Ω such that the line segment {λx 1 + (1 -λ)x 2 : λ ∈ [0, 1]} is contained in Ω, we have f (x 1 ) + f (x 2 ) 2 -f x 1 + x 2 2 ≤ c 0 4 x 1 -x 2 2 .
In this case we will write f ∈ SC(Ω). We say that f is locally semiconcave in Ω, and write f ∈ LSC(Ω), if f ∈ SC(A) for every A ⊂ Ω, A open and bounded. We say that g : Ω → R is semiconvex iff -g is semiconcave.

Proposition 2.15 (Properties of semiconcave functions). Let Ω be an open subset of R n , let c ∈ R, and let f : Ω → R be continuous. Then the following are equivalent:

(1) f ∈ SC(Ω) with semiconcavity constant c; (2) f (y) -f (x) ≤ ξ, y -x + c y -x 2 for all ξ ∈ ∂ P f (x) and y ∈ Ω.
Definition 2.16 (Multifunctions). Let Ω be a subset of R n . A map F : Ω → P(R m ) will be called a multifunction or set-valued function, and we will write

F : Ω ⇒ R m .
We say that a multifunction

F : Ω ⇒ R m is: -measurable, if for all closed C ⊂ R m we have that {x ∈ Ω : F (x) ∩ C = ∅} is Lebesgue measurable; -upper semicontinuous at x 0 ∈ Ω, if for any open set M containing F (x 0 )
there exists an open set A ⊂ Ω with x 0 ∈ A such that

F (A) := a∈A F (a) ⊆ M;
-lower semicontinuous at x 0 ∈ Ω, if for any y 0 ∈ F (x 0 ) and any open set M containing y 0 there exists an open set A ⊂ Ω with x 0 ∈ A such that F (x) ∩ M = ∅; -continuous at x 0 ∈ Ω, if F is both lower and upper semicontinuous at x 0 ; -Lipschitz continuous, if there exists K > 0, called a Lipschitz constant of F , such that for any

x 1 , x 2 ∈ Ω we have F (x 2 ) ⊆ F (x 1 ) + K x 1 -x 2 B m .
Definition 2.17 (Differential inclusions). Let F : R n ⇒ R n be a measurable multifunction. A solution or trajectory of the differential inclusion

(7) ẋ(t) ∈ F (x(t)), x(t 0 ) = x 0 ∈ R n ,
is an absolutely continuous map y x 0 : I → R n such that I is an open interval containing t 0 , y x 0 (t 0 ) = x 0 , and ẏx 0 (t) ∈ F (t, x(t)) for a.e. t ∈ I.

We refer the reader to the monograph [START_REF] Aubin | Differential inclusions, Grundlehren der Mathematischen Wissenschaften[END_REF] for further properties and results on multifunctions and differential inclusions. Definition 2.18 (Minimum time function). Let F : R n ⇒ R n be a measurable multifunction, and let S be a given closed subset of R n . We define the minimum time function T : R n →]0, +∞] by setting:

(8) T (x) = inf {τ > 0 : ∃y x (•) satisfying ẋ(t) ∈ F (x(t)), x(0) = x, y x (τ ) ∈ S} with the usual convention inf ∅ = +∞.
The reachable (or controllable) set is defined as R = dom(T ).

Standing hypothesis and first consequences

From now on, we will consider t 0 = 0 in the differential inclusion [START_REF]Hamilton-Jacobi equations, and optimal control[END_REF], and the associated minimum time function T defined in [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF]. Definition 3.1 (Hamiltonian). The Hamiltonian H : R n × R n → R associated with F is given by ( 9)

H(x, p) = sup v∈F (x) p, v .
In other terms, H(x, p) is the support function to the set F (x), evaluated at p. Definition 3.2 (Hypothesis (F)). We say that the hypothesis (F) is satisfied by system [START_REF]Hamilton-Jacobi equations, and optimal control[END_REF] if the following holds true: (F1) F (x) is nonempty, convex, and compact for each x ∈ R n ; (F2) F is Lipschitz continuous.

Definition 3.3 (Hypothesis (H))

. We say that the hypothesis (H) is satisfied by system (7) if the following holds true: (H1) There exists a constant c 0 ≥ 0 such that, for every p ∈ R n , x → H(x, p) is semiconvex with semiconvexity constant c 0 |p|. (H2) For all p = 0, the gradient ∇ p H(•, p) exists and is globally Lipschitz continuous, i.e. there exists

K 1 ≥ 0 such that (10) ∇ p H(x, p) -∇ p H(y, p) ≤ K 1 y -x , for all x, y ∈ R n , p ∈ R n \ {0}. Remark 3.4. If hypothesis (F) hold, and K is a Lipschitz constant for F , then for all v ∈ F (x 2 ) there exists η ∈ B n , ρ ∈ [0, 1], v ′ ∈ F (x 1 ) such that we have v = v ′ + Kρη x 1 -x 2 . Moreover, H(x, p) ∈ R for every x, p ∈ R n . In particular, p, v = p, v ′ + Kρ x 1 -x 2 η, p ≤ sup w∈F (x 1 ) p, w + K p • x 1 -x 2 = H(x 1 , p) + K p • x 1 -x 2 .
By passing to the supremum on v ∈ F (x 2 ), we have

H(x 2 , p) -H(x 1 , p) ≤ K p • x 1 -x 2 ,
whence, reversing the role of x 1 and x 2 , we end up with

(11) |H(x 1 , p) -H(x 2 , p)| ≤ K p • x 1 -x 2 ,
for all x 1 , x 2 , p ∈ R n . Take now x 1 = x, x 2 = 0, and let v ∈ F (x) be such that v = 0 and v = max

w∈F (x) w . Set p = v/ v . Then we have v = max w∈F (x) w = H(x, p) ≤ K x + H(0, p) ≤ K x + max w∈F (0)
w .

So, there exists

K 2 > 0 such that if F (x) = {0} it holds: (12) max w∈F (x) w ≤ K 2 (1 + x ).
Since the above inequality still holds even if F (x) = {0}, it holds for every x ∈ R n .

Remark 3.5. Global Lipschitz continuity in both (F2) and (H2) was assumed just to simplify computations. Indeed, our results still hold if F is locally Lipschitz with respect to the Hausdorff distance, and ∇ p H(•, p) is locally Lipschitz in x, uniformly so over p in R\{0}. In that case, however, we need to assume [START_REF] Colombo | Some new regularity properties for the minimal time function[END_REF] as an extra condition.

We collect now, in the following, some consequences of assumptions (F) and (H):

Proposition 3.6. Suppose that F and H satisfy hypotheses (F) and (H).

(i) For every p = 0 and x ∈ R n , it holds

∂H(x, p) ⊆ ∂ x H(x, p) × ∂ p H(x, p),
where ∂ x and ∂ p denote the Clarke's generalized gradient with respect to x variables and p variables, respectively. (ii) For every p = 0, if we set F p (x) = ∇ p H(x, p), then F p (x) ∈ F (x) and F p (x), p = H(x, p). Moreover, F p (•) is Lipschitz continuous with Lipschitz constant K 1 , i.e.,

F p (y) -F p (x) ≤ K 1 • y -x , ∀x, y ∈ R n .
(iii) For every ξ ∈ ∂ x H(x, p), it holds

H(y, p) -H(x, p) -ξ, y -x ≥ -c 0 • p • y -x 2 , ∀x, y ∈ R n .
Proof. See Proposition 1 in [START_REF] Cannarsa | Semiconcavity of the value function for a class of differential inclusions[END_REF].

Proposition 3.7. Assume that F and H satisfy assumptions (F) and (H). Let T > 0, p(•) : [0, T ] → R n be an absolutely continuous arc such that p(t) = 0 for all t ∈ [0, T ]. Given x 0 ∈ R n , then the problem

(13)    ẋ(t) = F p(t) (x(t)), for a.e. t ∈ [0, T ],
x(0) = x 0 , admits a unique solution y(•, x 0 ). Moreover, for all t > 0, the following holds:

(i) x 0 → y(t, x 0 ) is Lipschitz continuous on R n and y(t, z 0 ) -y(t, x 0 ) ≤ e Kt • z 0 -x 0 , ∀z 0 ∈ R n , (ii) y(t, x 0 ) ≤ ( x 0 + 1) • e K 2 t -1, (iii) y(t, x 0 ) -x 0 ≤ K 2 • ( x 0 + 1)e K 2 t t, where K 2 is the constant in Remark 3.4.
Proof. The proof is based on Gronwall's inequaliy, see Proposition 3.4, Lemma 3.5, and Lemma 3.7 in [START_REF] Cannarsa | Exterior sphere condition and time optimal control for differential inclusions[END_REF].

The following statement allows us to make local approximation of trajectories of [START_REF]Hamilton-Jacobi equations, and optimal control[END_REF] with smooth ones: Proposition 3.8. Assume F and H satisfy hypotheses (F) and (H). Let K ⊂ R n be compact and let δ > 0 be given. Set

M = sup { v : v ∈ F (x), x ∈ K + δB(0, 1)} , δ 1 = δ M + 1 .
Then for each x 0 ∈ K, and v ∈ F (x 0 ) there exists a C 1 trajectory y

x 0 (•) of (7) such that ẏx 0 (t) -v ≤ KMt, ∀t ∈ [0, δ 1 ]. Proof. See Proposition 2.3 in [9].
We recall the following result: Proposition 3.9. Assume that F and H satisfy (F) and (H). Suppose x(•) is an optimal trajectory starting from x 0 and ξ = 0 is a unit proximal normal vector to S at x(T (x 0 )) so that µ . = H(x(T (x 0 )), ξ) -1 ≤ 0. Then there exists an absolutely continuous arc p : [0, T ] → R n satisfying

(14)    ẋ(t) ∈ F p(t) (x(t)) -ṗ(t) ∈ ∂ x H(x(t), p(t))
a.e. t ∈ [0, T (x 0 )] and the transversality condition

-p(T ) = µ • ξ.
Proof. See Theorem 2.1 in [START_REF] Cannarsa | The dual arc inclusion with differential inclusions[END_REF].

Main results

4.1. The dual arc inclusion.

Theorem 4.1. Assume that F and H satisfy (F) and (H). Let x ∈ R n \S, let x(•) be an optimal trajectory which starts from x and reaches S in time T (x), and let ξ be a unit proximal inner normal to S at x = x(T (x)). Consider the system:

(15)    ẋ(t) = F p(t) (x(t)), -ṗ(t) ∈ ∂ x H(x(t), p(t)) for a.e. t ∈ [0, T (x)].
Then:

(i) if H(x, ξ) = 0 and we couple system (15) with the condition p(T (x)) = ξ H(x, ξ)

, we have -p(t) ∈ ∂ P T (x(t)) for all t ∈ [0, T (x)),

(ii) if H(x, ξ) = 0 and we couple system (15) with the condition p(T (x)) = ξ, we have -p(t) ∈ ∂ ∞ T (x(t)) for all t ∈ [0, T (x)).

Proof. Applying the dynamic programming principle, one can see that if the conclusion of the theorem holds for t = 0 then it will hold for all t ∈ [0, T (x)). Therefore, we only need to prove the result for t = 0. We divide the proof into two main steps.

Step 1 (near the target S): There exists a constant C 1 ≥ 0 such that for all ȳ ∈ S c and β ≤ T (ȳ) it holds:

(16) p(T (x)), ȳ -x + βH(x, p(T (x))) ≤ C 1 • ȳ -x 2 + β 2 . Proof of Step 1: Set α = H(x, p(T (x))). Since p(T (x)) = λ • ξ ∈ N P S c (x)
, we have that there exists C > 0 such that:

(17) p(T (x)), ȳ -x ≤ C • ȳ -x 2 , ∀ȳ ∈ S c .
Therefore, if β ≤ 0, then (16) follows from (17) by choosing C 1 = C. Otherwise, if 0 < β ≤ T (ȳ), we consider the differential equation ( 18) and set ȳ1 := y(β). Since ȳ1 ∈ S c , recalling [START_REF] Marigonda | Some regularity properties for a class of upper semicontinuous functions[END_REF] we have that

ẏ(t) = F p(T (x)) (y(t)), y(0) = ȳ,
p(T (x)), ȳ1 -x ≤ C • ȳ1 -x 2 ≤ 2C • ȳ1 -ȳ 2 + ȳ -x 2 ≤ 2C • y(β) -y(0) 2 + ȳ -x 2 ≤ C 2 • β 2 + ȳ -x 2 ,
where C 2 is a suitable positive constant. On the other hand, we compute p(T (x)), ȳ -ȳ1 = p(T (x)), -

β 0 F p(T (x)) (y(s)) ds = - β 0 p(T (x)), F p(T (x)) (y(s)) ds = - β 0 p(T (x)), F p(T (x)) (x) ds+ - β 0 p(T (x)), F p(T (x)) (y(s)) -F p(T (x)) (x) ds ≤ -α • β + C 3 • ȳ -x 2 + β 2 ,
where C 3 is another suitable positive constant (we used also item (ii) in Proposition 3.6). Combining the two above inequalities, we obtain that

(19) p(T (x)), ȳ -x ≤ -α • β + (C 2 + C 3 ) • ȳ -x 2 + β 2 .
Therefore, (16) holds with C 1 = max{C, C 2 + C 3 }, and this concludes the proof of Step 1. ⋄

Step 2: We show that (p(0), α) ∈ N P hypo(T ) (x, T (x)), i.e. there exists a positive constant C 5 such that for all y ∈ S c and β ≤ T (y):

(20) p(0), y -x + α(β -T (x)) ≤ C 5 • y -x 2 + |β -T (x)| 2

Proof of

Step 2: There are two possible cases:

First case: Suppose T 1 := T (y) ≤ T (x) =: T . In this case, we only need to show that (20) holds for β = T 1 , i.e., ( 21)

p(0), y -x + α(T 1 -T ) ≤ C 5 • y -x 2 + |T 1 -T | 2 .
We consider the differential equation:

(22) ẏ(t) = F p(t) (y(t)), y(0) = y,
and set y 1 = y(T 1 ), x 1 = x(T 1 ). Observing that T (x 1 ) = T -T 1 and y 1 ∈ S c . We first compute:

p(T 1 ), y 1 -x 1 = p(0), y -x + T 1 0 d ds p(s), y(s) -x(s) ds = p(0), y -x + T 1 0 ṗ(s), y(s) -x(s) + p(s), F p(s) (y(s)) -F p(s) (x(s)) ds = p(0), y -x + T 1 0 ṗ(s), y(s) -x(s) + H(y(s), p(s)) -H(x(s), p(s))ds.
Sinceṗ(s) ∈ ∂ x H(x(s), p(s)), by Proposition 3.6 we have that

-ṗ(s), y(s) -x(s) + H(x(s), p(s)) -H(y(s), p(s)) ≤ c 0 • p(s) • y(s) -x(s) 2 .
Hence, for a suitable constant C 6 > 0, it holds

-ṗ(s), y(s) -x(s) + H(x(s), p(s)) -H(y(s), p(s)) ≤ C 6 • y -x 2
Therefore, (23) p(0), yx ≤ p(T 1 ),

y 1 -x 1 + C 6 • y -x 2 .
Now, we compute

p(T 1 ), y 1 -x 1 = p(T ), y 1 -x 1 + p(T 1 ) -p(T ), y 1 -x 1 ≤ p(T ), y 1 -x 1 + C 7 • (|T -T 1 | 2 + y -x 2 ), and
p(T ),y 1 -x 1 = p(T ), x(T ) -x(T 1 ) + p(T ), y 1 -x ≤ T T 1 p(T ), F p(s) (x(s)) ds + p(T ), y 1 -x = T T 1 p(T ), F p(s) (x(s)) -F p(T ) (x(T )) ds + α • (T -T 1 ) + p(T ), y 1 -x .
Recalling ( 16), we have that

p(T ), y 1 -x ≤ C • y 1 -x 2 ≤ C 8 • |T -T 1 | 2 + y 1 -x 2 ,
for a suitable positive constant C 8 . On the other hand, for any s ∈ [T 1 , T ],

p(T ), F p(s) (x(s)) -F p(T ) (x(T )) = = p(T ), F p(T ) (x(s)) -F p(T ) (x(T )) + p(T ), F p(s) (x(s)) -F p(T ) (x(s)) ≤ C 9 • |s -T |,
for some constant C 9 > 0. Hence,

T T 1 p(T ), F p(s) (x(s)) -F p(T ) (x(T )) ds ≤ C 9 2 • |T -T 1 | 2 .
Therefore, we obtain that

p(T ), y 1 -x 1 ≤ α • (T -T 1 ) + C 10 • |T -T 1 | 2 + y -x 2 ,
for a suitable constant C 10 . Combining this estimate with (23), we finally get (21).

Second case: T 1 := T (y) > T (x) =: T . We consider the differential equation ( 24)

ẏ(t) = F p(t) (y(t)), y(0) = y,
and set ȳ = y(T ). By the same arguments of the first step, we have that

(25) p(0), y -x ≤ p(T ), ȳ -x + C • y -x 2 .
On the other hand, observing that ȳ ∈ S c , from ( 16) we obtain that

p(T ), ȳ -x + α • β 1 ≤ C 1 • ȳ -x 2 + β 2 1
for all β 1 ≤ T (ȳ). Thus, for every β ≤ T (y), by the dynamic programming principle we have that β -T ≤ T (ȳ). Hence, taking β 1 = β -T in the above inequality, we get that

p(T ), ȳ -x + α • (β -T ) ≤ C 1 • ȳ -x 2 + |β -T | 2
. By Gronwall's inequality, we finally obtain that there exists C 11 > 0 such that

p(T ), ȳ -x + α • (β -T ) ≤ C 11 • y -x 2 + |β -T | 2 .
The proof is complete.

The constancy of H.

Proposition 4.2. Assume (F) and (H). Let x ∈ R n \S, let x(•) be an optimal trajectory at x reaching S in time T (x), and let ξ be a proximal inner unit normal to S at x = x(T (x)). Consider the system:

(26) ẋ(t) = F p(t) (x(t)), -ṗ(t) ∈ ∂ x H(x(t), p(t)) for a.e. t ∈ [0, T (x)].
Then: (i) if H(x, ξ) = 0 and we couple system (26) with the condition p(T (x)) = ξ H(x, ξ)

, we have H(x(t), p(t)) = 1 for all t ∈ [0, T (x)],

(ii) if H(x, ξ) = 0 and we couple system (26) with the condition p(T (x)) = ξ, we have H(x(t), p(t)) = 0 for all t ∈ [0, T (x)].

Proof.

(i) Assume that H(x, p(T (x))) = 1. Fixing t ∈ (0, T (x)) we will show that H(x(t), p(t)) = 1. First, observe that, by Theorem 4.1, -p(t) ∈ ∂ P T (x(t)) for all t ∈ [0, T (x)). Now, for every v ∈ F (x(t)), Proposition 3.8 ensures that there exists a trajectory y(•) ∈ C 1 starting from x(t) at time t such that

ẏ(t + s) -v ≤ K • s, ∀s ∈ (0, δ).
Since -p(t) ∈ ∂ P T (x(t)), we have that

p(t), y(t + s) -x(t) + β -T (x(t)) ≤ ≤ C • y(t + s) -x(t) 2 + |β -T (x(t))| 2 ,
for all β ≤ T (y(t + s)). Observe that T (y(t + s)) ≥ T (x(t))s and choose β = T (x(t))s in the above inequality to obtain

p(t), y(t + s) -x(t) -s ≤ C 1 • s 2 .
Hence,

p(t), v = lim s→0 + p(t), y(t + s) -x(t) s ≤ 1.
This implies that H(x(t), p(t)) ≤ 1.

On the other hand, we have

p(t), x(t -s) -x(t) + T (x(t -s)) -T (x(t)) ≤ ≤ C • x(t -s) -x(t) 2 + |T (x(t -s)) -T (x(t))| 2 .
Since T (x(ts)) -T (x(t)) = s, we get that

p(t), x(t -s) -x(t) + s ≤ C 1 • s 2 . thus 1 ≤ lim sup s→0 + p(t), x(t) -x(t -s) s ≤ H(x(t), p(t)).
Therefore, we finally obtain that

H(x(t), p(t)) = 1, ∀t ∈ (0, T (x)].
By the continuity of H, the proof of (i) is complete.

(ii) Assume that H(x, p(T (x))) = 0. Fixing t ∈ (0, T (x)), we will show that H(x(t), p(t)) = 0. For every v ∈ F (x(t)), there exists a trajectory y(•) ∈ C 1 starting from x(t) at time t such that

ẏ(t + s) -v ≤ K • s, ∀s ∈ (0, δ).
Since -p(t) ∈ ∂ ∞ T (x(t)), we have that

p(t), y(t + s) -x(t) ≤ C • y(t + s) -x(t) 2 + |β -T (x(t))| 2 ,
for every β ≤ T (y(t + s)). Since T (y(t + s)) ≥ T (x(t))s, we can choose β = T (x(t))s to obtain, by the above inequality,

p(t), y(t + s) -x(t) ≤ C 1 • s 2 .
Hence

p(t), v = lim s→0 + p(t), y(t + s) -x(t) s ≤ 0.
Therefore, H(x(t), p(t)) ≤ 0.

On the other hand,

p(t), x(t -s) -x(t) ≤ ≤ C • x(t -s) -x(t) 2 + |T (x(t -s)) -T (x(t))| 2 .
Since T (x(ts)) -T (x(t)) = s, from the above inequality we deduce that

p(t), x(t -s) -x(t) ≤ C 1 • s 2 .
Thus,

0 ≤ lim sup s→0 + p(t), x(t) -x(t -s) s ≤ H(x(t), p(t)).
Therefore, H(x(t), p(t)) = 0, ∀t ∈ (0, T (x)]. By the continuity of H, the proof of (ii) is complete. 4.3. Optimality conditions. Theorem 4.3. Assume (F) and (H). Let x ∈ R n \ S and let x(•) be a trajectory starting from x such that x(T ) ∈ S. Suppose there exists a continuous function

p(•) : [0, T ] → R n such that (27)        ẋ(t) = F p(t) (x(t)) -p(t) ∈ ∂ P T (x(t)) H(x(t), p(t)) = 1 for a.e. t ∈ [0, T ] . Then x(•) is an optimal trajectory. Proof. Set ϕ(•) = T (x(•)).
Owing to the dynamic programming principle, for every t ∈ [0, T ] and 0 < s < Tt we have

ϕ(t + s) ≥ ϕ(t) -s. Hence, lim inf s→0 + ϕ(t + s) -ϕ(t) s ≥ -1.
On the other hand, since -p(t) ∈ ∂ P T (x(t)), we have that

p(t), x(t + s) -x(t) + ϕ(t + s) -ϕ(t) ≤ ≤ C • x(t + s) -x(t) 2 + |ϕ(t + s) -ϕ(t)| 2 .
This is equivalent to

C• x(t + s) -x(t) 2 s ≥ ≥ p(t), x(t + s) -x(t) s + ϕ(t + s) -ϕ(t) s • (1 -C • (ϕ(t + s) -ϕ(t))) = 1 s s 0 p(t), F p(t+τ ) (x(t + τ )) dτ + ϕ(t + s) -ϕ(t) s • (1 -C • (ϕ(t + s) -ϕ(t))) = 1 s s 0 p(t + τ ), F p(t+τ ) (x(t + τ )) dτ + 1 s s 0 p(t) -p(t + τ ), F p(t+τ ) (x(t + τ )) dτ + + ϕ(t + s) -ϕ(t) s • (1 -C • (ϕ(t + s) -ϕ(t))) = 1 s s 0 H(x(t + τ ), p(t)) dτ + 1 s s 0 p(t) -p(t + τ ), F p(t+τ ) (x(t + τ )) dτ + + ϕ(t + s) -ϕ(t) s • (1 -C • (ϕ(t + s) -ϕ(t))) , = 1 + 1 s s 0 p(t) -p(t + τ ), F p(t+τ ) (x(t + τ )) dτ + + ϕ(t + s) -ϕ(t) s • (1 -C • (ϕ(t + s) -ϕ(t))) ,
where we used the Mean Value Theorem and the fact that

p(t + τ ), F p(t+τ ) (x(t + τ )) = H(p(t + τ ), x(t + τ )) = 1,
for a.e. τ [0, s] and for every 0 < s < Tt. The continuity of p(•) and the estimate lim s→0 +

x(t + s)x(t) 2 s = 0, now yield for every t ∈]0, T [:

lim sup s→0 + ϕ(t + s) -ϕ(t) s ≤ -1.
Thus, lim

s→0 + ϕ(t + s) -ϕ(t) s = -1 for every 0 < t < T . Now, for s < 0, we have that ϕ(t + s) ≤ ϕ(t) -s. Thus, ϕ(t + s) -ϕ(t) s ≥ -1 for all 0 < t < T and -t < s < 0. Hence, lim inf s→0 - ϕ(t + s) -ϕ(t) s ≥ -1.
On the other hand, we have

C• x(t) -x(t + s) 2 ≥ ≥ p(t + s), x(t) -x(t + s) + (ϕ(t) -ϕ(t + s)) • (1 -C • (ϕ(t) -ϕ(t + s))) .
For s < 0, by performing similar computations as done in the case 0 < s < Tt, from the above inequality we get that

C • x(t) -x(t + s) 2 s ≥ ≥ p(t + s), x(t) -x(t + s) s + ϕ(t) -ϕ(t + s) s • (1 -C • (ϕ(t) -ϕ(t + s))) ≥ p(t + s) -p(t), x(t) -x(t + s) s + p(t), x(t) -x(t + s) s + + ϕ(t) -ϕ(t + s) s • (1 -C • (ϕ(t) -ϕ(t + s))) ≥ p(t + s) -p(t), x(t) -x(t + s) s - 1 s s 0 p(t), F p(t+τ ) (x(t + τ )) dτ + + ϕ(t) -ϕ(t + s) s • (1 -C • (ϕ(t) -ϕ(t + s))) ≥ p(t + s) -p(t), x(t) -x(t + s) s - 1 s s 0 p(t) -p(t + τ ), F p(t+τ ) (x(t + τ )) dτ + + ϕ(t) -ϕ(t + s) s • (1 -C • (ϕ(t) -ϕ(t + s))) - 1 s s 0 p(t + τ ), F p(t+τ ) (x(t + τ )) dτ.
Thus, for every 0 < t < T we have

lim sup s→0 - ϕ(t + s) -ϕ(t) s ≤ -1.
This implies that lim s→0 -ϕ(t+s)-ϕ(t) s = -1. Therefore, we finally have that φ(t) = -1 for all t ∈]0, T (x)[, so

T (x(t)) = ϕ(t) = ϕ(0) -t = T (x) -t,
that is, x(•) is an optimal trajectory. 4.4. Regularity results.

In order to prove the regularity results of this section we need the following technical lemma, the proof of which is postponed to the Appendix. (i) an optimal trajectory x 0 (•) with x 0 (0) = x 0 , x0 := x 0 (T (x 0 )) ∈ S, and (ii) a unit vector ξ 0 ∈ N P R n \S (x 0 ) such that H(x 0 , ξ 0 ) = 0. Proof. First of all, observe that, if (i) and (ii) hold true at a point x 0 ∈ R \ S, then ∂ ∞ T (x 0 ) = ∅ thanks to Theorem 4.1. Therefore, T (•) cannot be Lipschitz at x 0 .

In order to prove the converse, let x 0 ∈ R \ S be a point at which T (•) fails to be Lipschitz. Note that, owing to Theorem 4.1 in [START_REF] Cannarsa | Exterior sphere condition and time optimal control for differential inclusions[END_REF], hypo T satisfies an external sphere condition with a locally constant radius. Consequently, by Lemma 4.1 and Corollary 4.1 in [START_REF] Khai | Hypographs satisfying an external sphere condition and the regularity of the minimum time function[END_REF], x → N P hypo T (x, T (x)) has closed graph, and ∂ P T (x) reduces to the singleton {∇T (x)} at every x ∈ dom ∇T . Moreover, T (•) is differentiable a.e. in R \ S. Then, by Lemma 4.4, ∇T must be unbounded on any neighborhood of x 0 . So, there exists a sequence {x j } j 1 ⊂ dom ∇T and a unit vector ζ 0 ∈ R n such that Notice that, since the map x → N P hypo T (x, T (x)) has closed graph, ζ 0 ∈ ∂ ∞ T (x 0 ). Next, thanks to Proposition 3.9, we can construct sequences of absolutely continuous arcs {x j (•)} 1 , {p j (•)} 1 , and unit vectors {ξ j } 1 with the following properties:

(a) x j (0) = x j and xj := x j (T (x j )) ∈ S, i.e., x j (•) is an optimal trajectory starting from x j which reaches the target at xj ; (b) ξ j ∈ N P R n \S (x j ), and H(x j , ξ j ) = 0; (c) p j := p j (T (x j )) = ξ j H(x j , ξ j ) ;

(d) (x j (•), p j (•)) satisfies (28) ẋj (t) = ∇ p H(x j (t), p j (t)) -ṗj (t) = ∇ x H(x j (t), p j (t)) for a.e. t ∈ [0, T (x j )].
Also, since x j ∈ dom ∇T , Theorem 4.1 ensures that -p j (0) = ∇T (x j ). Since x j → x 0 and T (•) is continuous, a well known compactness property of the trajectories of the differential inclusion (29) ẋ(t) ∈ F (x(t))

ensure that, up to extracting a subsequence, one can assume that {x j (•)} j∈ 1 converges uniformly to an absolutely continuous arc, x 0 (•), which satisfies (29) together with x 0 (0) = x 0 . Again, since T (•) is continuous and S is closed, we have that x0 := x 0 (T (x 0 )) ∈ S, i.e. x 0 (•) is optimal. We can also assume that {ξ j } j∈N converges to the (proximal) inner unit normal ξ 0 to S at x0 by the smoothness of S.

We now claim that |p j | → ∞ as j → ∞. Indeed, since H is homogeneous of degree 1 in p and of class C 1,1 (R n × (R n \ {0})), for some constant M > 0 |∇ x H(x, p)| ≤ M|p| for all p ∈ R n \ {0} and all x in the bounded set

A := x j (t) : t ∈ [0, T (x j )] ∪ x 0 (t) : t ∈ [0, T (x 0 )] .
Therefore, (28) yields, for all j ≥ 1 and a.e. t ∈ [0, T (x j )],

- 1 2
d dt |p j (t)| 2 = -ṗj (t), p j (t) = ∇ x H x j (t), p j (t) , p j (t) ≤ M|p j (t)| 2 .
The above differential inequality implies that

|p j | ≥ e -M T (x j ) |p j (0)|.
Since |p j (0)| → ∞ and T (x j ) → T (x 0 ) as j → ∞, we conclude that also |p j | → ∞.

Finally, observe that p j = |p j | • ξ j and H(x j , p j ) = 1 for every j ∈ N. So,

1 = lim j→∞ H(x j , p j ) = lim j→∞ |p j | • H(x j , ξ j ). Since |p j | → ∞, we must have that lim j→∞ H(x j , ξ j ) = H(x 0 , ξ 0 ) = 0.
This shows points (i) and (ii) above. Invoke Theorem 4.1 to complete the proof .

Theorem 4.6. Suppose H ∈ C 1,1 R n × (R n \ {0}) , and let g ∈ C 2 b (R n ).
Define the target set S by S = {x ∈ R n : g(x) ≤ 0}, and let Σ be a countably H n-2 -rectifiable subset of ∂S. In addition to (F ) and (H), assume that:

(a) 0 ∈ F (x) for every x ∈ ∂S, (b) ∇g = 0 on ∂S, (c) T (•) is continuous in R, and (d) for all x ∈ ∂S \ Σ and λ ∈ R

(30) ∇ x H(x, -∇g(x)) -∇ p H(x, -∇g(x)) • ∇ 2 g(x) = λ∇g(x) .
Then:

(i) T (•) is a function of special bounded variation on R \ S, and (ii) there exists a closed countably

H n-1 -rectifiable set S ⊂ R such that T (•) is locally semiconcave on R \ S ∪ S .
Proof. We begin by showing the following property needed for the sequel of the proof: (⋆) if, for some point x ∈ ∂S, there exists a nonzero vector ξ ∈ N P R n \S (x) such that H(x, ξ) = 0, then x ∈ Σ. Indeed, since 0 ∈ F (x), we have that H(x, p) ≥ 0 for all x ∈ ∂S and p ∈ R n . Therefore, H attains a constrained minimum at (x, ξ). Moreover, since H(x, •) is positively homogeneous, (x, rξ) also minimizes H constrained to ∂S for all r ≥ 0. Now, -∇g(x) can be represented as rξ for some r > 0 because S has a smooth boundary. So, x is a minimizer of the smooth function x → H(x, -∇g(x)) on ∂S. Then, by Lagrange multiplier rule and (30), we have x ∈ Σ.

Next, let us prove the SBV property (i). Since hypo T satisfies an external sphere condition, owing to Proposition 6.1 in [START_REF] Marigonda | Some regularity properties for a class of upper semicontinuous functions[END_REF] we have that T ∈ BV loc (R\S). So, we just need to show that, on R\S, the singular part of DT (•) is concentrated on a set of σ-finite H n-1 -measure. Recalling that the characteristics of the pde

H(x, -∇T ) -1 = 0 satisfy (31) Ẋ(t) = -∇ p H(X(t), P (t)) Ṗ (t) = ∇ x H(X(t), P (t)), consider the flow (X, P ) : R × R n × R n → R n × R n , that is, for any (x, p) ∈ R n × R n , (X, P )(•, x, p) is the solution pf (31) with initial conditions (32) X(0) = x , P (0) = p.
Notice that (t, x) → (X, P ) t, x, -∇g(x) is Lipschitz continuous under our assumptions. Now, set

Φ(t, x) = X t, x, -∇g(x) t ≥ 0, x ∈ R n .
Then, by Lemma 4.5 we have that, for any t > 0,

Σ t := x ∈ R \ S : ∂ ∞ T (x) = ∅ , T (x) ≤ t ⊆ Φ (0, t] × Σ is countably H n-1 -rectifiable since Σ is countably H n-2 -
. Let g ∈ C 2 b (R n ), let S := {x ∈ R n : g(x) ≤ 0},
and assume that ∇g(x) = 0 at every x ∈ S. Choose a countable set Σ ⊆ S such that, for some function ψ

: Ω → [0, +∞[ of class C 1,1 , we have Σ = {y ∈ R n : ψ(y) = 0}. Define H(x, p) := ψ(x)dist p, ∇g(x) ⊥ ,
where ∇g(x) ⊥ denotes the hyperplane in R n that is orthogonal to ∇g(x). For all x, p, q ∈ R n , we have that H(x, λp) = λH(x, p) ≥ 0 for every λ ≥ 0, and H(x, p + q) ≤ H(x, p) + H(x, q). So, H(x, •) is the support function of a closed convex subset F (x) of R n . With these choices, we have that (30) is satisfied.

Appendix A. Proof of Lemma 4.4 We now prove the technical Lemma 4.4.

Proof. Since hypo f satisfies the external sphere condition, for some θ > 0, we have that for every y, z ∈ V there exists a unit vector v ∈ N P hypo f (z, f (z)) such that Let {y j } j∈N ⊆ V and {x j } j∈N ⊆ V be sequences converging to x such that x j = y j for all j ∈ N, and

lim j→∞ |f (y j ) -f (x j )| |y j -x j | = ∞.
We claim that there exist {z j } j∈N and {w j } j∈N such that z j → x, w j → x, f is differentiable at z j and at w j , |∇f (z j )| ≤ L and |∇f (w j )| ≤ L for every j ∈ N, and

lim j→∞ |f (z j ) -f (w j )| |z j -w j | = ∞.
Indeed, recalling that f ∈ C 0 (V ), for every j ∈ N there exists δ j > 0 such that if |y j -q| ≤ δ j , we have |f (y j )f (q)| ≤ |f (y j )f (x j )| 2 . Since f is a.e. differentiable on V by Theorem 3.1 in [START_REF] Khai | Hypographs satisfying an external sphere condition and the regularity of the minimum time function[END_REF], and |∇f (q)| ≤ L for a.e. q ∈ V by assumption, for every j ∈ N we can find z j ∈ B(y j , δ j ) ∩ B (y j , |y jx j | 2 ) such that f is differentiable at z j , |∇f (z j )| ≤ L, and z j = x j . Notice that To construct w j , it suffices to apply the above reasoning to x j , z j instead of y j , x j .

Next, recall that, owing to Lemma 4.1 in [START_REF] Khai | Hypographs satisfying an external sphere condition and the regularity of the minimum time function[END_REF],

N P hypo f (z j , f (z j )) = λ (-∇f (z j ), 1) |(-∇f (z j ), 1)| : λ ≥ 0 , N P hypo f (w j , f (w j )) = λ (-∇f (w j ), 1) |(-∇f (w j ), 1)| : λ ≥ 0 .

We can assume that, as j → +∞, (-∇f (z j ), 1) |(-∇f (z j ), 1)| → (ζ, ξ) and (-∇f (w j ), 1) |(-∇f (w j ), 1)| → (η, σ) with ξ, σ ≥ 1 √ 1 + C 2 > 0 since ∇f (z j ) and ∇f (w j ) are bounded. Moreover, (ζ, ξ), (η, σ) ∈ N P hypo f (x, f (x)) (since θ does not depend on z j or w j ), and, for every y ∈ V , we have that

(ζ, ξ), (y -x, f (y) -f (x)) ≤ 1 2θ |y -x| 2 + |f (y) -f (x)| 2 .
We now distinguish two cases.

a. Assume that {f (z j )f (x j )} j∈N has a monotone increasing subsequence. In this case, since it tends to 0, after relabeling, we have f (x j )f (z j ) ≥ 0 for every j ∈ N. Choosing, in (34), y = x j , z = z j , v = (-∇f (z j ), 1) |(-∇f (z j ), 1)| , we have

(-∇f (z j ), 1) |(-∇f (z j ), 1)| , x j -z j |f (x j ) -f (z j )| , f (x j ) -f (z j ) |f (x j ) -f (z j )| ≤ ≤ 1 2θ   |x j -z j | |f (x j )-f (z j )| |x j -z j | + |f (x j ) -f (z j )|   .
Passing to the limit in the above inequality yields ξ ≤ 0, which is a contradiction with the fact that ξ > 0.

b. Assume that {f (z j )f (x j )} j∈N has a monotone decreasing subsequence. In this case, we have that {f (x j )f (z j )} j∈N has a monotone increasing subsequence, and we apply the argument of the previous case by switching the roles of x j and z j , and replacing ξ with σ.

Since we have reached a contradiction assuming (35), the proof is complete.

http://arxiv.org/ps/1311.4415v1

x

  i y i the scalar product in R n ; x := x, x the Eulidean norm in R n ; ∂S, int(S), S the topological boundary, interior and closure of S; diam(S) := sup{ z 1z 2 : z 1 , z 2 ∈ S} the diameter of S; P(S) := {B ⊆ R n : B ⊆ S} the power set of S; B n :={w ∈ R n : w < 1} the unit open ball (centered at the origin); S n-1 := {w ∈ R n : w = 1} = ∂B n the unit sphere (centered at the origin); B(y, r) := {z ∈ R n : zy < r} = y + rB n the open ball centered at y of radius r; d K (y) := dist(y, K) = min{ zy : z ∈ K} the distance of y from K; π K (y) := {z ∈ K : zy = d K (y)} the set of projections of y onto K; S c := R n \ S the complement of S.

Definition 2 . 4 (

 24 Lipschitz functions). Given the Banach spaces X, Y , and two open sets

Figure 1 .

 1 Figure 1. First case of the proof of Theorem 4.1, Step 2.

Lemma 4 . 4 .

 44 Let D ⊆ R n be open, let f ∈ C 0 (D) be such that hypo f satisfies an external sphere condition with a locally uniform radius, and let V ⊆ D be a bounded open set. If ∇f is essentially bounded on V , then f is Lipschitz continuous on V . Lemma 4.5. Let S ⊆ R n be a closed nonempty set with a C 1,1 -smooth boundary. Assume (F ) and (H). Suppose H ∈ C 1,1 (R n × (R n \ {0})) and T (•) is continuous in R. Then x 0 ∈ R \ S is a point at which T (•) fails to be Lipschitz continuous if and only if there exists:

  lim j→∞ x j = x 0 , lim j→∞ |∇T (x j )| = ∞ and lim j→∞ (-∇T (x j ), 1) | (-∇T (x j ), 1) | = (ζ 0 , 0).

2 .

 2 yz, f (y)f (z)) ≤ 1 2θ |y -z| 2 + |f (y)f (z)| For f (y) = f (z), dividing the above inequality by |f (y)f (z)| we obtain v, yz |f (y)f (z)| , f (y)f (z) |f (y)f (z)| ≤ 1 2θ |y -z| |f (y)-f (z)| |y-z| + |f (y)f (z)| . (34)By contradiction, suppose there exists L > 0 such that |∇f (q)| ≤ L for a.e. q ∈ V and there exists x ∈ V such that (35) lim sup y,x→x y =x |f (y)f (x)| |y -x| = ∞.

1 .

 1 |x jy j | ≤ |x jz j | + |z jy j | ≤ |x jz j | + |x jy j | 2 |x jz j | ≤ |x jy j | + |y jz j | ≤ |x jy j | + |x jy j | 2 .Dividing both inequalities by |x jy j | and letting j → ∞ yieldslim j→∞ |x jz j | |x jy j | = Similarly, since |f (x j )f (y j )| ≤ |f (x j )f (z j )| + |f (z j )f (y j )| ≤ |f (x j )f (z j )| + |f (x j )f (y j )| 2 |f (x j )f (z j )| ≤ |f (x j )f (y j )| + |f (y j )f (z j )| ≤ |f (x j )f (y j )| + |f (x j )f (y j )| 2 ,we obtainlim j→∞ |f (x j )f (z j )| |f (x j )f (y j )| = 1.So,lim j→∞ |f (z j )f (x j )| |z jx j | = lim j→∞ |f (z j )f (x j )| |f (y j )f (x j )| |y jx j | |z jx j | |f (y j )f (x j )| |y jx j | = lim j→∞ |f (y j )f (x j )| |y jx j | = ∞.

  S since it is locally Lipschitz on such a set.

	rectifiable by hypothesis.
	Thus,
	Example 4.7 (Prescribing singularities)

S := x ∈ R \ S : T (•) fails to be Lipschitz at x = ∞ k=1 Σ k is countably H n-1 -rectifiable as well. Moreover, owing to Lemma 4.2 and Corollary 4.2 in [18], S is closed in R. Therefore, in view of Proposition 2.7, we conclude that T (•) ∈ SBV loc (R \ S). Finally, by Corollary 4.3 in [5], T (•) is locally semiconcave on R \ S ∪

The authors wish to acknowledge the support obtained by the ITN -Marie Curie Grant n. 264735-SADCO, and by the CNRS and INdAM through the GDRE CONEDP. The third author also wishes to acknowledge the support obtained by the ERC Starting Grant 2009 n.240385 ConLaws in Padova.