Polynomiality of Primal-Dual Affine Scaling Algorithms for NonlinearComplementarity Problems

摘要

This paper provides an analysis of the polynomiality of primal-dual interiorpoint algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu's scaled Lipschitz condition, but is also applicable to mappings that are not monotone. The authors show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision epsilon) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial of n, ln(1/epsilon) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in (13). (Copyright (c) 1995 by Faculty of Technical Mathematics and Informatics, Delft.)