Open Collections

Kagdiwala, Zenab Kutubuddin

University of British Columbia

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 dynamic conjugate algorithm will be a convex PLQ function (called primal). The goal is to output the conjugate (dual) object 𝑷﹡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 𝑷 using different interaction techniques and displays the modification on visualization of 𝑷﹡.

Text

2022-12-07

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/83374

Computer Science

University of British Columbia

UBCO

http://creativecommons.org/licenses/by-nc-nd/4.0/