Linear time method computes convex envelopes for bivariate piecewise functions
Computing the convex envelope of bivariate piecewise linear-quadratic functions in linear time
Symbolic Computation
Summary
Finding the convex envelope of a complex function means creating the best convex shape that fits underneath it. The authors present a fast, step-by-step way to calculate this envelope for certain two-variable functions made of curved and flat pieces. Their method uses operations like transformation and taking maximums, and runs in time proportional to the number of pieces, which is very efficient. They also show that the final envelope keeps a structured mathematical form, helping understand and work with these functions better.
What this means in practice
- •For optimization engineers: Efficiently compute tight convex underestimators for nonconvex bivariate problems in optimization software.
- •For computer graphics developers: Improve shape approximation methods in graphics by quickly finding convex hulls of piecewise quadratic surfaces.
Authors
Tanmaya Karmarkar, Yves Lucet
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.