Polynomial interior-point algorithms for horizontal linear complementarity problem

In this paper a class of polynomial interior-point algorithms for P ∗ ( κ ) horizontal linear complementarity problem based on a new parametric kernel function, with parameters p ∈ [ 0 , 1 ] and σ ≥ 1 , are presented. The proposed parametric kernel function is not exponentially convex and also not strongly convex like the usual kernel functions, and has a finite value at the boundary of the feasible region. It is used both for determining the search directions and for measuring the distance between the given iterate and the μ -center for the algorithm. The currently best known iteration bounds for the algorithm with large- and small-update methods are derived, namely, O ( ( 1 + 2 κ ) n log n log n ε ) and O ( ( 1 + 2 κ ) n log n ε ) , respectively, which reduce the gap between the practical behavior of the algorithms and their theoretical performance results. Numerical tests demonstrate the behavior of the algorithms for different results of the parameters p , σ and θ .