×

Separating doubly nonnegative and completely positive matrices. (English) Zbl 1263.90064

Summary: The cone of completely positive (CP) matrices can be used to exactly formulate a variety of NP-Hard optimization problems. A tractable relaxation for CP matrices is provided by the cone of doubly nonnegative (DNN) matrices; that is, matrices that are both positive semidefinite and componentwise nonnegative. A natural problem in the optimization setting is then to separate a given DNN but non-CP matrix from the cone of CP matrices. We describe two different constructions for such a separation that apply to \(5 \times 5\) matrices that are DNN but non-CP. We also describe a generalization that applies to larger DNN but non-CP matrices having block structure. Computational results illustrate the applicability of these separation procedures to generate improved bounds on difficult problems.

MSC:

90C26 Nonconvex programming, global optimization
90C22 Semidefinite programming
90C20 Quadratic programming
15B48 Positive matrices and their generalizations; cones of matrices

Software:

SeDuMi
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anstreicher K.M., Burer S.: Computable representations for convex hulls of low-dimensional quadratic forms. Math. Prog. B 124, 33–43 (2010) · Zbl 1198.90311 · doi:10.1007/s10107-010-0355-9
[2] Burer S., Anstreicher K.M., Dür M.: The difference between 5 {\(\times\)} 5 doubly nonnegative and completely positive matrices. Linear Algebra Appl. 431, 1539–1552 (2009) · Zbl 1175.15026 · doi:10.1016/j.laa.2009.05.021
[3] Barioli F.: Completely positive matrices with a book-graph. Linear Algebra Appl. 277, 11–31 (1998) · Zbl 0932.05055 · doi:10.1016/S0024-3795(97)10070-2
[4] Bundfuss S., Dür M.: An adaptive linear approximation algorithm for copositive programs. SIAM J. Optim. 20, 30–53 (2009) · Zbl 1187.90187 · doi:10.1137/070711815
[5] Bomze I.M., de Klerk E.: Solving standard quadratic optimization problems via linear, semidefinite and copositive programming. J. Global Optim. 24, 163–185 (2002) · Zbl 1047.90038 · doi:10.1023/A:1020209017701
[6] Bomze I.M., Frommlet F., Locatelli M.: Copositivity cuts for improving SDP bounds on the clique number. Math. Prog. B 124, 13–32 (2010) · Zbl 1198.90312 · doi:10.1007/s10107-010-0363-9
[7] Burer S., Letchford A.N.: On nonconvex quadratic programming with box constriants. SIAM J. Optim. 20, 1073–1089 (2009) · Zbl 1201.90146 · doi:10.1137/080729529
[8] Bomze I.M., Locatelli M., Tardella F.: New and old bounds for standard quadratic programming: dominance, equivalence and incomparability. Math. Prog. 115, 31–64 (2008) · Zbl 1171.90007 · doi:10.1007/s10107-007-0138-0
[9] Berman A., Shaked-Monderer N.: Completely Positive Matrices. World Scientific, Singapore (2003) · Zbl 1030.15022
[10] Burer S.: On the copositive representation of binary and continuous nonconvex quadratic programs. Math. Prog. 120, 479–495 (2009) · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z
[11] Burer S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Prog. Comp. 2, 1–19 (2010) · Zbl 1190.90135 · doi:10.1007/s12532-010-0010-8
[12] Berman A., Xu C.: 5 {\(\times\)} 5 Completely positive matrices. Linear Algebra Appl. 393, 55–71 (2004) · Zbl 1067.15019 · doi:10.1016/j.laa.2004.08.004
[13] Dong H., Anstreicher K.: On ’5 {\(\times\)} 5 Completely positive matrices’. Linear Algebra Appl. 433, 1001–1004 (2010) · Zbl 1191.15027 · doi:10.1016/j.laa.2010.04.031
[14] 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
[15] Dür M., Still G.: Interior points of the completely positive cone. Electron. J. Linear Algebra 17, 48–53 (2008) · Zbl 1151.15019
[16] Hall M. Jr: Combinatorial Theory. Blaisdell Publishing Company, Waltham (1967)
[17] Hogben L., Johnson C.R., Reams R.: The copositive completion problem. Linear Algebra Appl. 408, 207–211 (2005) · Zbl 1098.15010 · doi:10.1016/j.laa.2005.06.019
[18] Kogan N., Berman A.: Characterization of completely positive graphs. Discret. Math. 114, 297–304 (1993) · Zbl 0783.05071 · doi:10.1016/0012-365X(93)90374-3
[19] 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) · Zbl 1176.90611 · doi:10.1137/05064401X
[20] Väliaho H.: Almost copositive matrices. Linear Algebra Appl. 116, 121–134 (1989) · Zbl 0673.15008 · doi:10.1016/0024-3795(89)90402-3
[21] Yajima Y., Fujie T.: A polyhedral approach for nonconvex quadratic programming problems with box constraints. J. Global Optim. 13, 151–170 (1998) · Zbl 0912.90234 · doi:10.1023/A:1008293029350
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.