- This event has passed.
Thesis Defence: Symmetric Data Structure for Conjugate Computation, Distance, and Sensitivity Analysis of Convexity for Bivariate Convex PLQ Functions
November 22, 2022 at 8:00 am - 11:00 am
Zenab Kutubuddin Kagdiwala, supervised by Dr. Yves Lucet, will defend their thesis titled “Symmetric Data Structure for Conjugate Computation, Distance, and Sensitivity Analysis of Convexity for Bivariate Convex PLQ Functions” in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.
An abstract for Zenab’s thesis is included below.
Defences are open to all members of the campus community as well as the general public.
If you would like to attend this virtual defence please contact the supervisor at yves.lucet@ubc.ca to receive a zoom link.
ABSTRACT
The objective of this thesis is to develop efficient algorithms and data structures appropriate to support future dynamic algorithms for the conjugate operator in the Computational Convex Analysis (CCA) toolbox for piecewise-defined functions. The CCA toolbox implements efficient tools for computing essential transformations that arise in convex analysis. We focus only on piecewise linear-quadratic (PLQ) functions in our research. Different data structures can be used to represent this class of functions. We offer two representations as well as conversion methods between them. Using the symmetric data structure, we implement an offline conjugate method that runs in linear time. Additionally, we compute the distance between two PLQ functions, which is useful for unit testing and managing floating point issues.
The input of a future dynamic conjugate algorithm will be a convex PLQ function (called primal). The goal is to output the conjugate (dual) object P∗ each time the input data is modified. As a first step, we perform a sensitivity analysis to compute local modifications that keep the function convex. The primal objects are modified by changing either vertices or function coefficients or both. An interactive visualization using MATLAB’s AppDesigner is developed. The graphical user interface (GUI) modifies the primal object P using different interaction techniques and displays the modification on visualization of P.