TAME MAPPINGS ARE SEMISMOOTH

Dedicated to Stephen Robinson, who has so many of the best ideas first. 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+γ)k). Key words Semismoothness, semi-algebraic function, o-minimal structure, nonsmooth Newton method, structured optimization problem, superlinear convergence