A constructive characterization of \(Q_ 0\)-matrices with nonnegative principal minors.(English)Zbl 0618.90091
In a previous paper [ibid. 16, 374-377 (1979;Zbl 0416.90074)] we characterized the class of matrices with nonnegative principal minors for which the linear complementarity problem always has a solution. That class is contained in the one we study here. Our main result gives a finitely testable set of necessary and sufficient conditions under which a matrix with nonnegative principal minors has the property that if a corresponding linear complementarity problem is feasible then it is solvable. In short, we constructively characterize the matrix class known as \(Q_ 0\cap P_ 0\).
MSC:
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
classes of matrices;existence of solutions;nonnegative principal minors;necessary and sufficient conditions;linear complementarityCitations:
Zbl 0416.90074Cite
Full Text:DOI
References:
| [1] | M. Aganagić and R.W. Cottle, ”OnQ-matrices”, Technical Report SOL 78-9, Systems Optimization Laboratory, Department of Operations Research, Stanford University (Stanford, CA, 1978). |
| [2] | M. Aganagić and R.W. Cottle, ”A note onQ-matrices”,Mathematical Programming 16 (1979) 374–377. ·Zbl 0416.90074 ·doi:10.1007/BF01582122 |
| [3] | F.A. Al-Khayyal, ”Necessary and sufficient conditions for the existence of complementary solutions and characterizations of the matrix classesQ andQ o ”, Technical Report PDRC 85-05, Production and Distribution Center, Georgia Institute of Technology (Atlanta, November 1985). |
| [4] | R.W. Cottle, ”The principal pivoting method of quadratic programming”, in: G.B. Dantzig and A.F. Veinott, Jr., eds.,Mathematics of the Decision Sciences, Part I, (American Mathematical Society, Providence, RI, 1968) pp. 144–168. ·Zbl 0196.22902 |
| [5] | R.W. Cottle, ”Some recent developments in linear complementarity theory”, in: R.W. Cottle, F. Giannessi, and J.L. Lions, eds.,Variational Inequalities and Complementarity Problems (John Wiley & Sons, Chichester, 1980) pp. 97–104. ·Zbl 0484.90088 |
| [6] | R.D. Doverspike and C.E. Lemke, ”A partial characterization of a class of matrices defined by solutions to the linear complementarity problem”,Mathematics of Operations Research 7 (1982) 272–294. ·Zbl 0498.90077 ·doi:10.1287/moor.7.2.272 |
| [7] | B.C. Eaves, ”The linear complementarity problem”,Management Science 17 (1971) 612–634. ·Zbl 0228.15004 ·doi:10.1287/mnsc.17.9.612 |
| [8] | M. Fiedler and V. Pták, ”Some generalizations of positive definiteness and monotonicity”,Numerische Mathematik 9 (1966) 163–172. ·Zbl 0148.25801 ·doi:10.1007/BF02166034 |
| [9] | J.T. Fredericksen, L.T. Watson, and K.G. Murty, ”A finite characterization ofK-matrices in dimensions less than four”,Mathematical Programming 35 (1986) 17–31. ·Zbl 0641.90082 ·doi:10.1007/BF01589438 |
| [10] | C.B. Garcia, ”Some classes of matrices in linear complementarity theory”,Mathematical Programming 5 (1973), 299–310. ·Zbl 0284.90048 ·doi:10.1007/BF01580135 |
| [11] | A.W. Ingelton, ”A problem in linear inequalities”,Proceedings of the London Mathematical Society 16 (1966) 519–536. ·Zbl 0166.03005 ·doi:10.1112/plms/s3-16.1.519 |
| [12] | S. Karamardian, ”The complementarity problem”,Mathematical Programming 2 (1972) 107–129. ·Zbl 0247.90058 ·doi:10.1007/BF01584538 |
| [13] | C.E. Lemke, ”Some pivot schemes for the linear complementarity problem”,Mathematical Programming Study 7 (1978) 15–35. ·Zbl 0381.90073 |
| [14] | J.S. Pang, ”A note on an open problem in linear complementarity”,Mathematical Programming 13 (1977) 360–363. ·Zbl 0367.90080 ·doi:10.1007/BF01584349 |
| [15] | F.J. Pereira R., ”On characterizations of copositive matrices”, Ph.D. Thesis and Technical Report No. 72-8, Department of Operations Research, Stanford University (Stanford, CA, May 1972). |
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.
