An iteration potential reduction algorithm for linear complementarity problems

This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an such that y =Mx+q, x, y 0 and x ^Ty=0. The algorithm reduces the potential function by at least 0.2 in each iteration requiring O(n³) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by , it generates, in at most iterations, an approximate solution with the potential function value -, from which an exact solution in O(n³) arithmetic operations can be computed. The algorithm is closely related with the central path following algorithm recently given by the authors. The authors also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.