Optimal Transportation for Generalized Lagrangian

Ji LI Jianlu ZHANG

1 Introduction

Given a pile of soil and an excavation that we want to fill up with the soil.As early as 1781,Monge posed the question to find an optimal way to do this work.This is the primary statement of Monge problem.We can model the pile of soil and the excavation by two probability measures as the density of the mass.Concretely,given a space M,and a continuous function,called the cost function c(x,y):M ×M → R,given two probability measuresμ0andμ1on M, find the mapping t:M → M which transportμ0toμ1and minimize the total costc(x,t(x))dμ0.But unfortunately,the Monge problem is not always well-posed,for instance,considerμ0=δx, μ1=(δy+ δz)(x,y,z ∈ M),the Monge problem has no solution since there is no map t such that= μ1.

It is difficult to study the Monge problem directly.In 1942,Kantorovich raised a generalized problem,later called the Monge-Kantorovich(MK for short)problem,we will state it concretely in Section 4.As proved in[7],MK problem always has a solution.It turned out that through the solution of MK problem,sometimes we can construct the solution of the Monge problem.Recently,several mathematicians studied the connections between Aubry-Mather-Fathi theory,optimal transportation problem and Hamilton-Jacobi equations(see[4–6,10,12,14]).

In[2],they considered a Lagrangian function L(x,v,t):TM×[0,T]→R which satis fies the Tonelli conditions introduced by Mather,and considered the cost by

where the minimum is taken on the set of absolutely continuous curve γ :[0,1]→ M with γ(0)=x and γ(1)=y.One of the main results of[2]is that using the dual MK problem,they proved that the optimal transformation can be performed by a Borel map with the assumption that the initial measureμ0is absolutely continuous w.r.t.the Lebesgue measure,thus the Monge problem has a solution.

This paper is stimulated by[2],but we use another approach called optimal control,studying the optimal transportation problem of a generalized Lagrangian L=L(x,u(x,t),t).Consider the cost function as following:

where U is called a control set.x(t)satis fies the following equation:

here f satis fies some regular condition.About the control set and the regular condition,we will state it in Section 3.

We start from the point of optimal control to study the original optimal transportation problem,called the Monge problem:

Under the same assumption in[2]that the initial measureμ0is absolutely continuous w.r.t.the Lebesgue measure,we prove that the corresponding Monge problem has a Borel map as its solution.

2 Method of Characteristic

In this section,we brie fly introduce the method of characteristics in constructing a local classical solutions of the Cauchy problem for Hamilton-Jacobi equation like

where H and u0are of C2.

We suppose a priori that we have a solution u∈C2([0,T]×M)of the above equation.We call the solution of the following equation:

t→(t,X(t,z)),a characteristic curve associated to u starting from z.

Now we set

Easy calculation shows

Since

we obtain

Thus,the pair(X,P)solves the following ordinary differential equation:

with initial condition X(0)=z,P(0)=?u0(z),while U satis fies

Obviously,X,P and U are uniquely determined by the initial value u0.The above arguments suggests that we can obtain a solution to the Hamilton-Jacobi equation(2.1)by solving the characteristic system(2.4)provided the map z→X(t,z)is invertible.In[3],they listed a classic result.

Theorem 2.1(see[3])For any z∈Rn,let X(t,z),P(t,z)denote the solution of the characteristic system(2.4)and let U(t,z)be de fined by(2.5).Then,there exists T?≥0 such that the map z→X(t,z)is invertible with C1inverse x→Z(t,x),and there exists a unique solution u ∈ C2([0,T?)×M))of(2.1),which is given by

Remark 2.1T?in Theorem(2.1)is the uniform maximum time such that any two characteristic curves do not intersect with each other when the time T

3 Optimal Control Problem for Bolza Problem

Optimality is a universal principle of life.The first basic ingredient of an optimal control problem is the so-called control system,and it gives the possible behaviors.Usually,the control system is described by ordinary differential equations.In this paper,we consider the following form:

where x is the state,x∈M,t is the time,x0is the initial state,t0is the initial time,u is called control which depends on x,t,i.e.,u=u(x,t),t∈R.

Here are some basic assumptions on the control system:

(A1)There exists K0>0 such that|f(x,u)|≠K0(1+|x|+|u|), ?x ∈ Rn,u ∈ U;

(A2)f is Lipschitz w.r.t.x:There exists K1>0 such that|f(x2,u(x2,t))?f(x1,u(x1,t))|≤K1|x2?x1|for all x1,x2∈M,u∈U;

(A3)f is C1,1with respect to x:There exists K2>0 such that ∥fx(x2,u(x2,t)))?fx(x1,u(x1,t)∥≤K2|x2?x1|for all x1,x2∈M,u∈U.

The assumption(A2)ensures the existence of a unique global solution to the control system.

The second basic ingredient is the cost functional,and it associates a cost with each possible behavior.An optimal control problem consists of choosing a control u in the(ODE)in order to minimize the cost functional.

Let L=L(x,u(x,t),t)satisfy the following conditions:

(L1)L is superlinear w.r.t.u;

(L2)L is locally Lipschitz w.r.t.x: ?R>0,there exists αRsuch that

(L3)?x∈ M,the following set is convex

For the convenience and unity,we consider the following optimal control problem:

where L∈C2(M×R×[0,T]),I∈C(M),and x is the solution of the control system:

Note that fixing endpoint is the same as fixing initial point in essential.Here we use the same symbol x to denote a point or a solution of(3.1)without confusion.Now,we consider a time period of[0,T],and let t range over[0,T],x range over M.We introduce the value function.

Theorem 3.1(see[3])Assume(A1)–(A2),(L1)–(L3)hold,and the initial cost I is continuous.Then,?(x,t)∈M ×[0,T],there exists an optimal control u∈U for(BP).

De finition 3.1Given(t,x)∈ [0,T]×M,de fine

which is called the value function of the control problem(BP).

One of the most important principle in optimal control problem is so-called principle of optimality for V(t,x).

Theorem 3.2(Principle of Optimality)For every(t,x)∈[0,T]×M and?t∈(0,t),the value function V(t,x)satis fies the following relation:

The above principle of optimality means that in order to search for an optimal control,we can search over a small time interval for a control that minimizes the cost over this interval plus the subsequent optimal cost-to-go.

Now,let us look at the value function V(t,x)in a deep sight.We assume V(t,x) ∈ C1([0,T]×M),and consider the right-hand side of(3.2),

So,we can express V(t??t,x(t??t))as

and we have

Substituting(3.3)and(3.5)into the right-hand side of(3.2),we get

After simple calculation,we obtain

This is equivalent to the following equation:

It is remarkable to note that there are several forms which are equivalent to(3.8),but(3.8)is the reasonable form since flipping the sign in a PDE affects its viscosity solutions,so it will turn out that the above sign convention is the correct one.Let

We have the following theorem.

Theorem 3.3If the initial condition is equal to the initial cost,i.e.,u0(x)=I(x),then V(t,x)is the unique viscosity solution of(2.1)with Hamiltonian function H as in(3.9).

Proof Step 1(Viscosity subsolution)For every C1test function φ = φ(x,t),assume that φ ≥ V,and that φ ? V attains a local minimum at(t0,x0).We need to prove

Suppose the contrary:There exists a C1function φ,and a control u0,s.t.

and

Since

This is contradictory to the principle of optimal,so V(t,x)is a viscosity subsolution.

Step 2(Viscosity supersolution) For every C1test function φ = φ(t,x),assume that φ≤V,and that φ?V attains a local minimal at(t0,x0).We need to prove

Suppose the contrary:There exists a C1function ψ ,and a control u′0,s.t.

and

Since

We get a contradictory,thus V(t,x)is a viscosity supersolution.

Step 3(Uniqueness)By the comparison principle,the viscosity solution is unique!

From the above three steps,we have proved that V(t,x)is the unique viscosity solution.

Let the Hamiltonian H be as(3.9).We have the following theorem.

Theorem 3.4(see[3])Let(u,x)be an optimal pair for the point(t0,x0)∈ [0,T]×M and let p:[0,t]→Rnbe a dual arc associated with(u,x).Then(x,p)solves the system

for all s∈[0,t].As a consequence,x,p are of class C1.

Remark 3.1The above theorem tells us that the optimal trajectory of the optimal control problem is nothing else,but just the characteristic curve of the corresponding Hamilton-Jacobi equation.

4 Optimal Transportation Related to L(x,u,t)

Statement of the Monge problemLet M be a compact manifold,and a continuous cost function c(x,y)is given,c(x,y):M ×M → R,μ0,μ1are two probability measures on M.Find the mapping Ψ :M → M which transportμ0into μ1,and minimize the total cost:

where the transport means push-forward,which is de fined as following.

De finition 4.1(Push-forward)Let t:X→Y be a measurable map,μis a measure.De fine

for every Borel set B?Y.

The Monge problem can be stated as

In the rest of this paper,we consider the cost function as following:

where x satis fies the following ordinary equation:

As we said in the introduction,the Monge problem is not always well-posed,since sometimes there is no map Ψ such that= μ1.In the study of the Monge problem,mathematicians find that it is a good and effective approach to consider the MK problem first.

Statement of the Monge-Kantorovich problem

Under some proper conditions,we can use the solution of the MK problem to construct the solution of the Monge problem.In this paper,we use this approach.

The measure γ which satis fies(π1)?γ = μ0,(π2)?γ = μ1in(MK)is called a transport plan.We denote the transport plans by K(μ0,μ1).Observe that if Ψ is admissible for Monge problem,i.e.,Ψ?μ0= μ1,then the measure γ =(Id×Ψ)?μ0is a transport plan for(MK).Moreover,the class of transport plans is always non-empty since it always containsμ0×μ1.As proved in[7],the min in(MK)always can be achieved by a transport plan,and we call the transport plan which realizes the min an optimal transfer plan(see[2]).

Let the total cost

De finition 4.2(Admissible Kantorovich Pair)A pair of continuous function(?0,?1)is called an admissible Kantorovich pair if it satis fies the following relations:

for all point x∈M.

Kantorovich proved the following notable result.

Theorem 4.1

where the max is taken on the set of admissible Kantorovich pair(?0,?1).

This is the so-called dual Kantorovich problem.The admissible pairs which attain the max are called optimal Kantorovich pairs,usually,it is not unique!

Lemma 4.1If γ is an optimal transfer plan,and(?0,?1)is an optimal Kantorovich pair,then the support of γ is contained in the following set:

Lemma 4.2We have

where the max is taken on the set of admissible Kantorovich pairs.

It is deserved to note that for different pair of(x,y),the max may be achieved by different admissible Kantorovich pair.

Let(?0,?1)be an optimal Kantorovich pair,and

We construct a function on M×[0,T]as following:

Recall the de finition of the value function for(BP):

where x satis fies the control system(3.1).Obviously,we can see easily that U(x,t)is just the same as the value function V(t,x)with I(x)=?0(x).

So,the total cost C(μ0,μ1)can be realized by a viscosity solution of the Hamilton-Jacobi equation(2.1)with a proper initial condition.We have

Let us stop here for a little while,and look at the value function from another point of view.Assume that u?realizes the inf in the de finition of value function V(t,x).We de fine an operator T:Cac([0,t],R)→Cac([0,t],R)as following:

Obviously,Tt?0(x)=V(t,x).

As in[11,13],we call Ttthe solution semigroup since it is determined by the viscosity solution of the Hamilton-Jacobi equation(2.1).Actually,Ttis indeed a semigroup.

Theorem 4.2(Semi-group Property){Tt}t≥0is a one-parameter semigroup from C(M,R).

ProofTs?0(x)=u(x,s)means that the operator Tsjust sends the initial value ?0into the corresponding viscosity solution at time s under this initial condition.Similarly,Tt+s?0(x)=u(x,s+t)means that the operator Tt+ssends the initial value ?0into the corresponding viscosity solution at time t+s.Attention Tt? Ts?0(x)means that the operator Ttsends the initial value Ts?0to the corresponding viscosity solution at time t.Since the viscosity solution of Hamilton-Jacobi(2.1)is unique,it is obvious that Tt?Ts?0=Tt+s?0for arbitrary initial value ?0∈ C(M,R).

De finition 4.3Let(?0,?1)denote an optimal Kantorovich pair,and u? be one of the control which reaches the inf in the de finition of the value function V.We de fine F(?0,?1)?C2([0,1],M)as the set of curves γ(t)such that

Remark 4.1Obviously,if we rewrite(4.9)into the following form:

we can see that F(?0,?1)is just the set of pieces of characteristic curves.

Let F0(ψ0,ψ1)be the set of initial state(x,p)∈ T?M such that the curve t→ π ?x,v)belongs to F(?0,?1).We have the following lemma.

Lemma 4.3The maps π and π?:F0(?0,?1)→ M are surjective.If x is a differentiable point of ?0,then the set π?1(x) ∩ F(?0,?1)contains only one point.There exists a Borel measurable set Σ ? M of full measure,whose points are differentiable points of ?0,and such that the map

is Borel measurable on Σ.

ProofFor each x ∈ M,there exists a characteristic curve such that(4.9)–(4.10)are satis fied,so the projection π ?ψ10from F0(?0,?1)to M is surjective.For π,it is similar!

Next we consider a differentiable point x of ?0.By the characteristic method introduced in Section 2,the characteristic curves do not cumulate together at x,i.e.,there is only one characteristic curve starts from x.We construct S as

Since ?0is Lipschitz,the set of differentiable points of ?0is of total Lebesgue measure.Notice that there exists a sequence of compact sets Knsuch that ?0is differentiable at each point of Kn,and the Lebesgue measure of M?Knis converging to zero.For each n,the set π?1(Kn)∩F(?0,?1)is compact,and the canonocal projection π restricted to this set is injective and continuous,so the inverse function S is continuous on Kn.And as a consequence,S is a Borel measurable map on

Now let

And let m0∈ B(T?M)be a Borel probability measure on the cotangent bundle T?M.We call m0an initial transport measure if the measure η on M × M given by

is a transport plan.Here ψ is the time one map of the Hamiltonian flow,and π :T?M → M is the canonical projection.We denote I(μ0,μ1)the set of initial transport measures.Obviously,we can de fine the action of an initial transport measure as

Lemma 4.4The mapping(π × (π ? ψ))?:I(μ0,μ1)→ K(μ0,μ1)is surjective.

ProofWe shall prove that for arbitrary probability measure η∈B(M×M),there exists a probability measure m0∈ B(T?M)such that(π×(π?))?m0= η.Since the set of probability measures on M×M is the compact convex closure of the set of Dirac probability measures,we just need to prove it when η is a Dirac probability measure.Let η be a Dirac probability measure supported at(x,y)∈ M×M,and γ:[0,T]→ M be a curve with boundary conditions γ(0)=x, γ(1)=y satisfying the control system.Let m0be a Dirac probability measure supported at γ(0),˙γ(0).Obviously,we have

where η is a transport plan which is determined by m0through(π × (π ? ψ))?.

Theorem 4.3Ifμ0is absolutely continuous with respect to Lebesgue measure,then,there exists a Borel section S:M → TM such that the map π ??S is an optimal transport map between μ0and μ1.The section S is unique in the sense ofμ0everywhere.

ProofSince Σ is of full Labesgue measure,consider m0=S?(μ0|Σ),which is a probability measure on T?M,concentrated on F(?0,?1),and π?m0= μ0.Since π induces an isomorphism between π?1(Σ)∩ F0(?0,?1),and by Lemma 4.4,we have(μ0,μT)=A(m0),and that m0is the unique initial transport measure.Thus,m0is the unique optimal transport measure.π?ψ?S is an optimal transport map betweenμ0andμ1.

AcknowledgementWe appreciate the anonymous referees for their valuable comments.

[1]Ambrosio,L.,Lecture Notes on Optimal Transport Problems Mathematical Aspects of Evolving Interfaces,Lecture Notes in Mathematics,Vol.1812,2004,1–52.

[2]Bernard,P.and Buffoni,B.,Optimal mass transportation and Mather theory,J.Eur.Math.Soc.,9,2007,85–121.

[3]Cannarsa,P.and Sinestrari,C.,Semiconcave Functions,Hamilton-Jacobi Equations,and Optimal Control Progress in Nonlinear Differential Equations and Their Applications,2004.

[4]De Passcale,L.,Gelli,M.S.and Granieri,L.,Minimal measures,one-dimensional currents and the Monge-Kantorovich problem,Calculus of Variations and Partial Differential Equations,27(1),2006,1–23.

[5]Evans,L.C.and Gomes,D.,Linear programming interpretations of Mather’s variational principle,Attribute to J.L.Lions,Esaim Control Optim,Calc.Var.,8,2002,693–702.

[6]Granieri,L.,On action minimizing measures for the Monge-Kantorovich problem,NoDEA,14(1–2),2007,125–152.

[7]Kantorovich,L.V.,On the transfer of mass,Dokl.Akad.Nauk.USSR,37,1942,227–229.

[8]Kantorovich,L.V.,On a problem of Monge,Uspekhi Mat.Nauk.,3,1948,225–226.

[9]Liberzon,D.,Calculus of Variations and Optimal Control Theory:A Concise Introduction,ISBN:97814008426431.

[10]Pratelli,A.,Equivalence between some de finitions for the optimal mass transportation problem and for the transport density on manifolds,Annali di Math.Pura App.,2004.

[11]Su,X.F.and Yan,J.,Weak KAM theorem for Hamilton-Jacobi equations,preprint.arXiv:1312.1600

[12]Villani,C.,Topics in Optimal Transportation,American Mathematical Society,Providence,Rhode Island,2003.

[13]Wang,L.and Yan,J.,Uniqueness of viscosity solutions of Hamilton-Jacobi equations,Weak KAM theory for general Hamition-Jacobi equations II:The fundamental solution under Lipschitz conditions.arXiv:1408.3791v1

[14]Wolansky,G.,Optimal transportation in the presence of a prescribed pressure field.arXiv:mathph10306070

[15]Young,L.C.,Lectures on the Calculus of Variations and Optimal Control Theory,2nd edition,Chelsea,1980,Econometrica,39(3),1971,653.