no. 3
Monotone discretization of the Monge–Ampère equation of optimal transport
ESAIM: Mathematical Modelling and Numerical Analysis , Tome 56 (2022) no. 3, pp. 815-865

We design a monotone finite difference discretization of the second boundary value problem for the Monge–Ampère equation, whose main application is optimal transport. We prove the existence of solutions to a class of monotone numerical schemes for degenerate elliptic equations whose sets of solutions are stable by addition of a constant, and we show that the scheme that we introduce for the Monge–Ampère equation belongs to this class. We prove the convergence of this scheme, although only in the setting of quadratic optimal transport. The scheme is based on a reformulation of the Monge–Ampère operator as a maximum of semilinear operators. In dimension two, we recommend to use Selling’s formula, a tool originating from low-dimensional lattice geometry, in order to choose the parameters of the discretization. We show that this approach yields a closed-form formula for the maximum that appears in the discretized operator, which allows the scheme to be solved particularly efficiently. We present some numerical results that we obtained by applying the scheme to quadratic optimal transport problems as well as to the far field refractor problem in nonimaging optics.

DOI : 10.1051/m2an/2022029
Classification : 65N06, 65N12, 35J70, 35J96
Keywords: Monge–Ampère equation, optimal transport, monotone finite difference schemes, convergence analysis 
@article{M2AN_2022__56_3_815_0,
     author = {Bonnet, Guillaume and Mirebeau, Jean-Marie},
     title = {Monotone discretization of the {Monge{\textendash}Amp\`ere} equation of optimal transport},
     journal = {ESAIM: Mathematical Modelling and Numerical Analysis },
     pages = {815--865},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {3},
     doi = {10.1051/m2an/2022029},
     mrnumber = {4411481},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/m2an/2022029/}
}
TY  - JOUR
AU  - Bonnet, Guillaume
AU  - Mirebeau, Jean-Marie
TI  - Monotone discretization of the Monge–Ampère equation of optimal transport
JO  - ESAIM: Mathematical Modelling and Numerical Analysis 
PY  - 2022
SP  - 815
EP  - 865
VL  - 56
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/m2an/2022029/
DO  - 10.1051/m2an/2022029
LA  - en
ID  - M2AN_2022__56_3_815_0
ER  - 
%0 Journal Article
%A Bonnet, Guillaume
%A Mirebeau, Jean-Marie
%T Monotone discretization of the Monge–Ampère equation of optimal transport
%J ESAIM: Mathematical Modelling and Numerical Analysis 
%D 2022
%P 815-865
%V 56
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/m2an/2022029/
%R 10.1051/m2an/2022029
%G en
%F M2AN_2022__56_3_815_0
Bonnet, Guillaume; Mirebeau, Jean-Marie. Monotone discretization of the Monge–Ampère equation of optimal transport. ESAIM: Mathematical Modelling and Numerical Analysis , Tome 56 (2022) no. 3, pp. 815-865. doi: 10.1051/m2an/2022029

[1] G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal. 4 (1991) 271–283. | MR | Zbl | DOI

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

[3] J.-D. Benamou and V. Duval, Minimal convex extensions and finite difference discretization of the quadratic Monge—Kantorovich problem. Eur. J. Appl. Math. 30 (2019) 1041–1078. | MR | DOI

[4] J.-D. Benamou, B. D. Froese and A. M. Oberman, Numerical solution of the Optimal Transportation problem using the Monge-Ampère equation. J. Comput. Phys. 260 (2014) 107–126. | MR | DOI

[5] J.-D. Benamou, F. Collino and J.-M. Mirebeau, Monotone and consistent discretization of the Monge-Ampère operator. Math. Comp. 85 (2016) 2743–2775. | MR | DOI

[6] J.-D. Benamou, W. Ijzerman and G. Rukhaia, An entropic optimal transport numerical approach to the reflector problem (2020). HAL preprint . | HAL

[7] J. F. Bonnans, É. Ottenwaelter and H. Zidani, A fast algorithm for the two dimensional HJB equation of stochastic control. ESAIM: M2AN 38 (2004) 723–735. | MR | Zbl | Numdam | DOI

[8] J. F. Bonnans, G. Bonnet and J.-M. Mirebeau, A linear finite-difference scheme for approximating Randers distances on Cartesian grids (2021). HAL preprint . | HAL | MR

[9] J. F. Bonnans, G. Bonnet and J.-M. Mirebeau, Monotone and second order consistent scheme for the two dimensional Pucci equation. In: Numerical Mathematics and Advanced Applications ENUMATH 2019, edited by F. J. Vermolen and C. Vuik. Springer, Cham (2021) 733–742. | MR | DOI

[10] Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (1991) 375–417. | MR | Zbl | DOI

[11] K. Brix, Y. Hafizogullari and A. Platen, Solving the Monge-Ampère equations for the inverse reflector problem. Math. Models Methods Appl. Sci. 25 (2015) 803–837. | MR | DOI

[12] L. A. Caffarelli and V. I. Oliker, Weak solution of one inverse problem in geometric optics. J. Math. Sci. 154 (2008) 39–49. | MR | Zbl | DOI

[13] M. Carter, Foundations of Mathematical Economics. MIT Press, Cambridge, MA (2001). | MR | Zbl

[14] Y. Chen, J. W. L. Wan and J. Lin, Monotone mixed finite difference scheme for Monge-Ampère equation. J. Sci. Comput. 76 (2018) 1839–1867. | MR | DOI

[15] J. H. Conway and N. J. A. Sloane, Low-dimensional lattices. III. Perfect forms. Proc. Roy. Soc. London Ser. A 418 (1988) 43–80. | MR | Zbl | DOI

[16] M. G. Crandall, H. Ishii and P.-L. Lions, User’s guide to viscosity solutions of second order partial differential equations. Bull. Amer. Math. Soc. 27 (1992) 1–67. | MR | Zbl | DOI

[17] M. Cuturi, Sinkhorn distances: lightspeed computation of optimal transport. In: NIPS’13: Proceedings of the 26th International Conference on Neural Information Processing Systems, edited by C. J. C. Burges, L. Bottou, M. Welling and Z. Ghahramani. Vol. 2. Curran Associates Inc., Red Hook, NY (2013) 2292–2300.

[18] P. M. M. De Castro, Q. Mérigot and B. Thibert, Far-field reflector problem and intersection of paraboloids. Numer. Math. 134 (2016) 389–411. | MR | DOI

[19] R. De Leo, C. E. Gutiérrez and H. Mawi, On the numerical solution of the far field refractor problem. Nonlinear Anal. 157 (2017) 123–145. | MR | DOI

[20] G. De Philippis and A. Figalli, The Monge-Ampère equation and its link to optimal transportation. Bull. Amer. Math. Soc. 51 (2014) 527–580. | MR | Zbl | DOI

[21] F. Desquilbet, J. Cao, P. Cupillard, L. Métivier and J.-M. Mirebeau, Single pass computation of first seismic wave travel time in three dimensional heterogeneous media with general anisotropy. J. Sci. Comput. 89 (2021) 1–37. | MR | DOI

[22] L. C. Evans and R. F. Gariepy, Measure Theory and Fine Properties of Functions. Studies in Advanced Mathematics. CRC Press, Boca Raton, FL (1992). | MR | Zbl

[23] X. Feng and M. Jensen, Convergent semi-Lagrangian methods for the Monge-Ampère equation on unstructured grids. SIAM J. Numer. Anal. 55 (2017) 691–712. | MR | DOI

[24] A. Figalli and G. Loeper, C 1 regularity of solutions of the Monge-Ampère equation for optimal transport in dimension two. Calc. Var. Part. Differ. Equ. 35 (2009) 537–550. | MR | Zbl | DOI

[25] B. D. Froese and A. M. Oberman, Convergent filtered schemes for the Monge-Ampère partial differential equation. SIAM J. Numer. Anal. 51 (2013) 423–444. | MR | Zbl | DOI

[26] B. Froese Hamfeldt, Convergence framework for the second boundary value problem for the Monge-Ampère equation. SIAM J. Numer. Anal. 57 (2019) 945–971. | MR | DOI

[27] B. Froese Hamfeldt, J. Lesniewski, A convergent finite difference method for computing minimal Lagrangian graphs. Preprint (2021). | arXiv | MR

[28] B. Froese Hamfeldt and A. G. R. Turnquist, Convergent numerical method for the reflector antenna problem via optimal transport on the sphere. J. Optical Soc. Amer. A 38 (2021) 1704–1713. | DOI

[29] C. E. Gutiérrez, The Monge-Ampère Equation. Vol. 89 of Progress in Nonlinear Differential Equations and Their Applications. Birkhäuser, Basel (2016). | MR | Zbl | DOI

[30] C. E. Gutiérrez and Q. Huang, The refractor problem in reshaping light beams. Arch. Ration. Mech. Anal. 193 (2009) 423–443. | MR | Zbl | DOI

[31] C. E. Gutiérrez and Q. Huang, The near field refractor. Ann. Inst. H. Poincaré Anal. Non Linéaire 31 (2014) 655–684. | MR | Zbl | Numdam | DOI

[32] H. Ishii, P.-L. Lions, Viscosity solutions of fully nonlinear second-order elliptic partial differential equations. J. Differ. Equ. 83 (1990) 26–78. | MR | Zbl | DOI

[33] J. Kitagawa, Q. Mérigot and B. Thibert, Convergence of a Newton algorithm for semi-discrete optimal transport. J. Eur. Math. Soc. 21 (2019) 2603–2651. | MR | DOI

[34] S. A. Kochengin and V. I. Oliker, Determination of reflector surfaces from near-field scattering data. Inverse Prob. 13 (1997) 363–373. | MR | Zbl | DOI

[35] N. V. Krylov, Nonlinear Elliptic and Parabolic Equations of Second Order. Vol. 7 of Mathematics and its Applications. Springer, Netherlands (1987). | MR | Zbl

[36] P.-L. Lions, Two remarks on Monge-Ampère equations. Ann. Mat. Pura Appl. 142 (1985) 263–275. | MR | Zbl | DOI

[37] X.-N. Ma, N. S. Trudinger and X.-J. Wang, Regularity of potential functions of the optimal transportation problem. Arch. Ration. Mech. Anal. 177 (2005) 151–183. | MR | Zbl | DOI

[38] J.-M. Mirebeau, Efficient fast marching with Finsler metrics. Numer. Math. 126 (2014) 515–557. | MR | Zbl | DOI

[39] J.-M. Mirebeau, Discretization of the 3d Monge-Ampère operator, between wide stencils and power diagrams. ESAIM: M2AN 49 (2015) 1511–1523. | MR | Zbl | Numdam | DOI

[40] J.-M. Mirebeau, Riemannian fast-marching on cartesian grids, using voronoi’s first reduction of quadratic forms. SIAM J. Numer. Anal. 57 (2019) 2608–2655. | MR | DOI

[41] A. Oberman, The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. 135 (2007) 1689–1694. | MR | Zbl | DOI

[42] A. J. Salgado and W. Zhang, Finite element approximation of the Isaacs equation. ESAIM: M2AN 53 (2019) 351–374. | MR | Zbl | Numdam | DOI

[43] E. Selling, Uber die binären und ternären quadratischen Formen. J. Reine Angew. Math. 77 (1874) 143–229. | MR | JFM

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

[45] C. Villani, Optimal Transport. Vol. 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin (2009). | MR | Zbl | DOI

Cité par Sources :