Newton and quasi-Newton methods for normal maps with polyhedral sets

J. Han, Defeng Sun

Research output: Journal article publicationJournal articleAcademic researchpeer-review

7 Citations (Scopus)

Abstract

We present a generalized Newton method and a quasi-Newton method for solving H(x):=F(? c (x))+x-? c (x)=0, when C is a polyhedral set. For both the Newton and quasi-Newton methods considered here, the subproblem to be solved is a linear system of equations per iteration. The other characteristics of the quasi-Newton method include: (i) a Q-superlinear convergence theorem is established without assuming the existence of H' at a solution x* of H(x)=0; (ii) only one approximate matrix is needed; (iii) the linear independence condition is not assumed; (iv) Q-superlinear convergence is established on the original variable x; and (v) from the QR-factorization of the kth iterative matrix, we need at most O((1+2|J k |+2|L k |)n 2 ) arithmetic operations to get the QR-factorization of the (k+1)th iterative matrix.
Original languageEnglish
Pages (from-to)659-676
Number of pages18
JournalJournal of Optimization Theory and Applications
Volume94
Issue number3
DOIs
Publication statusPublished - 1 Sep 1997
Externally publishedYes

Keywords

  • Newton methods
  • Normal maps
  • Q-superlinear convergence
  • quasi-Newton methods

ASJC Scopus subject areas

  • Control and Optimization
  • Management Science and Operations Research
  • Applied Mathematics

Cite this