Duality between polyhedral approximation of value functions and optimal quantization of measures
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908519066763264 |
|---|---|
| author | Mehamdi, Abdellah Bulaich van Ackooij, Wim Brotcorne, Luce Gaubert, Stéphane Jacquet, Quentin |
| author_facet | Mehamdi, Abdellah Bulaich van Ackooij, Wim Brotcorne, Luce Gaubert, Stéphane Jacquet, Quentin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_04101 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Duality between polyhedral approximation of value functions and optimal quantization of measures Mehamdi, Abdellah Bulaich van Ackooij, Wim Brotcorne, Luce Gaubert, Stéphane Jacquet, Quentin Optimization and Control 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. |
| title | Duality between polyhedral approximation of value functions and optimal quantization of measures |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2509.04101 |