Abstract
The class of sufficient matrices is important in the study of the linear complementarity problem (LCP)—some interior point methods (IPM’s) for LCP’s with sufficient data matrices have complexity polynomial in the bit size of the matrix and its handicap.In this paper we show that the handicap of a sufficient matrix may be exponential in its bit size, implying that the known complexity bounds of interior point methods are not polynomial in the input size of the LCP problem. We also introduce a semidefinite programming based heuristic, that provides a finite upper bond on the handicap, for the sub-class of \({\mathcal{P}}\) -matrices (where all principal minors are positive).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Fiedler M., Pták V.: On matrices with non-positive off-diagonal elements and positive principal minors. Czech. Math. J. 12, 382–400 (1962)
Guu S.M.: Sign reversing and matrix classes. J. Optim. Theory Appl. 89(2), 373–387 (1996)
Guu S.M., Cottle R.W.: On a subclass of P 0. Linear Algebra Appl. 223(224), 325–335 (1995)
Henrion, D., Lasserre, J.-B., Löfberg, J.: Gloptipoly 3: moments, optimization and semidefinite programming. (2008) http://homepages.laas.fr/henrion/papers/gloptipoly3.pdf
Illés T., Peng J., Roos C., Terlaky T.: A strongly polynomial rounding procedure yielding a maximally complementary solution for P *(κ) linear complementarity problems. SIAM J. Optim. 11(2), 320–340 (2000)
Kojima M., Mizuno S., Yoshise A.: A polynomial-time algorithm for a class of linear complementary problems. Math. Program. 44, 1–26 (1989)
Kojima M., Megiddo N., Noma T., Yoshise A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. vol. 538 of Lecture Notes in Computer Science. Springer, Berlin (1991)
Lasserre J.: Global optimization with polynomials and the problem of moments. SIAM J. Optimization. 11, 796–817 (2001)
Laurent, M.: Sums of squares, moment matrices and optimization over polynomials. In: Putinar, M., Sullivant, S., (eds.) Emerging Applications of Algebraic Geometry, vol. 149 in IMA Volumes in Mathematics and its Applications. Springer, pp. 157–270 (2009). Updated version available at: http://homepages.cwi.nl/~monique/files/moment-ima-update-new.pdf
Megiddo N.: A Note on the Complexity of P-Matrix LCP and Computing an Equilibrium. Research Report RJ 6439. IBM Almaden Research Center, San Jose, California (1988)
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)
Putinar M.: Positive polynomials on compact semi-algebraic sets. Indiana Univ. Math. J. 42, 969–984 (1993)
Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11(12), 625–653 (1999)
Tseng P.: Co-NP-completeness of some matrix classification problems. Math. Program. 88, 183–192 (2000)
Väliaho H.: P *-matrices are just sufficient. Linear Algebra Appl. 239, 103–108 (1996)
Väliaho H.: Determining the handicap of a sufficient matrix. Linear Algebra Appl. 253, 279–298 (1997)
Vavasis S.A.: Quadratic programming is in NP. Inf. Process. Lett. 36(2), 73–77 (1990)
Open Access
This article is distributed under the terms of the Creative Commons Attribution Noncommercial License which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
de Klerk, E., -Nagy, M.E. On the complexity of computing the handicap of a sufficient matrix. Math. Program. 129, 383–402 (2011). https://doi.org/10.1007/s10107-011-0465-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0465-z