Existence and limiting behavior of a non-interior-point trajectory for nonlinear complementarity problems without strict feasibility condition

For P₀-complementarity problems, most existing non-interior-point path-following methods require the existence of a strictly feasible point. (For a P_*-complementarity problem, the existence of a strictly feasible point is equivalent to the nonemptyness and the boundedness of the solution set.) In this paper, we propose a new homotopy formulation for complementarity problems by which a new non-interior-point continuation trajectory is generated. The existence and the boundedness of this non interior-point trajectory for P₀-complementarity problems are proved under a very mild condition that is weaker than most conditions used in the literature. One prominent feature of this condition is that it may hold even when the often-assumed strict feasibility condition fails to hold. In particular, for a P_*-problem it turns out that the new non-interior-point trajectory exists and is bounded if and only if the problem has a solution. We also study the convergence of this trajectory and characterize its limiting point as the parameter approaches zero.