Adaptive, Anisotropic and Hierarchical cones of Discrete Convex functions
Mirebeau, Jean-Marie (2016), Adaptive, Anisotropic and Hierarchical cones of Discrete Convex functions, Numerische Mathematik, 132, 4, p. 807-853. 10.1007/s00211-015-0732-7
TypeArticle accepté pour publication ou publié
Journal nameNumerische Mathematik
MetadataShow full item record
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.
Subjects / KeywordsConvex optimization; Monopolist problem; Global convexity constraint
Showing items related by title and author.
Cohen, Albert; Dyn, Nina; Hecht, Frédéric; Mirebeau, Jean-Marie (2012) Article accepté pour publication ou publié
Chen, Da; Cohen, Laurent D.; Mirebeau, Jean-Marie (2014) Communication / Conférence
Vessel Tree Extraction using Radius-Lifted Keypoints Searching Scheme and Anisotropic Fast Marching Method Chen, Da; Mirebeau, Jean-Marie; Cohen, Laurent D. (2016) Article accepté pour publication ou publié
Mirebeau, Jean-Marie (2012) Document de travail / Working paper
Minimal Stencils for Discretizations of Anisotropic PDEs Preserving Causality or the Maximum Principle Mirebeau, Jean-Marie (2016) Article accepté pour publication ou publié