Introduction to Optimal Transport

We review optimal transport (OT) which can be informally described as “deforming” a source probability distribution into a target probability distribution with minimal cost. OT was formulated more than two centuries ago and became famous for its relevance to economics and logistics especially after the seminal work on linear programming by Kantorovich, Koopmans, and Dantzig. OT has since seen multiple resurgences, first due to the rise of computer vision in the <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1990\mathrm{s}$</tex>, and more recently due to the maturing of large-scale optimization solvers alongside the rise of machine learning and artificial intelligence. This tutorial formally introduces OT to a simulation audience that is steeped in the concepts of operations research (OR). The early parts of the tutorial focus on application contexts. This is followed by the Monge and Kantorovich OT formulations along with key structural results and examples. The tutorial ends with a short section on semidiscrete OT.