Existence of Interior Points and Interior Paths in Nonlinear Monotone Complementarity Problems

This paper establishes basic results on the existence of interior points and interior paths in a nonlinear monotone complementarity problem in ℝn under very weak interior conditions. We show that the interior paths are bounded, continuous, and all the limit points of the paths are solutions to the complementarity problem. We prove that certain sets, including the solution set to the complementary problem, form a compact convex set. We also prove the existence of generalized interior points and interior paths. These generalized paths are also continuous and contain readily available starting points from which we can follow the paths to locate the solutions to the complementarity problem. We prove our results in the context of maximal monotone operators. The result presented here can be used to develop polynomial time interior point algorithms for general monotone complementarity problems.