An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version
Christina Oberlin (coberlincs.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.
Entry Submitted: 06/09/2006
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|