Solving the Nonlinear Complementarity Problem by a Homotopy Method

Let F be a C² map from n-dimensional Euclidean space into itself. It is proved that, under some mild conditions on F, the complementarily problem z 0, F(z) 0, $zF(z) = 0$ can be solved by a homotopy algorithm developed by Chow, Mallet-Paret, Yorke, and Watson. The algorithm is globally convergent with probability one, and uses Mangasarian’s nonlinear system equivalent to the complementarity problem. Convergence theorems for the algorithm simultaneously prove existence of a solution, although existence is already well known. Some computational results are included.