Computing the quasiconvex envelope using a nonlocal line solver
For researchers in optimization and PDEs, this provides a practical algorithm for a previously difficult-to-solve PDE problem, though it is an incremental contribution building on existing theory.
The paper presents an algorithm for computing the quasiconvex envelope (QCE) of a function using a nonlocal line solver, with an explicit formula for the one-dimensional case. The method enables computation of convex hulls for level set functions.
Recently in a series of articles, Barron, Goebel, and Jensen \cite{barron2012functions} \cite{barron2012quasiconvex} \cite{barron2013quasiconvex} \cite{barron2013uniqueness} have studied second order degenerate elliptic PDE and first order nonlocal PDEs for the quasiconvex envelope. Quasiconvex functions are functions whose level sets are convex. The PDE is difficult to solve. In this article we present an algorithm for computing the quasiconvex envelope (QCE) of a given function. The QCE operator is a level set operator, so this algorithm gives a method to compute convex hull of sets represented by a level set functions. We present a nonlocal line solver for the quasiconvex envelope (QCE), based on solving the one dimensional problem on lines. We find an explicit formula for the QCE of a function defined on a line.