University of British Columbia
Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions
Abstract
dc:descriptionComputing 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