Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

Benjamin Jansen, Kees Roos, Tam\'{a}s Terlaky and Akiko Yoshise

This paper provides an analysis of the polynomiality of primal-dual interior point 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. We 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 \cite{int:Jansen10}.

Technical Report 95-83, Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands, September, 1995.

This paper can be also referenced as: No. 648, Discussion Paper Series, Institute of Socio-Economic Planning, University of Tsukuba, Tsukuba, Ibaraki 305, Japan.

If you would have a hard copy, please send me your address by e-mail at yoshise@shako.sk.tsukuba.ac.jp