Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
Abstract
We compute the convex envelope of (nonconvex) bivariate piecewise linear-quadratic (PLQ) functions (bivariate quadratic functions defined on a polyhedral subdivision). Our algorithm is composed of the following steps: (1) compute the convex envelope of each quadratic piece obtaining piecewise rational functions (quadratic divided by linear function) defined over a polyhedral subdivision; (2) compute the (Legendre-Fenchel) conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision; (3) compute the maximum of all those functions to obtain the conjugate of the original PLQ function as a piecewise quadratic function defined on a parabolic subdivision; (4) compute the conjugate of each resulting piece; and finally (5) compute the maximum over all those functions to obtain the convex envelope (biconjugate) as rational functions (quadratic divided by linear function) defined over a polyhedral subdivision. Our contribution includes a practical algorithm running in linear time, and proving that the convex envelope is a piecewise rational function.
Related
- Global Linear Convergence of the Proximal Bundle Method under Unknown Piecewise Smoothness and Quadratic Growth
- On Piecewise Quadratic Terminal Costs for MPC
- Stabilized SQP Method for Convex Piecewise Linear-Quadratic Composite Optimization Problems
- The classes of bivariate Schur and Herglotz matrix-valued rational functions: realizations, symmetrizations, and related determinantal representations
- A Gamma envelope and sharp moment inequalities for Gaussian quadratic forms
BibTeX
@misc{karmarkar2026computing,
title = {{Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time}},
author = {Tanmaya Karmarkar and Yves Lucet},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.19343},
eprint = {2609.19343},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.19343},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
AU - Tanmaya Karmarkar
AU - Yves Lucet
PY - 2026
DA - 2026/09/16
PB - arXiv
DO - 10.48550/arxiv.2609.19343
UR - https://arxiv.org/abs/2609.19343
AB - We compute the convex envelope of (nonconvex) bivariate piecewise linear-quadratic (PLQ) functions (bivariate quadratic functions defined on a polyhedral subdivision). Our algorithm is composed of the following steps: (1) compute the convex envelope of each quadratic piece obtaining piecewise rational functions (quadratic divided by linear function) defined over a polyhedral subdivision; (2) compute the (Legendre-Fenchel) conjugate of each resulting piece to obtain piecewise quadratic functions defined over a parabolic subdivision; (3) compute the maximum of all those functions to obtain the conjugate of the original PLQ function as a piecewise quadratic function defined on a parabolic subdivision; (4) compute the conjugate of each resulting piece; and finally (5) compute the maximum over all those functions to obtain the convex envelope (biconjugate) as rational functions (quadratic divided by linear function) defined over a polyhedral subdivision. Our contribution includes a practical algorithm running in linear time, and proving that the convex envelope is a piecewise rational function.
ER -