Univariate cubic L 1 splines – A geometric programming approach

Univariate cubic L 1 splines provide C 1 -smooth, shape-preserving interpolation of arbitrary data, including data with abrupt changes in spacing and magnitude. The minimization principle for univariate cubic L 1 splines results in a nondifferentiable convex optimization problem. In order to provide theoretical treatment and to develop efficient algorithms, this problem is reformulated as a generalized geometric programming problem. A geometric dual with a linear objective function and convex quadratic constraints is derived. A linear system for dual to primal conversion is established. The results of computational experiments are presented. In the natural norm for this class of problems, namely, the L 1 norm of the second derivative, the geometric programming approach finds better solutions than the previously used discretization method. Copyright Springer-Verlag Berlin Heidelberg 2002