Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
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 order...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-05-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/10/1099 |
| _version_ | 1827692615377616896 |
|---|---|
| author | Lakshman S. Thakur Mikhail A. Bragin |
| author_facet | Lakshman S. Thakur Mikhail A. Bragin |
| author_sort | Lakshman S. Thakur |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>l</mi><mo>∞</mo></msub></semantics></math></inline-formula>-norm used for maximum <i>r</i>th order curvature (a derivative of order <i>r</i>) 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. |
| first_indexed | 2024-03-10T11:27:29Z |
| format | Article |
| id | doaj.art-1970beb0b4ed4fc095b8cbd34d7b9cce |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T11:27:29Z |
| publishDate | 2021-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-1970beb0b4ed4fc095b8cbd34d7b9cce2023-11-21T19:31:43ZengMDPI AGMathematics2227-73902021-05-01910109910.3390/math9101099Data Interpolation by Near-Optimal Splines with Free Knots Using Linear ProgrammingLakshman S. Thakur0Mikhail A. Bragin1Department of Operations and Information Management, School of Business, University of Connecticut, Storrs, CT 06269, USADepartment of Electrical and Computer Engineering, School of Engineering, University of Connecticut, Storrs, CT 06269, USAThe 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><msub><mi>l</mi><mo>∞</mo></msub></semantics></math></inline-formula>-norm used for maximum <i>r</i>th order curvature (a derivative of order <i>r</i>) 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.https://www.mdpi.com/2227-7390/9/10/1099optimal splineslinear programmingdata interpolationsplines with free knots |
| spellingShingle | Lakshman S. Thakur Mikhail A. Bragin Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming Mathematics optimal splines linear programming data interpolation splines with free knots |
| title | Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming |
| title_full | Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming |
| title_fullStr | Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming |
| title_full_unstemmed | Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming |
| title_short | Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming |
| title_sort | data interpolation by near optimal splines with free knots using linear programming |
| topic | optimal splines linear programming data interpolation splines with free knots |
| url | https://www.mdpi.com/2227-7390/9/10/1099 |
| work_keys_str_mv | AT lakshmansthakur datainterpolationbynearoptimalsplineswithfreeknotsusinglinearprogramming AT mikhailabragin datainterpolationbynearoptimalsplineswithfreeknotsusinglinearprogramming |