Abstract
Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x ≥ 0,y ≥ 0,x i y i = 0 (i = 1, 2,⋯,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n 3 L) arithmetic operations by tracing the path of centers,{(x, y) ∈ S: x i y i =μ (i = 1, 2,⋯,n) for some μ > 0} of the feasible regionS = {(x, y) ≥ 0:y = Mx + q}, whereL denotes the size of the input data of the problem.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J.R. Birge and A. Gana, “Computational complexity of van der Heyden's variable dimensional algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's,”Mathematical Programming 26 (1983) 316–325.
S.J. Chung, “A note on the complexity of LCP: the LCP is strongly NP-complete,” Technical Report 792, Dept. of Industrial Engineering and Operations Engineering, The University of Michigan (Ann Arbor, Michigan, 1979).
G.B. Dantzig and R.W. Cottle, “Positive (semi-definite) matrices and mathematical programming,” Report ORC 63-18, (RR) 13, University of Berkeley (California, 1963).
Y. Fathi, “Computational complexity of LCPs associated with positive definite symmetric matrices,”Mathematical Programming 17 (1979) 335–344.
D.M. Gay, “A variant of Karmarkar's linear programming algorithm for problems in standard form,”Mathematical Programming 37 (1987) 81–90.
P.E. Gill, W. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method,”Mathematical Programming 36 (1986) 183–209.
C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer-Verlag, New York, 1988), to appear.
S. Kapoor and P.M. Vaidya, “Fast algorithms for convex quadratic programming and multicommodity flows,”Proceedings of the 18th Annual ACM Symposium on Theory of Computing (Berkeley, California, 1986) 147–159.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
L.G. Khachiyan, “A polynomial algorithm in linear programming,”Soviet Mathematics Doklady 20 (1979) 191–194.
M. Kojima, S. Mizuno and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer-Verlag, New York, 1988), to appear.
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689.
O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
O.L. Mangasarian, “Simple computable bounds for solutions of linear complementarity problems and linear programs,”Mathematical Programming Study 25 (1985) 1–12.
N. Megiddo, “Pathways to the optimal set in linear programming,”Proceedings of the 6th Mathematical Programming symposium of Japan (Nagoya, Japan, 1986) 1–35.
K.G. Murty, “Computational complexity of complementary pivot methods,”Mathematical Programming Study 7 (1978) 61–73.
J.M. Ortega and W.C. Rheinboldt,Iterative Solutions of Nonlinear Equations of Several Variables (Academic Press, New York, 1970).
J.S. Pang, I. Kaneko and W.P. Hallman, “On the solution of some (parametric) linear complementarity problems with application to portfolio selection, structural engineering and actuarial graduation,”Mathematical Programming 16 (1979) 325–347.
J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–94.
G. Sonnevend, “An ‘analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,”Proceedings of the 12th IFIP Conference on System Modeling and Optimization (Budapest, 1985), to appear inLecture Notes in Control and Information Sciences (Springer-Verlag).
A. Schrijver,Theory of Linear and Integer Programming (John Wiley & Sons, 1986).
J. Stoer and C. Witzgall,Convexity and Optimization in Finite Dimensions (Springer, New York, 1970).
K. Tanabe, “Complementarity-enforcing centered Newton method for linear programming: Global method,” Symposium, “New Method for Linear Programming” at The Institute of Statistical Mathematics (Tokyo, 1987).
L. Van der Heyden, “A variable dimension algorithm for the linear complementarity problem,”Mathematical Programming 19 (1980) 328–346.
P.M. Vaidya, “An algorithm for linear programming which requires O(((m + n)n 2 +(m + n) 1.5 n)L) arithmetic operations,” AT&T Bell Laboratories, Murray Hill (New Jersey, 1987).
Y. Ye and M. Kojima, “Recovering optimal dual solutions in Karmarkar's polynomial time algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317.
Y. Ye and E. Tse, “A polynomial-time algorithm for convex quadratic programming,” Working Paper, Dept. of Engineering-Economic Systems, Stanford University (California, 1986).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kojima, M., Mizuno, S. & Yoshise, A. A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming 44, 1–26 (1989). https://doi.org/10.1007/BF01587074
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01587074