Cutting planes for semidefinite relaxations based on triangle-free subgraphs

详细信息    查看全文

• 作者：Abraham Berman ; Mirjam Dür ; Naomi Shaked-Monderer ; Julia Witzel
• 关键词：Completely positive matrices ; Copositive cuts ; Semidefinite relaxation
• 刊名：Optimization Letters
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：10
• 期：3
• 页码：433-446
• 全文大小：441 KB
• 参考文献：1.Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Publishing, Cleveland (2003)CrossRef MATH
  2.Bomze, I.M., Frommlet, F., Locatelli, M.: Copositivity cuts for improving SDP bounds on the clique number. Math. Program. 124, 13–32 (2010)CrossRef MathSciNet MATH
  3.Bomze, I.M., Locatelli, M., Tardella, F.: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Math. Program. 115, 31–64 (2008)CrossRef MathSciNet MATH
  4.Burer, S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Program. 120, 479–495 (2009)CrossRef MathSciNet MATH
  5.Burer, S., Anstreicher, K., Dür, M.: The difference between \(5\times 5\) doubly nonnegative and completely positive matrices. Linear Algebra Appl. 431, 1539–1552 (2009)CrossRef MathSciNet MATH
  6.Burer, S., Dong, H.: Separation and relaxation for cones of quadratic forms. Math. Program. 137, 343–370 (2013)CrossRef MathSciNet MATH
  7.Cottle, R.W., Habetler, G.J., Lemke, C.E.: On classes of copositive matrices. Linear Algebra Appl. 3, 295–310 (1970)CrossRef MathSciNet MATH
  8.Dickinson, P.J.C., Gijben, L.: On the computational complexity of membership problems for the completely positive cone and its dual. Comput. Optim. Appl. 57, 403–415 (2014)CrossRef MathSciNet MATH
  9.Dickinson, P.J.C.: Geometry of the copositive and completely positive cones. J. Math. Anal. Appl. 380, 377–395 (2011)CrossRef MathSciNet MATH
  10.Dong, H., Anstreicher, K.: Separating doubly nonnegative and completely positive matrices. Math. Program. 137, 131–153 (2013)CrossRef MathSciNet MATH
  11.Drew, J.H., Johnson, C.R., Loewy, R.: Completely positive matrices associated with M-matrices. Linear Multilinear Algebra 37, 303–310 (1994)CrossRef MathSciNet MATH
  12.Hadeler, K.-P.: On copositive matrices. Linear Algebra Appl. 49, 79–89 (1983)CrossRef MathSciNet MATH
  13.Haynsworth, E., Hoffman, A.J.: Two remarks on copositive matrices. Linear Algebra Appl. 2, 387–392 (1969)CrossRef MathSciNet MATH
  14.Hildebrand, R.: The extreme rays of the \(5\times 5\) copositive cone. Linear Algebra Appl. 437, 1538–1547 (2012)CrossRef MathSciNet MATH
  15.Hoffman, A.J., Pereira, F.: On copositive matrices with \(-1, 0, 1\) entries. J. Comb. Theory (A) 14, 302–309 (1973)CrossRef MathSciNet MATH
  16.Kaplan, W.: A test for copositive matrices. Linear Algebra Appl. 313, 203–206 (2000)CrossRef MathSciNet MATH
  17.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
  18.Peña, J., Vera, J., Zuluaga, L.F.: Computing the stability number of a graph via linear and semidefinite programming. SIAM J. Optim. 18, 87–105 (2007)CrossRef MathSciNet MATH
  19.Sponsel, J., Dür, M.: Factorization and cutting planes for completely positive matrices by copositive projection. Math. Program. 143, 211–229 (2014)CrossRef MathSciNet MATH
  20.Väliaho, H.: Criteria for copositive matrices. Linear Algebra Appl. 81, 19–34 (1986)CrossRef MathSciNet MATH
  
• 作者单位：Abraham Berman (1)
  Mirjam Dür (2)
  Naomi Shaked-Monderer (3)
  Julia Witzel (2)
  
  1. Department of Mathematics, Technion - Israel Institute of Technology, 32000, Haifa, Israel
  2. Department of Mathematics, University of Trier, 54286, Trier, Germany
  3. The Max Stern Yezreel Valley College, 19300, D.N. Yezreel, Israel
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Optimization
  Operation Research and Decision Theory
  Numerical and Computational Methods in Engineering
  Numerical and Computational Methods
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1862-4480

文摘

We show how to separate a doubly nonnegative matrix, which is not completely positive and has a triangle-free graph, from the completely positive cone. This method can be used to compute cutting planes for semidefinite relaxations of combinatorial problems. We illustrate our approach by numerical tests on the stable set problem.