Journal article
Separating doubly nonnegative and completely positive matrices
Mathematical programming, Vol.137(1-2), pp.131-153
02/01/2013
DOI: 10.1007/s10107-011-0485-8
Abstract
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.
Details
- Title: Subtitle
- Separating doubly nonnegative and completely positive matrices
- Creators
- Hongbo Dong - University of IowaKurt Anstreicher - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Mathematical programming, Vol.137(1-2), pp.131-153
- Publisher
- Springer Nature
- DOI
- 10.1007/s10107-011-0485-8
- ISSN
- 0025-5610
- eISSN
- 1436-4646
- Number of pages
- 23
- Grant note
- CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 02/01/2013
- Academic Unit
- Industrial and Systems Engineering; Computer Science; Business Analytics
- Record Identifier
- 9984380523202771
Metrics
1 Record Views