×
Gowda, M. Seetharama; Pang, Jong-Shi

The basic theorem of complementarity revisited. (English) Zbl 0778.90074

Math. Program., Ser. A 58, No. 2, 161-177 (1993).
Summary: The basic theorem of (linear) complementarity was first stated by B. C. Eaves [Math. Program. 1, No. 1, 68-75 (1971; Zbl 0227.90044)]who credited C. E. Lembke for giving a constructive proof based on his almost complementary pivot algorithm. This theorem asserts that associated with an arbitrary linear complementarity problem, a certain augmented problem always possesses a solution. Many well-known existence results pertaining to the linear complementarity problem are consequences of this fundamental theorem.
We explore some further implications of the basic theorem of complementarity and derive new existence results for the linear complementarity problem. Based on these results, conditions for the existence of a solution to a linear complementarity problem with a fully- semimonotone matrix are examined. The class of the linear complementarity problems with a \(G\)-matrix is also investigated.

Cited in 8 Documents

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
49J40 Variational inequalities

Keywords:

variational inequality; almost complementary pivot algorithm; linear complementarity; fully-semimonotone matrix

Citations:

Zbl 0227.90044
Cite Review PDF
Full Text: DOI

References:

[1] M. Aganagić and R.W. Cottle, ”A constructive characterization ofQ o-matrices with nonnegative principal minors,”Mathematical Programming 37 (1987) 223–231. · Zbl 0618.90091 · doi:10.1007/BF02591696
[2] R.W. Cottle, ”Solution rays for a class of parametric linear complementarity problems,”Mathematical Programming Study 1 (1974) 59–70. · Zbl 0361.90040
[3] R.W. Cottle and R.E. Stone, ”On the uniqueness of solutions to linear complementarity problems,”Mathematical Programming 27 (1983) 191–213. · Zbl 0516.90071 · doi:10.1007/BF02591945
[4] B.C. Eaves, ”The linear complementarity problem,”Management Science 17 (1971) 612–634. · Zbl 0228.15004 · doi:10.1287/mnsc.17.9.612
[5] B.C. Eaves, ”On quadratic programming,”Management Science 17 (1971) 698–711. · Zbl 0242.90040 · doi:10.1287/mnsc.17.11.698
[6] B.C. Eaves, ”On the basic theorem of complementarity,”Mathematical Programming 1 (1971) 68–75. · Zbl 0227.90044 · doi:10.1007/BF01584073
[7] C.B. Garcia, ”Some classes of matrices in linear complementarity theory,”Mathematical Programming 5 (1973) 299–310. · Zbl 0284.90048 · doi:10.1007/BF01580135
[8] M.S. Gowda, ”On copositive linear complementarity problems,” Research Report, Department of Mathematics and Statistics, University of Maryland Baltimore County (Baltimore, MD, 1987).
[9] M.S. Gowda, ”Pseudomonotone and copositive star matrices,”Linear Algebra and its Applications 113 (1989) 107–118. · Zbl 0661.15018 · doi:10.1016/0024-3795(89)90289-9
[10] P.T. Harker and J.S. Pang, ”Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications,”Mathematical Programming (Series B) 48 (1990) 161–220. · Zbl 0734.90098 · doi:10.1007/BF01582255
[11] S. Karamardian, ”Generalized complementarity problem,”Journal of Optimization Theory and Applications 8 (1971) 161–168. · doi:10.1007/BF00932464
[12] S. Karamardian, ”The complementarity problem,”Mathematical Programming 2 (1972) 107–129. · Zbl 0247.90058 · doi:10.1007/BF01584538
[13] S. Karamardian, ”Complementarity problems over cones with monotone and pseudomonotone maps,”Journal of Optimization Theory and Applications 18 (1976) 445–454. · Zbl 0304.49026 · doi:10.1007/BF00932654
[14] S. Karamardian, ”An existence theorem for the complementarity problem,”Journal of Optimization Theory and Applications 19 (1976) 227–232. · Zbl 0307.49010 · doi:10.1007/BF00934094
[15] M. Kojima, ”A unification of the existence theorems of the nonlinear complementarity problem,”Mathematical Programming 9 (1975) 257–277. · Zbl 0347.90039 · doi:10.1007/BF01681350
[16] C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681
[17] C.E. Lemke, ”On complementary pivot theory,” in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of Decision Sciences, Part I (American Mathematical Society, Providence, RI 1968) pp. 95–14. · Zbl 0208.45502
[18] J.S. Pang, ”OnQ-matrices,”Mathematical Programming 17 (1979) 243–247. · Zbl 0416.90073 · doi:10.1007/BF01588247
[19] J.S. Pang, ”Iterative descent methods for a row sufficient linear complementarity problem,”SIAM Journal on Matrix Analysis and Applications 12 (1991) 611–624. · Zbl 0742.65048 · doi:10.1137/0612047
[20] J. Parida and K.L. Roy, ”A note on the linear complementarity problem,”Opsearch 18 (1981) 229–234. · Zbl 0482.90083
[21] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[22] R.E. Stone, ”Geometric aspects of the linear complementarity problem,” Ph.D. thesis, Department of Operations Research, Stanford University (Stanford, CA, 1981).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.