Back to search

University of British Columbia

Closest convex function approximation with minimal pieces for univariate piecewise linear-quadratic functions

Abstract

dc:description

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.

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
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Kundu, Namrata
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/87196

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

Kundu, Namrata. Closest convex function approximation with minimal pieces for univariate piecewise linear-quadratic functions. master's thesis, University of British Columbia, 2023. http://hdl.handle.net/2429/87196