Armijo Newton method for convex best interpolation

Hou Duo Qi, Xiaoqi Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

Newton's method with Armijo line search (Armijo Newton method) has been practically known extremely efficient for the problem of convex best interpolation and numerical experiment strongly indicates its global convergence. However, similar to the classical Newton method, the Newton matrix far from the solution may be singular or near singular, posing a great deal of difficulties in proving the global convergence of Armijo Newton method. 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 [at cost of O ( N ), N is the dimension of the problem] find a nearby point which has a well-conditioned Newton matrix and lower function value. In this case, Armijo Newton method starts from this nearby point. We prove that this slightly modified Armijo Newton method is globally as well as locally quadratically convergent, and in an important case, it also has finite termination property. Numerical results demonstrate the efficiency of the proposed method.
Original languageEnglish
Pages (from-to)179-200
Number of pages22
JournalOptimization Methods and Software
Volume21
Issue number2
DOIs
Publication statusPublished - 1 Apr 2006

Keywords

  • Convex interpolation
  • Line search
  • Newton's method

ASJC Scopus subject areas

  • Software
  • Control and Optimization
  • Applied Mathematics

Cite this