Go to  Advanced Search

Convex Hulls and Graph-Matrix Calculus: Algorithms in Computational Convex Analysis

Show full item record

Files in this item

Files Size Format Description   View
Thesis Bryan Gardiner.pdf 718.4Kb Adobe Portable Document Format   View/Open
Title: Convex Hulls and Graph-Matrix Calculus: Algorithms in Computational Convex Analysis
Author: Gardiner, Bryan Nicholas Carl
Issue Date: 2010
Publicly Available in cIRcle 2010-07-29
Series/Report no. University of British Columbia, Okanagan campus, Computer Science Undergraduate Honours Essays
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.
Affiliation: Psychology and Computer Science (PSCS) (IKBSAS) (Okanagan)
URI: http://hdl.handle.net/2429/27015
Peer Review Status: Unreviewed

This item appears in the following Collection(s)

Show full item record

All items in cIRcle are protected by copyright, with all rights reserved.

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893