We provide a general framework to construct finite dimensional approximations of the space of convex functions, which also applies to the space of c-convex functions and to the space of support functions of convex bodies. We give estimates of the distance between the approximation space and the admissible set. This framework applies to the approximation of convex functions by piecewise linear functions on a mesh of the domain and by other finite-dimensional spaces such as tensor-product splines. We show how these discretizations are well suited for the numerical solution of problems of calculus of variations under convexity constraints. Our implementation relies on proximal algorithms, and can be easily parallelized, thus making it applicable to large scale problems in dimension two and three. We illustrate the versatility and the efficiency of our approach on the numerical solution of three problems in calculus of variation : 3D denoising, the principal agent problem, and optimization within the class of convex bodies.
* Mesh versus grid constraints Carlier, Lachand-Robert and Maury proposed in @cite_22 to replace the space of P @math convex functions by the space of the space of . For every fixed mesh, a piecewise linear function is a convex interpolate if it is obtained by linearly interpolating the restriction of a convex function to the node of the mesh. Note that these functions are not necessarily convex, and the method is therefore not interior. Density results are straightforward in this context but the number of linear constraints which have to be imposed on nodes values is rather large. The authors observe that in the case of a regular grid, one needs @math constraints in order to describe the space of convex interpolates, where @math stands for the number of nodes of the mesh.
@cite_22
2047510318
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.