Thesis Defence: Closest Convex Function Approximation with Minimal Pieces for Univariate Piecewise Linear-Quadratic Function

Namrata Kundu, supervised by Dr. Yves Lucet, will defend their thesis titled “Closest Convex Function Approximation with Minimal Pieces for Univariate Piecewise Linear-Quadratic Functions” in partial fulfillment of the requirements for the degree of Master of Science in Computer Science.

An abstract for Namrata Kundu’s thesis is included below.

Defences are open to all members of the campus community as well as the general public. Registration is not required for in person defences.

---

ABSTRACT

In this thesis, we aim to find the closest convex piecewise linear-quadratic (PLQ) function with minimal pieces to a given univariate piecewise linearquadratic 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 algorithm and dive deep into its implications in the domain of road design.