NE SQP - A ROBUST ALGORITHM FOR THE NONLINEAR COMPLEMENTARITY-PROBLEM

In this paper, we present a new iterative method for solving the nonli near complementarity problem. This method, which we call NE/SQP (for N onsmooth Equations/Successive Quadratic Programming), is a damped Gaus s-Newton algorithm applied to solve a certain nonsmooth-equation formu lation of the complementarity problem; it is intended to overcome a ma jor deficiency of several previous methods of this type. Unlike these earlier algorithms whose convergence critically depends on a solvabili ty assumption on the subproblems, the NE/SQP method involves solving a sequence of nonnegatively constrained convex quadratic programs of th e least-squares type; the latter programs are always solvable and thei r solution can be obtained by a host of efficient quadratic programmin g subroutines. Hence, the new method is a robust procedure which, not only is very easy to describe and simple to implement, but also has th e potential advantage of being capable of solving problems of very lar ge size. Besides the desirable feature of robustness and ease of imple mentation, the NE/SQP method retains two fundamental attractions of a typical member in the Gauss-Newton family of algorithms; namely, it is globally and locally quadratically convergent. Besides presenting the detailed description of the NE/SQP method and the associated converge nce theory, we also report the numerical results of an extensive compu tational study which is aimed at demonstrating the practical efficienc y of the method for solving a wide variety of realistic nonlinear comp lementarity problems.