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