AN O(SQUARE-ROOT-N L) 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 (x,y) is-an-element-of-R2n such that y = Mx + q, (x,y) greater-than-or-equal-to 0 and x(T)y = 0. The algorithm reduces the potential function [GRAPHICS] by at least 0.2 in each iteration requiring O(n3) arithmetic operations. If it starts from an interior feasible solution with the potential function bounded by O(square-root n L), it generates, in at most O(square-root n L) iterations, an approximate solution with the potential function value -O(square-root n L), from which we can compute an exact solution in O(n3) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.