Copositivity tests based on the linear complementarity problem

详细信息    查看全文

• 作者：Carmo Brás ; Gabriele Eichfelder…
• 关键词：Conic optimization ; Copositivity ; Complementarity problems ; Linear programming ; 15A48 ; 90C33 ; 65F30 ; 65K99 ; 90C26
• 刊名：Computational Optimization and Applications
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：63
• 期：2
• 页码：461-493
• 全文大小：572 KB
• 参考文献：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)
  2.Bomze, I.M.: Copositive optimization - recent developments and applications. Eur. J. Oper. Res. 216, 509–520 (2012)CrossRef MathSciNet MATH
  3.Bomze, I.M., Eichfelder, G.: Copositivity detection by difference-of-convex decomposition and \(\omega \) -subdivision. Math. Program. Ser. A 138, 365–400 (2013)CrossRef MathSciNet MATH
  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)CrossRef MATH
  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)MathSciNet
  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)
  8.Bundfuss, S., Dür, M.: Algorithmic copositivity detection by simplicial partition. Linear Algebra Appl. 428, 1511–1523 (2008)CrossRef MathSciNet MATH
  9.Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009)CrossRef MathSciNet MATH
  10.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)
  11.Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. SIAM, New York (2009)CrossRef MATH
  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)CrossRef MathSciNet MATH
  14.DIMACS: Second DIMACS Challenge. Test instances available at http://​dimacs.​rutgers.​edu/​challenges . Accessed 13 Jan 2010
  15.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)CrossRef
  16.Eichfelder, G., Jahn, J.: Set-semidefinite optimization. J. Convex Anal. 15, 767–801 (2008)MathSciNet MATH
  17.Facchinei, F., Pang, J.-S.: Finite-Dimensional Variational Inequalities and Complementarity Problems. Springer, New York (2003)
  18.Hall Jr, M., Newman, M.: Copositive and completely positive quadratic forms. Proc. Camb. Philos. Soc. 59, 329–339 (1963)CrossRef MathSciNet MATH
  19.Hiriart-Urruty, J.-B., Seeger, A.: A variational approach to copositive matrices. SIAM Rev. 52, 593–629 (2010)CrossRef MathSciNet MATH
  20.Hoffman, A.J., Pereira, F.: On copositive matrices with \(-\) 1,0,1 entries. J. Combin. Theory A 14, 302–309 (1973)CrossRef MathSciNet MATH
  21.Horst, R., Pardalos, P.M., Thoai, N.: Introduction to Global Optimization. Kluwer Academic Publishers, Dordrecht (2000)CrossRef MATH
  22.Júdice, J., Faustino, A., Ribeiro, I.: On the solution of NP-hard linear complementarity problems. Top 10, 125–145 (2002)CrossRef MathSciNet MATH
  23.Kaplan, W.: A copositivity probe. Linear Algebra Appl. 337, 237–251 (2001)CrossRef MathSciNet MATH
  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)MATH
  27.Murty, K.G., Kabadi, S.N.: Some NP-complete problems in quadratic and linear programming. Math. Progr. 39, 117–129 (1987)CrossRef MathSciNet MATH
  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)CrossRef MATH
  30.Tanaka, A., Yoshise, A.: An LP-based algorithm to test copositivity. Pac. J. Optim. 11(1), 101–120 (2015)MathSciNet
  31.Väliaho, H.: Criteria for copositive matrices. Linear Algebra Appl. 81, 19–34 (1986)CrossRef MathSciNet MATH
  32.Väliaho, H.: Quadratic-programming criteria for copositive matrices. Linear Algebra Appl. 119, 163–182 (1989)CrossRef MathSciNet MATH
  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)CrossRef MathSciNet MATH
  
• 作者单位：Carmo Brás (1)
  Gabriele Eichfelder (2)
  Joaquim Júdice (3)
  
  1. CMA, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa, Lisboa, Portugal
  2. Institute for Mathematics, Technische Universität Ilmenau, PO Box 10 05 65, 98684, Ilmenau, Germany
  3. Instituto de Telecomunicações, Coimbra, Portugal
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operations Research and Mathematical Programming
  Operation Research and Decision Theory
  Statistics
  Convex and Discrete Geometry
  
• 出版者：Springer Netherlands
• ISSN：1573-2894

文摘

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. Keywords Conic optimization Copositivity Complementarity problems Linear programming