Open Collections

Kundu, Namrata

University of British Columbia

In this thesis, we aim to find the closest convex piecewise linear-quadratic (PLQ) function with minimal pieces to a given univariate piecewise linear-quadratic function. We consider several optimization problems to compute the closest convex PLQ function to a given univariate PLQ function where the distance between them is measured with the Euclidean norm. First, we assume that the breakpoints of the output function are fixed, obtaining a convex optimization problem. Next, we introduce adaptability by enabling the algorithm to determine optimal breakpoint placement. That is, we assume that the breakpoints in the output function are variable and form a superset of those in the input function, and we utilize a global optimization algorithm. Finally, we develop an algorithm rooted in greedy search preprocessing and dichotomic search strategy utilizing an optimization model, to approximate a given univariate PLQ function with another PLQ function containing minimal number of pieces while adhering to a specified error tolerance. We also explore multiple applications of these algorithms and dive deep into its implications in the domain of road design.

Text

2024-01-10

Attribution-NonCommercial-NoDerivatives 4.0 International

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

Computer Science

University of British Columbia

UBCO

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