We propose multigrid methods for solving Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The methods are based on the full approximation scheme. We propose a damped-relaxation method as smoother for multigrid. In contrast with policy iteration, the relaxation scheme is convergent for both HJB and HJBI equations. We show by local Fourier analysis that the damped-relaxation smoother effectively reduces high frequency error. For problems where the control has jumps, restriction and interpolation methods are devised to capture the jump on the coarse grid as well as during coarse grid correction. We will demonstrate the effectiveness of the proposed multigrid methods for solving HJB and HJBI equations arising from option pricing as well as problems where policy iteration does not converge or converges slowly.

Η μερική διαφορική εξίσωση Hamilton-Jacobi-Bellman παράγει τη λύση στο πρόβλημα του υπολογισμού της βέλτιστης ανάδρασης καταστάσεων σε μη γραμμικά δυναμικά συστήματα. Η προσπάθεια ανάπτυξης εύχρηστων και αξιόπιστων μεθόδων αριθμητικής ή προσεγγιστικής επίλυσης της εξίσωσης Hamilton-Jacobi-Bellman έχει τεράστια σημασία στη ρύθμιση διεργασιών γιατί μπορεί να οδηγήσει άμεσα σε εργαλεία σχεδιασμού μη γραμμικών ρυθμιστών. Ειδικότερα, στη ρύθμιση διεργασιών, η απόδοση ενός ρυθμιστικού συστήματος αξιολογείται βάσει ενός τετραγωνικού δείκτη απόδοσης σε άπειρο χρονικό ορίζοντα, και η βέλτιστη ανάδραση καταστάσεων μπορεί να υπολογισθεί μέσω της λύσης της εξίσωσης Hamilton-Jacobi-Bellman, μη εξαρτώμενης από το χρόνο. Στο πρόβλημα της επίλυσης της παραπάνω εξίσωσης παρουσιάζονται σοβαρές δυσκολίες, κυρίως λόγω υπολογιστικής πολυπλοκότητας. Για το λόγο αυτό, οι μέχρι στιγμής πρακτικές εφαρμογές υπήρξαν περιορισμένες. Στην παρούσα εργασία αναπτύσσεται υπολογιστική μέθοδος, βασισμένη στον αλγόριθμο επαναλήψεων Newton-Kantorovich, η οποία επιτυγχάνει πολυωνυμική προσέγγιση της λύσης της μερικής διαφορικής εξίσωσης Hamilton-Jacobi-Bellman υπό μορφή αναπτύγματος σε δυναμοσειρά Taylor. Με τον τρόπο αυτό επιταχύνονται σημαντικά οι υπολογισμοί για τον προσδιορισμό της βέλτιστης ανάδρασης καταστάσεων. Η μέθοδος εφαρμόζεται αρχικά σε ένα παράδειγμα ισοθερμοκρασιακού αντιδραστήρα συνεχούς λειτουργίας με ανάδευση, ο οποίος παρουσιάζει δυναμική συμπεριφορά μη-ελάχιστης φάσης, με μία είσοδο, μία έξοδο και δύο καταστάσεις. Στη συνέχεια, εφαρμόζεται σε παραδείγματα μη ισοθερμοκρασιακού αντιδραστήρα αντίστοιχης δυναμικής συμπεριφοράς, τριών καταστάσεων, πρωτίστως με μία είσοδο και μία έξοδο και κατόπιν με δύο εισόδους και δύο εξόδους. Με ανάπτυξη και εφαρμογή κώδικα MAPLE για κάθε μία περίπτωση χωριστά, υπολογίζονται προσεγγιστικά οι βέλτιστοι νόμοι ανάδρασης και σχεδιάζονται οι βέλτιστες αποκρίσεις των εισόδων και των εξόδων κάθε ενός από τα παραπάνω συστήματα, ενώ ταυτόχρονα γίνεται και καταγραφή των αντίστοιχων χρόνων εκτέλεσης κάθε κώδικα. Τέλος, στην περίπτωση του ισοθερμοκρασιακού αντιδραστήρα, γίνεται σύγκριση της προτεινόμενης μεθόδου με προϋπάρχουσες, κατά κύριο λόγο σε ζητήματα χρόνων εκτέλεσης, αλλά και σε ζητήματα απόδοσης στη ρύθμιση. / The partial differential equation Hamilton-Jacobi-Bellman produces the solution in the problem of calculation of optimal state feedback in non-linear dynamic systems. The effort of designing functional and reliable, numerical or approximate, methods for solving Hamilton-Jacobi-Bellman equation has enormous importance in process control because it can lead directly to tools of planning non-linear regulators. More specifically, in process control, the attribution of a regulating system is evaluated using a quadratic performance index in infinite time horizon, and the optimal state feedback can be calculated by the solution of the non time depended Hamilton-Jacobi-Bellman equation. The problem of solving the equation above encounters serious difficulties, mainly because of the calculation complexity. For this reason, the practical applications existed until now were very few. In the present work a calculating method is developed, based in the iterative algorithm Newton-Kantorovich, which achieves polynomial approach of the solution of partial differential equation Hamilton-Jacobi-Bellman under the form of Taylor series expansion. Thus the calculations for the determination of optimal state feedback are considerably accelerated. The method is initially applied in an example of continuous stirred tank reactor, with non-minimum phase dynamic behavior, with one input, one output and two state variables. Afterwards, it is applied in examples of not isothermal reactor of the same dynamic behavior, three state variables, firstly with one input and one output variables and then with two input and two output variables. Using the symbolic program MAPLE, a code was developed for each case separately, which calculates approximately the optimal feedback laws and designs the optimal responses of the inputs and outputs of each of the systems above, while the corresponding times of implementation of each code are simultaneously recording. Finally, in the case of isothermal reactor, a comparison is made between the proposed and preexisting methods, mainly in the base of the time of implementations and the regulation performance.

We propose multigrid methods for solving Hamilton-Jacobi-Bellman (HJB) and Hamilton-Jacobi-Bellman-Isaacs (HJBI) equations. The methods are based on the full approximation scheme. We propose a damped-relaxation method as smoother for multigrid. In contrast with policy iteration, the relaxation scheme is convergent for both HJB and HJBI equations. We show by local Fourier analysis that the damped-relaxation smoother effectively reduces high frequency error. For problems where the control has jumps, restriction and interpolation methods are devised to capture the jump on the coarse grid as well as during coarse grid correction. We will demonstrate the effectiveness of the proposed multigrid methods for solving HJB and HJBI equations arising from option pricing as well as problems where policy iteration does not converge or converges slowly.

Cette thèse est consacrée à l'étude de phénomènes de propagation dans des modèles d’EDP venant de la biologie. On étudie des équations cinétiques inspirées par le déplacement de colonies de bactéries ainsi que des équations de réaction-diffusion importantes en écologie afin de reproduire plusieurs phénomènes de dynamique et d'évolution des populations. La première partie étudie des phénomènes de propagation pour des équations cinétiques. Nous étudions l'existence et la stabilité d'ondes progressives pour des modèles ou la dispersion est donnée par un opérateur hyperbolique et non par une diffusion. Cela fait entrer en jeu un ensemble de vitesses admissibles, et selon cet ensemble, divers résultats sont obtenus. Dans le cas d'un ensemble de vitesses borné, nous construisons des fronts qui se propagent à une vitesse déterminée par une relation de dispersion. Dans le cas d'un ensemble de vitesses non borné, on prouve un phénomène de propagation accélérée dont on précise la loi d'échelle. On adapte ensuite à des équations cinétiques une méthode basée sur les équations de Hamilton-Jacobi pour décrire des phénomènes de propagation. On montre alors comment déterminer un Hamiltonien effectif à partir de l'équation cinétique initiale, et prouvons des théorèmes de convergence.La seconde partie concerne l'étude de modèles de populations structurées en espace et en phénotype. Ces modèles sont importants pour comprendre l'interaction entre invasion et évolution. On y construit d'abord des ondes progressives que l'on étudie qualitativement pour montrer l'impact de la variabilité phénotypique sur la vitesse et la distribution des phénotypes à l'avant du front. On met aussi en place le formalisme Hamilton-Jacobi pour l'étude de la propagation dans ces équations de réaction-diffusion non locales.Deux annexes complètent le travail, l'une étant un travail en cours sur la dispersion cinétique en domaine non-borné, l'autre étant plus numérique et illustre l’introduction. / This thesis is devoted to the study of propagation phenomena in PDE models arising from biology. We study kinetic equations coming from the modeling of the movement of colonies of bacteria, but also reaction-diffusion equations which are of great interest in ecology to reproduce several features of dynamics and evolution of populations. The first part studies propagation phenomena for kinetic equations. We study existence and stability of travelling wave solutions for models where the dispersal part is given by an hyperbolic operator rather than by a diffusion. A set of admissible velocities comes into the game and we obtain various types of results depending on this set. In the case of a bounded set of velocities, we construct travelling fronts that propagate according to a speed given by a dispersion relation. When the velocity set is unbounded, we prove an accelerating propagation phenomena, for which we give the spreading rate. Then, we adapt to kinetic equations the Hamilton-Jacobi approach to front propagation. We show how to derive an effective Hamiltonian from the original kinetic equation, and prove some convergence results.The second part is devoted to studying models for populations structured by space and phenotypical trait. These models are important to understand interactions between invasion and evolution. We first construct travelling waves that we study qualitatively to show the influence of the genetical variability on the speed and the distribution of phenotypes at the edge of the front. We also perform the Hamilton-Jacobi approach for these non-local reaction-diffusion equations.Two appendices complete this work, one deals with the study of kinetic dispersal in unbounded domains, the other one being numerical aspects of competition models.

Esta dissertação aborda a teoria dos jogos diferenciais em sua estreita relação com a teoria das equações de Hamilton-Jacobi (HJ). Inicialmente, uma revisão da noção de solução em teoria dos jogos é empreendida. Discutem-se nesta ocasião as idéias de equilíbrio de Nash e alguns de seus refinamentos. Em seguida, tem lugar uma introdução à teoria dos jogos diferenciais, onde noções de solução como a função de valor de Isaacs e de Friedman são discutidas. É nesta altura do trabalho que fica evidente a conexão entre este conceito de solução e a teoria das equações de Hamilton-Jacobi. Por ocasião desta conexão, é explorada a noção de solução clássica e é exposta uma demonstração do fato de que se um jogo diferencial possuir uma função de valor pelo menos continuamente diferenciável, esta será uma solução da equação de Hamilton-Jacobi associada ao jogo. Este resultado faz uso do princípio da programação dinâmica, devido a Bellman, e cuja demonstração está presente no texto. No entanto, quando a função de valor do jogo é apenas contínua, então embora esta não seja uma solução clássica da equação HJ associada a jogo, vemos que ela será uma solução viscosa, ou solução no sentido da viscosidade - e a esta altura são discutidos os elementos e propriedades desta classe de soluções, um teorema de existência e unicidade e alguns exemplos. Por fim, retomamos o estudo dos jogos diferenciais à luz das soluções viscosas da equação de Hamilton-Jacobi e, assim, expomos uma demonstração de existência da função de valor e do princípio da programação dinâmica a partir das noções da viscosidade / This dissertation aims to address the topic of Differential Game Theory in its connection with the Hamilton-Jacobi (HJ) equations framework. Firstly we introduce the idea of solution for a game, through the discussion of Nash equilibria and its refinements. Secondly, the solution concept is then translated to the context of Differential Games and the idea of value function is introduced in its Isaacs\'s as well as Friedman\'s version. As the value function is discussed, its relationship with the Hamilton-Jacobi equations theory becomes self-evident. Due to such relation, we investigate the HJ equation from two distinct points of view. First of all, we discuss a statement according to which if a differential game has a continuously differentiable value function, then such function is a classical solution of the HJ equation associated to the game. This result strongly relies on Bellman\'s Dynamic Programming Principle - and this is the reason why we devote an entire chapter to this theme. Furthermore, HJ is still at our sight from the PDE point of view. Our motivation is simple: under some lack of regularity - a value function which is continuous, but not continuously differentiable - a game may still have a value function represented as a solution of the associated HJ equation. In this case such a solution will be called a solution in the viscosity sense. We then discuss the properties of viscosity solutions as well as provide an existence and uniqueness theorem. Finally we turn our attention back to the theory of games and - through the notion of viscosity - establish the existence and uniqueness of value functions for a differential game within viscosity solution theory.

Dans les installations nucléaires, les explosions, qu’elles soient d’origine interne ou externe, peuvent entrainer la rupture du confinement et le rejet de matières radioactives dans l’environnement. Il est donc fondamental, dans un cadre de sûreté de modéliser ce phénomène. L’objectif de cette thèse est de contribuer à l’élaboration de schémas numériques performants pour résoudre ces modèles complexes. Les travaux présentés s’articule autour de deux axes majeurs : le développement de schémas volumes finis consistants pour les équations d’Euler compressible qui modélise les ondes de choc et celui de schémas performants pour la propagation d’interfaces comme le front de flamme lors d'une déflagration. La discrétisation spatiale est de type mailles décalées pour tous les schémas développés. Les schémas pour les équations d'Euler se basent sur une formulation en énergie interne qui permet de préserver sa positivité ainsi que celle de la masse volumique. Un bilan d'énergie cinétique discret peut être obtenu et permet de retrouver un bilan d'énergie totale par l'ajout d'un terme de correction dans le bilan d'énergie interne. Le schéma ainsi construit est consistant au sens de Lax avec les solutions faibles entropiques des équations continues. On utilise les propriétés des équations de type Hamilton-Jacobi pour construire une classe de schémas volumes finis performants sur une large variété de maillages modélisant la propagation du front de flamme. Ces schémas garantissent un principe du maximum et possèdent des propriétés importantes de monotonie et consistance qui permettent d'obtenir un résultat de convergence. / In nuclear facilities, internal or external explosions can cause confinement breaches and radioactive materials release in the environment. Hence, modeling such phenomena is crucial for safety matters. The purpose of this thesis is to contribute to the creation of efficient numerical schemes to solve these complex models. The work presented here focuses on two major aspects: first, the development of consistent schemes for the Euler equations which model the blast waves, then the buildup of reliable schemes for the front propagation, like the flame front during the deflagration phenomenon. Staggered discretization is used in space for all the schemes. It is based on the internal energy formulation of the Euler system, which insures its positivity and the positivity of the density. A discrete kinetic energy balance is derived from the scheme and a source term is added in the discrete internal energy balance equation to preserve the exact total energy balance. High order, MUSCL-like interpolators are used in the discrete momentum operators. The resulting scheme is consistent (in the sense of Lax) with the weak entropic solutions of the continuous problem. We use the properties of Hamilton-Jacobi equations to build a class of finite volume schemes compatible with a large number of meshes to model the flame front propagation. These schemes satisfy a maximum principle and have important consistency and monotonicity properties. These latters allows to derive a convergence result for the schemes based on Cartesian grids.

Cette thèse se développe sur deux fronts: nous nous concentrons sur les méthodes numériques des problèmes de contrôle optimal, en particulier sur le Principe de la Programmation Dynamique et sur le Model Predictive Control (MPC) et nous présentons des applications de techniques de contrôle en biologie. Dans la première partie, nous considérons l'approximation d'un problème de contrôle optimal avec horizon infini, qui combine une première étape, basée sur MPC permettant d'obtenir rapidement une bonne approximation de la trajectoire optimal, et une seconde étape, dans la quelle l¿équation de Bellman est résolue dans un voisinage de la trajectoire de référence. De cette façon, on peux réduire une grande partie de la taille du domaine dans lequel on résout l¿équation de Bellman et diminuer la complexité du calcul. Le deuxième sujet est le contrôle des méthodes Level Set: on considère un problème de contrôle optimal, dans lequel la dynamique est donnée par la propagation d'un graphe à une dimension, contrôlé par la vitesse normale. Un état finale est fixé, l'objectif étant de le rejoindre en minimisant une fonction coût appropriée. On utilise la programmation dynamique grâce à une réduction d'ordre de l'équation utilisant la Proper Orthogonal Decomposition. La deuxième partie est dédiée à l'application des méthodes de contrôle en biologie. On présente un modèle décrit par une équation aux dérivées partielles qui modélise l'évolution d'une population de cellules tumorales. On analyse les caractéristiques du modèle et on formule et résout numériquement un problème de contrôle optimal concernant ce modèle, où le contrôle représente la quantité du médicament administrée. / This thesis is divided in two parts: in the first part we focus on numerical methods for optimal control problems, in particular on the Dynamic Programming Principle and on Model Predictive Control (MPC), in the second part we present some applications of the control techniques in biology. In the first part of the thesis, we consider the approximation of an optimal control problem with an infinite horizon, which combines a first step based on MPC, to obtain a fast but rough approximation of the optimal trajectory and a second step where we solve the Bellman equation in a neighborhood of the reference trajectory. In this way, we can reduce the size of the domain in which the Bellman equation can be solved and so the computational complexity is reduced as well. The second topic of this thesis is the control of the Level Set methods: we consider an optimal control, in which the dynamics is given by the propagation of a one dimensional graph, which is controlled by the normal velocity. A final state is fixed and the aim is to reach the trajectory chosen as a target minimizing an appropriate cost functional. To apply the Dynamic Programming approach we firstly reduce the size of the system using the Proper Orthogonal Decomposition. The second part of the thesis is devoted to the application of control methods in biology. We present a model described by a partial differential equation that models the evolution of a population of tumor cells. We analyze the mathematical and biological features of the model. Then we formulate an optimal control problem for this model and we solve it numerically.

Cette thèse est consacrée à l’étude de phénomènes de propagation et de concentration dans des modèles d’équations intégro-différentielles venant de la écologie. On étudie certaines équations de réaction-diffusion non locales apparaissant en dynamique de populations, ainsi que des modèles représentant l’évolution Darwinienne avec un mode de reproduction sexué.Dans une première partie, nous étudions la propagation spatiale pour une équation de réaction-diffusion ou la dispersion opère via un noyau de convolution à queue lourde. Nous mesurons de manière précise l’accélération du front de propagation de la solution. Nous proposons également une échelle adaptée pour mesurer les «petites» mutations. Dans les deux cas nous utilisons le formalisme des équations de Hamilton-Jacobi.Dans un second temps nous étudions un modèle de génétique quantitative, avec un mode de reproduction sexuée. Un petit paramètre mesure la déviation entre le trait des descendants est la moyenne des traits des parents. Dans le régime où ce paramètre est petit nous étudions l’existence de solutions stationnaires, puis le problème de Cauchy lié à ce modèle. Les solutions se concentrent autour des optima de sélection, sous la forme de perturbations de distributions Gaussiennes avec petite variance fixée par le paramètre. Notre analyse généralise le cas linéaire de la reproduction asexuée en utilisant des outils d’analyse perturbative. Enfin dans une dernière partie nous fournissons des simulations numériques et des méthodes mathématiques pour étudier la dynamique interne des équilibres dans le régime de petite variance, pour les deux modes de reproduction : asexué et sexué. / This manuscript tackles propagation and concentration phenomena in different integro-differential equations with a background in ecology. We study non local reaction-diffusion equations from population dynamics, and models for Darwinian evolution with a sexual or asexual mode of reproduction, with a preference for the former.In a first part, we study spatial propagation for a reaction diffusion equation where dispersion acts through a fat tailed kernel. We measure accurately the acceleration of the propagation front of the population. We propose as well a scaling well adapted to “small mutations” when we consider the model in the context of adaptative dynamics. This scaling is very natural following the previous spatial investigation. In both cases we look at the long time behavior and we use the Hamilton-Jacobi framework. Then we turn our attention towards a quantitative genetics model, with a sexual mode of reproduction, imposed by the “infinitesimal operator”. In this non-linear setting, a small parameter tunes the deviation between the phenotypic trait of the offspring and the mean of the traits of the parents. In the regime where this parameter is small, we prove existence of stationary solutions, and their local uniqueness. We also provide an example of non-uniqueness in the case where the selection function admits several extrema. We prove that the solution concentrates around the points of minimum of the selection function. The analysis is carried by the small perturbations of special profiles : Gaussian distributions with small variance fixed by the parameter.We then study the stability of the Cauchy problem associated to the previous model. This time we prove that at all times, for a well prepared initial data, the solutions is arbitrary close to a Gaussian distribution with small variance. The proof follows the framework of the previous : we use perturbative analysis tools, but this time an even more precise description of the correctors is needed and we linearize the equation to obtain it. In a final part we show numerical simulations and different mathematical approaches to study inside dynamics of phenotypic lineages in the regime of small variance, with a moving environement.

We propose a discontinuous Galerkin finite element method (DGFEM) for fully nonlinear elliptic Hamilton--Jacobi--Bellman (HJB) partial differential equations (PDE) of second order with Cordes coefficients. Our analysis shows that the method is both consistent and stable, with arbitrarily high-order convergence rates for sufficiently regular solutions. Error bounds for solutions with minimal regularity show that the method is generally convergent under suitable choices of meshes and polynomial degrees. The method allows for a broad range of hp-refinement strategies on unstructured meshes with varying element sizes and orders of approximation, thus permitting up to exponential convergence rates, even for nonsmooth solutions. Numerical experiments on problems with nonsmooth solutions and strongly anisotropic diffusion coefficients demonstrate the significant gains in accuracy and computational efficiency over existing methods. We then extend the DGFEM for elliptic HJB equations to a space-time DGFEM for parabolic HJB equations. The resulting method is consistent and unconditionally stable for varying time-steps, and we obtain error bounds for both rough and regular solutions, which show that the method is arbitrarily high-order with optimal convergence rates with respect to the mesh size, time-step size, and temporal polynomial degree, and possibly suboptimal by an order and a half in the spatial polynomial degree. Exponential convergence rates under combined hp- and τq-refinement are obtained in numerical experiments on problems with strongly anisotropic diffusion coefficients and early-time singularities. Finally, we show that the combination of a semismooth Newton method with nonoverlapping domain decomposition preconditioners leads to efficient solvers for the discrete nonlinear problems. The semismooth Newton method has a superlinear convergence rate, and performs very effectively in computations. We analyse the spectral bounds of nonoverlapping domain decomposition preconditioners for a model problem, where we establish sharp bounds that are explicit in both the mesh sizes and polynomial degrees. We then go beyond the model problem and show computationally that these algorithms lead to efficient and competitive solvers in practical applications to fully nonlinear HJB equations.

No description available.