# Data Interpolation by Near-Optimal Splines with Free Knots Using Linear Programming
## 3 Problem Formulation
### Linear Optimization Formulation for Near-Optimal Solution to (1) and (2)
\begin{array}{c}\min_{f\left(\hat{x}_{1}\right),f\left(\hat{x}_{2} \right),\dots,f\left(\hat{x}_{(m-1)n+1}\right)}k\\ s.t.,\;\frac{\Delta_{h}^{\prime}\left[f\left(\hat{x}_{j}\right)\right)}{h^{r}} \leq k,\;j=1,\dots,l-r\\ \frac{\Delta_{h}^{\prime}\left[f\right]\left(\hat{z}_{j}\right)}{h^{r}}\geq-k,\;j=1,\dots,l-r\\ f\left(\hat{x}_{(m-1)i+1}\right)=y_{i},\;i=1,\dots n\end{array} \right\}\]is equivalent to formulation (3):  
\[\left. \begin{array}{c}\min_{f(\hat{x}_{1}),f(\hat{x}_{2}),\ldots,f \left(\hat{x}_{(m-1)+1}\right)}\max\left|\frac{\Delta_{h}^{\prime}[f]\left(\hat {x}_{j}\right)]}{h^{\prime}}\\ s.t.,\ f\left(\hat{x}_{(m-1)+1}\right)=y_{i},\ i=1,\ldots n\end{array} \right\}\]  
As the number of subintervals approaches infinity \((m\rightarrow\infty)\), the third-order difference approaches the third derivative, so formulation (4) becomes  
\[\left. \begin{array}{c}\min_{f(\hat{x}_{1}),f(\hat{x}_{2}),\ldots}\max\left|f^ {(3)}\left(\hat{x}_{j}\right)\right|\\ s.t.,\ f(x_{i})=y_{i},\ i=1,\ldots n\end{array} \right\} \tag{5}\]  
Despite having the same objective function, formulation (5) is theoretically not equivalent to the formulation of the original problem (1) and (2). Any countable (even infinitely countable) set of decision variables \(\left\{f(\hat{x}_{j})\right\}\) is a set of measure zero (a set of points that can be enclosed by intervals with arbitrarily small width), whereas the space over which problem (1) and (2) is optimized is continuous, namely, the entire interval \([A,B]\). In other words, formulations (1) and (2), and (5), though they have the same objective function, are optimized over different decision variable spaces, namely, discrete and continuous, respectively. Notwithstanding the differences between formulations (1) and (2), and (5) noted above, their respective optimal values differ by an infinitesimally small value as the number of subintervals approaches infinity. Indeed, for an arbitrarily small \(\varepsilon>0\), we can always find a large enough \(m\), the number of subintervals (of each interval), such that \(\left|\hat{x}_{j}-\hat{x}_{j+1}\right|<\varepsilon\). Since the third derivative of \(f\) exists almost everywhere for a cubic spline by definition, we can define central differences at the midpoints of each subinterval \((\hat{x}_{j},\hat{x}_{j+1})\) as \(\frac{\delta_{h}^{\prime}[f]\left(\frac{\hat{x}_{j}+\hat{x}_{j+1}}{2}\right) }{h^{\prime}}=f^{(3)}(x)+O\big{(}h^{2}\big{)}\). Now, as explained before, note that  
\[\frac{\delta_{h}^{\prime}[f]\left(\frac{\hat{x}_{j}+\hat{x}_{j+1}}{2}\right) }{h^{\prime}}=\frac{\Delta_{h}^{\prime}[f]\left(\hat{x}_{j-1}\right)}{h^{ \prime}}\]  
Therefore, the optimal solution to (5) differs from the optimal solutions by a quantity of the order of \(O\big{(}h^{2}\big{)}\). In other words, for any two arbitrarily close decision variables \(f\left(\hat{x}_{j}\right)\) and \(f\left(\hat{x}_{j+1}\right)\), the respective third derivative of \(f\) evaluated at any point between them differs from the third derivative evaluated at either of these points by a quantity that is arbitrary small except possibly at the points of discontinuity of \(f^{(r)}\), which constitute a set of measure zero since \(f^{(r)}\) exists almost everywhere. Therefore, respective optimal values of formulations (5)  
\[\left. \begin{array}{c}\min_{f(\hat{x}_{1}),f(\hat{x}_{2}),\ldots}\max\left|f ^{(r)}\left(\hat{x}_{j}\right)\right|\\ s.t.f(x_{i})=y_{i},\ i=1,\ldots,n\end{array} \right\}\]  
and (1) and (2)  
\[\left. \begin{array}{c}\min_{f\in\mathbb{C}^{2}}\left\|f^{(r)}\right\|_{\infty }\\ s.t.f(x_{i})=y_{i}\end{array} \right\}\]  
differ by a quantity of the order of \(O\big{(}h^{2}\big{)}\).