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

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...

Full description

Saved in:
Bibliographic Details
Published in:Computational optimization and applications 2018-06, Vol.70 (2), p.593-613
Main Authors: Haque, Tasnuva, Lucet, Yves
Format: Article
Language:English
Subjects:
Algorithms
Bivariate analysis
Calculus
Convex and Discrete Geometry
Data structures
Linear equations
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0926-6003
1573-2894
DOI:10.1007/s10589-018-0007-1