[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

The Second Boundary Value Problem for a Discrete Monge–Ampère Equation

  • Published:
Journal of Scientific Computing Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Availability of Data and Material (Data Transparency)

Available upon reasonable request.

References

  1. Aliprantis, C.D., Tourky, R.: Cones and duality. Graduate Studies in Mathematics, vol. 84. American Mathematical Society, Providence, RI (2007)

  2. Aurenhammer, F., Hoffmann, F., Aronov, B.: Minkowski-type theorems and least-squares clustering. Algorithmica 20(1), 61–76 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  3. Auslender, A., Teboulle, M.: Asymptotic Cones and Functions in Optimization and Variational Inequalities. Springer, Berlin (2006)

    MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  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)

  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)

  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)

  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)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  12. Benamou, J.-D., Froese, B.D., Oberman, A.M.: Numerical solution of the optimal transportation problem using the Monge-Ampère equation. J. Comput. Phys. 260, 107–126 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  15. Brusca, J., Hamfeldt, B.F.: A convergent quadrature-based method for the Monge-Ampère equation. SIAM J. Sci. Comput. 45(3), A1097–A1124 (2023)

    Article  MATH  Google Scholar 

  16. Caffarelli, L.A.: The regularity of mappings with a convex potential. J. Am. Math. Soc. 5(1), 99–104 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chou, K.-S., Wang, X.-J.: Minkowski problems for complete noncompact convex hypersurfaces. Topol. Methods Nonlinear Anal. 6(1), 151–162 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  18. Coppel, W.A.: Number Theory: An introduction to mathematics. Springer, Berlin (2009)

    Book  MATH  Google Scholar 

  19. Dhara, A., Dutta, J.: Optimality Conditions in Convex Optimization: A Finite-dimensional View. CRC Press (2011)

  20. Ferrera, J.: An Introduction to Nonsmooth Analysis. Academic Press (2013)

  21. Froese, B.D.: A numerical method for the elliptic Monge-Ampère equation with transport boundary conditions. SIAM J. Sci. Comput. 34(3), A1432–A1459 (2012)

    Article  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  25. Hamfeldt, B.F.: Convergence framework for the second boundary value problem for the Monge-Ampère equation. SIAM J. Numer. Anal. 57(2), 945–971 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  26. Hörmander, L.: Notions of Convexity. Springer, Berlin (2007)

    MATH  Google Scholar 

  27. Ioffe, A.D., Tihomirov, V.M.: Theory of Extremal Problems. Elsevier (2009)

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  31. Klain, D.A.: The Minkowski problem for polytopes. Adv. Math. 185(2), 270–288 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  32. Klee, V.L., Jr.: Extremal structure of convex sets. Arch. Math. (Basel) 8, 234–240 (1957)

    Article  MathSciNet  MATH  Google Scholar 

  33. Lévy, B., Schwindt, E.L.: Notions of optimal transport theory and how to implement them on a computer. Comput. Graph. 72, 135–148 (2018)

    Article  Google Scholar 

  34. Li, W., Nochetto, R.H.: Quantitative stability and error estimates for optimal transport plans. IMA J. Numer. Anal. 41(3), 1941–1965 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  35. Lindsey, M., Rubinstein, Y.A.: Optimal transport via a Monge-Ampère optimization problem. SIAM J. Math. Anal. 49(4), 3073–3124 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  40. Nochetto, R.H., Zhang, W.: Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation. Numer. Math. 141(1), 253–288 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  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)

  42. Oliker, V.I., Prussner, L.D.: 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)

    Article  MATH  Google Scholar 

  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)

  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)

    Article  MATH  Google Scholar 

  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)

  47. Stoer, J., Witzgall, C.: Convexity and Optimization in Finite Dimensions. I. Die Grundlehren der mathematischen Wissenschaften, Band 163. Springer, New York (1970)

  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)

  49. Villani, C.: Topics in Optimal Transportation. Graduate Studies in Mathematics, vol. 58. American Mathematical Society, Providence, RI (2003)

Download references

Acknowledgements

The author would like to thank the unknown referees, Carmel Aboua, Julienne Kabre and Nicolae Tarfulea for a careful reading of the manuscript and for constructive comments which substantially helped improve the quality of the paper.

Funding

The author was partially supported by NSF grant DMS-1720276. The author would like to thank the Isaac Newton Institute for Mathematical Sciences, Cambridge, for support and hospitality during the programme ”Geometry, compatibility and structure preservation in computational differential equations” where part of this work was undertaken. Part of this work was supported by EPSRC grant no EP/K032208/1.

Author information

Authors and Affiliations

  1. Department of Mathematics, Statistics, and Computer Science (M/C 249), University of Illinois at Chicago, Chicago, IL, 60607-7045, USA

    Gerard Awanou

Authors
  1. Gerard Awanou
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

N/A.

Corresponding author

Correspondence to Gerard Awanou.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Code availability (software application or custom code)

Available upon reasonable request.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Appendix

Appendix

We gave a geometric proof for Theorem 8 based on Lemma 8. Here we give an analytical proof based on infimal convolution. The epigraph of the infimal convolution illustrates with an analytical argument Lemma 8.

Let v be a continuous convex function on a closed convex set \({\widetilde{S}}\) with non empty interior. Let S denote the epigraph of v. Here S is unbounded unlike in Lemma 3. Let us consider another extension of v to \(\mathbb {R}^d\) as an extended value function

$$\begin{aligned} v_{\infty }(x) = \left\{ \begin{array}{ll} v(x) &{} \text { if } x \in {\widetilde{S}}\\ +\infty &{} \text { otherwise }. \end{array} \right. \end{aligned}$$

Recall the function \(k_{\varOmega ^*}\) from (22). The infimal convolution of \(v_{\infty }\) and \(k_{\varOmega ^*}\) is a function \(v_{\infty } \square k_{\varOmega ^*}: \mathbb {R}^d \rightarrow \mathbb {R}^d \cup \{ \, +\infty \, \}\) defined as

$$\begin{aligned} v_{\infty } \square k_{\varOmega ^*}(x) = \inf _{y \in \mathbb {R}^d} v_{\infty }(y) + k_{\varOmega ^*} (x-y). \end{aligned}$$

Since \( v_{\infty }(y) = +\infty \) for \(y \notin {\widetilde{S}}\), we have

$$\begin{aligned} v_{\infty } \square k_{\varOmega ^*}(x) = \inf _{y \in {\widetilde{S}} } v(y) + k_{\varOmega ^*} (x-y). \end{aligned}$$

Let \({\text {epi}}u\) denotes the epigraph of a function u. Note that \({\text {epi}}v = {\text {epi}}v_{\infty }\) as \(+\infty \notin \mathbb {R}\). For given functions \(\phi _1\) and \(\phi _2\) from \(\mathbb {R}^d\) to \(\mathbb {R}^d \cup \{ \, +\infty \, \}\) we have \({\text {epi}}\phi _1 + {\text {epi}}\phi _2 \subset {\text {epi}}\phi _1 \square \phi _2\). The infimal convolution is said to be exact at \(x \in \mathbb {R}^d\) if there exists \(y \in \mathbb {R}^d\) such that \(\phi _1 \square \phi _2(x) = \phi _1(y) + \phi _2(x-y)\). If \(\phi _1 \square \phi _2\) is exact at all \(x \in \mathbb {R}^d\), \({\text {epi}}\phi _1 + {\text {epi}}\phi _2 = {\text {epi}}\phi _1 \square \phi _2\), [20, Lemma 2.8].

Given \(x \in \mathbb {R}^d\), the function \(y \mapsto v(y) + k_{\varOmega ^*} (x-y)\) is continuous on \({\widetilde{S}}\) and hence has a minimum on \({\widetilde{S}}\). Thus \(v_{\infty } \square k_{\varOmega ^*} \) is exact at all points \(x \in \mathbb {R}^d\) and we conclude that

$$\begin{aligned} {\text {epi}}v_{\infty } \square k_{\varOmega ^*} = {\text {epi}}v + {\text {epi}}k_{\varOmega ^*}, \end{aligned}$$

i.e. \(M=S+K_{\varOmega ^*}\) where \(M={\text {epi}}v_{\infty } \square k_{\varOmega ^*}\). This is essentially the content of Lemma 8.

Theorem 28

A necessary and sufficient condition for \(v_{\infty } \square k_{\varOmega ^*}\) to be a convex extension of v is that \(\partial v(({\widetilde{S}})^\circ ) \subset \overline{\varOmega ^*}\).

Proof

Recall that a function \(\phi \) defined on \(\mathbb {R}^d\) is proper if there exists \(x_0 \in \mathbb {R}^d\) such that \(\phi (x_0)< +\infty \) and \(\phi (x) > - \infty \) for all \(x \in \mathbb {R}^d\). As \(v_{\infty }\) and \(k_{\varOmega ^*}\) are proper convex functions, \(v_{\infty } \square k_{\varOmega ^*}\) is a convex function by [19, Proposition 2.56].

Recall that \(\partial k_{\varOmega ^*}(\mathbb {R}^d) = \overline{\varOmega ^*}\). Let us first assume that \(v_{\infty } \square k_{\varOmega ^*}=v\) on \({\widetilde{S}}\). Then for all \(x \in ({\widetilde{S}})^\circ \), \(\partial v(x) = \partial v_{\infty } \square k_{\varOmega ^*} (x)\). This follows from the locality of the subdifferential c.f. [23, Exercise 1].

By [10, Proposition 16.48 (i) ], we have for \(x \in ({\widetilde{S}})^\circ \), \(\partial v(x) = \partial v_{\infty } \square k_{\varOmega ^*} (x) = \partial v_{\infty }(y) \cap \partial k_{\varOmega ^*} (x-y)\), where \(y \in {\widetilde{S}}\) with \(v_{\infty } \square k_{\varOmega ^*} (x) = v_{\infty }(y) + k_{\varOmega ^*} (x-y)\). Here \(y=x\) and \(\partial k_{\varOmega ^*} (0) = \overline{\varOmega ^*}\). We conclude that \(\partial v(({\widetilde{S}})^\circ ) \subset \overline{\varOmega ^*}\).

Let us now assume that \(\partial v(({\widetilde{S}})^\circ ) \subset \overline{\varOmega ^*}\). We show that \(v_{\infty } \square k_{\varOmega ^*}\) is a convex extension of v. Let \(x \in ({\widetilde{S}})^\circ \). We have \(v_{\infty } \square k_{\varOmega ^*}(x)\le v(x)\). Assume by contradiction that \(v_{\infty } \square k_{\varOmega ^*}(x) < v(x)\). This means that we can find \(y \in {\widetilde{S}}\) such that

$$\begin{aligned} v(y)+k_{\varOmega ^*}(x-y) < v(x). \end{aligned}$$
(48)

Let now \(p \in \partial v(x)\). We have \(p \in \overline{\varOmega ^*}\). By definition, \(v(y) \ge v(x) + p (y-x)\). Thus, by (48)

$$\begin{aligned} v(y) > v(y)+k_{\varOmega ^*}(x-y) + p \cdot (y-x). \end{aligned}$$

It follows that \(p \cdot (x-y) > k_{\varOmega ^*}(x-y) = \sup _{p \in \overline{\varOmega ^*}} p \cdot (x-y)\) This contradicts \(p \in \overline{\varOmega ^*}\). We conclude that \(v= v_{\infty } \square k_{\varOmega ^*}\) on \(({\widetilde{S}})^\circ \). Recall that v is continuous on \({\widetilde{S}}\). Also, \(v_{\infty } \square k_{\varOmega ^*}\) is a proper convex function which is bounded above on \({\widetilde{S}}\), and hence continuous on \({\widetilde{S}}\), c.f. [6, Lemma 2]. It follows that \(v_{\infty } \square k_{\varOmega ^*} = v\) on \({\widetilde{S}}\). \(\square \)

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Awanou, G. The Second Boundary Value Problem for a Discrete Monge–Ampère Equation. J Sci Comput 97, 22 (2023). https://doi.org/10.1007/s10915-023-02340-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10915-023-02340-0

Keywords

Mathematics Subject Classification

Search

Navigation