## Self-regular proximities and new search directions for nonlinear
$P_*(\kappa)$ complementarity problems

###
J. Peng, C. Roos, T. Terlaky and A. Yoshise

We deal with interior point methods (IPMs) for solving a class of
so-called $\Pstar$ complementarity problems (CPs). First of all,
several elementary results about $\Pstar$ mappings and $\Pstar$ CPs
are presented. Then we extend some notions introduced recently by
Peng, Roos and Terlaky for linear optimization problems to the case of
CPs. New large-update IPMs for solving CPs are introduced based on
the so-called {\em self-regular} proximities.
To build up the complexity of these new algorithms, we impose
a new smoothness condition on the underlying mapping and this
condition can be viewed as a natural generalization of the {\em
relative Lipschitz} condition for convex programs introduced by
Jarre~\cite{int:JarreTh}. By utilizing various appealing properties of
{\em self-regular} proximities, we will show that if the undertaken
problem satisfies certain conditions, then these new large-update IPMs
for solving CPs have polynomial
$\O\br{n^{\frac{q+1}{2q}}\log\frac{n}{\epsilon}}$ iteration bounds
where $q$ is a constant, the so-called barrier degree of the
corresponding proximity.
Preprint, Faculty of Information Technology and Systems, Delft University of
Technology, Mekelweg 4, 2628 CD, Delft, The Netherlands.

Contact: pengj@mcmaster.ca