THE MINIMUM SUM OF SQUARES CHANGE TO UNIVARIATE DATA THAT GIVES CONVEXITY

Let n measurements of a real valued function of one variable be given. If the function is convex but the data have lost convexity due to the errors of the measuring process, then the least sum of squares change to the data that provides nonnegative second divided differences may be required. An algorithm is proposed for this highly structured quadratic programming calculation. First a procedure that requires only O(n) computer operations generates a starting point for the main calculation, and then a version of the iterative method of Goldfarb & Idnani (1983) is applied. It is proved that the algorithm converges, the analysis being a special case of the theory of Goldfarb & Idnani. The algorithm is efficient because the matrices that occur are banded due to representing the required fit as a linear combination of B-splines. Some numerical results illustrate the method. They suggest that the algorithm can be used when n is very large, because the O(n) starting procedure identifies most of the convexity constraints that are active at the solution.