Today we are going to begin a 6 part series on Optimal Transport. My Honours thesis was based on Optimal Transport and I am fortunate enough to be taking Alessio Figalli’s course on Optimal Transport this year at the ETH. The focus of this blog is to run through in detail the mathematics behind solving the Optimal Transport problem. This post will introduce the Optimal Transport problem and then in the latter posts we will delve deeply into the mathematics behind it’s solution.
1. The Monge Problem
In 1781, Monge was interested in finding the most economic way of moving a pile of soil to a mound. Given points of masses , at locations in that needed to be moved to locations , Monge was interested in finding a bijective map that minimized the weighted distance cost
This minimizing map is known as the optimal transport map. In his memoir, he used geometric arguments to deduce that if an optimal map does exist then it must be determined by a potential . The precise contribution given by Monge was that if the optimal map exists, then it must satisfy
A continuous, general version of the Monge problem can be restated as follows. Let and be measure spaces with probability measures and respectively – these represent the pile of soil we wish to move and the mound we wish to create. We define the cost function as a measurable function . Note that in Monge’s original consideration, this was simply the weighted distance in (1). A transport map is a measurable map such that is the push forward of by . This means that for any measurable set , we should have that
over all measurable maps that satisfy . The solution to the Monge Problem (4) is called the optimal transport map and the cost associated with it is known as the optimal transportation cost. We will denote the optimal transportation cost between probability measures and by ; i.e.
2. The Kantorovich Problem
In 1942, Kantorovich introduced the following relaxed version of the Monge optimisation problem. We again consider two measure spaces and with probability measures and respectively. We define an admissible transport plan as a joint probability measure on that has marginals and . This means that for all measurable sets and we have
for all . He showed that a solution to his problem exists and that it is indeed determined by a potential, as was argued by Monge. In 1948, Kantorovich related his problem to the Monge optimization problem and showed that his results from could be applied. In fact, the Kantorovich problem is just a relaxed version of the Monge problem. The Monge problem is more stringent in that it does not allow a piece of mass at a point to be split up and sent to multiple different locations in . We can write the transport plans for the Kantorovich problem in terms of the transport maps of the Monge problem as
That brings us to the end of this introduction, stay tuned for all the details in the next few weeks!