Back to search

University of British Columbia

Convexity and structure of piecewise polynomial functions on polyhedral domains

Abstract

dc: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.

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
2019

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Singh, Shambhavi

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/70675

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

Singh, Shambhavi. Convexity and structure of piecewise polynomial functions on polyhedral domains. master's thesis, University of British Columbia, 2019. http://hdl.handle.net/2429/70675