Title: A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions.
Authors: Haque, Tasnuva; Lucet, Yves
Abstract: We propose the first algorithm to compute the conjugate of a bivariate Piecewise Linear-Quadratic (PLQ) function in optimal linear worst-case time complexity. The key step is to use a planar graph, called the entity graph, not only to represent the entities (vertex, edge, or face) of the domain of a PLQ function but most importantly to record adjacent entities. We traverse the graph using breadth-first search to compute the conjugate of each entity using graph-matrix calculus, and use the adjacency information to create the output data structure in linear time.
Subjects: BIVARIATE analysis; LINEAR equations; QUADRATIC equations; PLANAR graphs; DATA structures
Publication: Computational Optimization & Applications, 2018, Vol 70, Issue 2, p593
ISSN: 0926-6003
Publication type: Academic Journal
DOI: 10.1007/s10589-018-0007-1

A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions.

Haque, Tasnuva; Lucet, Yves