An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version

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^*$.

Citation

Optimization Technical Report 06-02, University of Wisconsin-Madison, April 2006. Revised January 2007.

Article

Download

View An Accelerated Newton Method for Equations with Semismooth Jacobians and Nonlinear Complementarity Problems: Extended Version