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

Branched

Eulerian

The variational setting

Equivalences

A Benamou-Brenier approach to branched transport
Lorenzo Brasco
Dipartimento di Matematica e Applicazioni "R. Cacciopp oli" Universit` di Nap oli "Federico I I" a

May 14, 2009


Branched

Eulerian

The variational setting

Equivalences

References

Some results of this talk are contained in L. B., G. Buttazzo, F. Santambrogio, A Benamou-Brenier approach to branched transport, submitted (http://cvgmt.sns.it/people/brasco)


Branched

Eulerian

The variational setting

Equivalences

Outline

1

Branched transport: introduction and models An Eulerian point of view on branched transport The variational setting Equivalences with other models

2

3

4


Branched

Eulerian

The variational setting

Equivalences

Some notations
RN compact and convex P () = Borel probability measures over M(; RN ) = RN -valued Radon measures over wp = p -Wasserstein distance wp (0 , 1 ) = min
â 1/p

|x - y |p d (x , y )

: (0 , 1 )

Wp () = p -Wasserstein space over , i.e. P () equipped with wp |µt |wp = limh
0

wp (µt +h , µt ) metric derivative |h|

= exponent between 0 and 1


Branched

Eulerian

The variational setting

Equivalences

Branched transport: what's this?
Transport problems where the cost has a subadditive dependence on the mass, i.e. moving a mass m for a distance costs (m) , with (m1 + m2 ) < (m1 ) + (m2 ) = total cost = typical choice (t ) = t , [0, 1] (m)

Due to concavity, grouping the mass during the transport could lower the total cost = typical optimal structures are tree-shap ed
m
1

m1 m1+ m
2

m

2

m2


Branched

Eulerian

The variational setting

Equivalences

Remark Many natural and artificial transportation systems satisfy this cost saving requirement (root systems in a tree, blood vessels...)

!

This PDF was produced by PStill, licensing the software will remove this mark See http://www.pstill.com or for the MacOS X version http://www.stone.com


Branched

Eulerian

The variational setting

Equivalences

Example: a power supply station
0 = x0 power supply station 1 = k=1 mi xk houses ( k=1 mi = 1) i i

Monge-Kantorovich solution

Branched transport solution

Comment it is better to construct an optimal network of wires (right) to save cost; this is not possible by looking at Monge-Kantorovich (left)


Branched

Eulerian

The variational setting

Equivalences

Some models: Gilbert's weighted oriented graphs
This is only suitable for discrete measures 0 =
k i =1 ai xi

P () and 1 =

m j =1 bj yj

P ()

Transport path between 0 and 1 g weigthed oriented graph consisting of: {vs }s
V H

vertices (comprising xi sources and yj sinks) edges orientations of the edges weigths (i.e. transiting mass on the edge eh ) + Kirchhoff 's Law for circuits

{eh }h - {} {mh }

h h H h H


Branched

Eulerian

The variational setting

Equivalences

Interior vertices
m1 m
2

v m4 m
3

m1 + m2 + m3 = m4

"Boundary" vertices
m1 m1+ m2 = a a
i i

m1 b m2 yj
j

m1+ m2 = b

j

x

i

m

2

Total cost M (g) =
h H mh H1 (eh ) (Gilbert-Steiner energy)


Branched

Eulerian

The variational setting

Equivalences

Some models: Xia's transport path model I
Idea: for the discrete case... g - g vector measure g , = divg = 0 - 1
h H

mh

eh

· dH -- h

1

Kirchhoff 's Law ...for the general case

transp ort path between 0 and 1 if {gn , n , n }n 01 , n i , i = 0, 1 gn i Total cost
M := relaxation of M M () =

N

s.t.

m(x ) d H1 (x ), +,

- if = m H1 , otherwise


Branched

Eulerian

The variational setting

Equivalences

Some models: Xia's transport path model II
Theorem (Xia, Morel-Santambrogio) Let (1 - 1/N , 1] and 0 , 1 P (), then
d (0 , 1 ) := min{M () : div = 0 - 1 } < +

Moreover d defines a distance on P (), equivalent to w1 (and thus to any wp , with 1 p < ) w1 (0 , 1 ) d (0 , 1 ) C w1 (0 , 1 )
N (-1)+1

Remark the exponent N ( - 1) + 1 can not be improved the lower bound is not optimal, actually we have w (Devillanova-Solimini)
1/

d


Branched

Eulerian

The variational setting

Equivalences

Some models: a Lagrangian approach I
Transportation is described through Q probability measures on Lipschitz paths (parametrized on [0, 1], let us say) Constraints (e0 ) Q = 0 , (e1 ) Q = 1 (where et ( ) = (t ) evaluation at t ) Multiplicity (i.e."transiting mass") [x ]Q = Q ({ : x ([0, 1])}) 1 Energy (Bernot-Caselles-Morel)
1

x

E ( Q ) =
Lip ([0,1];) 0

[ (t )]Q-1 | (t )| dt dQ ( )


Branched

Eulerian

The variational setting

Equivalences

Some models: a Lagrangian approach II
If E (Q ) < + and Q gives full mass to injective curves... Gilbert-Steiner energy, again! E ( Q ) =


[x ] d H1 (x ) Q

Theorem (Bernot-Caselles-Morel) For every 0 , 1 , this Lagrangian model is equivalent to Xia's one (i.e. same optimal structures, different description of the same energy) There exist other Lagrangian models (Maddalena-Morel-Soliminia , Bernot-Figalli) that we are neglecting, differing for the definition of the multiplicity: the one chosen here is not local in time
a

This was actually the first!


Branched

Eulerian

The variational setting

Equivalences

Aim of the talk
We want to present a model for branched transport of the type Energy
1

G (µ, v ) =
0

G (µt , vt ) dt with

t µt curve in P () t vt velocity field

Constraints: the continuity equation t µt + divx (vt µt ) = 0 µ0 = 0 , µ1 = 1 in ,

Remark This is Eulerian and dynamical, i.e. an optimal µ provides the evolution in time of the branched transport with its velocity field v , not just the optimal ramified structure


Branched

Eulerian

The variational setting

Equivalences

The Benamou-Brenier formula I
First of all, recall the dynamical formulation for wp (p > 1) Benamou-Brenier [Numer. Math. 84 (2000)]
1

wp (0 , 1 ) = min
0

|vt (x )|p d µt (x ) dt :


t µt + divx (vt µt ) = 0 µ0 = 0 , µ1 = 1

Important It can be reformulated as a convex optimization + linear constraints, introducing t := vt · µt (momentum) = |vt |p µt = |t |p µ Thanks to the Disintegration Theorem... (µ, ) can be thought as measures on [0, 1] â disintegrating as µ= µt dt and = t dt
1-p t

convex


Branched

Eulerian

The variational setting

Equivalences

The Benamou-Brenier formula II
|y |p x 1-p , 0, fp (x , y ) = +, if x > 0, y RN , if x = 0, y = 0, otherwise

is jointly convex and 1-homogeneous The functional can be rewritten as follows Benamou-Brenier functional Fp (µ, ) =
[0,1]â

fp

dµ d , dm dm

dm

Comment Fp l.s.c. and does not depend on the choice of m

wp (0 , 1 ) = min Fp (µ, ) : t µ + divx = 0 0 - 1 1


Branched

Eulerian

The variational setting

Equivalences

The Benamou-Brenier formula III
Remark By its very definition Fp (µ, ) < + = and in this case Fp (µ, ) =
[0,1]â

µ

d dµ

p

dµ

If moreover µ = Fp (µ, ) =

µt dt , then =
1 0

t dt with t = vt · µt and
1

d t d µt

p

d µt dt =
0

|vt |p d µt dt


Branched

Eulerian

The variational setting

Equivalences

A possible variant for branched transport: heuristics
We consider the lo cal and l.s.c. functional on measures if is atomic |({x })| d #(x ), g () = +, otherwise Energy? For µ = µt dt and =
1

t dt with d t d µt
1/

t

µ

t

1 t

G (µ, ) =
0

g



µ

dt =
0

g (|vt |1/ µt ) dt

This is a Gilbert-Steiner energy!
1

G (µ, ) =
0 k N

|vt (x

k ,t

)| µt ({xk ,t }) dt


Branched

Eulerian

The variational setting

Equivalences

A possible variant for branched transport: setting
D = admissible pairs (µ, ) µ C ([0, 1]; P ()) L1 ([0, 1]; M(; RN )) Dynamical branched energy G (µt , t ) =


t µt + divx t = 0 in

|vt (x )|µt ({x }) d #(x ) +
1 0

if t = vt · µt , if t µt

G (µ, ) = Important remark G (µ, ) < + = =

G (µt , t ) dt , (µ, ) D

µt atomic t µ and µt atomic on {|vt (x )| > 0}


Branched

Eulerian

The variational setting

Equivalences

Main result

Theorem (B.-Buttazzo-Santambrogio) For every 0 , 1 P (), the minimization problem B (0 , 1 ) = min {G (µ, ) : µ0 = 0 , µ1 = 1 }
(µ,)D

admits a solution Remark 1 The proof uses Direct Methods...l.s.c.? coercivity? As always, it is a matter of choosing the right top ology Remark 2 Observe that the problem is not convex, but rather concave


Branched

Eulerian

The variational setting

Equivalences

Choice of the topology

Proposal: pointwise convergence What about "µn µt for every t and t

n t

t for a.e. t "?

Answer: NO Good for l.s.c. (you simply apply Fatou Lemma, because G is l.s.c) but not so good for coercivity (how can we infer compactness from G C ?) Choice: weak topology (µn , n ) (µ, ) (as measures on [0, 1] â )


Branched

Eulerian

The variational setting

Equivalences

The basic inequalities
If (µ, ) D such that (B .I .)1 G (µt , t ) =
i

µ and t = vt · µ

t

µt ({xi }) |vt (xi )| =
i

µt ({xi }) |vt (xi )|1/ = vt




i

µt ({xi }) |vt (xi )|

1/

L1

/

(µt )

|µt |w

1/

(B .I .)2 G (µ, ) =
1 0

G (µt , t ) dt

1 0

|t |() dt = ||([0, 1] â )

Remark supt G C = ||([0, 1] â ) C and µt Lipschitz in W1/


Branched

Eulerian

The variational setting

Equivalences

Proof of the main result I

Stage 1 ­ Exctraction of a subsequence {(µn , n )} D minimizing sequence we can assume G (µn , n ) C for every n G 1-homogeneous w.r.t. vt (i.e. reparametrization invariant) (µn , n ) (µn , n ), with µn = µ ~~ ~s ~ µ and n
n t(s )

~s and n = t (s ) ·

n t(s )

choose t s.t. G (µn , n ) G (µn , n ) = G (µn , n ) C ~s ~s ~~ = µ ~
n

(thanks to (B .I .)1 and (B .I .)2 )


Branched

Eulerian

The variational setting

Equivalences

Proof of the main result II

Stage 2 ­ Admissibility of the limit clearly µ = µt dt (uniform limit of continuous curves) t dt , we use l.s.c. of Benamou-Brenier
n

to show that = functional F =
1/

(µ, ) lim inf

F

1/

( µn , n ) ~~

(B .I .)1



C

µ and =

t dt

(µ, ) still solves the continuity equation = (µ, ) D µ0 = 0 and µ1 = 1


Branched

Eulerian

The variational setting

Equivalences

Proof of the main result III (conclusion)

Stage 3 ­ l.s.c. along a minimizing sequence ~ remember that n = v n · µn and G (µn , n ) C ~~ ~~ define mn =
i

|vtn (xi ,t )| µn ({xi ,t }) ~ ~t

xi

,t

dt M([0, 1] â )

mn ([0, 1] â ) = G (µn , n ) C ~~ = mn m and m = mt dt
1 0

mn ([0, 1] â ) m([0, 1] â ) = G (µn , n ) ~~ show mt () G (µt , t ) (a little bit delicate) = G (µ, ) lim inf
n

mt () dt

G (µn , n ) = inf G ~~


Branched

Eulerian

The variational setting

Equivalences

Equivalences with other models
Theorem (B.-Buttazzo-Santambrogio) B (0 , 1 ) = min{E (Q ) : (ei ) Q = i } = d (0 , 1 ) As always, we have equivalence of the problems, not just equality of the minima Recall that
1

E ( Q ) =
Lip ([0,1];) 0

[ (t )]Q-1 | (t )| dt dQ ( )

Remark In order to compare the two models, we need to switch from curves of measures to measures on curves (and back!)


Branched

Eulerian

The variational setting

Equivalences

Some preliminary comments
Alert! - Transiting mass in our model = µt ({x }) (local in space/time) - Transiting mass in E model = [x ]Q (not local in time) We will need the following Theorem (Superposition principle (AGS, Theorem 8.2.1)) Let (µ, v ) solve the continuity equation, with vt pp (µt ) integrable L in time. Then µt = (et ) Q with Q concentrated on solutions of the ODE (t ) = vt ( (t )) Comment This is a probabilistic version of the method of characteristics


Branched

Eulerian

The variational setting

Equivalences

Sketch of the proof: B (0 , 1 ) d (0 , 1 )
Step 1 (µ, ) optimal = = v · µ and Step 2 - superposition principle Q s.t. µt = (et )# Q and (t ) = vt ( (t )) for Q -a.e. Step 3 - comparison of the multiplicities µt = (et ) Q = [x ]Q Q ({ : (t ) = x }) = µt ({x })
(B .I .)1 1 0

vt

L

1/

(µt )

dt B (0 , 1 )

[ (t )]-1 | (t )| dQ ( ) = Q

Step 2

[x ]

-1 Q

|vt (x )| d µt (x )
-1

Step 3

µt ({x })

|vt (x )| d µt (x )


Branched

Eulerian

The variational setting

Equivalences

Sketch of the proof: B (0 , 1 ) d (0 , 1 )
Step 0 ­ approximation Approximate (0 , 1 ) with (n , n ) (finite sums of Dirac masses) 01 s.t. d (n , n ) d (0 , 1 ) 01 Remark: why approximation? Q optimal s.t. [ (t )]Q = Q ({ (t ) = (t )}) the mass is synchronized (this is true if 0 is finitely atomic) Step 1 ­ curve in P () µt := (et ) Q and disintegrate Q = concentrated on { : (t ) = x })
t t Qx d µt (x ) (i.e. Qx is


Branched

Eulerian

The variational setting

Equivalences

Sketch of the proof: B (0 , 1 ) d (0 , 1 )
Step 2 ­ velocity field vt (x ) := Step 3 (µ, v · µ) D and G (µ, v · µ) E (Q ) = d (n , n ), with 01 µ0 = n and µ1 = n 0 1 Step 4 Putting all together, we have B (0 , 1 ) lim inf B (n , n ) lim d (n , n ) = d (0 , 1 ) 01 01
n n { : (t )=x } t (t ) dQx ( ) (average velocity)


Branched

Eulerian

The variational setting

Equivalences

A final remark: comparison of d and w1
Taking (µ, ) optimal for B (0 , 1 )
1 (B .I .)

/

|µt |w
0

1/

dt



1

B (0 , 1 )

equivalence

=

d (0 , 1 )

i.e. we have another proof of w1/ (0 , 1 ) d (0 , 1 ) Remark d and w1/ have exactly the same scaling d = m


w1/ =

m

1/




Branched

Eulerian

The variational setting

Equivalences

Further readings

- Standard reference on branched transport M. Bernot, V. Caselles, J.-M. Morel Optimal transportation networks ­ Models and theory, Springer Lecture Notes (2009) - Other models employing curves in Wasserstein spaces (but avoiding the use of the continuity equation) have been studied A. Brancolini, G. Buttazzo, F. Santambrogio, Path functionals over Wasserstein spaces, JEMS (2006) L. B., F. Santambrogio, An equivalent path functional formulation of branched transportation problems, accepted