- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Faculty Research and Publications /
- A linear-time algorithm to compute the conjugate of...
Open Collections
UBC Faculty Research and Publications
A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions. 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.
Item Metadata
Title |
A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions.
|
Creator | |
Publisher |
Springer
|
Date Issued |
2018
|
Description |
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.
|
Subject | |
Genre | |
Type | |
Language |
eng
|
Date Available |
2019-07-17
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0379902
|
URI | |
Affiliation | |
Citation |
Haque, T., & Lucet, Y. (2018). A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions. Computational Optimization and Applications, 70(2), 593-613.
|
Publisher DOI |
10.1007/s10589-018-0007-1
|
Peer Review Status |
Reviewed
|
Scholarly Level |
Faculty; Researcher
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International