| We present a polynomial interior-point algorithm for P*(κ) Linear Complementarity Problems (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 self-regular function, and non-self-regular kernel functions as special cases. The iteration bounds obtained in this paper are $O [{(1+2κ), q(p +1)n(p+q)/q(p+1)log n/κ] for large-update methods and O[(1+2κ)q2 √n log n/κ] for small-update methods. These bounds match the best know existing iteration bounds. As far as we know this is the first result on interior-point methods for P*(κ)-LCPs based on this class of kernel functions. |
|
