Kantorovich Problem

From Optimal Transport Wiki
Jump to navigation Jump to search

The Kantorovich problem [1] is one of the two essential minimization problems in optimal transport (the other being the Monge problem). It is named after Russian mathematician and Nobel Laureate Leonid Kantorovich.

Kantorovich Problem. The Kantorovich Problem (like the Monge Problem) can be visualized as distributing piles of sand into holes (of equal volume) in an optimal fashion. [2]


In contrast to the Monge problem, the Kantorovich problem involves working with a non-empty minimization set, a convex constraint set, and a convex effort functional. The Kantrovich problem admits a dual because it is a linear minimization problem with convex constraints.

Shipping problem

The intuition behind the Kantorovich problem can be given by an explanation of optimizing shipments. Suppose there is a merchant who is attempting to ship items from one place to another. The merchant can hire trucks at some cost for each unit of merchandise which is shipped from point to point . Now the shipper is approached by a mathematician, who claims that prices can be set such that they align with the shipper's financial interests [3]. This would be achieved by setting the price and such that the sum of and is always less than the cost . This may even involve setting negative prices in certain cases. However, it can be shown that the shipper will spend almost as much as they would have if instead they opted for the original pricing method [4].

Kantorovich Optimal Transport Problem

Transport Plans

The Monge problem was about the optimal way to rearrange mass [5]. Note that in the Monge formulation of the optimal transport problem, the mass cannot be split and thus it is mapped . When considering discrete cases, this results in problems when trying to establish maps T such that . Kantorovich made the observation that the mass in question could be split, which makes the problem much easier to model [6]. Allowing the mass to be split results in a relaxation of the problem (e.g. half of the mass from can go to and half can go to , and so on). To model this consider , which denotes the mass transported from x to y. This allows the mass to be moved to multiple places. Also consider and : where the total mass taken from measurable set must be equal to and the total mass taken from measurable set must equal .

The constraints of the problem can be written in the following manner:

for all measurable sets . As such, we can interpret as representing the amount of mass from that is directed to

If we have a measure that satisfies these constraints, then the set of such is referred to as -- the set of transport plans between and . Notice again that now we are dealing with transport plans instead of the transport maps that are used in the Monge formulation of the problem [7].

Problem Statement

Given and , solve

over all such

Assuming there is a transport map for the Monge problem, we define . Using this we can see that:

We can see that

thus .

Kantorovich Duality

Since the Kantorovich problem is a linear minimization problem with convex constraints it admits a dual problem. The astute reader may notice that this is a linear programming problem -- Kantorovich is also considered to be the founder of linear programming.

Calculus of Variations Approach

Under the right setting, one can show the Kantovorich problem indeed has a minimizer using the direct method of the calculus of variations. More specifically, if one turns to the narrow topology, then it turns out that we get compactness of the constraint set. Moreover, such a topology ensures us that our objective function is lower semi-continuous.

Knott-Smith Optimality Criterion

One useful result we have that allows us to connect both the Monge and Kantorovich problems is the so-called the Knott-Smith Optimality Criterion (see below).


Suppose is compact and . Let . Then,

(i) There exists proper, lower semi-continuous, and convex such that

    (b) For any optimal transport plan , we have that  -almost-everywhere .

(ii) Conversely, if and is proper, lower semi-continuous, and convex for which -almost-everywhere , then

    (a)  is optimal


  1. Villani, Cedric. Topics In Optimal Transportation. American Mathematical Soc., 2003.
  2. Mertens, Stephan. A New Approach to the Matching Problem. Physics, 7, 77. 21 July 2014.
  3. Carlier, Guillame. Optimal Transportation and Economic Applications. IMA. New Mathematical Models in Economics and Finance. 2010
  4. Paris, Quininio. An Economic Interpretations ofLinear Programming. Springer. 29 April 2016
  5. Craig, Katy. The Monge Problem. Math 260L. Univ. of Ca. at Santa Barbara. Spring 2020
  6. Craig, Katy. The Kantorovich Problem. Math 260L. Univ. of Ca. at Santa Barbara. Spring 2020
  7. Craig, Katy. The Kantorovich Problem. Math 260L. Univ. of Ca. at Santa Barbara. Spring 2020