Solving the Nonlinear Complementarity Problem

摘要

In order to solve the nonlinear complementarity problem, the authors 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 path either leading to an approximate solution or diverging towards infinity. They 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.