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

###
B. Jansen, C. Roos, T. Terlaky, A. 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 Jansen, Roos and Terlaky for LCP.

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

Contact: t.terlaky@twi.tudelft.nl