MAGIC118: Optimal Transport- theory and applications

Optimal transport is an area of mathematics that has seen a renewed interest in recent years through applications in machine learning and the development of novel numerical methods as well as through breakthroughs in analytical understanding. The first half of this course will introduce the classical theory of optimal transport. In the second half, we will explore recent numerical and analytical approaches.

The first half of the course will provide a theoretical basis on optimal transportation. Particular focus will be given to showcasing connections to other areas of mathematics. The course will begin by exploring the fundamental idea of couplings, a particular example of which is optimal transport. After covering some of the basic theory of optimal transport (existence, dual formulation), we will see how a number of problems in machine learning, biology and engineering can be formulated as a dynamical optimisation problem. A fundamental example of these dynamical optimisation problems is the Benamou-Brenier formulation of optimal transport. This formulation lends itself to a geometric interpretation of optimal transport. Hence the last part of the first half of the course will focus on giving an introduction to the geometry of Wasserstein spaces. This approach is crucial for understanding gradient flow techniques as well as very useful in deriving (variants and sharp versions of) functional inequalities such as the Sobolev inequality. The second part of the course will address the computational aspects, their theoretical analysis as well as applications. We will review the connections of the first part with the Jacobian PDE, the Monge—Ampère PDE and more generally Hamilton—Jacobi—Bellman PDEs. We will look at ad hoc numerical methods such as Oliker—Prussner’s algorithm for the Monge—Ampère solutions and the Benamou—Brenier method that uses ideas from computational fluid dynamics. We then move onto a review of more general methods such as the Finite difference methods. We will focus then on Galerkin methods for Monge—Ampère type problems. Time allowing we will look at connections with discrete methods arising in computer science including the Sinkhorn algorithm, the Bertsekas auction algorithms, and the Howard policy iteration algorithm.