Two-scale methods for convex envelopes
HTML articles powered by AMS MathViewer
- by Wenbo Li and Ricardo H. Nochetto;
- Math. Comp. 91 (2022), 111-139
- DOI: https://doi.org/10.1090/mcom/3521
- Published electronically: October 13, 2021
- HTML | PDF | Request permission
Abstract:
We develop two-scale methods for computing the convex envelope of a continuous function over a convex domain in any dimension. This hinges on a fully nonlinear obstacle formulation (see A. M. Oberman [Proc. Amer. Math. Soc. 135 (2007), pp. 1689–1694]). We prove convergence and error estimates in the max norm. The proof utilizes a discrete comparison principle, a discrete barrier argument to deal with Dirichlet boundary values, and the property of flatness in one direction within the non-contact set. Our error analysis extends to a modified version of the finite difference wide stencil method provided by Oberman [Math. Models Methods Appl. Sci. 18 (2008), pp. 759–780].References
- G. Barles and P. E. Souganidis, Convergence of approximation schemes for fully nonlinear second order equations, Asymptotic Anal. 4 (1991), no. 3, 271–283. MR 1115933, DOI 10.3233/ASY-1991-4305
- Sören Bartels, Linear convergence in the approximation of rank-one convex envelopes, M2AN Math. Model. Numer. Anal. 38 (2004), no. 5, 811–820. MR 2104430, DOI 10.1051/m2an:2004040
- Olivier Bokanowski, Stefania Maroso, and Hasnaa Zidani, Some convergence results for Howard’s algorithm, SIAM J. Numer. Anal. 47 (2009), no. 4, 3001–3026. MR 2551155, DOI 10.1137/08073041X
- Susanne C. Brenner and L. Ridgway Scott, The mathematical theory of finite element methods, 3rd ed., Texts in Applied Mathematics, vol. 15, Springer, New York, 2008. MR 2373954, DOI 10.1007/978-0-387-75934-0
- L. Caffarelli, L. Nirenberg, and J. Spruck, The Dirichlet problem for the degenerate Monge-Ampère equation, Rev. Mat. Iberoamericana 2 (1986), no. 1-2, 19–27. MR 864651, DOI 10.4171/RMI/23
- Guido De Philippis and Alessio Figalli, Optimal regularity of the convex envelope, Trans. Amer. Math. Soc. 367 (2015), no. 6, 4407–4422. MR 3324933, DOI 10.1090/S0002-9947-2014-06306-X
- Georg Dolzmann, Numerical computation of rank-one convex envelopes, SIAM J. Numer. Anal. 36 (1999), no. 5, 1621–1635. MR 1706747, DOI 10.1137/S0036142997325581
- G. Dolzmann and N. J. Walkington, Estimates for numerical approximations of rank one convex envelopes, Numer. Math. 85 (2000), no. 4, 647–663. MR 1771783, DOI 10.1007/PL00005395
- Xiaobing Feng and Max Jensen, Convergent semi-Lagrangian methods for the Monge-Ampère equation on unstructured grids, SIAM J. Numer. Anal. 55 (2017), no. 2, 691–712. MR 3623696, DOI 10.1137/16M1061709
- Cristian E. Gutiérrez, The Monge-Ampère equation, Progress in Nonlinear Differential Equations and their Applications, vol. 89, Birkhäuser/Springer, [Cham], 2016. Second edition [of MR1829162]. MR 3560611, DOI 10.1007/978-3-319-43374-5
- M. Hintermüller, K. Ito, and K. Kunisch, The primal-dual active set strategy as a semismooth Newton method, SIAM J. Optim. 13 (2002), no. 3, 865–888 (2003). MR 1972219, DOI 10.1137/S1052623401383558
- Max Jensen and Iain Smears, On the notion of boundary conditions in comparison principles for viscosity solutions, Hamilton-Jacobi-Bellman equations, Radon Ser. Comput. Appl. Math., vol. 21, De Gruyter, Berlin, 2018, pp. 143–154. MR 3823876
- Wenbo Li and Ricardo H. Nochetto, Optimal pointwise error estimates for two-scale methods for the Monge-Ampère equation, SIAM J. Numer. Anal. 56 (2018), no. 3, 1915–1941. MR 3819162, DOI 10.1137/18M1165670
- R. H. Nochetto, D. Ntogkas, and W. Zhang, Two-scale method for the Monge-Ampère equation: convergence to the viscosity solution, Math. Comp. 88 (2019), no. 316, 637–664. MR 3882279, DOI 10.1090/mcom/3353
- R. H. Nochetto, D. Ntogkas, and W. Zhang, Two-scale method for the Monge-Ampère equation: pointwise error estimates, IMA J. Numer. Anal. 39 (2019), no. 3, 1085–1109. MR 3984051, DOI 10.1093/imanum/dry026
- Ricardo H. Nochetto and Wujun Zhang, Discrete ABP estimate and convergence rates for linear elliptic equations in non-divergence form, Found. Comput. Math. 18 (2018), no. 3, 537–593. MR 3807356, DOI 10.1007/s10208-017-9347-y
- Ricardo H. Nochetto and Wujun Zhang, Pointwise rates of convergence for the Oliker-Prussner method for the Monge-Ampère equation, Numer. Math. 141 (2019), no. 1, 253–288. MR 3903208, DOI 10.1007/s00211-018-0988-9
- Adam M. Oberman, The convex envelope is the solution of a nonlinear obstacle problem, Proc. Amer. Math. Soc. 135 (2007), no. 6, 1689–1694. MR 2286077, DOI 10.1090/S0002-9939-07-08887-9
- Adam M. Oberman, Computing the convex envelope using a nonlinear partial differential equation, Math. Models Methods Appl. Sci. 18 (2008), no. 5, 759–780. MR 2413037, DOI 10.1142/S0218202508002851
- Adam M. Oberman and Yuanlong Ruan, A partial differential equation for the rank one convex envelope, Arch. Ration. Mech. Anal. 224 (2017), no. 3, 955–984. MR 3621814, DOI 10.1007/s00205-017-1092-5
- Adam M. Oberman and Luis Silvestre, The Dirichlet problem for the convex envelope, Trans. Amer. Math. Soc. 363 (2011), no. 11, 5871–5886. MR 2817413, DOI 10.1090/S0002-9947-2011-05240-2
- Martin L. Puterman and Shelby L. Brumelle, On the convergence of policy iteration in stationary dynamic programming, Math. Oper. Res. 4 (1979), no. 1, 60–69. MR 543609, DOI 10.1287/moor.4.1.60
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970. MR 274683, DOI 10.1515/9781400873173
- Iain Smears and Endre Süli, Discontinuous Galerkin finite element approximation of Hamilton-Jacobi-Bellman equations with Cordes coefficients, SIAM J. Numer. Anal. 52 (2014), no. 2, 993–1016. MR 3196952, DOI 10.1137/130909536
- Neil S. Trudinger and John I. E. Urbas, On second derivative estimates for equations of Monge-Ampère type, Bull. Austral. Math. Soc. 30 (1984), no. 3, 321–334. MR 766792, DOI 10.1017/S0004972700002069
- Michael Ulbrich, Semismooth Newton methods for variational inequalities and constrained optimization problems in function spaces, MOS-SIAM Series on Optimization, vol. 11, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA; Mathematical Optimization Society, Philadelphia, PA, 2011. MR 2839219, DOI 10.1137/1.9781611970692
- Shawn W. Walker, FELICITY: A MATLAB/C++ toolbox for developing finite element methods and simulation modeling, SIAM J. Sci. Comput. 40 (2018), no. 2, C234–C257. MR 3775142, DOI 10.1137/17M1128745
- S. W. Walker, FELICITY: Finite ELement Implementation and Computational Interface Tool for You, http://www.mathworks.com/matlabcentral/fileexchange/31141-felicity.
Bibliographic Information
- Wenbo Li
- Affiliation: Department of Mathematics, University of Tennessee, Knoxville, Tennessee 37996
- ORCID: 0000-0002-6678-6857
- Email: wli50@utk.edu
- Ricardo H. Nochetto
- Affiliation: Department of Mathematics, University of Maryland, College Park, Maryland 20742
- MR Author ID: 131850
- ORCID: 0000-0002-6678-6857
- Email: rhn@umd.edu
- Received by editor(s): December 29, 2018
- Received by editor(s) in revised form: February 25, 2019, and December 24, 2019
- Published electronically: October 13, 2021
- Additional Notes: Both authors were partially supported by the NSF Grant DMS -1411808. The first author was also partially supported by the Patrick and Marguerite Sung Fellowship in Mathematics
- © Copyright 2021 American Mathematical Society
- Journal: Math. Comp. 91 (2022), 111-139
- MSC (2020): Primary 65N06, 65N12, 65N15, 65N30; Secondary 35J70, 35J87
- DOI: https://doi.org/10.1090/mcom/3521
- MathSciNet review: 4350534