Back to search

University of British Columbia

Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions

Abstract

dc:description

Computing the minima of a convex function is much easier than computing the same for a nonconvex function. Every nonconvex function has the same minimum as its convex envelope and the minima of the nonconvex function are contained in the set of minima of its convex envelope. We compute the conjugate of a bivariate piecewise linear-quadratic (PLQ) function as a first step toward the computation of the convex envelope. Our algorithm starts with computing the convex envelope of each piece obtaining a rational function defined over a polyhedral subdivision. Then we compute the conjugate of each of those pieces and obtain a fractional form defined over a parabolic subdivision. The last step is to compute the maximum of all those functions to obtain the conjugate of the original piecewise linear-quadratic function as a piecewise function defined on a parabolic subdivision. Our implementation in MATLAB uses symbolic computation and rational numbers to avoid any floating-point errors. We have developed the theory to compute the conjugate by computing the maximum of the conjugates corresponding to all the pieces and have implemented the code to compute the convex envelope, conjugate of each piece and the conjugate of the PLQ function.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Karmarkar, Tanmaya Narendra
Contributors dc:contributor
  • Lucet, Yves

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/88581

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Karmarkar, Tanmaya Narendra. Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions. master's thesis, University of British Columbia, 2024. http://hdl.handle.net/2429/88581