Monotone discretization of the Monge-Ampère equation of optimal transport. (English) Zbl 1496.65197
A monotone difference discretization of the Monge-Ampere equation associated with an optimal transport problem is proposed. The authors prove the existence of the solution of the scheme under suitable assumptions. The proof of the convergence of the scheme is given but only in the quadratic optimal transport setting. This new scheme is based on a reformulation of the Monge-Ampere operator as a maximum of semilinear operators. The scheme is applied to the far field refractor problem in nonimaging optics.
Reviewer: Ljiljana Teofanov (Novi Sad)
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 65N12 | Stability and convergence of numerical methods for boundary value problems involving PDEs |
| 35J70 | Degenerate elliptic equations |
| 35J96 | Monge-Ampère equations |
Keywords:
Monge-Ampère equation; optimal transport; monotone finite difference schemes; convergence analysisReferences:
| [1] | G. Barles and P.E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal. 4 (1991) 271-283. · Zbl 0729.65077 |
| [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. · Zbl 0968.76069 · doi:10.1007/s002110050002 |
| [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. · Zbl 1427.65326 · doi:10.1017/S0956792518000451 |
| [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. · Zbl 1349.65554 · doi:10.1016/j.jcp.2013.12.015 |
| [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. · Zbl 1416.65400 · doi:10.1090/mcom/3080 |
| [6] | J.-D. Benamou, W. Ijzerman and G. Rukhaia, An entropic optimal transport numerical approach to the reflector problem (2020). HAL preprint hal-02539799. · Zbl 1473.49048 |
| [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. · Zbl 1130.93433 · doi:10.1051/m2an:2004034 |
| [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-03125879. |
| [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. · Zbl 1475.65164 · doi:10.1007/978-3-030-55874-1_72 |
| [10] | Y. Brenier, Polar factorization and monotone rearrangement of vector-valued functions. Comm. Pure Appl. Math. 44 (1991) 375-417. · Zbl 0738.46011 · doi:10.1002/cpa.3160440402 |
| [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. · Zbl 1326.35365 · doi:10.1142/S0218202515500190 |
| [12] | L.A. Caffarelli and V.I. Oliker, Weak solution of one inverse problem in geometric optics. J. Math. Sci. 154 (2008) 39-49. · Zbl 1202.78003 · doi:10.1007/s10958-008-9152-x |
| [13] | M. Carter, Foundations of Mathematical Economics. MIT Press, Cambridge, MA (2001). · Zbl 1047.91001 |
| [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. · Zbl 1402.65133 · doi:10.1007/s10915-018-0685-y |
| [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. · Zbl 0655.10022 · doi:10.1098/rspa.1988.0073 |
| [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. · Zbl 0755.35015 · doi:10.1090/S0273-0979-1992-00266-5 |
| [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. · Zbl 1354.78003 · doi:10.1007/s00211-015-0780-z |
| [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. · Zbl 1369.78175 · doi:10.1016/j.na.2017.03.009 |
| [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. · Zbl 1515.35005 · doi:10.1090/S0273-0979-2014-01459-4 |
| [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. · Zbl 1493.65172 · doi:10.1007/s10915-021-01607-8 |
| [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). · Zbl 0804.28001 |
| [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. · Zbl 1362.65117 |
| [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. · Zbl 1170.35400 · doi:10.1007/s00526-009-0222-9 |
| [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. · Zbl 1268.35070 |
| [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. · Zbl 1418.35207 · doi:10.1137/18M1201913 |
| [27] | B. Froese Hamfeldt, J. Lesniewski, A convergent finite difference method for computing minimal Lagrangian graphs. Preprint arXiv:2102.10159 (2021). · Zbl 1493.65173 |
| [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. · Zbl 07515866 · doi:10.1364/JOSAA.439679 |
| [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). · Zbl 1356.35004 · doi:10.1007/978-3-319-43374-5 |
| [30] | C.E. Gutiérrez and Q. Huang, The refractor problem in reshaping light beams. Arch. Ration. Mech. Anal. 193 (2009) 423-443. · Zbl 1173.78005 · doi:10.1007/s00205-008-0165-x |
| [31] | C.E. Gutiérrez and Q. Huang, The near field refractor. Ann. Inst. H. Poincaré Anal. Non Linéaire 31 (2014) 655-684. · Zbl 1301.78001 · doi:10.1016/j.anihpc.2013.07.001 |
| [32] | H. Ishii, P.-L. Lions, Viscosity solutions of fully nonlinear second-order elliptic partial differential equations. J. Differ. Equ. 83 (1990) 26-78. · Zbl 0708.35031 · doi:10.1016/0022-0396(90)90068-Z |
| [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. · Zbl 1439.49053 · doi:10.4171/JEMS/889 |
| [34] | S.A. Kochengin and V.I. Oliker, Determination of reflector surfaces from near-field scattering data. Inverse Prob. 13 (1997) 363-373. · Zbl 0871.35107 · doi:10.1088/0266-5611/13/2/011 |
| [35] | N.V. Krylov, Nonlinear Elliptic and Parabolic Equations of Second Order. Vol. 7 of Mathematics and its Applications. Springer, Netherlands (1987). · Zbl 0619.35004 · doi:10.1007/978-94-010-9557-0 |
| [36] | P.-L. Lions, Two remarks on Monge-Ampère equations. Ann. Mat. Pura Appl. 142 (1985) 263-275. · Zbl 0594.35023 · doi:10.1007/BF01766596 |
| [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. · Zbl 1072.49035 · doi:10.1007/s00205-005-0362-9 |
| [38] | J.-M. Mirebeau, Efficient fast marching with Finsler metrics. Numer. Math. 126 (2014) 515-557. · Zbl 1297.65074 · doi:10.1007/s00211-013-0571-3 |
| [39] | J.-M. Mirebeau, Discretization of the 3d Monge-Ampère operator, between wide stencils and power diagrams. ESAIM: M2AN 49 (2015) 1511-1523. · Zbl 1330.65161 · doi:10.1051/m2an/2015016 |
| [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. · Zbl 1447.65114 · doi:10.1137/17M1127466 |
| [41] | A. Oberman, The convex envelope is the solution of a nonlinear obstacle problem. Proc. Amer. Math. Soc. 135 (2007) 1689-1694. · Zbl 1190.35107 · doi:10.1090/S0002-9939-07-08887-9 |
| [42] | A.J. Salgado and W. Zhang, Finite element approximation of the Isaacs equation. ESAIM: M2AN 53 (2019) 351-374. · Zbl 1433.65311 · doi:10.1051/m2an/2018067 |
| [43] | E. Selling, Uber die binären und ternären quadratischen Formen. J. Reine Angew. Math. 77 (1874) 143-229. · JFM 06.0128.01 |
| [44] | C. Villani, Topics in Optimal Transportation. Vol. 58 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI (2003). · Zbl 1106.90001 |
| [45] | C. Villani, Optimal Transport. Vol. 338 of Grundlehren der mathematischen Wissenschaften. Springer, Berlin (2009). · Zbl 1156.53003 · doi:10.1007/978-3-540-71050-9 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
