AN INTERIOR POINT POTENTIAL REDUCTION ALGORITHM FOR THE LINEAR COMPLEMENTARITY-PROBLEM

The linear complementarity problem (LCP) can be viewed as the problem of minimizing x(T)y subject to y = Mx + q and x,y greater-than-or-equal-to 0. We are interested in finding a point with x(T)y < epsilon for a given epsilon > 0. The algorithm proceeds by iteratively reducing the potential function f(x,y) = rho ln x(T)y - SIGMA ln x(j)y(j), where, for example, rho = 2n. The direction of movement in the original space can be viewed as follows. First, apply a linear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, here the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space. A bound on the worst-case performance of the algorithm depends on the parameter lambda* = lambda*(M, epsilon), which is defined as the minimum of the smallest eigenvalue of a matrix of the form (I + Y-1MX)(I + M(T)Y-2MX)-1(I + XM(T)Y-1) where X and Y vary over the nonnegative diagonal matrices such that e(T)XYe greater-than-or-equal-to epsilon and X(jj)Y(jj) less-than-or-equal-to n2. If M is a P-matrix, lambda* is positive and the algorithm solves the problem in polynomial time in terms of the input size, \log epsilon\, and 1/lambda*. It is also shown that when M is positive semi-definite, the choice of rho = 2n + square-root 2n yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.