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.
Similar content being viewed by others
References
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)
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)
Anitescu, M., Lesaja, G., Potra, F.A.: Equivalence between different formulations of the linear complementarity problem. Optim. Methods Softw. 7(3), 265–290 (1997)
Anstreicher, K.M.: Interior-point algorithms for a generalization of linear programming and weighted centring. Optim. Methods Softw. 27(4–5), 605–612 (2012)
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)
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)
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)
Cottle, R.W., Pang, J.S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
Cottle, R.W., Pang, J.S., Venkateswaran, V.: Sufficient matrices and the linear complementarity problem. Linear Algebra Appl. 114(115), 231–249 (1989)
Eisenberg, E., Gale, D.: Consensus of subjective probabilities: the pari-mutuel method. Ann. Math. Statist. 30, 165–168 (1959)
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)
Gowda, M.S.: Reducing a monotone horizontal LCP to an LCP. Appl. Math. Lett. 8(1), 97–100 (1995)
Güler, O.: Generalized linear complementarity problems. Math. Oper. Res. 20(2), 441–448 (1995)
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)
Guu, S.M., Cottle, R.W.: On a subclass of \({ P}_0\). Linear Algebra Appl. 223(224), 325–335 (1995)
Illés, T., Nagy, M., Terlaky, T.: Polynomial interior point algorithms for general linear complementarity problems. Algorithm. Oper. Res. 5(1), 1–12 (2010)
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)
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)
Kheirfam, B.: A predictor-corrector interior-point algorithm for \(P_*(\kappa )\)-horizontal linear complementarity problem. Numer. Algorithms 66(2), 349–361 (2014)
de Klerk, E., E.-Nagy, M.: On the complexity of computing the handicap of a sufficient matrix. Math. Program. 129(2), 383–402 (2011)
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)
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)
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)
Potra, F.A.: Weighted complementarity problems–a new paradigm for computing equilibria. SIAM J. Optim. 22(4), 1634–1654 (2012)
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)
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)
Rockafellar, R.T.: Convex analysis. Princeton Mathematical Series, vol. 28. Princeton University Press, Princeton (1970)
Stoer, J.: High order long-step methods for solving linear complementarity problems. Ann. Oper. Res. 103, 149–159 (2001)
Stoer, J., Wechs, M.: Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity. Math. Progr. 83(3), 407–423 (1998)
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)
Väliaho, H.: \({P}_*\)-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)
Ye, Y.: A path to the Arrow-Debreu competitive market equilibrium. Math. Program. 111(1–2, Ser. B), 315–348 (2008)
Acknowledgments
This material is based upon work supported by the National Science Foundation under Grant No. DMS-1311923.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
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
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-015-9811-z