Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~ansobol/otarie/slides/wolansky.pdf Äàòà èçìåíåíèÿ: Fri May 21 21:15:07 2010 Äàòà èíäåêñèðîâàíèÿ: Sat Jun 26 04:28:38 2010 Êîäèðîâêà:

Limit Theorems for Optimal Mass Transportation and Applications to Networks
Gershon Wolansky
Department of Mathematics, Technion 32000 Haifa, ISRAEL E-mail: gershonw@math.technion.ac.il

S. Petersburg, May 2010

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

1 / 37


Review of Kantorovich metrics on the space of positive measures

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

2 / 37


Review of Kantorovich metrics on the space of positive measures Conditioned Kantorovich metrics and relation to metrics on 1-D graphs

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

2 / 37


Review of Kantorovich metrics on the space of positive measures Conditioned Kantorovich metrics and relation to metrics on 1-D graphs Cost function for transporting networks

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

2 / 37


Review of Kantorovich metrics on the space of positive measures Conditioned Kantorovich metrics and relation to metrics on 1-D graphs Cost function for transporting networks Replacing optimal networks by points allocation?

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

2 / 37


Review of Kantorovich metrics on the space of positive measures Conditioned Kantorovich metrics and relation to metrics on 1-D graphs Cost function for transporting networks Replacing optimal networks by points allocation? Generalization to Lagrangian action on compact manifolds

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

2 / 37


Definition
The Kantorovich metric for - , + B+ satisfying Wp ( , ) =
+ -

d - =
1/p

d +

inf


|x - y | d
2,#

p

Where B + ( â ), 1,# = + ,

= - .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

3 / 37


Definition
The Kantorovich metric for - , + B+ satisfying Wp ( , ) =
+ -

d - =
1/p

d +

inf


|x - y | d
2,#

p

Where B + ( â ), 1,# = + ,

= - .

In case p = 1, W1 (+ , - ) depends only on = + - - B0 .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

3 / 37


Definition
The Kantorovich metric for - , + B+ satisfying Wp ( , ) =
+ -

d - =
1/p

d +

inf


|x - y | d
2,#

p

Where B + ( â ), 1,# = + ,

= - .

In case p = 1, W1 (+ , - ) depends only on = + - - B0 . An equivalent definition

Definition
W1 () = sup
Lip1 ()

d

Where Lip1 () := { C () ; (x ) - (y ) |x - y | x , y }

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

3 / 37


Example:
If + =
1 N N

mi xi ; - =
1 N i

mi

yi

(1)

subjected to

N 1

mi =

mi

= 1, then

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

4 / 37


Example:
If + =
1 N N

mi xi ; - =
1 N i

mi

yi

(1)

subjected to

N 1

mi =

mi

= 1, then
N N 1/p i ,j p

Wp () = min
1 1

|xi - yj |

where = {i ,j } ie the set of all non-negative N â N matrices satisfying
n n


j =1

i ,j

=m

i

;
i =1



i ,j

= mj

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

4 / 37


Weak continuity: we may approximate ± by atomic measures.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

5 / 37


Weak continuity: we may approximate ± by atomic measures. Then the optimal plan is an atomic measure as well, solvable in the set of bi-stochastic matrices {i ,j }.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

5 / 37


Weak continuity: we may approximate ± by atomic measures. Then the optimal plan is an atomic measure as well, solvable in the set of bi-stochastic matrices {i ,j }. . This "discrete" plan is an approximation in the weak topology of .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

5 / 37


Weak continuity: we may approximate ± by atomic measures. Then the optimal plan is an atomic measure as well, solvable in the set of bi-stochastic matrices {i ,j }. . This "discrete" plan is an approximation in the weak topology of . An optimal map is sometimes deterministic:
p Wp (+ , - ) =

T# + =

inf

-

|x - T (x )|p d +

where T# + (B ) = - T -1 (B ) . Then (dxdy ) = + (dx )y -T (x ) dy is the optimal plan.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

5 / 37


Weak continuity: we may approximate ± by atomic measures. Then the optimal plan is an atomic measure as well, solvable in the set of bi-stochastic matrices {i ,j }. . This "discrete" plan is an approximation in the weak topology of . An optimal map is sometimes deterministic:
p Wp (+ , - ) =

T# + =

inf

-

|x - T (x )|p d +

where T# + (B ) = - T -1 (B ) . Then (dxdy ) = + (dx )y -T (x ) dy is the optimal plan. If p > 1 then T is obtained in terms of a "potential function" . In particular, p = 2 and + is continuous w.r to Lebesgue measure than T (x ) = (x ) where is a convex function, and this T is unique. (Brenier, McCann, Gangbo, Caffarelli)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

5 / 37


For the case p = 1, the optimal potential gives only partial information on the optimal mapping T (x ) = x + t (x ) where t is unknown (change with x).

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

6 / 37


For the case p = 1, the optimal potential gives only partial information on the optimal mapping T (x ) = x + t (x ) where t is unknown (change with x). The solvability of optimal map in the metric case (p = 1) is a difficult problem. First attempt by Sudakov (1979).

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

6 / 37


For the case p = 1, the optimal potential gives only partial information on the optimal mapping T (x ) = x + t (x ) where t is unknown (change with x). The solvability of optimal map in the metric case (p = 1) is a difficult problem. First attempt by Sudakov (1979). Equivalent formulation (Beckmann (1952))

Definition
W1 () = inf subject to · m = . |d m |

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

6 / 37


For the case p = 1, the optimal potential gives only partial information on the optimal mapping T (x ) = x + t (x ) where t is unknown (change with x). The solvability of optimal map in the metric case (p = 1) is a difficult problem. First attempt by Sudakov (1979). Equivalent formulation (Beckmann (1952))

Definition
W1 () = inf subject to · m = . |d m |

The optimal m := yields a complete information on T .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

6 / 37


For the case p = 1, the optimal potential gives only partial information on the optimal mapping T (x ) = x + t (x ) where t is unknown (change with x). The solvability of optimal map in the metric case (p = 1) is a difficult problem. First attempt by Sudakov (1979). Equivalent formulation (Beckmann (1952))

Definition
W1 () = inf subject to · m = . |d m |

The optimal m := yields a complete information on T . There is an interest in calculating the Transport Measure := |m|, and verifies · ( ) = .
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 6 / 37


Next attempts by Gangbo and Evans (1999): Approximating Lip1 by | |p where p .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

7 / 37


Next attempts by Gangbo and Evans (1999): Approximating Lip1 by | |p where p . minimizing p leads to · | |p
-2 -1

| |p -

d

=

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

7 / 37


Next attempts by Gangbo and Evans (1999): Approximating Lip1 by | |p where p . minimizing p leads to · | |p and to the approximation | |p
-2 -1

| |p -

d

=

-2

while | | 1.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

7 / 37


Next attempts by Gangbo and Evans (1999): Approximating Lip1 by | |p where p . minimizing p leads to · | |p and to the approximation | |p
-2 -1

| |p -

d

=

-2

while | | 1.

Other approaches by Trudinger, Wang, Ma, Caffarelli, Feldman, McCann Ambrosio, Pratelli... in the last decade.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

7 / 37


Conditional W1 distance

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

8 / 37


Conditional W1 distance

Definition
+ Define, for µ B1 (), B0 () and p > 1

W1 ( µ) := where q = p /(p - 1).

(p )

sup
0 C 1 ()



d
1/q

| |q d µ

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

8 / 37


Theorem
W1 () = inf+ W1 ( µ)
µB1 (p )

If p = 2 then any minimizer µ is a Transport measure supported in an optimal plan of W1 ().

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

9 / 37


Theorem
W1 () = inf+ W1 ( µ)
µB1 (p )

If p = 2 then any minimizer µ is a Transport measure supported in an optimal plan of W1 ().
Example: = m1 x1 + m2 x2 - m1 y1 - m2 y2 - m3 y3

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

9 / 37


Theorem
W1 () = inf+ W1 ( µ)
µB1 (p )

If p = 2 then any minimizer µ is a Transport measure supported in an optimal plan of W1 ().
Example: = m1 x1 + m2 x2 - m1 y1 - m2 y2 - m3 y3

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

9 / 37


Disadvantage of using W1 ( µ) for calculating transport measures:

(p )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

10 / 37


Disadvantage of using W1 ( µ) for calculating transport measures: (p ) W1 ( µ) is not continuous in µ.

(p )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

10 / 37


Disadvantage of using W1 ( µ) for calculating transport measures: (p ) W1 ( µ) is not continuous in µ. In particular W1 ( µn ) = for any atomic measure µn .
(p )

(p )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

10 / 37


Disadvantage of using W1 ( µ) for calculating transport measures: (p ) W1 ( µ) is not continuous in µ. In particular W1 ( µn ) = for any atomic measure µn . Thus, we cannot approximate µ as a limit of atomic measures.
(p )

(p )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

10 / 37


"Proof":
+ µB1 0C 1 ()

inf

sup



d
1/q

=

| |q d µ

+ 0C 1 () µB1

sup

inf



d
1/q

| |q d µ

while sup
+ µB1

| |q d µ = sup | (x )|q = Lip q ()
x

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

11 / 37


"Proof":
+ µB1 0C 1 ()

inf

sup



d
1/q

=

| |q d µ

+ 0C 1 () µB1

sup

inf



d
1/q

| |q d µ

while sup
+ µB1

| |q d µ = sup | (x )|q = Lip q ()
xi x

In case + =

N 1

mi

; - =
N N i

N 1

mi yi the optimal µ is given by

µ=
i

i , j |xi - yj | [

xi ,yj ]

with

i



i ,j

= mj ;

j



i ,j

= mi are the optimal transports.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

11 / 37


Theorem
For p > 1 W1 (||µ) = - lim
0 (p ) -1

Wp µ + + , µ +

-

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

12 / 37


Theorem
For p > 1 W1 (||µ) = - lim
0 (p ) -1

Wp µ + + , µ +
-

-

W1 () = lim
0

-1

µB1

inf+ Wp µ + + , µ +

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

12 / 37


Theorem
For p > 1 W1 (||µ) = - lim
0 (p ) -1

Wp µ + + , µ +
-

-

W1 () = lim
0

-1

µB1

inf+ Wp µ + + , µ +

Remark
Wp ( µ) := -1

Wp µ + + , µ +

-

is weakly continuous in µ.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

12 / 37


Let = x - y .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

13 / 37


Let = x - y .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

13 / 37


Let = x - y .

If = 1/n then µ is displayed in the n- gray shadows

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

13 / 37


Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

14 / 37


Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

14 / 37


Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

15 / 37


Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

15 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks?

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks? Suppose (p ) W () := inf W1 ( µ)
µ

where we minimize on probability measures µ supported on a given graph .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks? Suppose (p ) W () := inf W1 ( µ)
µ

where we minimize on probability measures µ supported on a given graph . W () = min


D (x , y )d (x , y )

where D is the distance reduced to .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks? Suppose (p ) W () := inf W1 ( µ)
µ

where we minimize on probability measures µ supported on a given graph . W () = min


D (x , y )d (x , y )

where D is the distance reduced to . Can we obtain a formulation of "optimal network" by restricting to a set of probability measures supported of graphs of prescribed length?
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks? Suppose (p ) W () := inf W1 ( µ)
µ

where we minimize on probability measures µ supported on a given graph . W () = min


D (x , y )d (x , y )

where D is the distance reduced to . Can we obtain a formulation of "optimal network" by restricting to a set of probability measures supported of graphs of prescribed length? Disadvantage: This is a formidable set, not natural, not compact.
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 16 / 37


Optimal Networks
Underlining idea: Cost of transforation depends on the flux as well. It is a increasing, concave function of the flux. (Butazzio, Xia, Stepanov ....) (p ) A different approach, using W1 ( µ):Can we restrict the conditioning measure µ to obtain optimal networks? Suppose (p ) W () := inf W1 ( µ)
µ

where we minimize on probability measures µ supported on a given graph . W () = min


D (x , y )d (x , y )

where D is the distance reduced to . Can we obtain a formulation of "optimal network" by restricting to a set of probability measures supported of graphs of prescribed length? Disadvantage: This is a formidable set, not natural, not compact. Certainly cannot be approximated by atomic measures!
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 16 / 37


Equivalent formulation:

Theorem
For p > 1
M 1-1/p

lim M

+ µBM

min Wp µ + + , µ +

-

= W1 (+ , - )

+ where BM stands for the set of all positive Borel measures µ normalized by d µ = M .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

17 / 37


Equivalent formulation:

Theorem
For p > 1
M 1-1/p

lim M

+ µBM

min Wp µ + + , µ +

-

= W1 (+ , - )

+ where BM stands for the set of all positive Borel measures µ normalized by d µ = M .

Suppose we replace the condition M by the condition n where µ is restricted to the set of atomic measures B n,+ of (at most) n atoms?

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

17 / 37


Equivalent formulation:

Theorem
For p > 1
M 1-1/p

lim M

+ µBM

min Wp µ + + , µ +

-

= W1 (+ , - )

+ where BM stands for the set of all positive Borel measures µ normalized by d µ = M .

Suppose we replace the condition M by the condition n where µ is restricted to the set of atomic measures B n,+ of (at most) n atoms?

Theorem
For any q > 1 and =
N 1

mi xi - mi yi .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

17 / 37


Equivalent formulation:

Theorem
For p > 1
M 1-1/p

lim M

+ µBM

min Wp µ + + , µ +

-

= W1 (+ , - )

+ where BM stands for the set of all positive Borel measures µ normalized by d µ = M .

Suppose we replace the condition M by the condition n where µ is restricted to the set of atomic measures B n,+ of (at most) n atoms?

Theorem
For any q > 1 and =
n N 1

mi xi - mi yi .
-

lim n

1-1/p

µB

inf ,+ Wp µ + + , µ + n

=W

(p )

()

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

17 / 37


Recall

Definition
W1 () = inf subject to · m = . |d m |

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

18 / 37


Recall

Definition
W1 () = inf subject to · m = . |d m |

Definition
(Xia) For p > 1 and an atomic metric W subject to · m = .
(p )

() = inf

|

d m 1/p | dH dH1

1

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

18 / 37


An oriented, weighted graph ( , m) associated with is a graph composed of vertices V ( ) and edges E ( ) and a function m : E R+ :

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

19 / 37


An oriented, weighted graph ( , m) associated with is a graph composed of vertices V ( ) and edges E ( ) and a function m : E R+ :

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

19 / 37


Definition
The set of all weighted graphs associated with is denoted by ().

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

20 / 37


Definition
The set of all weighted graphs associated with is denoted by (). W
(p )

() :=

( ,m)()

inf

|e |m
e E ( )

1/p e

Examples: p = 1 (Reduced to the metric Monge problem),

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

20 / 37


Definition
The set of all weighted graphs associated with is denoted by (). W
(p )

() :=

( ,m)()

inf

|e |m
e E ( )

1/p e

Examples: p = 1 (Reduced to the metric Monge problem), p = 0 (Reduced to Steiner problem of minimal graphs)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

20 / 37


We may associate a weighted graph ( , m) with an optimal plan: e (i , j );
i ,j

>0

, me =

i ,j

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

21 / 37


We may associate a weighted graph ( , m) with an optimal plan: e (i , j );
i ,j

>0

, me =

i ,j

Postulate
{x1 , . . . , y1 , . . .} V ( ).

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

21 / 37


We may associate a weighted graph ( , m) with an optimal plan: e (i , j );
i ,j

>0

, me =

i ,j

Postulate
{x1 , . . . , y1 , . . .} V ( ). For each i {1, N }, ± where ± e := ve .
{ e ,x i + e }

me = mi and

{e ,yi - e }

me = mi ,

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

21 / 37


We may associate a weighted graph ( , m) with an optimal plan: e (i , j );
i ,j

>0

, me =

i ,j

Postulate
{x1 , . . . , y1 , . . .} V ( ). For each i {1, N }, ± where ± e := ve .
{ e ,x i + e }

me = mi and
{ e ;v + e }

{e ,yi - e }

me = mi , me .

For each v V ( ) - {x1 , . . . yN },

me =

{e ;v - e }

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

21 / 37


We may associate a weighted graph ( , m) with an optimal plan: e (i , j );
i ,j

>0

, me =

i ,j

Postulate
{x1 , . . . , y1 , . . .} V ( ). For each i {1, N }, ± where ± e := ve .
{ e ,x i + e }

me = mi and
{ e ;v + e }

{e ,yi - e }

me = mi , me .

For each v V ( ) - {x1 , . . . yN },

me =

{e ;v - e }

Lemma
There exists an optimal plan { } whose graph contains at most 2N 3 nodes of order 3.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

21 / 37


o = mo

o = m

o

o =

o

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

22 / 37


The set B

n ,+

is, evidently, not a compact one. Still we claim
n ,+ -

Lemma
For each n N, a minimizer µn B
µB

W q () := inf ,+ Wq µ + + , µ + - = Wq µn + + , µn + n exists.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

23 / 37


The set B

n ,+

is, evidently, not a compact one. Still we claim
n ,+ -

Lemma
For each n N, a minimizer µn B
µB

W q () := inf ,+ Wq µ + + , µ + - = Wq µn + + , µn + n exists.

Theorem
Let µn be a regular minimizer of Wq (µ + + , µ + - ) in B n,+ . Then the associated optimal plan spans a reduced weighted tree (n , mn ) which ^ converges (in Hausdorff metric) to an optimal graph ( , m) () as ^ n ,

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

23 / 37


One direction

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

24 / 37


One direction

Definition
Reduced graph: Remove all nodes of degree =2.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

24 / 37


One direction

Definition
Reduced graph: Remove all nodes of degree =2.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

24 / 37



1 me /p |e | e E ( ) ^ e E ( ) ^

me |e |p

1/p

|E ( )| ^

(p -1)/p

.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

25 / 37



1 me /p |e | e E ( ) ^ e E ( ) ^

me |e |p

1/p

|E ( )| ^

(p -1)/p

.

p me |e |p = Wp (+ + µ, - + µ) e E ( ) ^

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

25 / 37



1 me /p |e | e E ( ) ^ e E ( ) ^

me |e |p

1/p

|E ( )| ^

(p -1)/p

.

p me |e |p = Wp (+ + µ, - + µ) e E ( ) ^

From Lemma: |E ( )|(p ^

-1)/p

=n

(p -1)/p

+ o (n).

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

25 / 37



1 me /p |e | e E ( ) ^ e E ( ) ^

me |e |p

1/p

|E ( )| ^

(p -1)/p

.

p me |e |p = Wp (+ + µ, - + µ) e E ( ) ^

From Lemma: |E ( )|(p ^ n
(1-p )/p

-1)/p

=n

(p -1)/p

+ o (n). Hence: m
e E ( ) ^ 1/p e

Wp (+ + µ, - + µ)

|e |

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

25 / 37


Generalization to Lagrangian on manifolds and relation with the Weak KAM Theory
Lagrangian-Hamiltonian duality (x , v ) T: l (x , v ) = sup p , v - h(x , p )
p T

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

26 / 37


Generalization to Lagrangian on manifolds and relation with the Weak KAM Theory
Lagrangian-Hamiltonian duality (x , v ) T: l (x , v ) = sup p , v - h(x , p )
p T

1 + µB1 C ()

sup

inf

h(x , d )d µ = E =:

C 1 () x

inf

sup h(x , d )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

26 / 37


Generalization to Lagrangian on manifolds and relation with the Weak KAM Theory
Lagrangian-Hamiltonian duality (x , v ) T: l (x , v ) = sup p , v - h(x , p )
p T

1 + µB1 C ()

sup

inf

h(x , d )d µ = E =:

C 1 () x

inf

sup h(x , d )

Example l (x , v ) = |v |2 /2 - V (x ) , h(x , p ) = |p |2 /2 + V (x ) sup
µ
+ B1

C 1 ()

inf

| |2 /2 + V (x ) d µ = sup V (x ) .
x

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

26 / 37


T

CT (x , y ) :=

inf
z (0)=x ,z (T )=y 0

l z (s ), z (s ) ds , T > 0 .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

27 / 37


T

CT (x , y ) :=

inf
z (0)=x ,z (T )=y 0

l z (s ), z (s ) ds , T > 0 .

Then CT (µ) := CT (µ, µ) =
P (µ,µ) M âM

min

CT (x , y )d (x , y )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

27 / 37


T

CT (x , y ) :=

inf
z (0)=x ,z (T )=y 0

l z (s ), z (s ) ds , T > 0 .

Then CT (µ) := CT (µ, µ) =
P (µ,µ) M âM

min

CT (x , y )d (x , y )

Theorem
(Buffoni and Bernard)
+ µB1

min CT (µ) = -T E

where the minimizers coincide, for any T > 0, with the projected Mather measure.
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 27 / 37


The action C

T

induces a "metric" on :

Definition
(x , t ) â DE (x , y ) = inf CT (x , y ) + TE .
T >0

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

28 / 37


The action C

T

induces a "metric" on :

Definition
(x , t ) â DE (x , y ) = inf CT (x , y ) + TE .
T >0

Lemma
DE (x , y ) = - for any x , y if E < E .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

28 / 37


The action C

T

induces a "metric" on :

Definition
(x , t ) â DE (x , y ) = inf CT (x , y ) + TE .
T >0

Lemma
DE (x , y ) = - for any x , y if E < E . If E E then DE (x , x ) = 0 for any x .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

28 / 37


The action C

T

induces a "metric" on :

Definition
(x , t ) â DE (x , y ) = inf CT (x , y ) + TE .
T >0

Lemma
DE (x , y ) = - for any x , y if E < E . If E E then DE (x , x ) = 0 for any x .

Example
For l (x , v ) = |v |2 /2 we get CT (x , y ) = |x - y |2 /2T while DE (x , y ) = 2E |x - y | if E 0, DE (x , y ) = - if E < 0. Here E = 0.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

28 / 37


The action C

T

induces a "metric" on :

Definition
(x , t ) â DE (x , y ) = inf CT (x , y ) + TE .
T >0

Lemma
DE (x , y ) = - for any x , y if E < E . If E E then DE (x , x ) = 0 for any x .

Example
For l (x , v ) = |v |2 /2 we get CT (x , y ) = |x - y |2 /2T while DE (x , y ) = 2E |x - y | if E 0, DE (x , y ) = - if E < 0. Here E = 0.

Lemma
DE () := DE (+ , - ) = sup
Gershon Wolansky (Technion)

d ; (x ) - (y ) DE (x , y )
Haifa, 2009 28 / 37

Action principle and OMT


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Theorem
If B0 , the following definitions are equivalent:

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Theorem
If B0 , the following definitions are equivalent:
1

CT () := T C

T

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Theorem
If B0 , the following definitions are equivalent:
1 2

CT () := T C CT () := supE

T E

DE () - ET .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Theorem
If B0 , the following definitions are equivalent:
1 2 3

CT () := T C CT () := supE CT () := inf

T E

DE () - ET . sup
C 1 (M ) M

+ µB1

-Th(x , d )d µ + d .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

29 / 37


Definition
C (; µ) := sup
C 1 ()

-h(x , d )d µ + d

C () := inf+ C (; µ) .
µB1

Theorem
If B0 , the following definitions are equivalent:
1 2 3

CT () := T C CT () := supE CT () := inf

T E

DE () - ET . sup
C 1 (M ) M

+ µB1

-Th(x , d )d µ + d .

In particular, for = x - y , CT (x , y ) := sup DE (x , y ) - ET
E E
Gershon Wolansky (Technion) Action principle and OMT Haifa, 2009 29 / 37


From definition CT (x , y ) CT (x , y )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

30 / 37


From definition CT (x , y ) CT (x , y ) In general, strict inequality. However, if T << 1 we get equality under mild conditions.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

30 / 37


From definition CT (x , y ) CT (x , y ) In general, strict inequality. However, if T << 1 we get equality under mild conditions.

Theorem
For any B0 , CT (; µ) = - lim
0 -1

C

T

(µ + - , µ + + ) .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

30 / 37


From definition CT (x , y ) CT (x , y ) In general, strict inequality. However, if T << 1 we get equality under mild conditions.

Theorem
For any B0 , CT (; µ) = - lim
0 -1

C

T

(µ + - , µ + + ) .

CT () = lim inf+
0 µB 1

-1

CT (µ + - , µ + + ) .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

30 / 37


Sketch of proof

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

31 / 37


Sketch of proof
Easy Lemma

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

31 / 37


Sketch of proof
Easy Lemma

Lemma
+ For any µ B1 , = + - - B0

lim inf
0

-1

C

T

(µ + - , µ + + ) CT ( µ) .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

31 / 37


Sketch of proof
Easy Lemma

Lemma
+ For any µ B1 , = + - - B0

lim inf
0

-1

C

T

(µ + - , µ + + ) CT ( µ) .

Harder lemma

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

31 / 37


Sketch of proof
Easy Lemma

Lemma
+ For any µ B1 , = + - - B0

lim inf
0

-1

C

T

(µ + - , µ + + ) CT ( µ) .

Harder lemma

Lemma
For T > 0, CT () lim sup
0 -1
+ µB1

inf C

T

(µ + + , µ + - ) .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

31 / 37


Proof of "hard" Lemma

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

32 / 37


Proof of "hard" Lemma
Given > 0 let
DE (x , y ) := inf [C n N nT

(x , y ) + nET ] .

Evidently, DE (x , y ) is continuous on M â M locally uniformly in E E . Moreover, lim DE = DE 0

uniformly on M â M and locally uniformly in E E as well.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

32 / 37


Proof of "hard" Lemma
Given > 0 let
DE (x , y ) := inf [C n N nT

(x , y ) + nET ] .

Evidently, DE (x , y ) is continuous on M â M locally uniformly in E E . Moreover, lim DE = DE 0

uniformly on M â M and locally uniformly in E E as well. We now decompose M â M into mutually disjoint Borel sets Qn :
M â M = n Qn , Qn QE ,n

= if n = n

such that
Qn {(x , y ) M â M ; DE (x , y ) = C nT

(x , y ) + nET } .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

32 / 37


Let E P (+ , - ) be an optimal plan for
DE () = DE (x , y )d E = P (+ ,- ) M âM

min

M âM Q
n

DE (x , y )d ,

and n = E

, the restriction of E to Qn .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

33 / 37


Let E P (+ , - ) be an optimal plan for
DE () = DE (x , y )d E = P (+ ,- ) M âM

min

M âM

DE (x , y )d ,

and n = E Qn , the restriction of E to Qn . Set ± to be the marginals n n on the first and second factors of M â M . of

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

33 / 37


Let E P (+ , - ) be an optimal plan for
DE () = DE (x , y )d E = P (+ ,- ) M âM

min

M âM

DE (x , y )d ,

and n = E Qn , the restriction of E to Qn . Set ± to be the marginals n n on the first and second factors of M â M . Then n E of n=1 = and

± = n
n=1

±

Remark
Note that Qn = for all but a finite number of n N. In particular, the sum contains only a finite number of non-zero terms.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

33 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

34 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

We observe that T E DE (), where E is the super gradient as a function of E . At this stage we choose E depending on , T such that

T



= T + 2T |± |

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

34 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

We observe that T E DE (), where E is the super gradient as a function of E . At this stage we choose E depending on , T such that

T Let n B + (TM ) satisfying



= T + 2T |± |
(t =nT ) (l ) #

I Exp

n = n

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

34 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

We observe that T E DE (), where E is the super gradient as a function of E . At this stage we choose E depending on , T such that

T Let n B + (TM ) satisfying



= T + 2T |± |
(t =nT ) (l ) #

I Exp Use n to define j := Exp n for j = 0, 1 . . . n.

n = n

(t =nT ) (l ) #

n B + (M )

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

34 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

We observe that T E DE (), where E is the super gradient as a function of E . At this stage we choose E depending on , T such that

T Let n B + (TM ) satisfying



= T + 2T |± |
(t =nT ) (l ) #

I Exp Use n to define j := Exp n

n = n

(t =nT ) (l ) #

n B + (M )
- n

for j = 0, 1 . . . n. Note that 0 = + n n

, n = n

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

34 / 37


Let |n | :=

M

d ± n

M âM

d . The averaged flight time is n


T

:= T
n=1

n|n |

We observe that T E DE (), where E is the super gradient as a function of E . At this stage we choose E depending on , T such that

T Let n B + (TM ) satisfying



= T + 2T |± |
(t =nT ) (l ) #

I Exp Use n to define j := Exp n

n = n

(t =nT ) (l ) #

n B + (M )
- n

for j = 0, 1 . . . n. Note that 0 = + n n C
nT

, n = n C
T

n -1

(+ , - ) + nET |n | = n n
j =0

(j , j +1 ) + ET |n | nn
Haifa, 2009 34 / 37

Gershon Wolansky (Technion)

Action principle and OMT


DE

DE

() =
n=1

(n ) =
n=1 n -1

C

nT

(+ , - ) + nET |n | n n

=
n=1 j =0

CT (jn , jn+1 ) + ET |n | . (2)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

35 / 37


DE

DE

() =
n=1

(n ) =
n=1 n -1

C

nT

(+ , - ) + nET |n | n n

=
n=1 j =0

CT (jn , jn+1 ) + ET |n | . (2)

Let now µ
,E

n -1

=
n=1 j =1



j n

.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

35 / 37


DE

DE

() =
n=1

(n ) =
n=1 n -1

C

nT

(+ , - ) + nET |n | n n

=
n=1 j =0

CT (jn , jn+1 ) + ET |n | . (2)

Let now µ Note that µ
,E ,E

n -1

=
n=1 j =1



j n

.


n

=
n=1 j =0

-
n=1

j n

-
n=1

0 n

n . n
Haifa, 2009 35 / 37

Gershon Wolansky (Technion)

Action principle and OMT


We obtain


µ

,E

=
n=1

(n + 1)|± | - 2|± | = 1 = µ n

,E

+ B1 .

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

36 / 37


We obtain


µ

,E

=
n=1

(n + 1)|± | - 2|± | = 1 = µ n
n-1

,E

+ B1 .

C
n=1 j =0

T

(j , j +1 ) nn

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

36 / 37


We obtain


µ

,E

=
n=1

(n + 1)|± | - 2|± | = 1 = µ n
n-1

,E

+ B1 .

C
n=1 j =0

T

(j , j +1 ) nn
n

C
T

n-1


j +1 n


n=1 j =0

j , n
n=1 j =1

=

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

36 / 37


We obtain


µ

,E

=
n=1

(n + 1)|± | - 2|± | = 1 = µ n
n-1

,E

+ B1 .

C
n=1 j =0

T

(j , j +1 ) nn
n

C
T

n-1


j +1 n


n=1 j =0

j , n
n=1 j =1 n-1

=


-1

n

C

T


n=1 j =0

j , n
n=1 j =1

j +1 n

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

36 / 37


We obtain


µ

,E

=
n=1

(n + 1)|± | - 2|± | = 1 = µ n
n-1

,E

+ B1 .

C
n=1 j =0

T

(j , j +1 ) nn
n

C
T

n-1


j +1 n


n=1 j =0

j , n
n=1 j =1 n-1

=


-1

n

C

T


n=1 j =0

j , n
n=1 j =1

j +1 n
-

=

-1

C

T

µ

,E

+ + , µ,E +

.

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

36 / 37


DE () - T E

-1

C

T

µ

,E

+ + , µ,E +
-1 µB1

- -



inf+ C

T

µ + + , µ +

. (3)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

37 / 37


DE () - T E

-1

C

T

µ

,E

+ + , µ,E +
-1 µB1

- -

Finally, CT () DE () - TE =
0 lim DE () - T E lim sup 0

inf+ C

T

µ + + , µ +

. (3)

-1

+ µB1

inf C

T

µ + + , µ +

-

. (4)

Gershon Wolansky (Technion)

Action principle and OMT

Haifa, 2009

37 / 37