Finite termination of a dual Newton method for convex best C¹ interpolation and smoothing

Given the data (xi, yi) ∈ ℜ2, i = 0, 1,..., n which are in convex position, the problem is to choose the convex best C1 interpolant with the smallest mean square second derivative among all admissible cubic C1-splines on the grid. This problem can be efficiently solved by its dual program, developed by Schmdit and his collaborators in a series of papers. The Newton method remains the core of their suggested numerical scheme. It is observed through numerical experiments that the method terminates in a small number of steps and its total computational complexity is only of O (n). The purpose of this paper is to establish theoretical justification for the Newton method. In fact, we are able to prove its finite termination under a mild condition, and on the other hand, we illustrate that the Newton method may fail if the condition is violated, consistent with what is numerically observed for the Newton method. Corresponding results are also obtained for convex smoothing.