Solution of monotone complementarity problems with locally Lipschitzian functions

The paper deals with complementarity problems CP(F), where the underlying function F is assumed to be locally Lipschitzian. Based on a special equivalent reformulation of CP(F) as a system of equations Phi(x) = 0 or as the problem of minimizing the merit function Psi = 1/2\\Phi\\(2)(2), we extend results which hold for sufficiently smooth functions F to the nonsmooth case. In particular, if F is monotone in a neighbourhood of x, it is proved that 0 is an element of partial derivative Psi(x) is necessary and sufficient for x to be a solution of CP(F). Moreover, for monotone functions F, a simple derivative-free algorithm that reduces Psi is shown to possess global convergence properties. Finally, the local behaviour of a generalized Newton method is analyzed. To this end, the result by Mifflin that the composition of semismooth functions is again semismooth is extended to p-order semismooth functions. Under a suitable regularity condition and if F is p-order semismooth the generalized Newton method is shown to be locally well defined and superlinearly convergent with the order of 1 + p.