Computing the conjugate of nonconvex bivariate piecewise linear-quadratic functions
department or school: Science, Irving K. Barber Faculty of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Karmarkar, Tanmaya Narendra
issued: 2024-07-05T22:31:17Z
issued: 2024
related degree: Master of Science - MSc
degree grantor: University of British Columbia
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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/88581
note: Computing the conjugate ofnonconvex bivariate piecewiselinear-quadratic functionsbyTanmaya Narendra KarmarkarB.E. Electrical Engineering, College of Engineering, Pune 1999A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe College of Graduate Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Okanagan)July 2024© Tanmaya Narendra Karmarkar, 2024The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Computing the conjugate of nonconvex bivariate piecewiselinear-quadratic functionssubmitted by Tanmaya Narendra Karmarkar in partial fulfilment ofthe requirements of the degree of Master of ScienceYves Lucet, I. K. Barber School Faculty of ScienceSupervisorHeinz Bauschke, I. K. Barber School Faculty of ScienceSupervisory Committee MemberWarren Hare, I. K. Barber School Faculty of ScienceSupervisory Committee MemberKlaske Van Heusden, School of EngineeringUniversity ExamineriiAbstractComputing the minima of a convex function is much easier than com-puting the same for a nonconvex function. Every nonconvex function hasthe same minimum as its convex envelope and the minima of the nonconvexfunction are contained in the set of minima of its convex envelope. We com-pute the conjugate of a bivariate piecewise linear-quadratic (PLQ) functionas a first step toward the computation of the convex envelope.Our algorithm starts with computing the convex envelope of each pieceobtaining a rational function defined over a polyhedral subdivision. Thenwe compute the conjugate of each of those pieces and obtain a fractionalform defined over a parabolic subdivision. The last step is to compute themaximum of all those functions to obtain the conjugate of the original piece-wise linear-quadratic function as a piecewise function defined on a parabolicsubdivision.Our implementation in MATLAB uses symbolic computation and ratio-nal numbers to avoi…
has type: Thesis/Dissertation
date issued: 2024-09
is shown at: 10.14288/1.0444097
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
contributor: Lucet, Yves
type: Text
identifier URI: http://hdl.handle.net/2429/88581