Abstract
We present copositivity tests based on new necessary and sufficient conditions which require the solution of linear complementarity problems (LCP). We propose methodologies involving Lemke’s method, an enumerative algorithm and a linear mixed-integer programming formulation to solve the required LCPs. Moreover, we discuss a new necessary condition for (strict) copositivity based on solving a linear program, which can be used as a preprocessing step. The algorithms with these three different variants are thoroughly applied to test matrices from the literature and to max-clique instances with matrices of order up to \(496\times 496\). We compare our procedures with three other copositivity tests from the literature as well as with a general global optimization solver. The numerical results are very promising and equally good and in many cases better than the results reported elsewhere.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Adler, I., Verma, S.: The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD. Manuscript, Department of IEOR, University of California, Berkeley (2011)
Bomze, I.M.: Copositive optimization - recent developments and applications. Eur. J. Oper. Res. 216, 509–520 (2012)
Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision. Math. Program. Ser. A 138, 365–400 (2013)
Bomze, I.M., Dür, M., de Klerk, E., Roos, C., Quist, A.J., Terlaky, T.: On copositive programming and standard quadratic optimization problems. J. Glob. Optim. 13, 369–387 (1998)
Bomze, I.M., Schachinger, W., Uchida, G.: Think co(mpletely)positive ! Matrix properties, examples and a clustered bibliography on copositive optimization. J. Glob. Optim. 52, 425–445 (2012)
Brooke, A., Kendrick, D., Meeraus, A., Raman, R.: GAMS a User’s Guide. GAMS Development Corporation, Washington (1998)
Bundfuss, S.: Copositive Matrices, Copositive Programming, and Applications. Dissertation, Technischen Universität Darmstadt (2009)
Bundfuss, S., Dür, M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428, 1511–1523 (2008)
Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009)
Burer, S.: Copositive programming. In: Anjos, M.F., Lasserre, J.-B. (eds.) Handbook of Semidefinite, Cone and Polynomial Optimization: Theory. Algorithms,Software and Applications. Operations Research and Management Science. Springer, Berlin (2011)
Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, New York (2009)
CPLEX, I.: 11.0 Users Manual. ILOG SA, Gentilly (2008)
de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875–892 (2002)
DIMACS: Second DIMACS Challenge. Test instances available at http://dimacs.rutgers.edu/challenges. Accessed 13 Jan 2010
Dür, M.: Copositive programming—a survey. In: Diehl, M., Glineur, F., Jarlebring, E., Michiels, W. (eds.) Recent Advances in Optimization and its Applications in Engineering, pp. 3–20. Springer, New York (2010)
Eichfelder, G., Jahn, J.: Set-semidefinite optimization. J. Convex Anal. 15, 767–801 (2008)
Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
Hall Jr, M., Newman, M.: Copositive and completely positive quadratic forms. Proc. Camb. Philos. Soc. 59, 329–339 (1963)
Hiriart-Urruty, J.-B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52, 593–629 (2010)
Hoffman, A.J., Pereira, F.: On copositive matrices with \(-\)1,0,1 entries. J. Combin. Theory A 14, 302–309 (1973)
Horst, R., Pardalos, P.M., Thoai, N.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2000)
Júdice, J., Faustino, A., Ribeiro, I.: On the solution of NP-hard linear complementarity problems. Top 10, 125–145 (2002)
Kaplan, W.: A copositivity probe. Linear Algebra Appl. 337, 237–251 (2001)
Moler, C., Little, J., Bangert, S.: Mass. Matlab User’s Guide—The Language of Technical Computing. The MathWorks, Sherborn (2001)
Murtagh, B., Saunders, M., Murray, W., Gill, P., Raman, R., Kalvelagen, E.: MINOS-NLP. Systems Optimization Laboratory, Stanford University, Palo Alto (2002)
Murty, K.G.: Linear Complementarity. Linear and Nonlinear Programming. Heldermann, Berlin (1988)
Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and linear programming. Math. Progr. 39, 117–129 (1987)
Sahinidis, N., Tawarmalani, M.: BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs. GAMS Development Corporation, Washington (2005)
Sponsel, J., Bundfuss, S., Dür, M.: An improved algorithm to test copositivity. J. Glob. Optim. 52, 537–551 (2012)
Tanaka, A., Yoshise, A.: An LP-based algorithm to test copositivity. Pac. J. Optim. 11(1), 101–120 (2015)
Väliaho, H.: Criteria for copositive matrices. Linear Algebra Appl. 81, 19–34 (1986)
Väliaho, H.: Quadratic-programming criteria for copositive matrices. Linear Algebra Appl. 119, 163–182 (1989)
Žilinskas, J., Dür, M.: Depth-first simplicial partition for copositivity detection, with an application to Maxclique. Optim. Methods. Softw. 26, 499–510 (2011)
Acknowledgments
The work of the first author was partially supported by the Portuguese Foundation for Science and Technology through the Project UID/MAT/00297/2013 (CMA). The research of the third author was in the scope of R&D Unit 50008, financed by the applicable financial framework (FCT/MEC through national funds and when applicable co-funded by FEDER PT2020 partnership agreement.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Brás, C., Eichfelder, G. & Júdice, J. Copositivity tests based on the linear complementarity problem. Comput Optim Appl 63, 461–493 (2016). https://doi.org/10.1007/s10589-015-9772-2
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-015-9772-2