Optimal partial transport problem with Lagrangian costs

Igbida, Noureddine; Nguyen, Van Thanh

ESAIM: Mathematical Modelling and Numerical Analysis , Tome 52 (2018) no. 5, pp. 2109-2132.

We introduce a dual dynamical formulation for the optimal partial transport problem with Lagrangian costs

$$c_L(x,y):=\underset{\begin{array}{c}\xi \in \mathrm{Lip}([0,1];{ℝ}^N)\end{array}}{inf}\{{\int }_0^{1}L(\xi \left(t\right),\dot{\xi }\left(t\right))\mathrm{d}t:\xi \left(0\right)=x,\xi \left(1\right)=y\}$$

based on a constrained Hamilton–Jacobi equation. Optimality condition is given that takes the form of a system of PDEs in some way similar to constrained mean field games. The equivalent formulations are then used to give numerical approximations to the optimal partial transport problem via augmented Lagrangian methods. One of advantages is that the approach requires only values of $L$ and does not need to evaluate $c_L(x,y)$, for each pair of endpoints $x$ and $y$, which comes from a variational problem. This method also provides at the same time active submeasures and the associated optimal transportation.

Mots clés : Optimal transport, optimal partial transport, Fenchel–Rockafellar duality, augmented Lagrangian method

[1] L. Ambrosio, N. Gigli and G. Savaré, Gradient Flows in Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics. ETH Zürich, Birkhäuser (2005). | MR | Zbl

[2] J.W. Barrett and L. Prigozhin, Partial ¹ Monge–Kantorovich problem: variational formulation and numerical approximation. Interfaces Free Bound. 11 (2009) 201–238. | DOI | MR | Zbl

[3] J.D. Benamou and Y. Brenier, A computational fluid mechanics solution to the Monge–Kantorovich mass transfer problem. Numer. Math. 84 (2000) 375–393. | DOI | MR | Zbl

[4] J.D. Benamou and G. Carlier, Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations. J. Optim. Theory Appl. 167 (2015) 1–26. | DOI | MR | Zbl

[5] J.D. Benamou, G. Carlier, M. Cuturi, L. Nenna and G. Peyré, Iterative Bregman projections for regularized transportation problems. SIAM J. Sci. Comput. 37 (2015) A1111–A1138. | DOI | MR | Zbl

[6] J.D. Benamou, G. Carlier and R. Hatchi, A numerical solution to Monge’s problem with a Finsler distance cost. ESAIM: M2AN (2017) DOI:. | DOI | MR

[7] J.D. Benamou, G. Carlier and F. Santambrogio, Variational Mean Field Games. Vol. 1 of Active Particles. Springer (2017) 141–171. | MR

[8] G. Bouchitté, G. Buttazzo and P. Seppercher, Energy with respect to a measure and applications to low dimensional structures. Calc. Var. 5 (1997) 37–54. | DOI | MR | Zbl

[9] G. Bouchitté, G. Buttazzo and P. Seppecher, Shape optimization solutions via Monge–Kantorovich equation. C. R. Acad. Sci. Paris Sér. I Math. 324 (1997) 1185–1191. | DOI | MR | Zbl

[10] L.M. Briceno-Arias, D. Kalise and F.J. Silva, Proximal Methods for Stationary Mean Field Games with Local Couplings. SIAM J. Control Optim. 56 (2018) 801–836. | MR

[11] L. Caffarelli and R.J. Mccann, Free boundaries in optimal transport and Monge–Ampere obstacle problems. Ann. Math. 171 (2010) 673–730 | DOI | MR | Zbl

[12] P. Cannarsa and C. Sinestrari, Semiconcave Functions, Hamilton–Jacobi Equations, and Optimal Control. Vol. 58 of Progress Nonlin. Differ. Equ. Appl. Springer (2004). | MR | Zbl

[13] P. Cardaliaguet, Weak solutions for first order mean field games with local coupling. Vol. 11 of Analysis and Geometry in Control Theory and its Applications. Springer (2015) 111–158. | MR | Zbl

[14] P. Cardaliaguet and P.J. Graber, Mean field games systems of first order. ESAIM: COCV 21 (2015) 690–722. | Numdam | MR | Zbl

[15] P. Cardaliaguet, G. Carlier and B. Nazaret, Geodesics for a class of distances in the space of probability measures. Calc. Var. Partial Differ. Equ. 48 (2013) 395–420. | MR | Zbl

[16] P. Cardaliaguet, A.R. Mészáros and F. Santambrogio, First order mean field games with density constraints: pressure equals price. SIAM J. Control Optim. 54 (2016) 2672–709. | DOI | MR | Zbl

[17] S. Chen and E. Indrei, On the regularity of the free boundary in the optimal partial transport problem for general cost functions. J. Differ. Equ. 258 (2015) 2618–2632. | DOI | MR | Zbl

[18] L. Chizat, G. Peyré, B. Schmitzer and F.X. Vialard, Scaling Algorithms for Unbalanced Transport Problems. Preprint (2016). | arXiv | MR

[19] G. Davila and Y.H. Kim, Dynamics of optimal partial transport. Calc. Var. Partial Differ. Equ. 55 (2016) 116. | MR

[20] J. Eckstein and D.P. Bertsekas, On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55 (1992) 293–318. | DOI | MR | Zbl

[21] I. Ekeland and R. Teman, Convex analysis and variational problems, in Studies in Mathematics and Its Applications, North-Holland American Elsevier, New York (1976). | MR | Zbl

[22] L.C. Evans, Partial differential equations, 2nd edn. Vol. 19 of Graduate Studies in Mathematics. American Mathematical Society (2010). | MR | Zbl

[23] A. Figalli, The optimal partial transport problem. Arch. Ration. Mech. Anal. 195 (2010) 533–560. | DOI | MR | Zbl

[24] M. Fortin and R. Glowinski, Augmented Lagrangian methods: applications to the numerical solution of boundary-value problems. Vol. 15 of Studies in Mathematics and Its Applications. North-Holland (1983). | MR | Zbl

[25] R. Glowinski and P. Le Tallec, Augmented Lagrangian and operator-splitting methods in nonlinear mechanics. Vol. 9 of Studies in Applied and Numerical Mathematics. SIAM (1989). | DOI | MR | Zbl

[26] F. Hecht, New development in FreeFem++. J. Numer. Math. 20 (2012) 251–266. | DOI | MR | Zbl

[27] M. Huang, P.E. Caines and R.P. Malhamé, Large-population cost-coupled LQG problems with nonuniform agents: individual-mass behavior and decentralized ε-Nash equilibria. IEEE Trans. Automat. Control 52 (2007) 1560–1571. | DOI | MR | Zbl

[28] N. Igbida and V.T. Nguyen, Optimal partial mass transportation and obstacle Monge–Kantorovich equation. J. Differ. Equ. 264 (2018) 6380–6417. | MR | Zbl

[29] N. Igbida and V.T. Nguyen, Augmented Lagrangian method for optimal partial transportation. IMA J. Numer. Anal. 38 (2018) 156–183. | DOI | MR | Zbl

[30] E. Indrei, Free boundary regularity in the optimal partial transport problem. J. Funct. Anal. 264 (2013) 2497–2528. | DOI | MR | Zbl

[31] C. Jimenez, Dynamic formulation of optimal transport problems. J. Convex Anal. 15 (2008) 593–622. | MR | Zbl

[32] J.M. Lasry and P.L. Lions, Jeux à champ moyen I. Le cas stationnaire. C. R. Math. Acad. Sci. Paris 343 (2006) 619–625. | DOI | MR | Zbl

[33] J.M. Lasry and P.L. Lions, Jeux à champ moyen II. Horizon fini et controle optimal. C. R. Math. Acad. Sci. Paris 343 (2006) 679–684. | DOI | MR | Zbl

[34] J.M. Lasry and P.L. Lions, Mean field games. Jpn J. Math. 2 (2007) 229–260. | DOI | MR | Zbl

[35] B. Maury, A. Roudneff-Chupin and F. Santambrogio, A macroscopic crowd motion model of gradient flow type. Math. Models Methods Appl. Sci. 20 (2010) 1787–1821. | DOI | MR | Zbl

[36] A.R. Mészáros and F.J. Silva, A variational approach to second order mean field games with density constraints: the stationary case. J. Math. Pures Appl. 104 (2015) 1135–1159. | DOI | MR | Zbl

[37] A.R. Mészáros and F.J. Silva, On the variational formulation of some stationary second order mean field games systems. SIAM J. Math. Anal. 50 (2018) 1255–1277. | MR

[38] G.D. Philippis, A.R. Mészáros, F. Santambrogio and B. Velichkov, BV estimates in optimal transportation and applications. Arch. Ration. Mech. Anal. 219 (2016) 829–860. | DOI | MR | Zbl

[39] W. Rudin, Real and Complex Analysis. McGraw-Hill Book Co., New York (1987). | MR | Zbl

[40] F. Santambrogio, A modest proposal for MFG with density constraints. Netw. Heterog. Media 7 (2012) 337–347. | DOI | MR | Zbl

[41] F. Santambrogio, Optimal Transport for Applied Mathematicians. Vol. 87 of Progress in Nonlinear Differential Equations and Their Applications. Birkhäuser (2015). | DOI | MR | Zbl

[42] C. Villani, Topics in Optimal Transportation. Vol. 58 of Graduate Studies in Mathematics. American Mathematical Society (2003). | MR | Zbl

[43] C. Villani, Optimal Transport, Old and New. Vol. 338 of Grundlehren des Mathematischen Wissenschaften (Fundamental Principles of Mathematical Sciences). Springer, New York (2009). | MR | Zbl