Domain decomposition for optimal transport and localized optimality conditions
by Ismael Medina Suarez
Date of Examination:2024-12-11
Date of issue:2024-12-19
Advisor:Prof. Dr. Bernhard Schmitzer
Referee:Prof. Dr. Bernhard Schmitzer
Referee:Prof. Dr. Axel Munk
Persistent Address:
http://dx.doi.org/10.53846/goediss-10958
Files in this item
Name:main.pdf
Size:6.05Mb
Format:PDF
Description:Thesis manuscript
The following license files are associated with this item:
Abstract
English
Optimal transport (OT) is a fundamental tool in the study of the space of probability measures. Several algorithmic breakthroughs, such as the Sinkhorn algorithm, have allowed practicioners to solve the OT problem efficiently in many domains of applicability, but large OT problems remain challenging. Domain decomposition is an efficient approach for solving large OT problems by decomposing the global problem into a collection of small problems that can be solved rapidly and in a parallelized manner. This thesis is devoted to an in-depth study of the domain decomposition algorithm for optimal transport. We start by revisiting the original formulation of domain decomposition for unregularized optimal transport and showing convergence for the squared cost under an improved set of assumptions. Next, we define a domain decomposition algorithm for unbalanced, entropic optimal transport, show convergence for serial and parallel variants, and demonstrate numerically its efficiency compared to Sinkhorn-based methods. To better understand the excellent experimental performance of domain decomposition on regular problems, we next perform an asymptotic analysis of the algorithm as the subdomain size tends to zero. We find that the limit dynamics are described by a (weak) continuity equation, whose momentum field can be extracted as the minimizer of the $\Gamma$-limit of the domain decomposition subproblems. One of the main findings of this asymptotic analysis is that some initializations lead to poor performance of domain decomposition in the limit of vanishing subdomain size. Such initializations exhibit what we call a `curl' component, which formally implies some kind of `rotation' with respect to the optimal coupling. To address this issue, we enhance domain decomposition with a global update step that progressively removes the curl component, improving upon the excellent convergence properties reported for the standard version of the algorithm. Our investigation of the relationship between curl and optimal transport led us to study a system of coupled partial differential equations modelling the evolution of a (possibly infinite) collection of immiscible, incompressible fluids under a common, pointwise volume constraint. Besides the clear connections to the topic of multiphasic flows in porous media, such systems can also be interpreted as a relaxation of the Angenent-Haker-Tannenbaum (AHT) scheme for unregularized OT, which tackles the OT problem by iteratively removing the curl of an initial transport map. We prove existence of (weak) solutions to the system of partial differential equations with a JKO argument, show asymptotic convergence of such solutions to the minimizer of the entropic OT problem, and finally delve into the implications this analysis has for the convergence properties of a relaxed version of the AHT scheme. Finally, most of the numerical experiments in this thesis are based on a novel GPU implementation of entropic domain decomposition, which we document in the Appendix.
Keywords: computational optimal transport; GPU computing; AHT scheme; gradient flows; JKO minimizing movement; multiphasic flows; Sinkhorn algorithm; convex optimization; Wasserstein total variation; Gamma convergence; unbalanced optimal transport; domain decomposition
