{"ID":2874582,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.04101","arxiv_id":"2509.04101","title":"Duality between polyhedral approximation of value functions and optimal quantization of measures","abstract":"Approximating a convex function by a polyhedral function that has a limited number of facets is a fundamental problem with applications in various fields, from mitigating the curse of dimensionality in optimal control to bi-level optimization. We establish a connection between this problem and the optimal quantization of a positive measure. Building on recent stability results in optimal transport, by Delalande and Mérigot, we deduce that the polyhedral approximation of a convex function is equivalent to the quantization of the Monge-Ampère measure of its Legendre-Fenchel dual. This duality motivates a simple greedy method for computing a parsimonious approximation of a polyhedral convex function, by clustering the vertices of a Newton polytope. We evaluate our algorithm on two applications: 1) A high-dimensional optimal control problem (quantum gate synthesis), leveraging McEneaney's max-plus-based curse-of-dimensionality attenuation method; 2) A bi-level optimization problem in electricity pricing. Numerical results demonstrate the efficiency of this approach.","short_abstract":"Approximating a convex function by a polyhedral function that has a limited number of facets is a fundamental problem with applications in various fields, from mitigating the curse of dimensionality in optimal control to bi-level optimization. We establish a connection between this problem and the optimal quantization...","url_abs":"https://arxiv.org/abs/2509.04101","url_pdf":"https://arxiv.org/pdf/2509.04101v1","authors":"[\"Abdellah Bulaich Mehamdi\",\"Wim van Ackooij\",\"Luce Brotcorne\",\"Stéphane Gaubert\",\"Quentin Jacquet\"]","published":"2025-09-04T11:04:10Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}