Quadratic convergence of Newton's method for convex interpolation and smoothing (Q1864181)

The paper is concerned with the convergence of Newton's method for solving the convex interpolation problem: (1) minimize \(\|f''\|_2\) subject to \(f(t_i) = y_i\), \(i=1,2,\dots , N+2\), with \(f\in W^{2.2}\) convex on \([a,b]\), where \(a=t_1<t_2<\dots <t_{N+2}=b,\) and \(y_i\) are given. One supposes that the divided differences \(d_i\) at \((t_i,y_i)\) are all strictly positive. In a previous paper [Numer. Math. 87, No. 3, 435-456 (2001; Zbl 0970.65009)] the authors have shown that problem (1) has a unique solution which is a cubic spline. It turns out that problem (1) is equivalent to its Lagrange dual: \[ \max_{\lambda\in \mathbb R^N}\left[-\frac{1}{2}\int_a^b\left(\sum_{i=1}^N \lambda _iB_i(t)\right)_+^2 dt + \sum_{i=1}^N\lambda _id_i\right], \] where \(B_i\) are the normalized cubic spline. In the second section of the paper the authors study the analytic properties of the function \(F\) given by \[ F_k(\lambda) = \int_a^b\left(\sum_{i=1}^N \lambda _iB_i(t)\right)_+ ^2B_i(t) dt. \] Since the function \(F\) is Lipschitz, by Rademacher's theorem it is differentiable a.e., and the study is carried out via Bouligand's generalized Jacobian. A damped Newton method, having global quadratic convergence, is also presented. Similar results are obtained also for the convex smoothing method. The paper ends with some numerical examples.