Convexity and structure of piecewise polynomial functions on polyhedral domains
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: Singh, Shambhavi
issued: 2019-06-18T16:30:42Z
issued: 2019
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: First, we consider how to efficiently determine whether a piecewise-defined function in 2D is convex. For a piecewise linear quadratic (PLQ) function, convexity can be characterized with a linear number of constraints with respect to the number of edges of the partition defining the domain. The number of constraints in 2D is in fact linear with respect to the number of vertices in the domain. A similar characterization is given for piecewise cubic functions in 2D. We then consider the set of convex PLQ functions, which can be split into sub-classes based on how neighbouring pieces interact with each other. The sub-class of difference-definite functions on boxes is shown to be characterized by a quasi-separable structure. This in turn gives a parametrization that is linear with respect to the number of grid points in the domain, while the general case requires a quadratic number of parameters. The characterization of convexity is finally used in optimization algorithms under convex constraints. We make the connection with previous work, and show our results are much more general. We illustrate the results by computing the closest convex function.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/70675
note: Convexity and structure of piecewisepolynomial functions on polyhedraldomainsbyShambhavi SinghBachelor of Science, Indian Institute of Technology Kanpur, 2017A 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)June 2019c© Shambhavi Singh, 2019The following individuals certify that they have read, and recommendto the College of Graduate Studies for acceptance, a thesis/dissertation en-titled:Convexity and structure of piecewise polynomial functionson polyhedral domainssubmitted by Shambhavi Singh in partial fulfilment of the requirements ofthe degree of Master of ScienceDr. Yves Lucet, Irving K. Barber School of Arts and SciencesSupervisorDr. Heinz Bauschke, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Warren Hare, Irving K. Barber School of Arts and SciencesSupervisory Committee MemberDr. Abbas Milani, School of EngineeringUniversity ExamineriiAbstractFirst, we consider how to efficiently determine whether a piecewise-defined function in 2D is convex. For a piecewise linear quadratic (PLQ)function, convexity can be characterized with a linear number of constraintswith respect to the number of edges of the partition defining the domain.The number of constraints in 2D is in fact linear with respect to the numberof vertices in the domain. A similar characterization is given for piecewisecubic functions in 2D.We then consider the set of convex PLQ functions, which can be splitinto sub-classes based on how neighbouring pieces interact with each other.The sub-class of difference-definite functions on boxes is shown to be charac-terized by a quasi-separable structure. This in turn gives a parametrizationthat is linear with respect to the number of grid points in the domain, whilethe general case requires a quadratic number of parameters.The characterization of convexity is finally used in optimization algo-…
has type: Thesis/Dissertation
date issued: 2019-09
is shown at: 10.14288/1.0379504
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/70675