# 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)
Briefly, the first-order difference \(\frac{f\left(x+\frac{b}{2}\right)-f\left(x-\frac{b}{2}\right)}{h}\) divided by \(h\) can be expanded into Taylor series in the following way:  
\[\frac{f\left(x+\frac{b}{2}\right)-f\left(x-\frac{b}{2}\right)}{h}\approx\]  
\[\left(\frac{f(x)}{h}+\frac{f^{{}^{\prime}}(x)}{2}+\frac{f^{{}^{\prime\prime}}( x)}{2}h+\frac{1}{48}f^{(3)}(x)h^{2}\right)-\left(\frac{f(x)}{h}-\frac{f^{{  
from which one can observe that \(\frac{f\left(x+\frac{b}{2}\right)-f\left(x-\frac{b}{2}\right)}{h}-f^{{}^{\prime}} (x)=O(h^{2})\) while \(\frac{f\left(x+h\right)-f\left(x\right)}{h}-f^{{}^{\prime}}(x)=O(h)\). Similar arguments hold for higher order finite differences.  
Even though the forward difference approximates the \(r\)th derivative at \(\hat{x}_{j}\) with the error of the order of \(O(h)\), it approximates the \(r\)th derivative at midpoint \(\frac{\hat{x}_{j+1}+\hat{x}_{j+2}}{2}\) with the error of the order of \(O(h^{2})\), as in the discussion of central differences above. Indeed, if we denote \(\hat{z}_{j}=\frac{\hat{x}_{j+1}+\hat{x}_{j+2}}{2}\), then  
\[\frac{f\left(\hat{x}_{j}\right)-rf\left(\hat{x}_{j+1}\right)+\frac{r\left(r-1 \right)}{2}f\left(\hat{x}_{j+2}\right)+\dots+(-1)^{r}f\left(\hat{x}_{j+3} \right)}{h^{r}}=\]  
\[\frac{f\left(\hat{z}_{j}-\frac{3h}{2}\right)-rf\left(\hat{z}_{j}-\frac{h}{2} \right)+\frac{r\left(r-1\right)}{2}f\left(\hat{z}_{j}+\frac{h}{2}\right)+ \dots+(-1)^{r}f\left(\hat{z}_{j}+\frac{3h}{2}\right)}{h^{r}},\]  
which is the \(r\)th-order central difference, and therefore, the overall accuracy of the approximation is of the order of \(O(h^{2})\). Our approach to find a near-optimal solution of (1) and (2) is to minimize the maximum of the \(r\)th-order differences directly:  
\[\left. \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)}\max\left|\frac{\Delta_{h}^{ \prime}\left[f\right]\left(\hat{z}_{j}\right)}{h^{r}}\right|\\ s.t.,\;f\left(\hat{x}_{(m-1)i+1}\right)=y_{i},\;i=1,\dots n\end{array} \right\} \tag{3}\]  
Note that in this discretized version (and for the rest of the paper), points denoted by \(f\left(\hat{x}_{j}\right)\) are decision variables, where \(\hat{x}_{j}=1,\dots,(n-1)m+1\) are endpoints of subintervals. Since the objective function in formulation (3) is clearly nonlinear due to \(max\) and absolute value operators, in order to deal with this nonlinearity, the problem is converted into an equivalent linear counterpart (similar to ([58], p. 28)):  
\[\left. \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)}\\ s.t.,\;\frac{\Delta_{h}^{\prime}\left[f\right]\left(\hat{z}_{j}\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\} \tag{4}\]  
Since \(f\left(\hat{x}_{(m-1)i+1}\right)=y_{i}\) are given as data, the actual decision variables to determine are \(f\left(\hat{x}_{j}\right)\), with the exception of \(f\left(\hat{x}_{(m-1)i+1}\right)\), \(i=1,\dots,n\), although for more convenient implementation, \(f\left(\hat{x}_{(m-1)i+1}\right)\) can still be treated as decision variables. Additionally, due to linearity, (4) can be solved with much higher efficiency than (3); regardless of the problem instance, formulation (4) remains the LP problem and the LP optimization methods converge within the polynomial time, as discussed above. The reduction of complexity is generally the goal of all linearization processes used to deal with nonlinearity from a computational perspective. Theorem 3.1: _The optimal value of formulation (4) approaches \(k^{*}\), which is the optimal value of the formulation (1) and (2), as the number of subintervals approaches infinity \((m\to\infty)\)._  
Proof: As established above, formulation (4)  
\[\left.