Abstract (EN)

We introduce a new class of adaptive methods for optimization problems posed on the cone of convex functions. Among the various mathematical problems which possess such a formulation, the Monopolist problem (Rochet and Choné, Econometrica 66:783–826, 1998; Ekeland and Moreno-Bromberg, Numer Math 115:45–69, 2010) arising in economics is our main motivation. Consider a two dimensional domain Ω, sampled on a grid X of N points. We show that the cone Conv(X) of restrictions to X of convex functions on Ω is typically characterized by ≈N2 linear inequalities; a direct computational use of this description therefore has a prohibitive complexity. We thus introduce a hierarchy of sub-cones Conv(V) of Conv(X), associated to stencils V which can be adaptively, locally, and anisotropically refined. We show, using the arithmetic structure of the grid, that the trace U|X of any convex function U on Ω is contained in a cone Conv(V) defined by only O(Nln2N) linear constraints, in average over grid orientations. Numerical experiments for the Monopolist problem, based on adaptive stencil refinement strategies, show that the proposed method offers an unrivaled accuracy/complexity trade-off in comparison with existing methods. We also obtain, as a side product of our theory, a new average complexity result on edge flipping based mesh generation.