A New Class of Polynomial Interior-Point Algorithms for \u3cem\u3eP\u3c/em\u3e*(κ)-Linear Complementarity Problems

We present a polynomial interior-point algorithm for P*(K) Linear Complementarity Problem (LCP) based on a class of parametric kernel functions, with parameters p ∈ [0, 1] and q ≥ 1. The same class of kernel function was considered earlier for Linear Optimization (LO) by Bai et al. in [7]. This class is fairly general and includes the classical logarithmic function, the prototype sellf-regular function, and non-self-regular kernel functions as special cases. The iteration bounds obtained in this paper are O [(1+2K) q(p+1)n(p+q)/q(p+1) log n/E] for large-update methods and O [(1+2K) q2√n log n/E] for small-update methods. These bounds match the best known existing iteration bounds. As far as we know this is the first result on interior-point methods for P*(K)-LCPs based on this class of kernel functions