Quadratic convergence of Newton's method for convex interpolation and smoothing
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.
- Constrained interpolation and smoothing
- The best interpolation problem with nonzero lower bounds solved by a semismooth Newton algorithm
- scientific article; zbMATH DE number 1981779
- Finite termination of a dual Newton method for convex best \(C^1\) interpolation and smoothing
- scientific article; zbMATH DE number 4077928
- Convergence of Newton's method for convex best interpolation
- Regularity and well-posedness of a dual program for convex best \(C^{1}\)-spline interpolation
- Convex interval interpolation with cubic splines. II
- An unconstrained dual program for computing convex \(C^ 1\)-spline approximants
- Convex interval interpolation with cubic splines
- Shape-preserving interpolation and smoothing for options market implied volatility
- Differentiability and semismoothness properties of integral functions and their applications
- An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
- Some properties of smooth convex functions and Newton's method
- Convergence rate of Newton's method for \(L_2\) spectral estimation
- Finite termination of a dual Newton method for convex best \(C^1\) interpolation and smoothing
- Semismoothness of solutions to generalized equations and the Moreau-Yosida regularization
- Smooth and semismooth Newton methods for constrained approximation and estimation
- The best interpolation problem with nonzero lower bounds solved by a semismooth Newton algorithm
- Quadratic Convergence of Smoothing Newton's Method for 0/1 Loss Optimization
- Computing the best approximation over the intersection of a polyhedral set and the doubly nonnegative cone
- Armijo Newton method for convex best interpolation
- Some theoretical aspects of Newton's method for constrained best interpolation
- Convergence of Newton's method for convex best interpolation
- Constrained data smoothing via optimal control
- A smoothing Newton-type method for solving the \(L _{2}\) spectral estimation problem with lower and upper bounds
- Moreau-Yosida regularization of Lagrangian-dual functions for a class of convex optimization problems
- On almost smooth functions and piecewise smooth functions
This page was built for publication: Quadratic convergence of Newton's method for convex interpolation and smoothing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1864181)
