Polynomial interior-point algorithms for P∗(κ) 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κ)nlognlognε) and O((1+2κ)nlognε), 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 θ.