Primal-Dual IPMs for a Class of Linear Complementarity Problems Based on Kernel Functions

Recently, Y.Q. Bai M. El Ghami and C.Roos (SIAM Journal of Optimization, 13(3):766--782, 2003) investigated a new class of kernel functions which differs from the class of self-regular kernel functions. The class is defined by some simple conditions on the growth and the barrier behavior of the kernel function. Based on these properties the authors simplified the analysis of IPMs based on these kernel functions for linear optimization. In this paper we generalize the analysis presented by Y.Q. Bai M. El Ghami and C.Roos for a class of linear complementarity problems. We will show that the iteration bound, for primal-dual methods is the same as that obtained for linear optimization. Keywords: Interior point method, kernel function, complexity, linear complementarity.