Two-scale methods for convex envelopes
Provides rigorous error analysis for convex envelope computation, benefiting numerical analysis and optimization communities.
The authors develop two-scale methods for computing the convex envelope of a continuous function over a convex domain, proving convergence and error estimates in the max norm.
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 [A. M. Oberman, "The convex envelope is the solution of a nonlinear obstacle problem", Proc. Amer. Math. Soc. 135(6):1689--1694, 2007]. 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 of [A. M. Oberman, "Computing the convex envelope using a nonlinear partial differential equation", Math. Models Meth. Appl. Sci, 18(05):759--780, 2008].