A Wide-Neighborhood Interior-Point Algorithm for the P_*(κ)-Matrix Linear Complementarity Problem

This paper describes a new wide-neighborhood potential reduction interior-point algorithm for P*(κ)-matrix linear complementarity problem, using the neighborhood N-∞(β) which is much wider. The algorithm is based on the idea of wide-neighborhood algorithm for linear programming. At each iteration, search direction can be computed as a solution of a linear system, and uses a potential function to choose a step size, so this algorithm decreases the potential function by a fixed amount, under the condition that the duality gap decreases at the same. Finally, we prove that its iteration complexity is O((κ+1)nt) under general conditions.