Solving the nonlinear complementarity problem

In order to solve the nonlinear complementarity problem we propose a simplicial restart algorithm that subdivides the set on which the problem is defined into simplices and generates from an arbitrarily chosen starting point a piecewise linear either leading to an approximate solution or diverging towards infinity. We will give a convergence condition under which the algorithm will find an approximate solution. If the accuracy of the approximate solution is not sufficient the algorithm can be restarted at the approximate solution with a finer simplicial subdivision. The piecewise linear path generated by the algorithm is followed by a sequence of adjacent simplices of varying dimension.

Kremers, Johannes and Dolf Talman (1990), Solving the nonlinear complementarity problem, Methods of Operations Research 62 , 91--103