Skip to main content
Log in

Sufficient weighted complementarity problems

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

This paper presents some fundamental results about sufficient linear weighted complementarity problems. Such a problem depends on a nonnegative weight vector. If the weight vector is zero, the problem reduces to a sufficient linear complementarity problem that has been extensively studied. The introduction of the more general notion of a weighted complementarity problem (wCP) was motivated by the fact that wCP can model more general equilibrium problems than the classical complementarity problem (CP). The introduction of a nonzero weight vector makes the theory of wCP more complicated than the theory of CP. The paper gives a characterization of sufficient linear wCP and proposes a corrector–predictor interior-point method for its numerical solution. While the proposed algorithm does not depend on the handicap \(\kappa \) of the problem its computational complexity is proportional with \(1+\kappa \). If the weight vector is zero and the starting point is relatively well centered, then the computational complexity of our algorithm is the same as the best known computational complexity for solving sufficient linear CP.

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

Access this article

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. Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16(2), 400–417 (2005). (electronic)

    Article  MathSciNet  MATH  Google Scholar 

  2. Amini, K., Peyghami, M.: Exploring complexity of large update interior-point methods for \(P_*(\kappa )\) linear complementarity problem based on kernel function. Appl. Math. Comput. 207(2), 501–513 (2009)

    MathSciNet  MATH  Google Scholar 

  3. Anitescu, M., Lesaja, G., Potra, F.A.: Equivalence between different formulations of the linear complementarity problem. Optim. Methods Softw. 7(3), 265–290 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  4. Anstreicher, K.M.: Interior-point algorithms for a generalization of linear programming and weighted centring. Optim. Methods Softw. 27(4–5), 605–612 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  5. Atkinson, D.S., Vaidya, P.M.: A scaling technique for finding the weighted analytic center of a polytope. Math. Progr. 57(2), 163–192 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cho, G.M.: A new large-update interior point algorithm for \(P_*(\kappa )\) linear complementarity problems. J. Comput. Appl. Math. 216(1), 265–278 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cho, G.M., Kim, M.K., Lee, Y.H.: Complexity of large-update interior point algorithm for \(P_\ast (\kappa )\) linear complementarity problems. Comput. Math. Appl. 53(6), 948–960 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)

    MATH  Google Scholar 

  9. Cottle, R.W., Pang, J.S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114(115), 231–249 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  10. Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Statist. 30, 165–168 (1959)

    Article  MathSciNet  MATH  Google Scholar 

  11. Freund, R.M.: Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the \({\rm w}\)-center problem. Math. Progr. 58(3), 385–414 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gowda, M.S.: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8(1), 97–100 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  13. Güler, O.: Generalized linear complementarity problems. Math. Oper. Res. 20(2), 441–448 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gurtuna, F., Petra, C., Potra, F.A., Shevchenko, O., Vancea, A.: Corrector-predictor methods for sufficient linear complementarity problems. Comput. Optim. Appl. 48(3), 453–485 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  15. Guu, S.M., Cottle, R.W.: On a subclass of \({ P}_0\). Linear Algebra Appl. 223(224), 325–335 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  16. Illés, T., Nagy, M., Terlaky, T.: Polynomial interior point algorithms for general linear complementarity problems. Algorithm. Oper. Res. 5(1), 1–12 (2010)

    MathSciNet  MATH  Google Scholar 

  17. Illés, T., Nagy, M., Terlaky, T.: A polynomial path-following interior point algorithm for general linear complementarity problems. J. Global Optim. 47(3), 329–342 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  18. Illés, T., Peng, J., Roos, C., Terlaky, T.: A strongly polynomial rounding procedure yielding a maximally complementary solution for \(P_*(\kappa )\) linear complementarity problems. SIAM J. Optim. 11(2), 320–340 (2000). (electronic)

    Article  MathSciNet  MATH  Google Scholar 

  19. Kheirfam, B.: A predictor-corrector interior-point algorithm for \(P_*(\kappa )\)-horizontal linear complementarity problem. Numer. Algorithms 66(2), 349–361 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  20. de Klerk, E., E.-Nagy, M.: On the complexity of computing the handicap of a sufficient matrix. Math. Program. 129(2), 383–402 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science, vol. 538. Springer, New York (1991)

    Book  MATH  Google Scholar 

  22. Liu, X., Potra, F.A.: Corrector-predictor methods for sufficient linear complementarity problems in a wide neighborhood of the central path. SIAM J. Optim. 17(3), 871–890 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  23. Potra, F.A.: Corrector-predictor methods for monontone linear complementarity problems in a wide neighborhood of the central path. Math. Program. 111(1–2, Ser. B), 243–272 (2008)

    MathSciNet  MATH  Google Scholar 

  24. Potra, F.A.: Weighted complementarity problems–a new paradigm for computing equilibria. SIAM J. Optim. 22(4), 1634–1654 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  25. Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24(1), 1–28 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. Potra, F.A., Liu, X.: Predictor-corrector methods for sufficient linear complementarity problems in a wide neighborhood of the central path. Optim. Methods Softw. 20(1), 145–168 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  27. Rockafellar, R.T.: Convex analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)

    Google Scholar 

  28. Stoer, J.: High order long-step methods for solving linear complementarity problems. Ann. Oper. Res. 103, 149–159 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  29. Stoer, J., Wechs, M.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Math. Progr. 83(3), 407–423 (1998)

    MathSciNet  MATH  Google Scholar 

  30. Stoer, J., Wechs, M., Mizuno, S.: High order infeasible-interior-point methods for solving sufficient linear complementarity problems. Math. Oper. Res. 23(4), 832–862 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  31. Väliaho, H.: \({P}_*\)-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)

    MathSciNet  MATH  Google Scholar 

  32. Ye, Y.: A path to the Arrow-Debreu competitive market equilibrium. Math. Program. 111(1–2, Ser. B), 315–348 (2008)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgments

This material is based upon work supported by the National Science Foundation under Grant No. DMS-1311923.

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Florian A. Potra.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Potra, F.A. Sufficient weighted complementarity problems. Comput Optim Appl 64, 467–488 (2016). https://doi.org/10.1007/s10589-015-9811-z

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9811-z

Keywords

Navigation