Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming

Lakshman S. Thakur and Mikhail A. Bragin
Additional contact information
Lakshman S. Thakur: Department of Operations and Information Management, School of Business, University of Connecticut, Storrs, CT 06269, USA
Mikhail A. Bragin: Department of Electrical and Computer Engineering, School of Engineering, University of Connecticut, Storrs, CT 06269, USA

Mathematics, 2021, vol. 9, issue 10, 1-12

Abstract: The problem of obtaining an optimal spline with free knots is tantamount to minimizing derivatives of a nonlinear differentiable function over a Banach space on a compact set. While the problem of data interpolation by quadratic splines has been accomplished, interpolation by splines of higher orders is far more challenging. In this paper, to overcome difficulties associated with the complexity of the interpolation problem, the interval over which data points are defined is discretized and continuous derivatives are replaced by their discrete counterparts. The l ? -norm used for maximum r th order curvature (a derivative of order r ) is then linearized, and the problem to obtain a near-optimal spline becomes a linear programming (LP) problem, which is solved in polynomial time by using LP methods, e.g., by using the Simplex method implemented in modern software such as CPLEX. It is shown that, as the mesh of the discretization approaches zero, a resulting near-optimal spline approaches an optimal spline. Splines with the desired accuracy can be obtained by choosing an appropriately fine mesh of the discretization. By using cubic splines as an example, numerical results demonstrate that the linear programming (LP) formulation, resulting from the discretization of the interpolation problem, can be solved by linear solvers with high computational efficiency and the resulting spline provides a good approximation to the sought-for optimal spline.

Keywords: optimal splines; linear programming; data interpolation; splines with free knots (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/10/1099/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/10/1099/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:10:p:1099-:d:553756

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().