Back to search

University of British Columbia

Symmetric data structure for conjugate computation, distance, and sensitivity analysis of convexity for bivariate convex piecewise linear quadratic functions

Abstract

dc:description

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 𝑷﹡.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kagdiwala, Zenab Kutubuddin
Contributors dc:contributor
  • Lucet, Yves

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivatives 4.0 International
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/83374

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Kagdiwala, Zenab Kutubuddin. Symmetric data structure for conjugate computation, distance, and sensitivity analysis of convexity for bivariate convex piecewise linear quadratic functions. master's thesis, University of British Columbia, 2022. http://hdl.handle.net/2429/83374