Separating doubly nonnegative and completely positive matrices

• 成果类型: Article
• 署名作者: Dong, Hongbo; Anstreicher, Kurt
• 署名单位: University of Iowa; University of Iowa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-011-0485-8
• 发表日期: 2013
• 页码: 131-153
• 关键词: standard quadratic optimization; 5 x 5; stability number; semidefinite; approximation; bounds; graph

摘要

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 x 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.