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

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.Arts and Sciences, Irving K. Barber School of (Okanagan)Computer Science, Mathematics, Physics and Statistics, Department of (Okanagan)UnreviewedUndergraduat