Handling convexity-like constraints in variational problems

in collaboration with Q. Merigot



Choné and Le Meur discovered that some convex functions cannot be approximated by piecewise-linear convex functions on a regular grids. More precisely, Choné and Le Meur proved that piecewise-linear functions on the regular grid satisfy the inequality $ \frac{\partial^2 f}{\partial x \partial y} \geq 0 $ in a weak sense. One can easily construct convex functions that do not satisfy this inequality, and this implies that the union of the spaces of piecewise-linear convex functions on the regular grids $ (G_\delta)_{\delta > 0}$ is not dense in the space of convex functions on the unit square. Moreover, this difficulty is local, and it is likely that for any fixed sequence of mesh, one can construct convex functions $ f $ that cannot be obtained as limits of piecewise-linear convex functions on these meshes. This phenomenon makes it challenging to use $ P^1$ finite elements to approximate the solution of variational problems with convexity constraints.

In this work we provide a general framework to construct approximations of the space of convex functions on a bounded domain that satisfies a Lipschitz bound. Our approximating space is a finite-dimensional polyhedron, that is a subset of a finite-dimensional functional space that satisfies a finite number of linear constraints. Our main theoretical contribution of this article is a bound on the (Hausdorff) distance between the approximating polyhedron and the admissible set of convex functions.

Regularization of a convex graph

This type of discretization is well suited to the numerical resolution of problems of calculus of variations under convexity constraints. For instance, we show how to compute the $ L^2 $ projection onto the discretized space of convex functions in dimension $ d=3 $ by combining a proximal algorithm and an efficient projection operator on the space of 1D discrete convex functions. See the above illustration.

Finally, we note that the discretization of the space of convex functions we propose can be generalized to other spaces of functions satisfying similar constraints, such as the space of support functions of convex bodies. As an example, we reconstruct below the support function of the icosaedron:

Move your mouse on the pictures to animate (slow connection be patient)

Denoising the support function of a convex body. On the left the perturbed support function of the icosaedron. On the right its projection into the set of support functions.

The proximal algorithm can also be applied to this modified case, thus providing the first method able to approximate the projection of a function on the sphere onto the space of support functions of convex bodies. We present below the numerical computations of $ L^p $ projections (for $ p=1,2,\infty$) of the support function of a unit regular simplex onto the set of support functions of convex bodies with constant width. We believe that these projection operators could be useful in the numerical study of a famous conjecture due to Bonnesen and Fenchel (1934) concerning the so-called Meissner's convex bodies.

L1, L2 and Linfinity projection of the support function of a regular simplex