Abstract
The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B.C. Eaves, “On the basic theorem of complementarity,”Mathematical Programming 1 (1971) 68–75.
B.C. Eaves, “Computing stationary points,”Mathematical Programming Study 7 (1978) 1–14.
B.C. Eaves, “Computing stationary points, again,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 3 (Academic Press, New York, 1978) pp. 391–405.
M.S. Gowda and J.S. Pang, “The basic theorem of complementarity revisited,”Mathematical Programming 58 (1993) 149–160.
C.E. Lemke, “Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1964) 681–689.
L. Mathiesen, “Computation of economic equilibria by a sequence of linear complementarity problems,”Mathematical Programming 23 (1985) 144–162.
K.G. Murty, “Computational complexity of complementary pivot methods,”Mathematical Programming Study 7 (1978) 61–73.
A.J.J. Talman and L. Van der Heyden, “Algorithms for the linear complementarity problem which allow an arbitrary starting point,” in: B.C. Eaves et al., eds.,Homotopy Methods and Global Convergence (Plenum Press, New York, 1983) pp. 267–285.
Author information
Authors and Affiliations
Additional information
This research is part of the VF-program “Competition and Cooperation”.
Rights and permissions
About this article
Cite this article
Kremers, H., Talman, D. A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point. Mathematical Programming 63, 235–252 (1994). https://doi.org/10.1007/BF01582068
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01582068