Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling (Q2353897): Difference between revisions

The problem of optimal transportation, since its formulation by Gaspard Monge in the 18th century, has attracted the attention of the mathematical community and is still going strong as we speak, with the interest towards it renewed as an account of many fascinating new developments both in the abstract and applied mathematical aspects (such as e.g. the understanding of the intricate metric and geometric structure of the space of probability spaces through its metrization in terms of the Wasserstein distance, its connection with a number of important nonlinear PDEs etc.) as well as due to the surprisingly broad scope of possible applications in areas as diverse as theoretical physics (such as e.g. the celebrated understanding of the Landau damping effect by Cedric Villani, or the study of image processing, economics, medical imaging, machine learning etc. The problem of optimal transporation essentially, given two probability measures \(\mu \in {\mathcal P}(X)\), \(\nu \in {\mathcal P}(Y)\), and a cost function \(c : X \times Y \to [0,\infty]\), is the determination of a mapping \(T : X \to Y\) such that \(T\# \mu = \nu\) (i.e., \(\mu(T^{-1}(A))=\nu(A)\), for every \(A\), and which minimizes the trasport cost \(M(T)=\int c(x,T(x) d\mu(x)\). This nonlinear problem, that is related to the Monge-Ampére equation for the determination of \(T\), has been reformulated by Kantorovich as an infinite dimensional linear dynamic programming problem over the set of transportation plans. This reformulation led to a renewed interest in the field, and a number of interesting results were developed in the field, designating optimal transport as an interesting theoretical tool in understanding and metrizing the space of probability measures, in treating fundamental evolution equations or as a modelling tool for a variety of applications including economics, engineering etc. This book offers an excellent, exciting and enjoyable, tour through the theory of optimal transportation, with a very good choice of topics focusing on its connection with applied mathematics and in particular with the nonlinear partial differential equations, as well as numerical analytic aspects related to the calculation of the Wasserstein distance, and the application of optimal transport in a number of applied optimization and modelling problems ranging from operations research to game theory. It is well written and thorough and provides an excellent introduction to applied mathematicians (and not only) who wish an introduction to those aspects of optimal transport theory which are intimately connected with PDEs, numerical analysis or mathematical modelling. All the results are carefully and clearly proved, memo boxes help as a reminder of fundamental concepts needed, facilitating the reader, and extended discussion sections at the end of every chapter, guide the reader to those issues that were not covered in the book but may be of interest. An extensive list of references provides a full picture of the field up to the publication of the book. Finally, a carefully selected list of exercises, make it ideal either as a textbook for an advanced postgraduate of doctoral level course, or for independent study. Below follows a brief account of the contents of the book. Chapter 1 introduces the problem of optimal transport (OT) and its various primal and dual formulations. In particular, the Kantorovich reformulation of the classical Monge problem is discussed at length, and a detailed introduction is made to useful concepts such as c-concavity, duality and optimality and their connections with OT. After a general discussion the exposition focuses mainly on the case that \(X=Y={\mathbb R}^{d}\), or some subset of it. An extended discussion section connects these concepts and results with issues such as the Monge-Ampere equation, martingale optimal transport, multi-marginal transport, matching problems and also gives a flavour for possible applications. Chapter 2 offers a detailed account of the one dimensional theory in which explicit constructions are possible, and presents connections with the problem of the Knothe transport as well as applications in e.g. histogram equilization etc. Chapter 3 focuses on the \(L^{1}\) theory ( in which the transportation cost is \(c(x,y)=|x-y|\)) and the \(L^{\infty}\) theory (i.e. the case there the \(L^{\infty}\) norm of the displacement \(\| x-y\|_{L^{\infty}(\gamma)}\), where \(\gamma\) is the trasportation plan, is to be minimized), which requires more specialized techniques, providing detailed results on duality, related variational problems, the geometry of transport rays etc. Chapter 4 introduces the reader to the theory of minimal flows, which are intimately connected with optimal transport problems. After an introduction to the fundamental tools from the theory of the continuity equation, the continuous trasportation model of Beckmann and several of its variants are studied, leading to a good understanding of the techniques and problems involved in the theory of minimal flows. Possble applications in traffic equilibria and Wardrop equilibria in discrete and continuous settings are discussed. Chapter 5 introduces the conept of the Wasserstein space and deals with the understanding of curves in this space. The family of Wasserstein metrics \(W_{p}(\mu,\nu)\) are introduced, as the \(p\)-th root of the minimal cost of the Kantorovich formulation of the optimal transportation for the choice of cost \(c(x,y)=|x-y|^{p}\), it properties are carefully derived and the topology induced by this metric on the space of probability measures is thoroughly discussed. Attention is then driven to the study of curves in the Wasserstein space (i.e. the space of probability measures endowed with the Wasserstein metric) and their connections with the continuity equation through the Benamou-Brenier functional are made. Wassersteins space is then identified as a geodesic space and properties of the geodesic curves are studied. The Benamou-Brenier reformulation of the OT problem is derived rigorously in this setting. The discussion that follows intoduces concepts such as the Wasserstein barycenter, the sliced Wasserstein distance etc. Chapter 6 introduces a number of alternative numerical methods for the calculation of the Wasserstein distance and the optimal transport map. Both continuous and discrete methods are presented, the continuous being based essentially on reformulations involving the continuity equation (as for example the Benamou-Brenier algorithm, which after an appropriate duality argument leads to an Uzawa type algorithm involving the solution of a Poisson equation and a projection step) or solutions of the Monge-Ampére equation, while the discrete ones are essentially linear programming based techniques stemming from the Kantorovich formulation, possibly with regularization terms such as for instance entropic regularization needed for better performance. Chapter 7 studies a number of important functionals on Wasserstein space, including the potential functional energy, the interaction energy or the entropy functional. Properties such as semicontiuity, covexity, sub-differentiability or displacement convexity are thoroughly discussed, with a view towards building the necessary tools for the study of optimizatio problems involving such functionals. Chapter 8, to quote directly the author ``presents one of the most spectacular application of optimal transport and Wasserstein distance to PDEs'', and in particular establishes the fact that various important evolution equations (e.g. the Fokker-Planck equation) can be expressed as gradient flows, of functionals on the Wasserstein space, of the type studied in Chapter 7. This important observation leads to a deeper understanding of the dynamics of such evolution equations, opens the possibility for the development of novel numerical schemes for their treatment and helps in the construction of mathematical models including physical and biological systems, mean field games etc.