UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Convexity and structure of piecewise polynomial functions on polyhedral domains Singh, Shambhavi


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 Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International