Separating Doubly Nonnegative and Completely Positive Matrices
Hongbo Dong (hongbo-donguiowa.edu)
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 5x5 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.
Keywords: Completely positive matrices, copositive programming, semidefinite programming
Category 1: Global Optimization (Theory )
Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )
Category 3: Linear, Cone and Semidefinite Programming (Other )
Citation: Working paper, Dept. of Management Sciences, University of Iowa, Iowa City IA, March 2010.
Entry Submitted: 03/04/2010
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|