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

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.