Polynomial interpolation to LP How I can convert next program to LP (linear programming) or to get some direction how to do this (references).
The problem is :


  I want to find a polynomial $P$ of degree at most $d$ that $||P(x)-y||_1$ is minimal.
  Where $x, y$ vectors in $\mathbb{R}^n$ and $P$ is vector of $(p(x_1), \ldots, p(x_n))$
Let $A$ be the Vandermonde Matrix of $x_1,x_2,...$ then if $z$ is the Vector of polynomial coefficients $z=(a_0,a_1,...)^t$ it is $P(x)=Az$.

For $\textrm{min }||Az-y||_2$ the solution is $z=(A^tA)^{-1}A^ty$.

The problem $\textrm{min }||Az-y||_1$ is equivalent to the LP

minimize $\sum \lambda_i$

subject to 

$+Az-I\lambda&lt;=+y$

and

$-Az-I\lambda&lt;=-y$

with $\lambda:=(\lambda_1,...)$

In the following change $||Az-y||$ to $||Ax-b||$

Here's some matlab code that does polynomial regression

This is the output from the code:
I suppose that if you want to find $P$, this means that $x$ and $y$ are known vectors. If you also know $d$, than your polynomial becomes $p(x) = \sum_{k=1}^d a_k x^k$. You can formulate your linear programming problem as :

$$\min z = \sum_{i = 1}^n p_i + n_i$$
subject to
$$ p_i - n_i + p(x_i) - y_i, \forall i=1\dots n$$
$$ 0 \le p_i, d_i &lt; \infty$$
$$ -\infty \le a_k &lt; \infty$$

In this formulation,you can take $p_i$ and $n_i$ as the positive and negative parts of the absolute value. If $p(x_i) - y_i&gt;0$, then $p_i &gt;0$ and $n_i = 0$, and conversly.

Hope this helps.