Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2505.06442 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918015774228480 |
|---|---|
| author | Karmarkar, Tanmaya Lucet, Yves |
| author_facet | Karmarkar, Tanmaya Lucet, Yves |
| contents | We propose the first linear-time algorithm to compute the conjugate of (nonconvex) bivariate piecewise linear-quadratic (PLQ) functions (bivariate quadratic functions defined on a polyhedral subdivision). Our algorithm starts with computing the convex envelope of each quadratic piece obtaining rational functions (quadratic over linear) defined over a polyhedral subdivision. Then we compute the conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision. Finally we compute the maximum of all those functions to obtain the conjugate as a piecewise quadratic function defined on a parabolic subdivision. The resulting algorithm runs in linear time if the initial subdivision is a triangulation (or has a uniform upper bound on the number of vertexes for each piece).
Our open-source implementation in MATLAB uses symbolic computation and rational numbers to avoid floating-point errors, and merges pieces as soon as possible to minimize computation time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06442 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions Karmarkar, Tanmaya Lucet, Yves Optimization and Control Symbolic Computation 90C25, 65K10, 49M29, 26B25 We propose the first linear-time algorithm to compute the conjugate of (nonconvex) bivariate piecewise linear-quadratic (PLQ) functions (bivariate quadratic functions defined on a polyhedral subdivision). Our algorithm starts with computing the convex envelope of each quadratic piece obtaining rational functions (quadratic over linear) defined over a polyhedral subdivision. Then we compute the conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision. Finally we compute the maximum of all those functions to obtain the conjugate as a piecewise quadratic function defined on a parabolic subdivision. The resulting algorithm runs in linear time if the initial subdivision is a triangulation (or has a uniform upper bound on the number of vertexes for each piece). Our open-source implementation in MATLAB uses symbolic computation and rational numbers to avoid floating-point errors, and merges pieces as soon as possible to minimize computation time. |
| title | A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions |
| topic | Optimization and Control Symbolic Computation 90C25, 65K10, 49M29, 26B25 |
| url | https://arxiv.org/abs/2505.06442 |