- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Convexity and structure of piecewise polynomial functions...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Convexity and structure of piecewise polynomial functions on polyhedral domains Singh, Shambhavi
Abstract
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.
Item Metadata
Title |
Convexity and structure of piecewise polynomial functions on polyhedral domains
|
Creator | |
Publisher |
University of British Columbia
|
Date Issued |
2019
|
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.
|
Genre | |
Type | |
Language |
eng
|
Date Available |
2019-06-18
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0379504
|
URI | |
Degree | |
Program | |
Affiliation | |
Degree Grantor |
University of British Columbia
|
Graduation Date |
2019-09
|
Campus | |
Scholarly Level |
Graduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International