Interior point method for solving linear complementarity problems with P*-matrix

摘要

In this paper, we study the following Linear complementarity problem:M ∈ Rn×n, q ∈ Rn, find x ≥ 0, such that Mx + q ≥ 0 and xT (Mx + q) = 0. First of all, We study several properties of the P*-matrix,then we construct a combined homotopy equation, prove the existence and the convergence of the homotopy path, which is from any interior point to the solution of the problem. Numerical example shows that this method is feasible and effective.