Conjugate of some rational functions and convex envelope of quadratic functions over a polytope
department or school: Arts and Sciences, Irving K. Barber School of (Okanagan)
department or school: Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)
data provider: DSpace
degree campus: UBCO
creator: Kumar, Deepak
issued: 2019-01-14T17:17:28Z
issued: 2019
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: Computing the convex envelope or biconjugate is the core operation that bridges the domain of nonconvex analysis with convex analysis. For a bivariate PLQ function de ned over a polytope, we start with computing the convex envelope of each piece. This convex envelope is characterized by a polyhedral subdivision such that over each member of the subdivision, it has an implicitly de ned rational form(square of a linear function over a linear function). Computing this convex envelope involves solving an exponential number of subproblems which, in turn, leads to an exponential time algorithm. After that, we compute the conjugate of each such rational function de- ned over a polytope. It is observed that the conjugate has a parabolic subdivision such that over each member of its subdivision, it has an implicitly de ned fractional form(linear function over the square root of a linear function). This computation of the conjugate is performed with a worst-case linear time complexity algorithm. Finally, some directions and insights about computing the maximum of all the conjugates of each piece of a PLQ function and then the conjugate of that to obtain the biconjugate are provided as conjectures for future work.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/68242
note: Conjugate of some Rational functionsand Convex Envelope of Quadraticfunctions over a PolytopebyDeepak KumarBachelor of Technology, Indian Institute of Information Technology, Design andManufacturing, Jabalpur, 2012A 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)January 2019c© Deepak Kumar, 2019The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Conjugate of some Rational functions and Convex Envelopeof Quadratic functions over a Polytopesubmitted by Deepak Kumar in partial fulfilment of the requirements ofthe degree of Master of Science.Dr. Yves Lucet, I. K. Barber School of Arts & SciencesSupervisorDr. Heinz Bauschke, I. K. Barber School of Arts & SciencesSupervisory Committee MemberDr. Warren Hare, I. K. Barber School of Arts & SciencesSupervisory Committee MemberDr. Homayoun Najjaran, School of EngineeringUniversity ExamineriiAbstractComputing the convex envelope or biconjugate is the core operation thatbridges the domain of nonconvex analysis with convex analysis. For a bi-variate PLQ function defined over a polytope, we start with computing theconvex envelope of each piece. This convex envelope is characterized by apolyhedral subdivision such that over each member of the subdivision, ithas an implicitly defined rational form(square of a linear function over alinear function). Computing this convex envelope involves solving an expo-nential number of subproblems which, in turn, leads to an exponential timealgorithm.After that, we compute the conjugate of each such rational function de-fined over a polytope. It is observed that the conjugate has a parabolicsubdivision such that over each member of its subdivision, it has an im-plicitly defined fractional form(linear function over square root of a linearfunction). This computat…
has type: Thesis/Dissertation
date issued: 2019-02
is shown at: 10.14288/1.0376049
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
type: Text
identifier URI: http://hdl.handle.net/2429/68242