Dans cette thèse, notre but est de donner un cadre numérique général pour approcher les solutions des problèmes du transport optimal (TO). L’idée générale est d’introduire une régularisation entropique du problème initial. Le problème régularisé correspond à minimiser une entropie relative par rapport à une mesure de référence donnée. En effet, cela équivaut à trouver la projection d’un couplage par rapport à la divergence de Kullback-Leibler. Cela nous permet d’utiliser l’algorithme de Bregman/Dykstra et de résoudre plusieurs problèmes variationnels liés au TO. Nous nous intéressons particulièrement à la résolution des problèmes du transport optimal multi-marges (TOMM) qui apparaissent dans le cadre de la dynamique des fluides (équations d’Euler incompressible à la Brenier) et de la physique quantique (la théorie de fonctionnelle de la densité ). Dans ces cas, nous montrons que la régularisation entropique joue un rôle plus important que de la simple stabilisation numérique. De plus, nous donnons des résultats concernant l’existence des transports optimaux (par exemple des transports fractals) pour le problème TOMM. / In this thesis we aim at giving a general numerical framework to approximate solutions to optimal transport (OT) problems. The general idea is to introduce an entropic regularization of the initialproblems. The regularized problem corresponds to the minimization of a relative entropy with respect a given reference measure. Indeed, this is equivalent to find the projection of the joint coupling with respect the Kullback-Leibler divergence. This allows us to make use the Bregman/Dykstra’s algorithm and solve several variational problems related to OT. We are especially interested in solving multi-marginal optimal transport problems (MMOT) arising in Physics such as in Fluid Dynamics (e.g. incompressible Euler equations à la Brenier) and in Quantum Physics (e.g. Density Functional Theory). In these cases we show that the entropic regularization plays a more important role than a simple numerical stabilization. Moreover, we also give some important results concerning existence and characterization of optimal transport maps (e.g. fractal maps) for MMOT .

Le progrès technologique nécessite des techniques de plus en plus sophistiquées et précises de traitement de matériaux. Nous étudions le traitement de matériaux par faisceaux de haute énergie : un jet d’eau abrasif, une sonde ionique focalisée, un laser. L’évolution de la surface du matériau sous l’action du faisceau de haute énergie est modélisée par une EDP. Cette équation contient l’ensemble des coefficients inconnus - les paramètres de calibration de mo- dèle. Les paramètres inconnus peuvent être calibrés par minimisation de la fonction coût, c’est-à-dire, la fonction qui décrit la différence entre le résultat de la modélisation et les données expérimentales. Comme la surface modélisée est une solution du problème d’EDP, cela rentre dans le cadre de l’optimisation sous contrainte d’EDP. L’identification a été rendue bien posée par la régularisation du type Tikhonov. Le gradient de la fonction coût a été obtenu en utilisant les deux méthodes : l’approche adjointe et la différen- ciation automatique. Une fois la fonction coût et son gradient obtenus, nous avons utilisé un minimiseur L-BFGS pour réaliser la minimisation.Le problème de la non-unicité de la solution a été résolu pour le problème de traitement par le jet d’eau abrasif. Des effets secondaires ne sont pas inclus dans le modèle. Leur impact sur le procédé de calibration a été évité. Ensuite, le procédé de calibration a été validé pour les données synthétiques et expérimentales. Enfin, nous avons proposé un critère pour distinguer facilement entre le régime thermique et non- thermique d’ablation par laser. / The technological progress demands more and more sophisticated and precise techniques of the treatment of materials. We study the machining of the material with the high energy beams: the abrasive waterjet, the focused ion beam and the laser. Although the physics governing the energy beam interaction with material is very different for different application, we can use the same approach to the mathematical modeling of these processes.The evolution of the material surface under the energy beam impact is modeled by PDE equation. This equation contains a set of unknown parameters - the calibration parameters of the model. The unknown parameters can be identified by minimization of the cost function, i.e., function that describes the differ- ence between the result of modeling and the corresponding experimental data. As the modeled surface is a solution of the PDE problem, this minimization is an example of PDE-constrained optimization problem. The identification problem was regularized using Tikhonov regularization. The gradient of the cost function was obtained both by using the variational approach and by means of the automatic differentiation. Once the cost function and its gradient calculated, the minimization was performed using L-BFGS minimizer.For the abrasive waterjet application the problem of non-uniqueness of numerical solution is solved. The impact of the secondary effects non included into the model is avoided as well. The calibration procedure is validated on both synthetic and experimental data.For the laser application, we presented a simple criterion that allows to distinguish between the thermal and non-thermal laser ablation regimes.

No description available.

No description available.

Le test à base de modèles des systèmes réactifs est le processus de vérifier si un système sous test (SUT) est conforme à sa spécification. Il consiste à gérer à la fois la génération des données de test et le calcul de verdicts en utilisant des modèles. Nous spécifions le comportement des systèmes réactifs à l'aide des systèmes de transitions symboliques temporisées à entrée-sortie (TIOSTS). Quand les TIOSTSs sont utilisés pour tester des systèmes avec une interface centralisée, l'utilisateur peut ordonner complètement les événements (i.e., les entrées envoyées au système et les sorties produites). Les interactions entre le testeur et le SUT consistent en des séquences d'entrées et de sortie nommées traces, pouvant être séparées par des durées dans le cadre du test temporisé, pour former ce que l'on appelle des traces temporisées. Les systèmes distribués sont des collections de composants locaux communiquant entre eux et interagissant avec leur environnement via des interfaces physiquement distribuées. Différents événements survenant à ces différentes interfaces ne peuvent plus être ordonnés. Cette thèse concerne le test de conformité des systèmes distribués où un testeur est placé à chaque interface localisée et peut observer ce qui se passe à cette interface. Nous supposons qu'il n'y a pas d’horloge commune mais seulement des horloges locales pour chaque interface. La sémantique de tels systèmes est définie comme des tuples de traces temporisées. Nous considérons une approche du test dans le contexte de la relation de conformité distribuée dtioco. La conformité globale peut être testée dans une architecture de test en utilisant des testeurs locaux sans communication entre eux. Nous proposons un algorithme pour vérifier la communication pour un tuple de traces temporisées en formulant le problème de message-passing en un problème de satisfaction de contraintes (CSP). Nous avons mis en œuvre le calcul des verdicts de test en orchestrant à la fois les algorithmes du test centralisé off-line de chacun des composants et la vérification des communications par le biais d'un solveur de contraintes. Nous avons validé notre approche sur un cas étude de taille significative. / Model-based testing of reactive systems is the process of checking if a System Under Test (SUT) conforms to its model. It consists of handling both test data generation and verdict computation by using models. We specify the behaviour of reactive systems using Timed Input Output Symbolic Transition Systems (TIOSTS) that are timed automata enriched with symbolic mechanisms to handle data. When TIOSTSs are used to test systems with a centralized interface, the user may completely order events occurring at this interface (i.e., inputs sent to the system and outputs produced from it). Interactions between the tester and the SUT are sequences of inputs and outputs named traces, separated by delays in the timed framework, to form so-called timed traces. Distributed systems are collections of communicating local components which interact with their environment at physically distributed interfaces. Interacting with such a distributed system requires exchanging values with it by means of several interfaces in the same testing process. Different events occurring at different interfaces cannot be ordered any more. This thesis focuses on conformance testing for distributed systems where a separate tester is placed at each localized interface and may only observe what happens at this interface. We assume that there is no global clock but only local clocks for each localized interface. The semantics of such systems can be seen as tuples of timed traces. We consider a framework for distributed testing from TIOSTS along with corresponding test hypotheses and a distributed conformance relation called dtioco. Global conformance can be tested in a distributed testing architecture using only local testers without any communication between them. We propose an algorithm to check communication policy for a tuple of timed traces by formulating the verification of message passing in terms of Constraint Satisfaction Problem (CSP). Hence, we were able to implement the computation of test verdicts by orchestrating both localised off-line testing algorithms and the verification of constraints defined by message passing that can be supported by a constraint solver. Lastly, we validated our approach on a real case study of a telecommunications distributed system.

Cette thèse se décompose en quatre parties auxquelles s'ajoute une présentation. Dans un premier temps, on expose les outils mathématiques essentiels à la compréhension des prochains chapitres. Dans un deuxième temps, on s'intéresse à la régression non paramétrique locale pour des données fonctionnelles appartenant à un espace de Hilbert. On propose, tout d'abord, un estimateur de l'opérateur de régression. La construction de cet estimateur est liée à la résolution d'un problème inverse linéaire. On établit des bornes de l'erreur quadratique moyenne (EQM) de l'estimateur de l'opérateur de régression en utilisant une décomposition classique. Cette EQM dépend de la fonction de petite boule de probabilité du régresseur au sujet de laquelle des hypothèses de type Gamma-variation sont posées. Dans le chapitre suivant, on reprend le travail élaboré dans le précédent chapitre en se plaçant dans le cadre de données fonctionnelles appartenant à un espace semi-normé. On établit des bornes de l'EQM de l'estimateur de l'opérateur de régression. Cette EQM peut être vue comme une fonction de la fonction de petite boule de probabilité. Dans le dernier chapitre, on s'intéresse à l'estimation de la fonction auxiliaire associée à la fonction de petite boule de probabilité. D'abord, on propose un estimateur de cette fonction auxiliare. Ensuite, on établit la convergence en moyenne quadratique et la normalité asymptotique de cet estimateur. Enfin, par des simulations, on étudie le comportement de de cet estimateur au voisinage de zéro. / This thesis is divided in four sections with an additionnal presentation. In the first section, We expose the essential mathematics skills for the comprehension of the next sections. In the second section, we adress the problem of local non parametric with functional inputs. First, we propose an estimator of the unknown regression function. The construction of this estimator is related to the resolution of a linear inverse problem. Using a classical method of decomposition, we establish a bound for the mean square error (MSE). This bound depends on the small ball probability of the regressor which is assumed to belong to the class of Gamma varying functions. In the third section, we take again the work done in the preceding section by being situated in the frame of data belonging to a semi-normed space with infinite dimension. We establish bound for the MSE of the regression operator. This MSE can be seen as a function of the small ball probability function. In the last section, we interest to the estimation of the auxiliary function. Then, we establish the convergence in mean square and the asymptotic normality of the estimator. At last, by simulations, we study the bahavour of this estimator in a neighborhood of zero.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Cette thèse s’intéresse au problème classique de tournées de véhicules avec contraintes de capacité (CVRP pour Capacitated Vehicle Routing Problem) ainsi qu’une variante beaucoup plus complexe, soit le problème de tournées de véhicules dépendant du temps avec fenêtres de temps et points de transfert défini sur un réseau routier (TDVRPTWTP-RN pour Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network). Dans le premier article, le TDVRPTWTP-RN est résolu en adaptant une métaheuristique qui représente l’état de l’art pour le CVRP, appelé Slack Induction for String Removals (SISR). Cette métaheuristique fait appel au principe “détruire et reconstruire” en retirant des séquences de clients consécutifs dans les routes de la solution courante et en réinsérant ensuite ces clients de façon à créer une nouvelle solution. Le problème est défini sur un réseau routier où différents chemins alternatifs peuvent être utilisés pour se déplacer d’un client à l’autre. De plus, le temps de parcours sur chacun des arcs du réseau n’est pas fixe, mais dépend du moment où le véhicule quitte le sommet origine. S’inspirant de problèmes rencontrés en logistique urbaine, nous considérons également deux types de véhicules, de petite et grande capacité, où les grands véhicules sont interdits de passage au centre-ville. Ainsi, les clients du centre-ville ne peuvent être servis que suite au transfert de leur demande d’un grand à un petit véhicule à un point de transfert. Comme un point de transfert n’a pas de capacité, une problématique de synchronisation apparaît quand un grand véhicule doit y rencontrer un ou plusieurs petits véhicules pour leur transférer une partie de son contenu. Contrairement aux problèmes stricts de tournées de véhicules à deux échelons, les grands véhicules peuvent aussi servir des clients localisés à l’extérieur du centre-ville. Comme le problème abordé est beaucoup plus complexe que le CVRP, des modifications importantes ont dû être apportées à la métaheuristique SISR originale. Pour évaluer la performance de notre algorithme, un ensemble d’instances tests a été généré à partir d’instances existantes pour le TDVRPTW-RN. Les réseaux omt été divisés en trois régions : centre-ville, frontière et extérieur. Le centre-ville et l’extérieur sont respectivemnt les royaumes des petits et grands véhicules, tandis que la frontière (où l’on retrouve les points de transfert) peut être visité par les deux types de véhicules. Les résultats numériques montrent que la métaheuristique proposée exploite les opportunités d’optimiser une solution en déplaçant autant que possible les clients neutres, soit ceux qui peuvent être servis indifféremment par un petit ou un grand véhicule, des routes des petits véhicules vers les routes des grands véhicules, réduisant ainsi les coûteuses visites aux points de transfert. Les deuxième et troisième article s’intéressent à des concepts plus fondamentaux et font appel au problème plus simple du CVRP pour les évaluer. Dans le second article, un étude expérimentale est conçue afin d’examiner l’impact de données (distances) imprécises sur la performance de différents types d’heuristiques, ainsi qu’une méthode exacte, pour le CVRP. À cette fin, différents niveaux d’imprécision ont été introduits dans des instances tests classiques pour le CVRP avec 100 à 1 000 clients. Nous avons observé que les meilleures métaheuristiques demeurent les meilleures, même en présence de hauts niveaux d’imprécision, et qu’elles ne sont pas affectées autant par les imprécisions qu’une heuristique simple. Des expériences avec des instances réelles ont mené aux mêmes conclusions. Le troisième article s’intéresse à l’intégration de l’apprentissage automatique dans la métaheuristique SISR qui représente l’état de l’art pour le CVRP. Dans ce travail, le principe “détruire et reconstruire” au coeur de SISR est hybridé avec une méthode d’apprentissage par renforcement qui s’inspire des systèmes de colonies de fourmis. L’ap- prentissage automatique a pour but d’identifier les arêtes les plus intéressantes, soit celles qui se retrouvent le plus fréquemment dans les solutions de grande qualité précédemment rencontrées au cours de la recherche. L’inclusion de telles arêtes est alors favorisé lors de la réinsertion des clients ayant été retirés de la solution par le mécanisme de destruction. Les instances utilisées pour tester notre approche hybride sont les mêmes que celles du second article. Nous avons observé que notre algorithme ne peut produire que des solutions lé- gèrement meilleures que la métaheuristique SISR originale, celle-ci étant déjà quasi-optimale. / This thesis is concerned both with the classical Capacitated Vehicle Routing Problem (CVRP) and a much more complex variant called the Time-Dependent Vehicle Routing Problem with Time Windows and Transfer Points on a Road Network (TDVRPTWTP-RN ). In the first paper, the TDVRPTWTP RN is solved by adapting a state-of-the-art metaheuris- tic for the CVRP, called Slack Induction for String Removals (SISR). This metaheuristic is based on the ruin and recreate principle and removes strings of consecutive customers in the routes of the current solution and then reinserts the removed customers to create a new solution. The problem is formulated in a full road network where different alternative paths can be used to go from one customer to the next. Also, the travel time on each arc of the road network is not fixed, but depends on the departure time from the origin node. Motivated from city logistics applications, we also consider two types of vehicles, large and small, with large vehicles being forbidden from the downtown area. Thus, downtown customers can only be served through a transfer of their goods from large to small vehicles at designated transfer points. Since transfer points have no capacity, synchronization issues arise when a large vehicle must meet one or more small vehicles to transfer goods. As opposed to strict two-echelon VRPs, large vehicles can also directly serve customers that are outside of the downtown area. Given that the TDVRPTWTP-RN is much more complex than the CVRP, important modifications to the original SISR metaheuristic were required. To evaluate the performance of our algorithm, we generated a set of test instances by extending existing instances of the TDVRPTW-RN . The road networks are divided into three regions: downtown, boundary and outside. The downtown and outside areas are the realm of small and large vehicles, respectively, while the boundary area that contains the transfer points can be visited by both small and large vehicles. The results show that the proposed metaheuristic exploits optimization opportunities by moving as much as possible neutral customers (which can be served by either small or large vehicles) from the routes of small vehicles to those of large vehicles, thus avoiding costly visits to transfer points. The second and third papers examine more fundamental issues, using the classical CVRP as a testbed. In the second paper, an experimental study is designed to examine the impact of inaccurate data (distances) on the performance of different types of heuristics, as well as one exact method, for the CVRP. For this purpose, different levels of distance inaccuracies were introduced into well-known benchmark instances for the CVRP with 100 to 1,000 customers. We observed that the best state-of-the-art metaheuristics remain the best, even in the presence of high inaccuracy levels, and that they are not as much affected by inaccuracies when compared to a simple heuristic. Some experiments performed on real-world instances led to the same conclusions. The third paper focuses on the integration of learning into the state-of-the-art SISR for the CVRP. In this work, the ruin and recreate mechanism at the core of SISR is enhanced by a reinforcement learning technique inspired from ant colony systems. The learning component is aimed at identifying promising edges, namely those that are often found in previously encountered high-quality solutions. The inclusion of these promising edges is then favored during the reinsertion of removed customers. The benchmark instances of the second paper were also used here to test the new hybrid algorithm. We observed that the latter can produce only slightly better solutions than the original SISR, due to the quasi-optimality of the original solutions.

Ce texte de synthèse a pour but de présenter l'´évolution de mes recherches postèrieures à ma thèse. Ce travail s'articule autour de plusieurs axes de recherche dans le cadre des équations aux dérivées partielles non linéaires et en particulier des lois de conservation.<br />Il s'inscrit dans l'étude des problèmes hyperboliques, des problème mixtes et des équations cinétiques. Les domaines d'application sont la mécanique des fluides ou du solide, la propagation de composants chimiques, l'électromagnétisme, l'optique.<br />Mon activité concerne d'abord la modélisation de phénomènes physiques ou chimiques sous forme d'équations aux dérivées partielles non linéaires telles que les équations de Bloch, Korteweg, Navier-Stokes, Saint-Venant, puis vient l'étude mathématique de ces équations à travers les<br />problèmes d'existence, d'unicité, de régularité avec éventuellement la mise au point de méthodes numériques de résolution.<br /> Ce document est divisé en une introduction générale et trois chapitres qui concernent respectivement les systèmes hyperboliques avec conditions aux limites et la chromatographie, les problèmes d'analyse asymptotique et enfin les méthodes cinétiques.<br />Dans chaque partie, un historique et une présentation des différents résultats mathématiques sont faits et quelques problèmes ouverts sont donnés.

Les approches basées sur les modèles de champ moyen reproduisent avec succès certaines propriétés nucléaires comme les masses et les rayons, dans le cadre des théories de la fonctionnelle de la densité pour l'énergie (EDF). Cependant, plusieurs corrélations complexes sont absentes dans les théories de champ moyen et un certain nombre d'observables liées aux propriétés à une particule et collectives des systèmes nucléoniques ne peuvent pas être prédites avec précision. La nécessité de fournir une description précise des données disponibles ainsi que des prévisions fiables dans les régions exotiques de la carte nucléaire motive l'utilisation de modèles plus sophistiqués, qui vont au-delà du champ moyen. Des corrélations et des corrections d'ordre supérieur (au-delà du premier ordre, qui représente l'approximation de champ moyen) sont introduites dans ces modèles. Un aspect crucial dans ces calculs est le choix de l'interaction efficace qui doit être utilisée quand on va au-delà du premier ordre (les interactions efficaces existantes sont généralement ajustées avec des calculs de champ moyen). Dans la première partie de la thèse, nous traitons l'équation d'état de la matière nucléaire, évaluée jusqu'au deuxième ordre avec la force phénoménologique de Skyrme. Nous analysons la divergence ultraviolette qui est liée à la portée nulle de l'interaction et nous introduisons des interactions régularisées de type Skyrme qui peuvent être utilisées au deuxième ordre. Des procédures de régularisation avec un cutoff et des techniques de régularisation dimensionnelle sont analysées et appliquées. Dans le cas de la régularisation dimensionnelle, des connexions sont naturellement établies entre le cadre EDF et des techniques employées dans les théories de champ effectives. Dans la deuxième partie de la thèse, nous vérifions si les interactions régularisées introduites pour la matière nucléaire peuvent être utilisées également pour les noyaux finis. A titre d'illustration, cette analyse est effectuée dans le modèle de couplage particule vibration, qui représente un exemple de modèle qui va au-delà de l'approximation de champ moyen, où une divergence ultraviolette apparaît si des forces de portée nulle sont utilisées. Ces premières applications suggèrent plusieurs directions à explorer pour fournir à plus long terme des interactions régularisées qui sont bien adaptés pour les calculs au-delà du champ moyen pour les noyaux finis. Les conclusions et des perspectives sont illustrées à la fin du manuscrit. / Mean-field approaches successfully reproduce nuclear bulk properties like masses and radii within the Energy Density Functional (EDF) framework. However, complex correlations are missing in mean-field theories and several observables related to single-particle and collective nuclear properties cannot be predicted accurately. The necessity to provide a precise description of the available data as well as reliable predictions in the exotic regions of the nuclear chart motivates the use of more sophisticated beyond-mean-field models. Correlations and higher-order corrections (beyond the leading mean-field order) are introduced. A crucial aspect in these calculations is the choice of the effective interaction to be used when one goes beyond the leading order (available effective interactions are commonly adjusted at the mean-field level). In the first part, we deal with the equation of state of nuclear matter evaluated up to the second order with the phenomenological Skyrme force. We analyze the ultraviolet divergence that is related to the zero range of the interaction and we introduce Skyrme-type regularized interactions that can be used at second order for matter. Cutoff regularization and dimensional regularization techniques are explored and applied. In the latter case, connections are naturally established between the EDF framework and some techniques employed in Effective Field Theories. In the second part, we check whether the regularized interactions introduced for nuclear matter can be employed also for finite nuclei. As an illustration, this analysis is performed within the particle-vibration model that represents an example of beyond mean-field models where an ultraviolet divergence appears if zero-range forces are used. These first applications suggest several directions to be explored to finally provide regularized interactions that are specially tailored for beyond-mean-field calculations for finite nuclei. Conclusions and perspectives are finally illustrated.