A theorem for piecewise convex–concave data approximation

摘要

We are given univariate data that include random errors. We consider the problem of calculating a best approximation to the data by minimizing a strictly convex function of the errors subject to the condition that there are at most q sign changes in the sequence of the second divided differences of the approximation, where q is a prescribed integer. There are about O(nq) combinations of positions of sign changes, which make an exhaustive approach prohibitively expensive. However, Demetriou and Powell (Approximation Theory and Optimization, Cambridge University Press, Cambridge, 1997, pp. 109–132), have proved the remarkable property that there exists a partitioning of the data into (q+1) disjoint subsets such that the approximation may be calculated by a separate convex programming calculation on each subset. Based on this result, we provide a characterization theorem that reduces the problem to an equivalent one, where the unknowns are the positions of the sign changes subject to feasibility restrictions at the sign changes. Furthermore, we present counterexamples on two conjectures that investigate whether the search for optimal sign changes may be restricted to certain subranges of the data.