A new polynomial time method for a linear complementarity problem (Q1207309)

A polynomial time method is developed for solving a linear complementarity problem with a positive semidefinite matrix. The method follows a sequence of points and requires at most \(O(\sqrt n L)\) iterations for any initial feasible point whose components lie between \(2^{-O(L)}\) and \(2^{O(L)})\). A feature of this method is that if the sequence is generated on a path then a path following procedure can be constructed; if the sequence is generated based on a potential function then a potential reduction method is obtained.