Abstract
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 ordern forn ≥ 2—he has shown that to solve the problem of ordern, 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 whichM 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), whenM is positive definite and symmetric and obtain similar results.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
R.W. Cottle and G.B. Dantzig, “Complementary pivot theory of mathematical programming”,Linear Algebra and Its Applications 1 (1968) 103–125.
R.W. Cottle, “Monotone solutions of the parametric linear complementarity problem”,Mathematical Programming 3 (1972) 210–224.
V. Klee and G.L. Minty, “How good is the simplex algorithm”, in: O. Shisha, ed.,Inequalities III (Academic Press, New York, 1976).
M.M. Kostreva, “Direct algorithms for complementarity problems”, Dissertation, Rennselaer Polytechnic Institute (Troy, New York, 1976).
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming”,Management Science 4 (1965) 681–689.
K.G. Murty,Linear and combinatorial programming (Wiley, New York, 1976).
K.G. Murty, “Computational complexity of complementary pivot methods”,Mathematical Programming Study 7 (1978) 61–73.
K.G. Murty, “On the number of solutions of the complementarity problems and spanning properties of complementary cones”,Linear Algebra and Its Applications 5 (1972) 65–108.
K.G. Murty, “On the parametric complementarity problem”,Summer conference notes (The University of Michigan, 1971).
K.G. Murty, “Note on a Bard-type scheme for solving the complementarity problem”,Opsearch 7 (1970) 263–268.
K.G. Murty, “On a characterization ofP-matrices”,SIAM Journal on Applied Mathematics 20 (3) (1971) 378–384.
R. Saigal, “On the class of complementary cones and Lemke's algorithm”,SIAM Journal on Applied Mathematics 23 (1972) 47–60.
A.C. Stickney and L.T. Watson, “Digraph models of Bard-type algorithms for the linear complementarity problem”,Mathematics of Operations Research 3 (1978) 322–333.
Author information
Authors and Affiliations
Additional information
This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.
Rights and permissions
About this article
Cite this article
Fathi, Y. Computational complexity of LCPs associated with positive definite symmetric matrices. Mathematical Programming 17, 335–344 (1979). https://doi.org/10.1007/BF01588254
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588254