Spline fit with bounded derivations

How can I do a Spline Fit with bounds on some derivations?

Problem

Given:

• Set of data points $t_k, x_k$
• Set of nodes $n_i$
• order $D$ of the spline (in my case $D=5$)
• lower and upper bounds $m_d$,$M_d$ on the $d$-th derivation for $1\le d \le r$ (in my case $r=3$)

Wanted:

The spline $f$ (of order $D$) with nodes $n_i$, that fits the data point best in terms of square errors (ie. $f$ minimizes $\sum_k{(f(t_k)-x_k)^2}$) under the condition that $m_d \le f \le M_d$ for $1 \le d \le r$

Discussion

Without the restriction on the derivations this is a well known procedure, refer for example to: http://www.geometrictools.com/Documentation/BSplineCurveLeastSquaresFit.pdf

Maybe this problem can be dealt with convex optimization, since the set of splines, that meet the restrictions, is convex and the function to be minimized is a quadratic form on the coefficients of the spline. But I don't know much about convex optimization, so I would be grateful for a reference on a text that fits best to the problem at hand.

For my purposes, it doesn't need to be a least square fit. A fit, that minimizes the maximum distance would be as useful or even better. Possible advantage: the maximum is a convex function. Disadvantage: the maximum is not partially differentiable in the coefficients.

-

1 Answer

See section 6.5.2 of the book "Convex Optimization" by Stephen Boyd and Lieven Vandenberghe. It's available on the web as a pdf file or as a quite reasonably priced printed book from Cambridge University Press. See the book's web page at:

http://www.stanford.edu/~boyd/cvxbook/

-
Thanks a lot. It seems like that book and section covers my problem. Now I have to backtrace the book from page 330 to see how the calculations are actually done. – Max Kubierschky Nov 10 '11 at 15:24
The material on algorithms for solving convex optimization problems is actually later in the book. However, I have to say that the coverage of algorithms for solving convex optimzation problems in Boyd and Vandenberghe is much less useful than the material on formulating convex optimization problems and the basic theory (optimality conditions, etc.) that is in this book. Frankly, you should try to implement your own solver. Rather, use a well supported package such as CVX to do the work. – Brian Borchers Nov 11 '11 at 4:46