- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Undergraduate Research /
- Convex Hulls and Graph-Matrix Calculus: Algorithms...
Open Collections
UBC Undergraduate Research
Convex Hulls and Graph-Matrix Calculus: Algorithms in Computational Convex Analysis Gardiner, Bryan Nicholas Carl
Abstract
At the core of Convex Analysis and its applications are a collection of frequently used operators for transforming convex functions, along with the convex hull operation for convexifying functions. While numerical algorithms are usually applied to general functions with little known structure, we focus on the class of univariate piecewise linear-quadratic (PLQ) functions, for which exact algorithms have been developed. This thesis presents two main results. In the first part, we investigate two convex hull algorithms for univariate PLQ functions. The rst algorithm is an extension of the linear-time planar Beneath-Beyond algorithm, and performs a plane sweep that converts a function into its convex hull. The second uses convex duality theory to deconstruct a nonconvex function and build its convex hull using convex operators, in worst-case quadratic time. The trade-off is complexity: the second algorithm can be significantly simpler to implement. The second part is concerned with the computation of convex transforms, such as the Legendre-Fenchel transform and the Moreau Envelope. We introduce a new family of algorithms that stores and manipulates models of the subdifferential instead of the original function. We performed numerical experiments comparing the two convex hull algorithms, and comparing the new subdifferential algorithms to existing PLQ algorithms. These experiments confirm the time complexity for the convex hull algorithms, and show that the subdifferential algorithms have the same complexity as the PLQ algorithms, while performing an order of magnitude faster.
Item Metadata
Title |
Convex Hulls and Graph-Matrix Calculus: Algorithms in Computational Convex Analysis
|
Creator | |
Date Issued |
2010
|
Description |
At the core of Convex Analysis and its applications are a collection of frequently used operators for transforming convex functions, along with the convex hull operation for convexifying functions. While numerical algorithms are usually applied to general functions with little known structure, we focus on the class of univariate piecewise linear-quadratic (PLQ) functions, for which exact algorithms have been developed.
This thesis presents two main results. In the first part, we investigate two convex hull algorithms for univariate PLQ functions. The rst algorithm is an extension of the linear-time planar Beneath-Beyond algorithm, and performs a plane sweep that converts a function into its convex hull. The second uses convex duality theory to deconstruct a nonconvex function and build its convex hull using convex operators, in worst-case quadratic time. The trade-off is complexity: the second algorithm can be significantly simpler to implement.
The second part is concerned with the computation of convex transforms, such as the Legendre-Fenchel transform and the Moreau Envelope. We introduce a new family of algorithms that stores and manipulates models of the subdifferential instead of the original function. We performed numerical experiments comparing the two convex hull algorithms, and comparing the new subdifferential algorithms to existing PLQ algorithms. These experiments confirm the time complexity for the convex hull algorithms, and show that the subdifferential algorithms have the same complexity as the PLQ algorithms, while performing an order of magnitude faster.
|
Genre | |
Type | |
Language |
eng
|
Series | |
Date Available |
2010-07-29
|
Provider |
Vancouver : University of British Columbia Library
|
Rights |
Attribution-NonCommercial-NoDerivatives 4.0 International
|
DOI |
10.14288/1.0052227
|
URI | |
Affiliation | |
Campus | |
Peer Review Status |
Unreviewed
|
Scholarly Level |
Undergraduate
|
Rights URI | |
Aggregated Source Repository |
DSpace
|
Item Media
Item Citations and Data
Rights
Attribution-NonCommercial-NoDerivatives 4.0 International