Polynomial regression with penalty for non-smoothness

I am looking for a solution to the following curve fitting problem.

Given a sample of data points $\{ (x_i, y_i)_{i=1}^n \}$:

$$\underset{f}{\arg\min} \sum_{i=1}^n (y_i - f(x_i))^2 + \lambda \int_{x_{(1)}}^{x_{(n)}} f''(x)^2 dx,$$

where $f(x)$ is constrained to be a polynomial of fixed degree $p\,$ ($\ge 2$), that is $f(x) = c_0 + c_1 x^1 + ... + c_p x^p$. And $\lambda\,$ ($\ge 0$) is fixed as well.

• What is your integration domain in the penalty-term? Jan 19, 2017 at 14:19
• The domain/range of $x$ or $[\min(x_i), \max(x_i)]$
– Jim
Jan 19, 2017 at 14:20

By minimizing $f$ you basically minizime over $c_0$ to $c_p$, so you can replace the functional by $$min_{c_1, ...c_p} \sum_{i=1}^n(y_i - \sum_{q=0}^pc_q x^q)^2 + \lambda \int_{x_1}^{x_n}2c_2 +6c_3x + 12c_4 x^2 + \dotsc + p(p-1)c_px^{p-2} dx$$ You want to minimize along all $c$, so you should get partial derivatives. The first sum is quite easy being qudratic in every $c_i$ while the integral is even linear in every $c_i$.
The second derivative could have negative values. So if it should be used as a "penalty", I think it should better be $$\min_f \sum_{i=1}^n (y_i-f(x_i))^2 +\lambda\int\left(f''(x)\right)^2dx$$ The function that is going to be minimized is an expression with the variables $c_0,\ldots,c_p$. You can differentiate with respect to those variables and try to achieve that all derivatives are $0$, which will yield a system of linear equations, which in turn can be solved e.g. with Gaussian elimination.