Skip to main content
SpringerLink
Log in

On the solution of large, structured linear complementarity problems: The block partitioned case

  • Published:
Applied Mathematics and Optimization Submit manuscript

Abstract

This paper delineates the underlying theory of an efficient method for solving a class of specially-structured linear complementarity problems of potentially very large size. We propose a block-iterative method in which the subproblems are linear complementarity problems. Problems of the type considered here arise in the process of making discrete approximations to differential equations in the presence of special side conditions. This problem source is exemplified by the free boundary problem for finite-length journal bearings. Some of the authors' computational experience with the method is presented.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. R. J. Arms, L. D. Gates, and B. Zondek, A method of block iteration,J. SIAM, 4, 220–229 (1956).

    Google Scholar 

  2. J. C. Bierlein, The journal bearing,Scientific American, 233, 50–64 (1975).

    Google Scholar 

  3. J. Céa, Recherche numérique d'un optimum dans un espace produit, colloquium on methods of optimization,Lecture Notes in Mathematics, 112, Springer-Verlag, New York, 1970.

    Google Scholar 

  4. J. Céa and R. Glowinski, Sur des methodes d'optimisation par relaxation,RAIRO R-3, 5–32 (1973).

    Google Scholar 

  5. R. Chandrasekaran, A special case of the complementary pivot problem,Opsearch, 7, 263–268 (1970).

    Google Scholar 

  6. D. G. Christopherson, A new mathematical method for the solution of film lubrication problems,Inst. Mech. Engrs. J. Proc., 146, 126–135 (1941).

    Google Scholar 

  7. R. W. Cottle and G. B. Dantzig, Complementary pivot theory of mathematical programming,Linear Algebra and Appl., 1, 103–125 (1968).

    Google Scholar 

  8. R. W. Cottle and R. S. Sacher, On the solution of large, structured, linear complementarity problems: The tridiagonal case,J. Appl. Math. and Optimization, 3, 321–340 (1977).

    Google Scholar 

  9. R. W. Cottle, G. H. Golub, and R. S. Sacher,On the solution of large, structured linear complementarity problems: Technical Report 74-7, Department of Operations Research, Stanford University, Stanford, California, 1974.

    Google Scholar 

  10. C. W. Cryer, The solution of a quadratic programming problem using systematic overrelaxation,J. SIAM Control, 9, 385–392 (1971).

    Google Scholar 

  11. M. A. Diamond, The solution of a large quadratic programming problem using fast methods to solve systems of linear equations,Int. J. Systems Sci., 5, 131–136 (1974).

    Google Scholar 

  12. V. M. Fridman and V. S. Chernina, An iteration process for the solution of the finite-dimensional contact problem,U.S.S.R. Comp. Math. and Math. Phys., 8, 210–214 (1967).

    Google Scholar 

  13. C. L. Gerling,Die ausgleichs-rechnungen der practischen geometrie oder die methode der kleinsten quadrate mit ihren anwendungen für geodätiche aufgaben, Gothe, Hamburg, 1843.

    Google Scholar 

  14. C. Hildreth, A quadratic programming procedure,Nav. Res. Logist. Quart, 4, 79–85 (1957).

    Google Scholar 

  15. E. Isaacson and H. B. Keller,Analysis of Numerical Methods, J. Wiley and Sons, New York, 1966.

    Google Scholar 

  16. C. E. Lemke, On complementary pivot theory,Mathematics of the Decision Sciences, Part I (G. B. Dantzig and A. F. Veinott, Jr., eds.), American Mathematical Society, Providence, R.I., 1968.

    Google Scholar 

  17. O. Pinkus and B. Sternlicht,Theory of Hydrodynamic Lubrication, McGraw-Hill, New York, 1961.

    Google Scholar 

  18. H. L. Royden,Real Analysis, 2nd edition, Macmillan Co., London, 1968.

    Google Scholar 

  19. S. Schechter, “Relaxation methods for convex problems,”SIAM J. Numer. Anal., 5, 601–612 (1968).

    Google Scholar 

  20. S. Schechter, Iteration methods for nonlinear problems,Trans. Amer. Math. Soc., 104, 179–189 (1962).

    Google Scholar 

  21. R. S. Varga,Matrix Iterative Analysis, Prentice Hall, Englewood Cliffs, N. J., 1962.

    Google Scholar 

  22. D. M. Young,Iterative Solution of Large Linear Systems, Academic Press, New York, 1971.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Operations Research, Stanford University, 94305, Stanford, California, USA

    Richard W. Cottle, Gene H. Golub & Richard S. Sacher

  2. Department of Computer Science, Stanford University, 94305, Stanford, California, USA

    Richard W. Cottle, Gene H. Golub & Richard S. Sacher

  3. Department of Mathematical Sciences, Rensselaer Polytechnic Institute, 12181, Troy, New York, USA

    Richard W. Cottle, Gene H. Golub & Richard S. Sacher

Authors
  1. Richard W. Cottle
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Gene H. Golub
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Richard S. Sacher
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Research partially supported by the Office of Naval Research under contract N-00014-67-A-0112-0011; U.S. Atomic Energy Commission Contract AT (04-3)-326 PA No. 18.

Research partially supported by U.S. Atomic Energy Commission Contract AT(04-3)-326 PA No. 30; and National Science Foundation Grant GJ 35135X.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Cottle, R.W., Golub, G.H. & Sacher, R.S. On the solution of large, structured linear complementarity problems: The block partitioned case. Appl Math Optim 4, 347–363 (1977). https://doi.org/10.1007/BF01442149

Download citation

  • Received:

  • Issue Date:

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

Keywords

Search

Navigation