COMPUTATIONAL COMPLEXITY OF LCPS ASSOCIATED WITH POSITIVE DEFINITE SYMMETRIC MATRICES

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs-one of order n for n ≥ 2-he has shown that to solve the problem of order n, either of the two methods goes through 2n pivot steps before termination. However that paper leaves it as an open question to show whether or not the same property holds if the matrix, M, in the LCP is positive definite and symmetric. The class of LCPs in which M is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications. In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), when M is positive definite and symmetric and obtain similar results. © 1979 North-Holland Publishing Company.