The second boundary value problem for a discrete Monge-Ampère equation. (English) Zbl 1526.65050
Summary: In this work we propose a discretization of the second boundary condition for the Monge-Ampère equation arising in geometric optics and optimal transport. The discretization we propose is the natural generalization of the popular Oliker-Prussner method proposed in 1988. For the discretization of the differential operator, we use a discrete analogue of the subdifferential. Existence, unicity and stability of the solutions to the discrete problem are established. Convergence results to the continuous problem are given.
MSC:
| 65N06 | Finite difference methods for boundary value problems involving PDEs |
| 35J96 | Monge-Ampère equations |
| 78A05 | Geometric optics |
| 52B55 | Computational aspects related to convexity |
References:
| [1] | Aliprantis, C.D., Tourky, R.: Cones and duality. Graduate Studies in Mathematics, vol. 84. American Mathematical Society, Providence, RI (2007) · Zbl 1127.46002 |
| [2] | Aurenhammer, F.; Hoffmann, F.; Aronov, B., Minkowski-type theorems and least-squares clustering, Algorithmica, 20, 1, 61-76 (1998) · Zbl 0895.68135 · doi:10.1007/PL00009187 |
| [3] | Auslender, A.; Teboulle, M., Asymptotic Cones and Functions in Optimization and Variational Inequalities (2006), Berlin: Springer, Berlin · Zbl 1017.49001 |
| [4] | Awanou, G.: Convergence of a damped Newton’s method for discrete Monge-Ampère functions with a prescribed asymptotic cone. arXiv: http://arxiv.org/abs/1911.00260 (2019) |
| [5] | Awanou, G., Computational nonimaging geometric optics: Monge-Ampére, Notices Am. Math. Soc., 68, 2, 186-193 (2021) · Zbl 1460.78002 · doi:10.1090/noti2220 |
| [6] | Awanou, G.: On the weak convergence of Monge-Ampère measures for discrete convex mesh functions. Acta Appl. Math., 172:Paper No. 6, 31 (2021) · Zbl 1471.35173 |
| [7] | Awanou, G.: Discrete Aleksandrov solutions of the Monge-Ampère equation. In: 2021 UNC Greensboro PDE Conference, vol. 26 of Electron. J. Differ. Equ. Conf., pp. 13-32 (2022) · Zbl 1497.65206 |
| [8] | Bakelman, I.J.: Convex Analysis and Nonlinear Geometric Elliptic Equations. Springer, Berlin. With an obituary for the author by William Rundell, Edited by Steven D. Taliaferro (1994) · Zbl 0815.35001 |
| [9] | Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Systems and Control: Foundations and Applications. Birkhäuser Boston Inc., Boston, MA. With appendices by Maurizio Falcone and Pierpaolo Soravia (1997) · Zbl 0890.49011 |
| [10] | Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC. Springer, New York. With a foreword by Hédy Attouch (2011) · Zbl 1218.47001 |
| [11] | Benamou, J-D; Duval, V., Minimal convex extensions and finite difference discretisation of the quadratic Monge-Kantorovich problem, Eur. J. Appl. Math., 30, 6, 1041-1078 (2019) · Zbl 1427.65326 · doi:10.1017/S0956792518000451 |
| [12] | Benamou, J-D; Froese, BD; Oberman, AM, Numerical solution of the optimal transportation problem using the Monge-Ampère equation, J. Comput. Phys., 260, 107-126 (2014) · Zbl 1349.65554 · doi:10.1016/j.jcp.2013.12.015 |
| [13] | Berman, R.J.: Convergence rates for discretized Monge-Ampère equations and quantitative stability of optimal transport. Found. Comput. Math., pp. 1-42 (2020) |
| [14] | Bonnet, G.; Mirebeau, J-M, Monotone discretization of the Monge-Ampère equation of optimal transport, ESAIM Math. Model. Numer. Anal., 56, 3, 815-865 (2022) · Zbl 1496.65197 · doi:10.1051/m2an/2022029 |
| [15] | Brusca, J.; Hamfeldt, BF, A convergent quadrature-based method for the Monge-Ampère equation, SIAM J. Sci. Comput., 45, 3, A1097-A1124 (2023) · Zbl 1518.35422 · doi:10.1137/22M1494658 |
| [16] | Caffarelli, LA, The regularity of mappings with a convex potential, J. Am. Math. Soc., 5, 1, 99-104 (1992) · Zbl 0753.35031 · doi:10.1090/S0894-0347-1992-1124980-8 |
| [17] | Chou, K-S; Wang, X-J, Minkowski problems for complete noncompact convex hypersurfaces, Topol. Methods Nonlinear Anal., 6, 1, 151-162 (1995) · Zbl 0873.53043 · doi:10.12775/TMNA.1995.037 |
| [18] | Coppel, WA, Number Theory: An introduction to mathematics (2009), Berlin: Springer, Berlin · Zbl 1195.11001 · doi:10.1007/978-0-387-89486-7 |
| [19] | Dhara, A., Dutta, J.: Optimality Conditions in Convex Optimization: A Finite-dimensional View. CRC Press (2011) · Zbl 1251.90002 |
| [20] | Ferrera, J.: An Introduction to Nonsmooth Analysis. Academic Press (2013) · Zbl 1290.49001 |
| [21] | Froese, BD, A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions, SIAM J. Sci. Comput., 34, 3, A1432-A1459 (2012) · Zbl 1252.65180 · doi:10.1137/110822372 |
| [22] | Gu, X.; Luo, F.; Sun, J.; Yau, S-T, Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampère equations, Asian J. Math., 20, 2, 383-398 (2016) · Zbl 1339.49039 · doi:10.4310/AJM.2016.v20.n2.a7 |
| [23] | Gutiérrez, C.E.: KIT Lectures, April 2013. Exercises on the Monge-Ampère equation. https://math.temple.edu/ gutierre/ |
| [24] | Gutiérrez, C.E.: The Monge-Ampère Equation. Progress in Nonlinear Differential Equations and their Applications, 44. Birkhäuser Boston Inc., Boston, MA (2001) · Zbl 0989.35052 |
| [25] | Hamfeldt, BF, Convergence framework for the second boundary value problem for the Monge-Ampère equation, SIAM J. Numer. Anal., 57, 2, 945-971 (2019) · Zbl 1418.35207 · doi:10.1137/18M1201913 |
| [26] | Hörmander, L., Notions of Convexity (2007), Berlin: Springer, Berlin · Zbl 1108.32001 |
| [27] | Ioffe, A.D., Tihomirov, V.M.: Theory of Extremal Problems. Elsevier (2009) · Zbl 0407.90051 |
| [28] | Ishii, H.; Lions, P-L, Viscosity solutions of fully nonlinear second-order elliptic partial differential equations, J. Differ. Equ., 83, 1, 26-78 (1990) · Zbl 0708.35031 · doi:10.1016/0022-0396(90)90068-Z |
| [29] | Kawecki, E., Lakkis, O., Pryer, T.: A Finite Element Method for the Monge-Ampère Equation with Transport Boundary Conditions (2018) |
| [30] | Kitagawa, J.; Mérigot, Q.; Thibert, B., Convergence of a Newton algorithm for semi-discrete optimal transport, J. Eur. Math. Soc., 21, 9, 2603-2651 (2019) · Zbl 1439.49053 · doi:10.4171/JEMS/889 |
| [31] | Klain, DA, The Minkowski problem for polytopes, Adv. Math., 185, 2, 270-288 (2004) · Zbl 1053.52015 · doi:10.1016/j.aim.2003.07.001 |
| [32] | Klee, VL Jr, Extremal structure of convex sets, Arch. Math. (Basel), 8, 234-240 (1957) · Zbl 0079.12501 · doi:10.1007/BF01899998 |
| [33] | Lévy, B.; Schwindt, EL, Notions of optimal transport theory and how to implement them on a computer, Comput. Graph., 72, 135-148 (2018) · doi:10.1016/j.cag.2018.01.009 |
| [34] | Li, W.; Nochetto, RH, Quantitative stability and error estimates for optimal transport plans, IMA J. Numer. Anal., 41, 3, 1941-1965 (2021) · Zbl 1510.65122 · doi:10.1093/imanum/draa045 |
| [35] | Lindsey, M.; Rubinstein, YA, Optimal transport via a Monge-Ampère optimization problem, SIAM J. Math. Anal., 49, 4, 3073-3124 (2017) · Zbl 1479.35395 · doi:10.1137/16M1071560 |
| [36] | Mérigot, Q.: A multiscale approach to optimal transport. In: Computer Graphics Forum, vol. 30, pp. 1583-1592. Wiley Online Library (2011) |
| [37] | Mérigot, Q., Delalande, A., Chazal, F.: Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space. In: International Conference on Artificial Intelligence and Statistics, pp. 3186-3196 (2020) |
| [38] | Mirebeau, J-M, Discretization of the 3D Monge-Ampère operator, between wide stencils and power diagrams, ESAIM Math. Model. Numer. Anal., 49, 5, 1511-1523 (2015) · Zbl 1330.65161 · doi:10.1051/m2an/2015016 |
| [39] | Neilan, M., Salgado, A.J., Zhang, W.: The Monge-Ampère equation. In: Geometric Partial Differential Equations. Part I, vol. 21 of Handb. Numer. Anal., pp. 105-219. Elsevier/North-Holland, Amsterdam [2020] (2020) · Zbl 1455.35275 |
| [40] | Nochetto, RH; Zhang, W., Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation, Numer. Math., 141, 1, 253-288 (2019) · Zbl 1407.65263 · doi:10.1007/s00211-018-0988-9 |
| [41] | Oliker, V.: Mathematical aspects of design of beam shaping surfaces in geometrical optics. In: Trends in Nonlinear Analysis, pp. 193-224. Springer, Berlin (2003) · Zbl 1062.78002 |
| [42] | Oliker, VI; Prussner, LD, On the numerical solution of the equation \((\partial^2z/\partial x^2)(\partial^2z/\partial y^2)-((\partial^2z/\partial x\partial y))^2=f\) and its discretizations, I. Numer. Math., 54, 3, 271-293 (1988) · Zbl 0659.65116 · doi:10.1007/BF01396762 |
| [43] | Paffenholz, A.: Polyhedral geometry and linear optimization. Unpublished Lecture Notes. Available at: http://www.mathematik.tu-darmstadt.de/paffenholz/daten/preprints/ln.pdf (2010) |
| [44] | Prins, C.R., Beltman, R., ten Thije Boonkkamp, J.H.M., Ijzerman, W.L., Tukker, T.W.: A least-squares method for optimal transport using the Monge-Ampère equation. SIAM J. Sci. Comput. 37(6), B937-B961 (2015) · Zbl 1342.65149 |
| [45] | Qiu, W.; Tang, L., A note on the Monge-Ampère type equations with general source terms, Math. Comput., 89, 326, 2675-2706 (2020) · Zbl 1446.65179 · doi:10.1090/mcom/3554 |
| [46] | Schneider, R.: Convex bodies: the Brunn-Minkowski theory, vol. 151 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, expanded edition (2014) · Zbl 1287.52001 |
| [47] | Stoer, J., Witzgall, C.: Convexity and Optimization in Finite Dimensions. I. Die Grundlehren der mathematischen Wissenschaften, Band 163. Springer, New York (1970) · Zbl 0203.52203 |
| [48] | Trudinger, N.S., Wang, X.-J.: The Monge-Ampère equation and its geometric applications. In: Handbook of Geometric Analysis. No. 1, vol. 7 of Adv. Lect. Math. (ALM), pp. 467-524. Int. Press, Somerville, MA (2008) · Zbl 1156.35033 |
| [49] | Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence, RI (2003) · Zbl 1106.90001 |
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.
