Feasibility problems with complementarity constraints

R. Andreani, J. J. Júdice, J. M. Martínez, T. Martini

Abstract

In this paper, a Projected-Gradient Underdetermined Newton type (PGUN) algorithm is introduced for finding a solution of a Horizontal Nonlinear Complementarity Problem (HNCP) corresponding to a feasible solution of a Mathematical Programming Problem with Linear and Nonlinear Complementarity Constraints (MPCC). The algorithm employs a combination of Interior-Point Newton type and Projected-Gradient directions and a line-search procedure that guarantees global convergence to a solution of HNCP or at least a stationary point of the natural merit function associated to this problem. Fast local convergence is established under reasonable hypotheses. PGUN can also be applied to the computation of a feasible solution of MPCC with a target objective function value. Computational experience on the solution of a number of test problems from well-known sources is reported illustrating the eciency of the algorithm to find feasible solutions of MPCC in practice.