A New Class of Polynomial Interior-Point Algorithms for P*(κ)-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+2 K ) q ( p +1) n ^{( p + q )/ q ( p +1)} log n/E ] for large-update methods and O [(1+2 K ) q ² √ 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.