×

Copositivity tests based on the linear complementarity problem. (English) Zbl 1360.90245

Summary: 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.

MSC:

90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C26 Nonconvex programming, global optimization
65F30 Other matrix algorithms (MSC2010)
65K99 Numerical methods for mathematical programming, optimization and variational techniques

Software:

Matlab; MINOS; GAMS; CPLEX; BARON
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] 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) · Zbl 1226.65037
[2] Bomze, I.M.: Copositive optimization - recent developments and applications. Eur. J. Oper. Res. 216, 509-520 (2012) · Zbl 1262.90129 · doi:10.1016/j.ejor.2011.04.026
[3] Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and \[\omega\] ω-subdivision. Math. Program. Ser. A 138, 365-400 (2013) · Zbl 1267.65060 · doi:10.1007/s10107-012-0543-x
[4] 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) · Zbl 0916.90214 · doi:10.1023/A:1008369322970
[5] 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) · Zbl 1268.90051
[6] Brooke, A., Kendrick, D., Meeraus, A., Raman, R.: GAMS a User’s Guide. GAMS Development Corporation, Washington (1998)
[7] Bundfuss, S.: Copositive Matrices, Copositive Programming, and Applications. Dissertation, Technischen Universität Darmstadt (2009) · Zbl 1170.65047
[8] Bundfuss, S., Dür, M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428, 1511-1523 (2008) · Zbl 1138.15007 · doi:10.1016/j.laa.2007.09.035
[9] Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479-495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[10] Burer, S.; Anjos, MF (ed.); Lasserre, J-B (ed.), Copositive programming (2011), Berlin · Zbl 1272.90044
[11] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, New York (2009) · Zbl 1192.90001 · doi:10.1137/1.9780898719000
[12] CPLEX, I.: 11.0 Users Manual. ILOG SA, Gentilly (2008)
[13] de Klerk, E., Pasechnik, D.V.: Approximation of the stability number of a graph via copositive programming. SIAM J. Optim. 12, 875-892 (2002) · Zbl 1035.90058 · doi:10.1137/S1052623401383248
[14] DIMACS: Second DIMACS Challenge. Test instances available at http://dimacs.rutgers.edu/challenges. Accessed 13 Jan 2010 · Zbl 0999.15027
[15] Dür, M.; Diehl, M. (ed.); Glineur, F. (ed.); Jarlebring, E. (ed.); Michiels, W. (ed.), Copositive programming—a survey, 3-20 (2010), New York · doi:10.1007/978-3-642-12598-0_1
[16] Eichfelder, G., Jahn, J.: Set-semidefinite optimization. J. Convex Anal. 15, 767-801 (2008) · Zbl 1172.90013
[17] Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003) · Zbl 1062.90002
[18] Hall Jr, M., Newman, M.: Copositive and completely positive quadratic forms. Proc. Camb. Philos. Soc. 59, 329-339 (1963) · Zbl 0124.25302 · doi:10.1017/S0305004100036951
[19] Hiriart-Urruty, J.-B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52, 593-629 (2010) · Zbl 1207.15037 · doi:10.1137/090750391
[20] Hoffman, A.J., Pereira, F.: On copositive matrices with \[--1,0,1\] entries. J. Combin. Theory A 14, 302-309 (1973) · Zbl 0273.15019 · doi:10.1016/0097-3165(73)90006-X
[21] Horst, R., Pardalos, P.M., Thoai, N.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2000) · Zbl 0966.90073 · doi:10.1007/978-1-4615-0015-5
[22] Júdice, J., Faustino, A., Ribeiro, I.: On the solution of NP-hard linear complementarity problems. Top 10, 125-145 (2002) · Zbl 1006.90082 · doi:10.1007/BF02578944
[23] Kaplan, W.: A copositivity probe. Linear Algebra Appl. 337, 237-251 (2001) · Zbl 0999.15027 · doi:10.1016/S0024-3795(01)00351-2
[24] Moler, C., Little, J., Bangert, S.: Mass. Matlab User’s Guide—The Language of Technical Computing. The MathWorks, Sherborn (2001)
[25] Murtagh, B., Saunders, M., Murray, W., Gill, P., Raman, R., Kalvelagen, E.: MINOS-NLP. Systems Optimization Laboratory, Stanford University, Palo Alto (2002)
[26] Murty, K.G.: Linear Complementarity. Linear and Nonlinear Programming. Heldermann, Berlin (1988) · Zbl 0634.90037
[27] Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and linear programming. Math. Progr. 39, 117-129 (1987) · Zbl 0637.90078 · doi:10.1007/BF02592948
[28] Sahinidis, N., Tawarmalani, M.: BARON 7.2.5: Global Optimization of Mixed-Integer Nonlinear Programs. GAMS Development Corporation, Washington (2005)
[29] Sponsel, J., Bundfuss, S., Dür, M.: An improved algorithm to test copositivity. J. Glob. Optim. 52, 537-551 (2012) · Zbl 1250.65061 · doi:10.1007/s10898-011-9766-2
[30] Tanaka, A., Yoshise, A.: An LP-based algorithm to test copositivity. Pac. J. Optim. 11(1), 101-120 (2015) · Zbl 1327.90181
[31] Väliaho, H.: Criteria for copositive matrices. Linear Algebra Appl. 81, 19-34 (1986) · Zbl 0598.15017 · doi:10.1016/0024-3795(86)90246-6
[32] Väliaho, H.: Quadratic-programming criteria for copositive matrices. Linear Algebra Appl. 119, 163-182 (1989) · Zbl 0681.15012 · doi:10.1016/0024-3795(89)90076-1
[33] Žilinskas, J., Dür, M.: Depth-first simplicial partition for copositivity detection, with an application to Maxclique. Optim. Methods. Softw. 26, 499-510 (2011) · Zbl 1226.65037 · doi:10.1080/10556788.2010.544310
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.