- An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version Christina Oberlin (coberlincs.wisc.edu) Stephen J. Wright (swrightcs.wisc.edu) Abstract: We discuss local convergence of Newton's method to a singular solution $x^*$ of the nonlinear equations $F(x) = 0$, for $F:\R^n \rightarrow \R^n$. It is shown that an existing proof of Griewank, concerning linear convergence to a singular solution $x^*$ from a starlike domain around $x^*$ for $F$ twice Lipschitz continuously differentiable and $x^*$ satisfying a particular regularity condition, can be adapted to the case in which $F'$ is only strongly semismooth at the solution. Further, under this regularity assumption, Newton's method can be accelerated to produce fast linear convergence to a singular solution by overrelaxing every second Newton step. These results are applied to a nonlinear-equations formulation of the nonlinear complementarity problem (NCP) whose derivative is strongly semismooth when the function $f$ arising in the NCP is sufficiently smooth. Conditions on $f$ are derived that ensure that the appropriate regularity conditions are satisfied for the nonlinear-equations formulation of the NCP at $x^*$. Keywords: Nonlinear Equations, Semismooth Functions, Newton's Method, Nonlinear Complementarity Problems Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares ) Category 2: Complementarity and Variational Inequalities Citation: Optimization Technical Report 06-02, University of Wisconsin-Madison, April 2006. Revised January 2007. Download: [PDF]Entry Submitted: 06/09/2006Entry Accepted: 06/09/2006Entry Last Modified: 01/30/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.