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.