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
Haque, Tasnuva; Lucet, Yves
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
Legendre–Fenchel transform; Conjugate; Piecewise linear-quadratic functions; Subdifferential; Convex function; Computational convex analysis (CCA); Computer-aided convex analysis
Genre
Article
Type
Text
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
http://hdl.handle.net/2429/71038
Affiliation
Arts and Sciences, Irving K. Barber School of (Okanagan); Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
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
http://creativecommons.org/licenses/by-nc-nd/4.0/
Aggregated Source Repository
DSpace

Item Media

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivatives 4.0 International