Journal of Convex Analysis 32 (2025), No. 2, 467--486
Copyright Heldermann Verlag 2025
Closest Univariate Convex Linear-Quadratic Function Approximation with Minimal Number of Pieces
Namrata Kundu
Dept. of Computer Science, I. K. Barber Faculty of Science, University of British Columbia, Okanagan, Kelowna, Canada
Yves Lucet
Dept. of Computer Science, I. K. Barber Faculty of Science, University of British Columbia, Okanagan, Kelowna, Canada
yves.lucet@ubc.ca
We compute the closest convex piecewise linear-quadratic (PLQ) function with minimal number of pieces to a given univariate piecewise linear-quadratic function. The Euclidean norm is used to measure the distance between functions. First, we assume that the number and positions of the breakpoints of the output function are fixed, and solve a convex optimization problem. Next, we assume the number of breakpoints is fixed, but not their position, and solve a nonconvex optimization problem to determine optimal breakpoints placement. Finally, we propose an algorithm composed of a greedy search preprocessing and a dichotomic search that solves a logarithmic number of optimization problems to obtain an approximation of any PLQ function with minimal number of pieces thereby obtaining in two steps the closest convex function with minimal number of pieces. We illustrate our algorithms with multiple examples, compare our approach with a previous globally optimal univariate spline approximation algorithm, and apply our method to simplify vertical alignment curves in road design optimization. CPLEX, Gurobi, and BARON are used with the YALMIP library in MATLAB to effectively select the most efficient solver.
Keywords: Closest convex function, piecewise linear-quadratic, spline approximation, global optimization.
MSC: 52A10, 65D07, 90C26.
[ Fulltext-pdf (800 KB)] for subscribers only.