Abstract

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.

Author information

Contact details are reproduced from the original publication and may be historical.

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

Keywords

  • Closest convex function
  • piecewise linear-quadratic
  • spline approximation
  • global optimization

Mathematics Subject Classification

52A10, 65D07, 90C26

References

  1. K. M. Ayman, W. Hare, Y. Lucet: A multi-road quasi network flow model for the vertical alignment optimization of a road network, Eng. Optimization 56/7 (2023) 1–24.https://doi.org/10.1080/0305215X.2023.2227841Google Scholar
  2. H. H. Bauschke, Y. Lucet, H. M. Phan: On the convexity of piecewise-defined functions, ESAIM: Control, Optim. Calc. Var. 22 (2016) 728–742.https://doi.org/10.1051/cocv/2015023Google Scholar
  3. H. H. Bauschke, W. M. Moursi: An Introduction to Convexity, Optimization, and Algorithms, MOS-SIAM Series on Optimization Vol. 34, Society for Industrial and Applied Mathematics, Philadelphia (2024).https://doi.org/10.1137/1.9781611977806Google Scholar
  4. V. Beiranvand, W. Hare, Y. Lucet, S. Hossain: Multi-haul quasi network flow model for vertical alignment optimization, Eng. Optimization 49 (2017) 1777–1795.https://doi.org/10.1080/0305215X.2016.1271880Google Scholar
  5. Y. Bosch, P. Schäfer, J. Spoerhase, S. Storandt, J. Zink: Consistent simplification of polyline tree bundles, in: Computing and Combinatorics, C.-Y. Chen et al. (eds.), Springer, Cham (2021) 231–243.https://doi.org/10.1007/978-3-030-89543-3_20Google Scholar
  6. W. S. Chan, F. Chin: Approximation of polygonal curves with minimum number of line segments, in: Algorithms and Computation, T. Ibaraki et al. (eds.), Springer, Berlin (1992) 378–387.https://doi.org/10.1007/3-540-56279-6_90Google Scholar
  7. L. Contento, A. Ern, R. Vermiglio: A linear-time approximate convex envelope algorithm using the double Legendre-Fenchel transform with application to phase separation, Comp. Optimization Appl. 60 (2015) 231–261.https://doi.org/10.1007/s10589-014-9666-8Google Scholar
  8. D. H. Douglas, T. K. Peucker: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature, Cartographica 10 (1973) 112–122.https://doi.org/10.3138/FM57-6770-U75U-7727Google Scholar
  9. B. Gardiner, K. Jakee, Y. Lucet: Computing the partial conjugate of convex piecewise linear-quadratic bivariate functions, Comp. Optimization Appl. 58 (2014) 249–272.https://doi.org/10.1007/s10589-013-9622-zGoogle Scholar
  10. B. Gardiner, Y. Lucet: Convex hull algorithms for piecewise linear-quadratic functions in computational convex analysis, Set-Valued Var. Analysis 18 (2010) 467–482.https://doi.org/10.1007/s11228-010-0157-5Google Scholar
  11. B. Gardiner, Y. Lucet: Graph-matrix calculus for computational convex analysis, in: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, H. H. Bauschke et al. (eds.), Springer Optimization and Its Applications Vol. 49, Springer, New York (2011) 243–259.https://doi.org/10.1007/978-1-4419-9569-8_12Google Scholar
  12. M. Godau: A natural metric for curves – computing the distance for polygonal chains and approximation algorithms, in: Theoretical Aspects of Computer Science, Proc. Symp. Hamburg 1991, Lecture Notes in Computer Science 480, Springer, Berlin (1991) 127–136.https://doi.org/10.1007/BFb0020793Google Scholar
  13. N. Goldberg, S. Rebennack, Y. Kim, V. Krasko, S. Leyffer: MINLP formulations for continuous piecewise linear function fitting, Comp. Optimization Appl. 79/1 (2021) 223–233.https://doi.org/10.1007/s10589-021-00268-5Google Scholar
  14. I. Goodfellow, Y. Bengio, A. Courville: Deep Learning, MIT Press (2016).Google Scholar
  15. Gurobi Optimizer Reference Manual (11.0): Gurobi Optimization LLC (2024).Google Scholar
  16. T. Haque, Y. Lucet: A linear-time algorithm to compute the conjugate of convex piecewise linear-quadratic bivariate functions, Comp. Optimization Appl. 70 (2018) 593–613.https://doi.org/10.1007/s10589-018-0007-1Google Scholar
  17. D. Henrion, J. B. Lasserre: GloptiPoly: Global optimization over polynomials with MATLAB and SeDuMi, ACM Trans. Math. Software 29 (2003) 165–194.https://doi.org/10.1145/779359.779363Google Scholar
  18. J.-B. Hiriart-Urruty, Y. Lucet: Parametric computation of the Legendre-Fenchel conjugate, J. Convex Analysis 14 (2007) 657–666.https://doi.org/10.68381/jca14039Google Scholar
  19. J. Hull: Options, Futures and Other Derivatives, Pearson, London (2002).Google Scholar
  20. A. Iannantuono, W. Hare, Y. Lucet: Optimization with regularization to create sensible vertical alignments in road design, Decision Analytics J. 6 (2023), art.no. 100183.https://doi.org/10.1016/j.dajour.2023.100183Google Scholar
  21. H. Imai, M. Iri: Polygonal approximations of a curve – formulations and algorithms, Machine Intell. Pattern Recog. 6 (1988) 71–86.https://doi.org/10.1016/B978-0-444-70467-2.50011-4Google Scholar
  22. K. Kazda, X. Li: A linear programming approach to difference-of-convex piecewise linear approximation, Eur. J. Oper. Res. 312 (2024) 493–511.https://doi.org/10.1016/j.ejor.2023.07.026Google Scholar
  23. H. Konno, T. Kuno: Best piecewise constant approximation of a function of single variable, Oper. Res. Letters 7 (1988) 205–210.https://doi.org/10.1016/0167-6377(88)90030-2Google Scholar
  24. J. Lofberg: YALMIP: a toolbox for modeling and optimization in MATLAB, in: Proc. IEEE Int. Conf. Robotics Automation, Taipei (2004) 284–289.https://doi.org/10.1109/CACSD.2004.1393890Google Scholar
  25. Y. Lucet: Faster than the fast Legendre transform, the linear-time Legendre transform, Numer. Algorithms 16 (1997) 171–185.https://doi.org/10.1023/A:1019191114493Google Scholar
  26. Y. Lucet: Fast Moreau envelope computation. I: Numerical algorithms, Numer. Algorithms 43 (2006) 235–249.https://doi.org/10.1007/s11075-006-9056-0Google Scholar
  27. Y. Lucet: What shape is your conjugate? A survey of computational convex analysis and its applications, SIAM Review 52 (2010) 505–542.https://doi.org/10.1137/100788458Google Scholar
  28. Y. Lucet, H. H. Bauschke, M. Trienis: The piecewise linear-quadratic model for computational convex analysis, Comp. Optimization Appl. 43 (2009) 95–118.https://doi.org/10.1007/s10589-007-9124-yGoogle Scholar
  29. S. G. Mallat, E. A. A. Books: A Wavelet Tour of Signal Processing: the Sparse Way, 3rd ed., Elsevier / Academic Press, Amsterdam (2009).Google Scholar
  30. H. Markowitz: Portfolio selection, J. Finance 7 (1952) 77–91.https://doi.org/10.1111/j.1540-6261.1952.tb01525.xGoogle Scholar
  31. R. Mohr, M. Coblenz, P. Kirst: Globally optimal univariate spline approximations, Comp. Optimization Appl. 85/2 (2023) 409–439.https://doi.org/10.1007/s10589-023-00462-7Google Scholar
  32. N. S. Momo, W. Hare, Y. Lucet: Modeling side slopes in vertical alignment resource road construction using convex optimization, Comp.-Aided Civil Infrastructure Eng. 38 (2023) 211–224.https://doi.org/10.1111/mice.12879Google Scholar
  33. S. Nickel, C. Steinhardt, H. Schlenker, W. Burkart, M. Reuter-Oppermann: IBM ILOG CPLEX Optimization Studio V12.10.0, IBM (2020) 9–23.https://doi.org/10.1007/978-3-662-62185-1_2Google Scholar
  34. N. Nisan, T. Roughgarden, E. Tardos, V. Vazirani: Algorithmic Game Theory, Cambridge University Press, Cambridge (2007).https://doi.org/10.1017/CBO9780511800481Google Scholar
  35. U. Ramer: An iterative procedure for the polygonal approximation of plane curves, Comp. Graphics Image Proc. 1 (1972) 244–256.https://doi.org/10.1016/S0146-664X(72)80017-0Google Scholar
  36. J. B. Rawlings, D. Q. Mayne, M. M. Diehl: Model Predictive Control: Theory and Design, Nob Hill Publishing, Madison (2009).Google Scholar
  37. S. Rebennack, J. Kallrath: Continuous piecewise linear delta-approximations for univariate functions: Computing minimal breakpoint systems, J. Optimization Theory Appl. 167 (2014) 617–643.https://doi.org/10.1007/s10957-014-0687-3Google Scholar
  38. K. Reumann, A. P. M. Witkam: Optimizing curve segmentation in computer graphics, in: Proc. Int. Computing Symposium, Davos 1973, North-Holland, Amsterdam (1974) 467–472.Google Scholar
  39. R. T. Rockafellar, R. J.-B. Wets: Variational Analysis, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  40. N. V. Sahinidis: BARON Branch and Reduce Optimization Navigator, User’s Manual Version 4.0, June 2000.Google Scholar
  41. S. Shalev-Shwartz, S. Ben-David: Understanding Machine Learning: From Theory to Algorithms, Cambridge University Press, Cambridge (2013).https://doi.org/10.1017/CBO9781107298019Google Scholar
  42. S. Singh, Y. Lucet: Linear-time convexity test for low-order piecewise polynomials, SIAM J. Optimization 31 (2021) 972–990.https://doi.org/10.1137/19M1290851Google Scholar
  43. J. Spoerhase, S. Storandt, J. Zink: Simplification of polyline bundles, in: Proc. 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT’20), S. Albers (ed.), LIPIcs Vol. 162, Leibniz-Zentrum für Informatik (2020) 35:1–35:20.Google Scholar
  44. The MathWorks Inc.: MATLAB, version: 9.13.0 (R2022b) (2022).Google Scholar
  45. M. Visvalingam, D. Whyatt: The Douglas‐Peucker algorithm for line simplification: Re‐evaluation through visualization, Computer Graphics Forum 9 (2007) 213–225.https://doi.org/10.1111/j.1467-8659.1990.tb00398.xGoogle Scholar
  46. J. A. Warwicker, S. Rebennack: A comparison of two mixed-integer linear programs for piecewise linear function fitting, INFORMS J. Computing 34 (2021) 1042–1047.https://doi.org/10.1287/ijoc.2021.1114Google Scholar

Suggested citation

N. Kundu, Y. Lucet. “Closest Univariate Convex Linear-Quadratic Function Approximation with Minimal Number of Pieces.” Journal of Convex Analysis 32 (2025), No. 2, 467–486. https://doi.org/10.68381/jca32023

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2025. Rights now held by Banach Press LLC.