Optimization Online


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

Christina Oberlin (coberlin***at***cs.wisc.edu)
Stephen J. Wright (swright***at***cs.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/2006
Entry Accepted: 06/09/2006
Entry Last Modified: 01/30/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society