## Two-scale methods for convex envelopes

HTML articles powered by AMS MathViewer

- by
Wenbo Li and Ricardo H. Nochetto
**HTML**| PDF - Math. Comp.
**91**(2022), 111-139 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, N.J., 1970. MR**0274683**, 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.

## Additional 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