Solving Inequality Constrained Spline Optimization Problems

We solve various variational spline curve problems subject to polygonal constraints, including best near interpolation, smoothing splines with obstacles, shape preserving spines, best spline by spline approximation, and polynomial degree reduction with polygonal constraints. To solve these problems, we develop the active set method for quadratic programming. We provide necessary and sufficient conditions for global minima. We show how to efficiently implement the algorithm using rank one updates of QR factorizations, without the need for dual bases. We show that the algorithm will converge in finite steps (under certain conditions), which solves an open problem posed in the literature. We show that solutions to the problem of near interpolation under polygonal constraints are smoothing splines with weights determined from the multipliers in the active set method, which generalized in a result in the literature on near interpolation and smoothing splines, and allows us to choose optimal weights for smoothing splines. We generalize the problem of polynomial degree reduction with box constraints to polygonal and circular constraints. Furthermore, we supplement this with an iterative technique for better choosing data sites and knots so as to further minimize the bending energy of near interpolant spline curves, offering an easy solution to the problem of best spline interpolation with free data sites and free knots.