A linear-time algorithm to compute the conjugate of nonconvex bivariate piecewise linear-quadratic functions
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- A Simpler Linear-Time Algorithm for Intersecting Two Convex Polyhedra in Three DimensionsDiscrete & Computational Geometry, 2016
- Computing the conjugate of convex piecewise linear-quadratic bivariate functionsMathematical Programming, 2013
- On convex envelopes for bivariate functions over polytopesMathematical Programming, 2012
- On convex relaxations for quadratically constrained quadratic programmingMathematical Programming, 2012
- Computable representations for convex hulls of low-dimensional quadratic formsMathematical Programming, 2010
- The piecewise linear-quadratic model for computational convex analysisComputational Optimization and Applications, 2007
- A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programsMathematical Programming, 2005
- A fast computational algorithm for the Legendre-Fenchel transformComputational Optimization and Applications, 1996
- An explicit characterization of the convex envelope of a bivariate bilinear function over special polytopesAnnals of Operations Research, 1990
- Recognition problems for special classes of polynomials in 0–1 variablesMathematical Programming, 1989