{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T03:34:51Z","timestamp":1775360091701,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T00:00:00Z","timestamp":1677542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Hochschule f\u00fcr Wirtschaft und Gesellschaft Ludwigshafen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We revisit the problem of computing optimal spline approximations for univariate least-squares splines from a combinatorial optimization perspective. In contrast to most approaches from the literature we aim at globally optimal coefficients as well as a globally optimal placement of a fixed number of knots for a discrete variant of this problem. To achieve this, two different possibilities are developed. The first approach that we present is the formulation of the problem as a mixed-integer quadratically constrained problem, which can be solved using commercial optimization solvers. The second method that we propose is a branch-and-bound algorithm tailored specifically to the combinatorial formulation. We compare our algorithmic approaches empirically on both, real and synthetic curve fitting data sets from the literature. The numerical experiments show that our approach to tackle the least-squares spline approximation problem with free knots is able to compute solutions to problems of realistic sizes within reasonable computing times.<\/jats:p>","DOI":"10.1007\/s10589-023-00462-7","type":"journal-article","created":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T19:03:06Z","timestamp":1677610986000},"page":"409-439","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Globally optimal univariate spline approximations"],"prefix":"10.1007","volume":"85","author":[{"given":"Robert","family":"Mohr","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-3856","authenticated-orcid":false,"given":"Maximilian","family":"Coblenz","sequence":"additional","affiliation":[]},{"given":"Peter","family":"Kirst","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,2,28]]},"reference":[{"issue":"3","key":"462_CR1","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1016\/S0096-3003(03)00179-6","volume":"149","author":"G Beliakov","year":"2004","unstructured":"Beliakov, G.: Least squares splines with free knots: global optimization approach. Appl. Math. Comput. 149(3), 783\u2013798 (2004)","journal-title":"Appl. Math. Comput."},{"key":"462_CR2","volume-title":"Introduction to Linear Optimization","author":"D Bertsimas","year":"1997","unstructured":"Bertsimas, D., Tsitsiklis, J.N.: Introduction to Linear Optimization. Athena Scientific, Belmont, MA (1997)"},{"key":"462_CR3","volume-title":"Branch-and-Bound Applications in Combinatorial Data Analysis. Statistics and Computing","author":"MJ Brusco","year":"2005","unstructured":"Brusco, M.J., Stahl, S.: Branch-and-Bound Applications in Combinatorial Data Analysis. Statistics and Computing. Springer, New York, NY (2005)"},{"key":"462_CR4","unstructured":"IBM ILOG CPLEX V12.7, Users manual for CPLEX. International Business Machines Corporation (2017)"},{"issue":"1","key":"462_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1093\/imanum\/1.1.3","volume":"1","author":"MG Cox","year":"1981","unstructured":"Cox, M.G.: The least squares solution of overdetermined linear equations having band or augmented band structure. IMA J. Numer. Anal. 1(1), 3\u201322 (1981)","journal-title":"IMA J. Numer. Anal."},{"key":"462_CR6","unstructured":"de\u00a0Boor, C., Rice, J.R.: Least squares cubic spline approximation, II\u2014variable knots. Technical Report No. CSD TR 21, Purdue University (1968)"},{"key":"462_CR7","volume-title":"A practical guide to splines","author":"C de Boor","year":"2001","unstructured":"de Boor, C.: A practical guide to splines. Springer, Berlin (2001)"},{"issue":"3","key":"462_CR8","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1111\/1467-9868.00128","volume":"60","author":"DGT Denison","year":"1998","unstructured":"Denison, D.G.T., Mallick, B.K., Smith, A.F.M.: Automatic Bayesian curve fitting. J. R. Stat. Soc.: Ser. B (Methodol.) 60(3), 333\u2013350 (1998)","journal-title":"J. R. Stat. Soc.: Ser. B (Methodol.)"},{"key":"462_CR9","volume-title":"Curve and surface fitting with splines. Monographs on Numerical Analysis","author":"P Dierckx","year":"1996","unstructured":"Dierckx, P.: Curve and surface fitting with splines. Monographs on Numerical Analysis. Clarendon Press, Oxford (1996)"},{"issue":"4","key":"462_CR10","doi-asserted-by":"publisher","first-page":"1055","DOI":"10.1093\/biomet\/88.4.1055","volume":"88","author":"I DiMatteo","year":"2001","unstructured":"DiMatteo, I., Genovese, C.R., Kass, R.E.: Bayesian curve-fitting with free-knot splines. Biometrika 88(4), 1055\u20131071 (2001)","journal-title":"Biometrika"},{"issue":"341","key":"462_CR11","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1080\/01621459.1973.10481353","volume":"68","author":"A Ronald Gallant","year":"1973","unstructured":"Ronald Gallant, A., Fuller, W.A.: Fitting segmented polynomial regression models whose join points have to be estimated. J. Am. Stat. Assoc. 68(341), 144\u2013147 (1973)","journal-title":"J. Am. Stat. Assoc."},{"issue":"3","key":"462_CR12","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1093\/imamat\/12.3.329","volume":"12","author":"W Morven Gentleman","year":"1973","unstructured":"Morven Gentleman, W.: Least squares computations by givens transformations without square roots. IMA J. Appl. Math. 12(3), 329\u2013336 (1973)","journal-title":"IMA J. Appl. Math."},{"issue":"2","key":"462_CR13","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1137\/0710036","volume":"10","author":"GH Golub","year":"1973","unstructured":"Golub, G.H., Pereyra, V.: The differentiation of pseudo-inverses and nonlinear least squares problems whose variables separate. SIAM J. Numer. Anal. 10(2), 413\u2013432 (1973)","journal-title":"SIAM J. Numer. Anal."},{"key":"462_CR14","unstructured":"Gurobi Optimization, LLC Gurobi Optimizer Reference Manual (2020)"},{"issue":"1","key":"462_CR15","first-page":"1","volume":"30","author":"DJ Hand","year":"1981","unstructured":"Hand, D.J.: Branch and bound in statistical data analysis. J. R. Stat. Soc. Ser. D (The Statistician) 30(1), 1\u201313 (1981)","journal-title":"J. R. Stat. Soc. Ser. D (The Statistician)"},{"key":"462_CR16","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1093\/imanum\/13.3.365","volume":"13","author":"H Yingkang","year":"1993","unstructured":"Yingkang, H.: An algorithm for data reduction using splines with free knots. IMA J. Numer. Anal. 13, 365\u2013381 (1993)","journal-title":"IMA J. Numer. Anal."},{"issue":"2","key":"462_CR17","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1137\/0715022","volume":"15","author":"DL Jupp","year":"1978","unstructured":"Jupp, D.L.: Approximation to data by splines with free knots. SIAM J. Numer. Anal. 15(2), 328\u2013343 (1978)","journal-title":"SIAM J. Numer. Anal."},{"issue":"2","key":"462_CR18","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0021-9290(82)90041-0","volume":"15","author":"H Lanshammar","year":"1982","unstructured":"Lanshammar, H.: On practical evaluation of differentiation techniques for human gait analysis. J. Biomech. 15(2), 99\u2013105 (1982)","journal-title":"J. Biomech."},{"issue":"8","key":"462_CR19","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1080\/00949650213743","volume":"72","author":"TC Lee","year":"2002","unstructured":"Lee, T.C.: On algorithms for ordinary least squares regression spline fitting: a comparative study. J. Stat. Comput. Simul. 72(8), 647\u2013663 (2002)","journal-title":"J. Stat. Comput. Simul."},{"issue":"2","key":"462_CR20","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1080\/10618600.1999.10474817","volume":"8","author":"MJ Lindstrom","year":"1999","unstructured":"Lindstrom, M.J.: Penalized estimation of free knot splines. J. Comput. Graph. Stat. 8(2), 333\u2013352 (1999)","journal-title":"J. Comput. Graph. Stat."},{"issue":"1","key":"462_CR21","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1214\/aos\/1034276635","volume":"25","author":"E Mammen","year":"1997","unstructured":"Mammen, E., van de Geer, S.: Locally adaptive regression splines. Ann. Stat. 25(1), 387\u2013413 (1997)","journal-title":"Ann. Stat."},{"issue":"5","key":"462_CR22","doi-asserted-by":"publisher","first-page":"362","DOI":"10.1007\/BF01436249","volume":"7","author":"RS Martin","year":"1965","unstructured":"Martin, R.S., Peters, G., Wilkinson, J.H.: Symmetric decomposition of a positive definite matrix. Numer. Math. 7(5), 362\u2013383 (1965)","journal-title":"Numer. Math."},{"issue":"1","key":"462_CR23","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1198\/1061860031284","volume":"12","author":"S Miyata","year":"2003","unstructured":"Miyata, S., Shen, X.: Adaptive free-knot splines. J. Comput. Graph. Stat. 12(1), 197\u2013213 (2003)","journal-title":"J. Comput. Graph. Stat."},{"key":"462_CR24","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372","volume-title":"Integer and Combinatorial Optimization","author":"GL Nemhauser","year":"1988","unstructured":"Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience, New York, NY (1988)"},{"key":"462_CR25","volume-title":"Combinatorial Optimization: Algorithms and Complexity","author":"CH Papadimitriou","year":"1982","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Prentice-Hall Inc, Upper Saddle River, NJ (1982)"},{"issue":"5\u20136","key":"462_CR26","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/0021-9290(77)90010-0","volume":"10","author":"JC Pezzack","year":"1977","unstructured":"Pezzack, J.C., Norman, R.W., Winter, D.A.: An assessment of derivative determining techniques used for motion analysis. J. Biomech. 10(5\u20136), 377\u2013382 (1977)","journal-title":"J. Biomech."},{"issue":"7","key":"462_CR27","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1109\/34.865188","volume":"22","author":"J Pittman","year":"2000","unstructured":"Pittman, J., Murthy, C.A.: Fitting optimal piecewise linear functions using genetic algorithms. IEEE Trans. Pattern Anal. Mach. Intell. 22(7), 701\u2013718 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"343","key":"462_CR28","first-page":"515","volume":"68","author":"DJ Poirier","year":"1973","unstructured":"Poirier, D.J.: Piecewise regression using cubic splines. J. Am. Stat. Assoc. 68(343), 515\u2013524 (1973)","journal-title":"J. Am. Stat. Assoc."},{"issue":"4","key":"462_CR29","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1198\/106186002853","volume":"11","author":"D Ruppert","year":"2002","unstructured":"Ruppert, D.: Selecting the number of knots for penalized splines. J. Comput. Graph. Stat. 11(4), 735\u2013757 (2002)","journal-title":"J. Comput. Graph. Stat."},{"issue":"3","key":"462_CR30","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF01732610","volume":"35","author":"H Schwetlick","year":"1995","unstructured":"Schwetlick, H., Sch\u00fctze, T.: Least squares approximation by splines with free knots. BIT Numer. Math. 35(3), 361\u2013384 (1995)","journal-title":"BIT Numer. Math."},{"key":"462_CR31","unstructured":"Smith, P.L.: Curve fitting and modeling with splines using statistical variable selection techniques. Report NASA 166034, NASA Langley Research Center, Hampton (1982)"},{"issue":"6","key":"462_CR32","doi-asserted-by":"publisher","first-page":"1020","DOI":"10.1080\/00949655.2011.647317","volume":"83","author":"S Spiriti","year":"2013","unstructured":"Spiriti, S., Eubank, R., Smith, P.W., Young, D.: Knot selection for least-squares and penalized splines. J. Stat. Comput. Simul. 83(6), 1020\u20131036 (2013)","journal-title":"J. Stat. Comput. Simul."},{"key":"462_CR33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-55360-2","volume-title":"Grundz\u00fcge der Globalen Optimierung","author":"O Stein","year":"2018","unstructured":"Stein, O.: Grundz\u00fcge der Globalen Optimierung. Springer Spektrum, Berlin (2018)"},{"issue":"4","key":"462_CR34","doi-asserted-by":"publisher","first-page":"1371","DOI":"10.1214\/aos\/1031594728","volume":"25","author":"CJ Stone","year":"1997","unstructured":"Stone, C.J., Hansen, M.H., Kooperberg, C., Truong, Y.K.: Polynomial splines and their tensor products in extended linear modeling. Ann. Stat. 25(4), 1371\u20131425 (1997)","journal-title":"Ann. Stat."},{"key":"462_CR35","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s001800000047","volume":"15","author":"MP Wand","year":"2000","unstructured":"Wand, M.P.: A comparison of regression spline smoothing procedures. Comput. Stat. 15, 443\u2013462 (2000)","journal-title":"Comput. Stat."},{"issue":"1","key":"462_CR36","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/00401706.1974.10489142","volume":"16","author":"S Wold","year":"1974","unstructured":"Wold, S.: Spline functions in data analysis. Technometrics 16(1), 1\u201311 (1974)","journal-title":"Technometrics"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00462-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00462-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00462-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,15]],"date-time":"2024-10-15T11:08:46Z","timestamp":1728990526000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00462-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,28]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["462"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00462-7","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,28]]},"assertion":[{"value":"11 October 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 February 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No funds, grants, or other support was received. The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}