{"ID":23475863,"CreatedAt":"2026-09-18T01:09:05.407443952Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.19343","arxiv_id":"2609.19343","title":"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.","short_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 (quadra...","url_abs":"https://arxiv.org/abs/2609.19343","url_pdf":"https://arxiv.org/pdf/2609.19343v1","authors":"[\"Tanmaya Karmarkar\",\"Yves Lucet\"]","published":"2026-09-16T19:11:11Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.SC\"]","methods":"[]","has_code":false}