Globally and superlinearly convergent algorithm for minimizing a normal merit function

In this paper we present two new concepts related to the solution of systems of nonsmooth equations (NE) and variational inequalities (VI). The first concept is that of a normal merit function, which summarizes the simple basic properties shared by various known merit functions. In general, normal merit functions are locally Lipschitz, but not differentiable. The second concept is that of a Newtonian operator, whose values generalize the concept of the Hessian for normal merit functions. These two concepts are then used to generalize the nonsmooth Newton method for solving the equation ▽f(x) = 0, where f is a normal merit function with f ∈ C1, to the case where f is only locally Lipschitz and the set-valued inclusion 0 ∈ ∂f(x) needs to be Solved. Combining the resulting generalized Newton method with certain first-order methods, we obtain a globally and superlinearly convergent algorithm for minimizing normal merit functions.