Polynomial interior-point algorithms for P*(κ) horizontal linear complementarity problem

In this paper a class of polynomial interior-point algorithms for P-*(kappa) horizontal linear complementarity problem based on a new parametric kernel function, with parameters p epsilon vertical bar 0, 1 vertical bar and alpha >= 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 mu-center for the algorithm. The currently best known iteration bounds for the algorithm with large-and small-update methods are derived, namely, 0((1 +2 kappa) root n log n log n/epsilon) and 0((1 + 2 kappa) root n log n/epsilon), 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.sigma and theta. (C) 2009 Elsevier B.V. All rights reserved.