Finite volume approximation of optimal transport and Wasserstein gradient flows
Approximation volumes finis du transport optimal et de flots de gradient Wasserstein
Résumé
This thesis is devoted to the design of locally conservative and structure preserving schemes for Wasserstein gradient flows, i.e. steepest descent curves in the Wasserstein space. The time discretization is based on variational approaches that mimic at the discrete in time level the behavior of steepest descent curves. These discretizations involve the computation of the Wasserstein distance, an instance of optimal transport problem. The space discretization is based on Two-Point Flux Approximation (TPFA) finite volumes, a well-known methodology particularly suited for the discretization of partial differential equations that present a conservative structure. In order to preserve the variational structure at the discrete level, we follow a first discretize then optimize approach. We start by presenting TPFA discretizations for the Wasserstein distance based on the Benamou-Brenier dynamical formulation. We expose some stability issues related to these discetizations, propose a possible solution to overcome them and derive quantitative estimate on the convergence of the discrete model. To solve the discrete optimization problem, we introduce an interior point strategy. Then, we propose first and second order accurate schemes for Wasserstein gradient flows. At this level, to reduce the computational complexity, we use an implicit linearization of the Wasserstein distance. By taking adavantage of the monotonicity of the upwind reconstruction, we propose a first order scheme which can be efficiently solved with a Newton method and show its convergence towards distributional solutions of the Fokker-Planck equation. In order to higher the accuracy in space, we use a centered reconstruction, which requires a different optimization technique. We use again the interior point strategy for this purpose. Finally, we propose a modified variational BDF2 time discretization and prove its convergence towards Wasserstein gradient flows. Thanks to these new discretizations, we design a second order accurate scheme in both time and space. All our approaches are validated with several numerical results.
Cette thèse a pour objet la construction de schémas numériques localement conservatif et préservant la structure pour des flots de gradient Wasserstein, c’est à dire des courbes de descente maximale dans l’espace de Wasserstein. Les discrétisations en temps reposent sur des formulations variationnelles imitant au niveau discret ce comportement de courbes de descente maximale. Ces discrétisation font intervenir le calcul de la distance de Wasserstein, un exemple de problèmes de transport optimal. Les discrétisations en espaces sont basées sur des approximations volumes finis avec reconstructions à deux points des flux, également appelés schémas TPFA. Ces méthodes sont bien connues et particulièrement adaptées pour discrétiser des équations conservatives. Afin de conserver les structures variationnelles au niveau discret, notre approche est de d’abord discrétiser puis optimiser. Dans une première partie nous présentons des discrétisations TPFA pour la distance de Wasserstein, basées sur la formulation dynamique de Benamou-Brenier du transport optimal. Nous montrons des problèmes de stabilité liés à ces discrétisations et proposons une méthode permettant de les surmonter. Nous dérivons des estimations quantitatives de convergence pour ce model discret. Afin de résoudre le problème d'optimisation discret, nous introduisons une stratégie de point intérieur. Ensuite nous proposons des schémas d’ordre un puis deux pour des flots de gradients Wasserstein. Afin de réduire la complexité numérique des problèmes étudiés nous utilisons une linéarisation implicite de la distance de Wasserstein. En exploitant la monotonie de la reconstruction upwind, nous proposons un schéma d'ordre un que l'on peut résoudre efficacement avec une méthode de Newton et nous montrons sa convergence vers des solutions faibles de l'équation de Fokker-Planck. Pour augmenter l’ordre de convergence en espace, nous utilisons une reconstruction centrée qui nécessite une technique d’optimisation différente. Nous utilisons à nouveau la stratégie du point intérieur pour cela. Finalement, pour monter en ordre en temps, nous proposons une version modifiée de la discrétisation variationnelle BDF2 pour laquelle nous prouvons la convergence vers des flots de gradient Wasserstein. À l'aide de ces nouvelles discrétisations, nous construisons un schéma d'ordre deux en espace et en temps. Tous les schémas proposés sont accompagnés de nombreux résultats numériques.
Origine : Version validée par le jury (STAR)