Introduction to Monge-Kantorovich Problem
Qinglan Xia
University of California at Davis
March 11, 2008

•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Monge’s Transport Problem
How do you best move given pilesof sand to fill up given holes of thesame total volume?
Mathematical Formulation:
Pile of Sand: a positive Radon measure µ+ on a convex subset X ⊂ Rm.
Hole: another positive Radon measure µ− on X.
Same Volume: 0 < µ+ (X) = µ− (X) < +∞. Usually, we normalize themass to 1. So, both µ+ and µ− are probability measures.
Move: a Borel, one-to-one map ψ : X → X
Fill: ψ#µ+ = µ− (i.e. µ−(A) = ψ#µ+(A) = µ+(ψ −1(A)).).
Best: minimum total “work”R or transport cost.
Work or cost of ψ: I (ψ) = X |x − ψ (x)| dµ+ (x).
•First •Prev •Next •Last •Go Back •Full Screen •Close •Quit

Monge’s problem (1781): Given two probability measures on X, minimize
the costZI [ψ] :=|x − ψ (x)| dµ+ (x)Xamong all “transport maps” in+A = ψ : X → X Borel, one-to-one, ψ# µ = µ− .

• • • • •FirstPrevNextLastGo Back•

Full Screen•

Close•

Quit

Monge’s problem (1781): Given two probability measures on X, minimize
the cost
ZI [ψ] :=|x − ψ (x)| dµ+ (x)Xamong all “transport maps” in+A = ψ : X → X Borel, one-to-one, ψ# µ = µ− .
Or in more general case, minimize
Zc (x, ψ (x)) dµ+ (x)I [ψ] :=
X

for some given cost function c : X × X → [0, +∞).
Some important cases:• linear cost: c(x, y) = |x − y|;• quadratic cost: c(x, y) = |x − y|2;
• c(x, y) = |x − y|p, for 0 < p < ∞;• c(x, y) = h(|x − y|) for some convex function h.
• • • • •FirstPrevNextLastGo Back•

Full Screen•

Close•

QuitDiscrete Cases:
Bothµ+ =Xaiδxi

and µ− =iX

bj δyjjare atomic measures of equal total mass. We assume {xi, yj } are distinct.
Example:151+µ = δx1 + δx2 + δx334
12151−µ = δy1 + δy2 + δy3
3
4
12
Only one admissible transport map here. Each xi is mapped to yi.

• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

Quit

So, for nontrivial case,we may assume ai = bj = n1 . That is,µ+ =nX
1nδxi and µ− =

i=1n
X
1n

δyj .

j=1

Each transport map is just a permutation σ of {1, · · · , n}. In this case,Monge’s problem becomes minimizing
1Xc(xi, yσ(i))
niamong all permutations σ ∈ Sn. It corresponds to finding an optimal matching between the source points xi and the target points yj .

• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

QuitContinuous Cases:

Assume both µ+ and µ− are absolutely continuous with respect to Lebesgue
measure:µ+ = f (x)dx and µ− = g(x)dx
for some integrable density functions f and g on X.
In this case, an one-to-one smooth map ϕ : Rn → Rn satisfies the constraint
ϕ#µ+ = µ− if and only if
f (x) = g(ϕ(x))|det(Dϕ(x))|.
We’ll see later (or this afternoon) that if f and g have finite second moments,
there exists an optimal transport map ϕ(x) = ∇ψ(x) for some convex function ψ(x) with respect to the quadratic cost c(x, y) = |x − y|2. Thus, ψ(x)solves a particular form of Monge-Ampe’re equation
det(D2ψ(x)) =f (x).
g(∇ψ(x))• • • • •FirstPrev

Next

Last

Go Back•

Full Screen•

Close•

Quit

Difficulties in solving Monge’s problem• Highly nonlinear structure ofZ
I [ψ] =c (x, ψ (x)) dµ+ (x)XLet c(x, y) = |x − y|.
• Example X = [−1, 1], µ+ = δ0, µ− = 21 δ−1 + 21 δ1. No transport map!
So, no splitting of mass may cause non-existence of transport maps.

• • • • •FirstPrevNextLastGo Back•

Full Screen•

Close•

QuitOptimality test for c(x, y) = |x − y|Suppose ϕ is a transport map from µ+ to µ−. How to know if ϕ is optimal?
Let u : X → R be a Lipschitz function with Lip(u) ≤ 1. (We denoteu ∈ Lip1(X)). Then,ZZ
Zu(x)d(µ− − µ+) =[u(ϕ(x)) − u(x)]dµ+ ≤|ϕ(x) − x|dµ+.
XXX

Thus, if the equality is achieved for some u ∈ Lip1, then ϕ must be an
optimal transport map.

• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

Quit• Example (Book Shifting)
X = R, µ+ = χ[0,n]dx, µ− = χ[1,n+1]dx.
Both ϕ(x) = x + 1 andx + n on [0, 1)
are optimal transport maps.
φ(x) =x on [1, n]
In fact, if we take u(x) = x, then u ∈ Lip1 andZ
Z n+1
Z nu(x)d(µ− − µ+) =xdx −xdx = n.
X10On the other hand,ZZ|ϕ(x) − x|dµ+ =|ψ(x) − x|dµ+ = n.
XXThis example says minimizers are not necessarily unique.

• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

Quit• Example

X = R2, µ+ = δ(−1,0) + δ(1,0)

and µ− be any mass 2 measure supported in the imaginary y-axis.

• • • • •First

Prev

Next

Last

Go Back•

Full Screen•

Close•

Quit• Example

X = R2, µ+ = δ(−1,0) + δ(1,0)

and µ− be any mass 2 measure supported in the imaginary y-axis.
In this case, any admissible transport map is optimal.

• • • • •First

Prev

Next

LastGo Back•

Full Screen

•

Close

•

Quit

One more trouble in Monge’s problem: A limit of minimizing sequence ofmaps ψi may fail to be a map.

• • • • •FirstPrev

Next

Last

Go Back•

Full Screen

•

Close

•

Quit

One more trouble in Monge’s problem: A limit of minimizing sequence ofmaps ψi may fail to be a map.
Well, Monge’s problem is not easy to deal with. What shall we do ??????!!!

• • • • •First

Prev

Next

Last

Go Back•Full Screen

•

Close

•

Quit

One more trouble in Monge’s problem: A limit of minimizing sequence ofmaps ψi may fail to be a map.
Well, Monge’s problem is not easy to deal with. What shall we do ??????!!!
“Relax!” said Kantorovich, more than 150 years later.

• • • • •FirstPrev

Next

LastGo Back•

Full Screen

•

Close

•

Quit

One more trouble in Monge’s problem: A limit of minimizing sequence ofmaps ψi may fail to be a map.
Well, Monge’s problem is not easy to deal with. What shall we do ??????!!!
“Relax!” said Kantorovich, more than 150 years later.
Kantorovich’s relaxation:“Graphs” of maps can be viewed as positive measures in the product space. Limits of maps may fail to be maps, but limits ofmeasures will still be measures.

• • • • •FirstPrev

Next

Last

Go Back•

Full Screen•

Close•

Quit

One more trouble in Monge’s problem: A limit of minimizing sequence ofmaps ψi may fail to be a map.
Well, Monge’s problem is not easy to deal with. What shall we do ??????!!!
“Relax!” said Kantorovich, more than 150 years later.
Kantorovich’s relaxation:“Graphs” of maps can be viewed as positive measures in the product space. Limits of maps may fail to be maps, but limits ofmeasures will still be measures.
Idea: associate with each transport map ψ the measureγψ = (Id × ψ)#µ+in the product space X × X. Let πi be the projection map from X × X
to its i-th coordinates. Then π1#(γψ ) = µ+ and π2#(γψ ) = ψ#µ+ = µ−.
Moreover,ZZc(x, y)dγψ =c(x, ψ(x))dµ+.
X×XX• • • • •FirstPrev

Next

LastGo Back•

Full Screen•Close•QuitKantorovich (1940’s)
Transform it into a linear problem on a convex set.
Transport Plan

Transport mapµ−Relaxationµ−µ+Minimizeµ+Z
J (γ) :=c (x, y) dγ (x, y)
X×X

in the class of transport plansΠ(µ+, µ−) = {γ ∈ P (X × X) |π1#γ = µ+, π2#γ = µ−}.
Existence: from a simple compactness argument of probability measures (forsimplicity, assume X is compact here.)• • • • •FirstPrev

Next

Last

Go Back•

Full Screen•Close•

Quit

The discrete case.
Letnni=1

j=11X
1X−+δxi and µ =δyj .
µ =nnThen, any transport plan from µ+ to µ− can be represented as a bistochasticn × n matrix π = (πij ). Here by bistochasticity we mean that all the πij arenonnegative and thatXX∀j,πij = 1; and ∀i,πij = 1.
ij• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

Quit

So, in this case, the Kantorovich problem reduces to minimize
1Xπij c(xi, yj )ni,jamong all bistochastic n × n matrices π.
This is a linear minimizing problem on a bounded convex set. By Choquet’stheorem and Birkhoff’s theorem, its solutions are given by permutation matrices π, (i.e. πij = δj,σ(i) for some permutation σ.) Thus, in this case,
optimal transport plans in Kantorovich’s problem coincide with solutions ofMonge’s problem
1X
inf{c(xi, yσ(i)); σ ∈ Sn}.
ni• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

QuitRelations between Monge and KantorovichSince every transport map determines a transport plan of the same cost,ZZ
minc (x, y) dγ (x, y) ≤inf|x − ψ (x)| dµ+ (x) .
γ∈Π(µ+,µ−) X×X

ψ#µ+=µ− X

In general, when will solutions to the Kantorovich and Monge problems coincide? Will an optimal transport plan come from an optimal transport map?
Let X = Rn, c(x, y) = |x − y|p, 0 < p < +∞, and µ+, µ− are compactly
supported. Then,• • • • •FirstPrevNextLastGo Back•

Full Screen•

Close•Quit• If p > 1, the strictly convexity of c(x, y) = |x − y|p guarantees that, ifµ+, µ− are absolutely continuous with respect to Lebesgue measure, thenthere is a unique solution to the Kantorovich problem, which turns out tobe also the solution to the Monge problem. The same result holds true
when µ+ is nonatomic (i.e. contains no atomics: µ+({x}) = 0 for allx ∈ X.)• In the case of a quadratic case, p = 2, these optimal maps are the (restrictions of) gradients of convex functions Rn.
• Sometimes, optimal transport plans may have to split mass and solution tothe Monge problem may fail to exist.
• If p = 1, µ+, µ− are absolutely continuous with respect to Lebesgue measure, then there are solutions of the Monge problem which are also solutions of the Kantorovich problem. However,uniqueness may fail here.
• If 0 < p < 1, there is in general no solution of the Monge problem, except
if µ+ and µ− are concentrated on disjoint sets.
• • • • •FirstPrev

NextLast

Go Back•

Full Screen•

Close•QuitOne dimensional case

Let X = [a, b] be a closed interval in R. Let c(x, y) = |x−y|p for some p ≥ 1.
If µ+ is nonatomic (i.e. µ+({x}) = 0, for all x), then there exists a unique(modulo countable sets) nondecreasing function ψ : spt(µ+) → X such that
ψ#µ+ = µ−.
This function ψ is given byψ(s) := sup{t ∈ [a, b] : µ−([a, t]) ≤ µ+([a, s])}.
The function ψ is an optimal transport map. When p > 1, it is the uniqueoptimal transport.
This is a sharp result in the one-dimensional case. µ+ has atoms may cause
non-existence of maps. Dropping monotonicity may cause non-uniqueness.
• • • • ••• •FirstPrev

NextLast

Go Back

Full Screen

CloseQuitFinite moments (in case X is unbounded)
For any p > 0, let Pp(X) be the set of all probability measures with finite
moments of order p. i.e. those measures µ such that for some (and thus any)x0 ∈ X,Z|x − x0|pdµ(x) < +∞.
X

Of course, if X is bounded, then Pp(X) coincides with the set P (X) of allprobability measures on X.
We now assume both µ+ and µ− are in Pp(X). This condition ensures thatthe cost of any transport plan γ ∈ Π(µ+, µ−) is always finite. Indeed,ZZ|x − y|pdγ(x, y) ≤2p(|x|p + |y|p)dγ(x, y) < +∞.
X×X
X×XSince Π(µ+, µ−) is compact with respect to weak * convergence of prob-ability measures, the Kantorovich minimization problem inf{J(γ) : γ ∈Π(µ+, µ−} admits a minimizer.
• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

QuitWassenstein distances on P (X)Definition. Given p ∈ (0, +∞) (usually [1, +∞)), for any two probability
measures µ+, µ− ∈ Pp (X), defineZ|x − y|p dγ (x, y)]min(1,1/p).
Wp µ+, µ− := [ minγ∈Π(µ+,µ−) X×X

distance between measures= minimal cost to suitable powers
Proposition. Wp is a distance on Pp (X) and metrizes the weak * topologyof Pp (X).

• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

QuitKantorovich Duality
Kantorovich problem is a linear minimization problem with convex constraints, so it also admits a dual formulation:
Zinfc(x, y)dγ(x, y)+−γ∈Π(µ ,µ ) X×XZ
Z= sup[ ϕ(x)dµ+ +ψdµ−].
ΦcXXHere,Φc = {(ϕ, ψ) ∈ L1(dµ+) × L1(dµ−) with ϕ(x) + ψ(y) ≤ c(x, y)}.
How to understand it? Here, we quoted a paragraph from Villani’s book:• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

Quit

“The shipper’s problem. Here is an informal way of interpreting Kantorovich duality principle, which we learnt from Caffarelli. Suppose for instance that you are an industrial willing to transfer a huge amount of coalfrom your mines to your factories. You can hire trucks to do this transportation problem, but you have to pay them c(x; y) for each ton of coal which istransported from place x to place y. Both the amount of coal which you can
extract from each mine, and the amount which each factory will receive, arefixed. As you are trying to solve the associated Monge-Kantorovich problem in order to minimize the price you have to pay, another mathematician
comes to you and tells you “My friend, let me handle this for you: I will shipall your coal with my own trucks and you won’t have to care of what goes
where. I will just set a price ϕ(x) for loading one ton of coal at place x, and aprice ψ(y) for unloading it at destination y. I will set the prices in such a waythat your financial interest will be to let me handle all your transportation !
Indeed, you can check very easily that for all x and all y, the sum ϕ(x) + ψ(y)will always be less that the cost c(x; y) (in order to achieve this goal, I am• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

Quiteven ready to give financial compensations for some places, in the form ofnegative prices !)”. Of course you accept the deal. Now, what Kantorovich’s
duality tells you is that if this shipper is clever enough, then he can arrange
the prices in such a way that you will pay him (almost) as much as you would
have been ready to spend by the other method.”• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

QuitIdea of a formal proof:
Want:
Zinfc(x, y)dγ(x, y)+−γ∈Π(µ ,µ ) X×X
ZZ= sup[ ϕ(x)dµ+ +ψdµ−].
ΦcXX

Idea: Rewrite the constrained infimum problem as an inf sup problem, andexchange the two operations by formally applying a minimax principle,i.e.
replacing an “inf sup” by a “sup inf”.
Let M+(X × X) be the space of all nonnegative Borel measures on X × X.
Then,• • • • •FirstPrev

Next

LastGo Back•

Full Screen•

Close•

QuitZinfγ∈Π(µ+,µ−) X×X

c(x, y)dγ(x, y)

Z0,if γ ∈ Π(µ+, µ−)=inf[c(x, y)dγ(x, y) +]+∞elseγ∈M+(X×X) X×X
Z=
inf{c(x, y)dγ(x, y)γ∈M+(X×X) X×X
ZZZ+ sup [ ϕdµ+ + ψdµ− − [ϕ(x) + ψ(y)]dγ(x, y)]}
(ϕ,ψ)
Z
=
inf
sup [c(x, y)dγ(x, y)γ∈M+(X×X) (ϕ,ψ) X×X
ZZZ+ ϕdµ+ + ψdµ− − [ϕ(x) + ψ(y)]dγ(x, y)]• • • • •FirstPrevNextLastGo Back•

Full Screen•Close•Quit

Taking for granted that a minimax principle can be invoked, we rewrite thisasZc(x, y)dγ(x, y)= supinf{(ϕ,ψ) γ∈M+(X×X) X×XZZZ+ ϕdµ+ + ψdµ− − [ϕ(x) + ψ(y)]dγ(x, y)}
ZZZ= sup { ϕdµ+ + ψdµ− +inf[c(x, y) − ϕ(x) − ψ(y)]dγ}γ∈M+(X×X)(ϕ,ψ)
Z
Z0,if (ϕ, ψ) ∈ Φc+−= sup [ ϕdµ + ψdµ +]
−∞
else
(ϕ,ψ)
ZZ
= sup[ ϕ(x)dµ+ +ψdµ−].
ΦcXX• • • • •FirstPrev

NextLastGo Back•

Full Screen•

Close•

QuitApplications: Monge-Kantorovich problem has many applications in Economic (Nobel Prize in 1975); Fluid Mechanics; PDE; Optimization; meteorology and oceanography; surface reconstruction; · · · .
Many experts will attend this workshop!
References:• Villani C., Topics in Optimal Transportation; Graduate Studies in mathematics, Volume 58.
• Ambrosio L., Lecture notes on optimal transport problems.
and hundreds of references listed in them.

• • • • •FirstPrev

NextLast

Go Back•

Full Screen•

Close•

Quit