View Related Documents

Abstract

Superlinear convergence of the Newton method for nonsmooth equations requires a “semismoothness” assumption. In this work we prove that locally Lipschitz functions definable in an o-minimal structure (in particular semialgebraic or globally subanalytic functions) are semismooth. Semialgebraic, or more generally, globally subanalytic mappings present the special interest of being γ-order semismooth, where γ is a positive parameter. As an application of this new estimate, we prove that the error at the kth step of the Newton method behaves like O(2-(1+g)k)O(2^{-{(1+\gamma)}^k}) .

Keywords  Semismoothness - Semi-algebraic function - o-minimal structure - Nonsmooth Newton method - Structured optimization problem - Superlinear convergence

Mathematics Subject Classification (2000)  Primary: 49J52 - 14P10 - Secondary: 90C31 - 65K10


Dedicated to Stephen Robinson, who has so many of the best ideas first.


A. Daniilidis was supported by the MEC Grant MTM2005-08572-C03-03 (Spain) and A. Lewis was supported by the National Science Foundation Grant DMS-0504032 (USA).


Adrian Lewis: Research supported in part by National Science Foundation Grant DMS-0504032.

Fulltext Preview

Image of the first page of the fulltext document