AN EXTENSION OF THE POTENTIAL REDUCTION ALGORITHM FOR LINEAR COMPLEMENTARITY-PROBLEMS WITH SOME PRIORITY GOALS

We extend the potential reduction algorithm to solve the restricted convex linear complementarity problem (LCP) x(T)s = 0, x(I) = 0, s(J) = 0, s = Mx + q, and 0 less-than-or-equal-to x, s is-an-element-of R(n) for some index sets I and J. In polynomial time, the algorithm will either discover that no solution exists or generate a sequence of pairs (x(k), s(k)) which simultaneously drives (x(k))(T)S(k), x(I)k, and s(J)k to zero. In particular, we discuss how to apply the algorithm to solving the combined Phase I-Phase II convex LCP and to identifying a vertex linear programming solution.