Computing the Conjugate of Convex Piecewise Linear-Quadratic Bivariate functions

Abstract

We present a new algorithm to compute the Legendre-Fenchel conjugate of convex piecewise linear-quadratic (PLQ) bivariate functions. The algorithm stores a function using a (primal) planar arrangement. It then computes the (dual) arrangement associated with the conjugate by looping through each entity in the primal arrangement and building its associated dual entity. Using optimal computational geometry data structures, the algorithm enjoys a linear time worst-case complexity. We present the algorithm, and illustrate it with numerical examples. We proceed to build a toolbox for convex bivariate PLQ functions by implementing the addition, and scalar multiplication operations. Finally, we compose these operators to compute classical convex analysis operators such as the Moreau envelope, and the proximal average.

Joint work with Bryan Gardiner.

Details