SOME NONINTERIOR CONTINUATION METHODS FOR LINEAR COMPLEMENTARITY-PROBLEMS

We introduce some new path-following methods for the solution of the l inear complementarity problem. We call these methods noninterior conti nuation methods since, in contrast to interior-point methods, not all iterates have to stay in the positive orthant. This is possible since we reformulate certain perturbed complementarity problems as a nonline ar system of equations. However, similar to interior-point methods, we also try to follow the central path. We present some conditions which guarantee the existence of this central path, prove a global converge nce result for some implementable noninterior continuation methods, an d report some numerical results obtained with these methods. We also p rove global error bound results for the perturbed linear complementari ty problems.