Skip to main content
SpringerLink
Log in

Iterative methods for linear complementarity problems with upperbounds on primary variables

  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper is concerned with iterative methods for the linear complementarity problem (LCP) of findingx and y in Rn such thatc+Dx+y≥0, b-x≥0, andx T (c+Dx+y)=y T (b-x)=0 whenb>0. This is the LCP (M, q) withM=( D tl 0 ), which is in turn equivalent to a linear variational inequality over a rectangle. This type of problem arises, for example, from quadratic programming (QP) problems with upper and lower bounds ifD is symmetric, and from multicommodity market equilibrium problems with institutional price controls imposed ifD is not necessarily symmetric.

Iterative methods for the LCP (M, q) with symmetricM are well developed and studied using QP applications. For nonsymmetric cases withM being either an H-matrix with positive diagonals, or a Z-matrix, there exists a robust iterative method with guaranteed convergence.

This paper extends this algorithm so that the LCP (M, q) withM=( D tl 0 ) which is neither symmetric, nor an H-matrix with positive diagonals, nor a Z-matrix, can be processed when onlyD notM satisfies such properties. The case whereD is nonsymmetric is explicitly discussed.

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. M. Aganagic, “Variational inequalities and generalized complementaritys problems”, Technical Report 78-11, Department of Operations Research, Stanford University (Stanford, CA, September 1978).

    Google Scholar 

  2. Byong-hun Ahn and W. W. Hogan, “On convergence of the PIES algorithm for computing equilibria”,Operations Research 30 (1982) 281–300

    MATH  MathSciNet  Google Scholar 

  3. Byong-hun Ahn, “Solution of nonsymmetric linear complementarity problems by iterative methods”,Journal of Optimization Theory and Applications 33 (1981) 175–185

    Article  MathSciNet  Google Scholar 

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

    MathSciNet  Google Scholar 

  5. J.C. Cheng, “Analysis of a quantum price model in commodity future markets and a fair salary administration system,” Ph.D. Thesis, Department of Mathematics, MIT, (Cambridge, MA, 1975).

    Google Scholar 

  6. D.G. Christopherson, “A new mathematical method for the solution of film lubrication problems,”Institute of Mechanical Engineers, Proceedings 146 (1941), 126–135.

    MathSciNet  Google Scholar 

  7. R.W. Cottle and M. Goheen, “A special class of large quadratic programs”, in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds,Nonlinear programming 3 (Academic Press, New York, 1978) pp. 361–390.

    Google Scholar 

  8. R.W. Cottle, G. Golub, and R.S. Sacher, “On the solution of large structured linear complementarity problems”,Applied Mathematics and Optimization 4 (1978) 347–363

    MATH  MathSciNet  Google Scholar 

  9. C.W. Cryer, “The solution of quadratic programming problems using systematic overrelaxation”,SIAM Journal on Control 9 (1971) 385–392.

    Article  MATH  MathSciNet  Google Scholar 

  10. S. Dafermos, “Traffic equilibrium and variational inequalities”,Transportation Science 14 (1980) 52–54.

    Article  MathSciNet  Google Scholar 

  11. M.A. Diamond, “The solution of a quadratic programming problem using fast methods to solve systems of linear equations”,International Journal of Systems Science 5 (1974) 131–136.

    MathSciNet  MATH  Google Scholar 

  12. M. Fiedler and V. Pták, “On matrices with nonpositive off-diagonal elements and positive principal minors”,Czechoslovak Mathematical Journal 12 (1962) 382–400.

    MathSciNet  Google Scholar 

  13. R. Fletcher and M.P. Jackson, “Minimization of a quadratic function of many variables subject only to lower and upper bounds”,Journal of Institute for Mathematics and Its Applications 14 (1974) 159–174.

    MATH  MathSciNet  Google Scholar 

  14. T. Hansen and A.S. Manne, “Equilibrium and linear complementarity—an economy with institutional constraints on prices”, in: G. Schwödiauer, ed.,Equilibrium and disequilibrium in economic theory (D. Reidel Publishing Company, Dordrecht, 1977) pp. 227–237.

    Google Scholar 

  15. J.M. Henderson and R.E. Quandt,Microeconomic theory: mathematical approach, 3rd edn. (McGraw-Hill Inc., New York, 1980) pp. 235–264.

    Google Scholar 

  16. W.W. Hogan, “Project independence evaluation system: structure and algorithm”,Proceedings of Symposia in Applied Mathematics 21 (1977).

  17. L. Hurwicz, “On the problem of the integrability of demand functions”, in J.C. Chipman, ed.,Preferences, utility and demand (Harcourt Brace Javonovich, New York, 1971).

    Google Scholar 

  18. I. Kaneko, “Isotone solutions of parametric linear complementarity problems”,Mathematical Programming 12 (1977) 48–59.

    Article  MATH  MathSciNet  Google Scholar 

  19. S. Karamardian, “Generalized complementarity problem”,Journal of Optimization Theory and Applications 8 (1971) 161–168.

    Article  MATH  MathSciNet  Google Scholar 

  20. O.L. Mangasarian, “Solution of symmetric linear complementarity problems by iterative methods”,Journal of Optimization Theory and Applications 22 (1977) 465–485.

    Article  MATH  MathSciNet  Google Scholar 

  21. L. Mathiesen, “Efficiency pricing in a linear programming model: a case of constraints on the dual variables,”, Operations Research Report 74-108, Department of Operations Research, Stanford University (Stanford, CA, 1974).

    Google Scholar 

  22. J.J. Moré, “Classes of functions and feasibility conditions in nonlinear complementarity problems”,Mathematical Programming 6 (1974) 327–338.

    Article  MATH  MathSciNet  Google Scholar 

  23. A.M. Ostrowski,Solution of equations and systems of equations 2nd edn. (Academic Press, New York, 1966).

    MATH  Google Scholar 

  24. J.S. Pang, “On a class of least-element complementarity problems”,Mathematical Programming 16 (1979) 111–126.

    Article  MATH  MathSciNet  Google Scholar 

  25. J.S. Pang, “The implicit complementarity problem: part II”, Management Science Research Report 459, Graduate School of Industrial Administration, Carnegie-Mellon University (Pittsburgh, PA, 1980).

    Google Scholar 

  26. J. Quirk and R. Saposnik,Introduction to general equilibrium theory and welfare economics (McGraw-Hill, New York, 1968) pp. 61–64.

    Google Scholar 

  27. F. Scarpini, “Some algorithms solving the unilateral Dirichlet problem with two constraints”,Calcolo 12 (1975) 113–149.

    Article  MATH  MathSciNet  Google Scholar 

  28. G. Stampacchia, “Variational inequalities”, in: A. Ghizzetti, ed.,Theory and application of monotone operators, Proceedings of NATO Advanced Study Institute (Venice, Italy, 1968).

  29. A. Tamir, “The complementarity problem of mathematical programming”, Ph.D. Thesis, Department of Operations Research, Case Western Reserve University (Cleveland, OH, 1973).

    Google Scholar 

  30. A.F. Veinott Jr, “Leastd-majorized network flows with inventory and statistical applications”,Management Science 17 (1971) 547–567.

    MathSciNet  MATH  Google Scholar 

  31. A. Whinston, “The bounded variable problem—an application of the dual method for quadratic programming”,Naval Research Logistics Quarterly 12 (1975), 173–179.

    MathSciNet  Google Scholar 

  32. Y. Yoo, “Iterative methods for linear complementarity problems and large scale quadratic programming problems”, M. S. Thesis Korea Advanced Institute of Science and Technology (Seoul, Korea, 1981).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Korea Advanced Institute of Science and Technology, Seoul, Korea

    Byong-Hun AHN

Authors
  1. Byong-Hun AHN
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Byong-Hun, A. Iterative methods for linear complementarity problems with upperbounds on primary variables. Mathematical Programming 26, 295–315 (1983). https://doi.org/10.1007/BF02591868

Download citation

  • Received:

  • Accepted:

  • Issue Date:

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

Key words

Search

Navigation