We consider the problem of approximating the solution of variational problems subject to the constraint that the admissible functions must be convex. This problem is at the interface between convex analysis, convex optimization, variational problems, and partial differential equation techniques. The approach is to approximate the (non-polyhedral) cone of convex functions by a polyhedral cone which can be represented by linear inequalities. This approach leads to an optimization problem with linear constraints which can be computed efficiently, hundreds of times faster than existing methods.
There have been a few different numerical approaches to this problem, which rely on adapting PDE techniques to the problem at hand. Early work @cite_4 using PDE-type methods, did not make assertions about the convexity (or approximate convexity) of the resulting solutions. Later work by @cite_0 and @cite_5 identified some of the difficulties in working with convex functions. These difficulties suggest that a straightforward adaptation of standard numerical methods is not possible. The introduction of a large number (superlinear in the number of variables) of global constraints was required in order to ensure discrete convexity.
@cite_0 @cite_5 @cite_4
2047510318 1994641279 2006026366
We describe an algorithm to approximate the minimizer of an elliptic functional in the form ( j(x, u, u) ) on the set ( C ) of convex functions u in an appropriate functional space X. Such problems arise for instance in mathematical economics [4]. A special case gives the convex envelope (u_0^ ** ) of a given function (u_0 ). Let ((T_n) ) be any quasiuniform sequence of meshes whose diameter goes to zero, and (I_n ) the corresponding affine interpolation operators. We prove that the minimizer over ( C ) is the limit of the sequence ((u_n) ), where (u_n ) minimizes the functional over (I_n( C ) ). We give an implementable characterization of (I_n( C ) ). Then the finite dimensional problem turns out to be a minimization problem with linear constraints. We present numerical methods to solve optimization problems on the space of convex functions or among convex bodies. Hence convexity is a constraint on the admissible objects, whereas the functionals are not required to be convex. To deal with this, our method mixes geometrical and numerical algorithms. We give several applications arising from classical problems in geometry and analysis: Alexandrov's problem of finding a convex body of prescribed surface function; Cheeger's problem of a subdomain minimizing the ratio surface area on volume; Newton's problem of the body of minimal resistance. In particular for the latter application, the minimizers are still unknown, except in some particular classes. We give approximate solutions better than the theoretical known ones, hence demonstrating that the minimizers do not belong to these classes. The goal of this paper is to introduce the approximated convex envelope of a function and to estimate how it differs from its convex envelope. Such a problem arises in various physical situations where the function considered is some energy that has to be minimized.This study is a first step toward understanding how to approximate the quasi-convex envelope of a function. The importance of this issue is due to the various applications that are encountered, in particular, in the field of material science.