Adaptive, Anisotropic and Hierarchical cones of Discrete Convex functions
This work provides a practical discretization method for optimization problems involving convex functions, such as the principal-agent problem in economics, by reducing computational complexity while maintaining accuracy.
The paper addresses the computational complexity of discretizing the cone of convex functions on a 2D grid, which typically requires N^2 linear inequalities. They introduce a hierarchy of sub-cones with adaptive, local, and anisotropic stencils, and demonstrate through numerical experiments that a-posteriori refinement strategies optimize the accuracy-complexity tradeoff.
We address the discretization of optimization problems posed on the cone of convex functions, motivated in particular by the principal agent problem in economics, which models the impact of monopoly on product quality. Consider a two dimensional domain, sampled on a grid of N points. We show that the cone of restrictions to the grid of convex functions is in general characterized by N^2 linear inequalities; a direct computational use of this description therefore has a prohibitive complexity. We thus introduce a hierarchy of sub-cones of discrete convex functions, associated to stencils which can be adaptively, locally, and anisotropically refined. Numerical experiments optimize the accuracy/complexity tradeoff through the use of a-posteriori stencil refinement strategies.