Armijo Newton Method for Convex Best Interpolation

More than a decade agao, Newton's method has been proposed for constructing the convex best interpolant. Its local quadratic convergence has only been established recently by recasting it as the generalized Newton method for semismooth equations. It still remains mysterious that the Newton method coupled with line search strategies works practically well in global sense. Similar to the classical Newton method, the Newton matrix far from the solution may be singular or near singular, posing a great deal of di#culties in proving the global convergence of the Newton method with line search. By employing the objective function of Lagrange dual problem, it is observed that whenever the Newton matrix is near singular at some point, one can easily find a nearby point which has well-conditioned Newton matrix and a lower function value. Based on this fact, Newton's method with Armijo line search is shown to be globally convergent as well as locally quadratically convergent. And in an important case, it also has finite termination property. Numerical results demonstrate the e#ciency of the proposed method