A constructive characterization ofQ o-matrices with nonnegative principal minors | Mathematical Programming Skip to main content
Springer Nature Link
Log in

A constructive characterization ofQ o-matrices with nonnegative principal minors

  • Published:
Mathematical Programming Submit manuscript

Abstract

In [2] we characterized the class of matrices with nonnegative principla 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 asQ o ∩P o .

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

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).

    Google Scholar 

  2. M. Aganagić and R.W. Cottle, “A note onQ-matrices”,Mathematical Programming 16 (1979) 374–377.

    Article  MathSciNet  MATH  Google Scholar 

  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).

    Google Scholar 

  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.

    Google Scholar 

  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.

    Google Scholar 

  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.

    MATH  MathSciNet  Google Scholar 

  7. B.C. Eaves, “The linear complementarity problem”,Management Science 17 (1971) 612–634.

    Article  MathSciNet  MATH  Google Scholar 

  8. M. Fiedler and V. Pták, “Some generalizations of positive definiteness and monotonicity”,Numerische Mathematik 9 (1966) 163–172.

    Article  MATH  MathSciNet  Google Scholar 

  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.

    Article  MathSciNet  Google Scholar 

  10. C.B. Garcia, “Some classes of matrices in linear complementarity theory”,Mathematical Programming 5 (1973), 299–310.

    Article  MATH  MathSciNet  Google Scholar 

  11. A.W. Ingelton, “A problem in linear inequalities”,Proceedings of the London Mathematical Society 16 (1966) 519–536.

    Article  MathSciNet  Google Scholar 

  12. S. Karamardian, “The complementarity problem”,Mathematical Programming 2 (1972) 107–129.

    Article  MATH  MathSciNet  Google Scholar 

  13. C.E. Lemke, “Some pivot schemes for the linear complementarity problem”,Mathematical Programming Study 7 (1978) 15–35.

    MATH  MathSciNet  Google Scholar 

  14. J.S. Pang, “A note on an open problem in linear complementarity”,Mathematical Programming 13 (1977) 360–363.

    Article  MATH  MathSciNet  Google Scholar 

  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).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Energoinvest-IRCA, Sarajevo, Yugoslavia

    Muhamed Aganagić

  2. Department of Operations Research, Stanford University, 94305, Stanford, CA, USA

    Richard W. Cottle

Authors
  1. Muhamed Aganagić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Richard W. Cottle
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research partially supported by the National Science Foundation Grant DMS-8420623 and U.S. Department of Energy Contract DE-AA03-76SF00326, PA # DE-AS03-76ER72018.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Aganagić, M., Cottle, R.W. A constructive characterization ofQ o-matrices with nonnegative principal minors. Mathematical Programming 37, 223–231 (1987). https://doi.org/10.1007/BF02591696

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02591696

Key words

Search

Navigation