A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions
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_ | 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 |