Convergence of Newton's method for singular smooth and nonsmooth equations using adaptive outer inverses

Xiaojun Chen, Zuhair Nashed, Liqun Qi

Research output: Journal article publicationJournal articleAcademic researchpeer-review

45 Citations (Scopus)

Abstract

We present a local convergence analysis of generalized Newton methods for singular smooth and nonsmooth operator equations using adaptive constructs of outer inverses. We prove that for a solution x* of F(x) = 0, there exists a ball S = S(x*, r), r > 0 such that for any starting point x0∈ S the method converges to a solution x̄* ∈ S of ΓF(x) = 0, where Γ is a bounded linear operator that depends on the Fréchet derivative of F at x0or on a generalized Jacobian of F at x0. Point x̄* may be different from x* when x* is not an isolated solution. Moreover, we prove that the convergence is quadratic if the operator is smooth and superlinear if the operator is locally Lipschitz. These results are sharp in the sense that they reduce in the case of an invertible derivative or generalized derivative to earlier theorems with no additional assumptions. The results are illustrated by a system of smooth equations and a system of nonsmooth equations, each of which is equivalent to a nonlinear complementarity problem.
Original languageEnglish
Pages (from-to)445-462
Number of pages18
JournalSIAM Journal on Optimization
Volume7
Issue number2
DOIs
Publication statusPublished - 1 Jan 1997
Externally publishedYes

Keywords

  • Convergence theory
  • Newton's method
  • Nonlinear complementarity problems
  • Nonsmooth analysis
  • Outer inverses

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science

Cite this