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.
Aguilera and Morin @cite_3 proposed a finite-difference approximation of the space of convex functions using discrete convex Hessians. They prove that it is possible to impose convexity by requiring a linear number of nonlinear constraints with respect to the number of nodes. The leading fully nonlinear optimization problems are solved using semidefinite programming codes. Whereas, convergence is proved in a rather general setting, the practical efficiency of this approach is limited by the capability of semidefinite solvers. In a similar spirit, Oberman @cite_10 considers the space of function that satisfy local convexity constraints on a finite set of directions. By changing the size of the stencil, the author proposed different discretizations which lead to exterior or interior approximations. Estimates of the quality of the approximation are given for smooth convex functions.
@cite_10 @cite_3
2068491204 2016361304
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 (nonpolyhedral) 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. Many problems of theoretical and practical interest involve finding an optimum over a family of convex functions. For instance, finding the projection on the convex functions in Hk(Ω), and optimizing functionals arising from some problems in economics. In the continuous setting and assuming smoothness, the convexity constraints may be given locally by asking the Hessian matrix to be positive semidefinite, but in making discrete approximations two difficulties arise: the continuous solutions may be not smooth, and functions with positive semidefinite discrete Hessian need not be convex in a discrete sense. Previous work has concentrated on non-local descriptions of convexity, making the number of constraints to grow super-linearly with the number of nodes even in dimension 2, and these descriptions are very difficult to extend to higher dimensions. In this paper we propose a finite difference approximation using positive semidefinite programs and discrete Hessians, and prove convergence under very general conditions, even when the continuous solution is not smooth, working on any dimension, and requiring a linear number of constraints in the number of nodes. Using semidefinite programming codes, we show concrete examples of approximations to problems in two and three dimensions.