Global Newton-type methods and semismooth reformulations for NCP (Q1861964)

A popular way to reformulate a nonlinear complementarity problem (NCP) \[ x_if_i(x_1,\ldots,x_n)=0,\quad x_i\geq 0,\qquad f_i(x_1,\ldots,x_n)\geq 0,\quad i=1\ldots,n \] as a nonlinear system consists in choosing an NCP-function, i. e., a function \(\varphi\) of two variables such that \(\varphi(a,b)=0\) iff \(a\geq 0, b\geq 0\) and \(ab=0\), and then obtaining the equivalent nonlinear system \[ \varphi(x_i,f_i(x_1,\ldots,x_n))=0,\quad i=1\ldots,n. \] A hybrid Newton-type method is presented which combines a finite-difference Newton-type method for solving the last system with a cheap direct search method for the minimization of a continuously differentiable merit function; the Newton-type method is enhanced by a line-search strategy based on a continuous merit function. Two different merit functions are used, one for the line search strategy in a primary Newton-type method and the other for the auxiliary direct search method: both of them have to be equivalent to the natural merit function. Under standard assumptions on the level sets of the merit functions, the method is proved to be globally convergent with fast local rate of convergence. The method is implemented with several choices for the reformulation and the merit function used in the line-search procedure. The numerical results show a good performance of the method with all the choices.