- 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