  


Separating Doubly Nonnegative and Completely Positive Matrices
Hongbo Dong (hongbodonguiowa.edu) Abstract: The cone of Completely Positive (CP) matrices can be used to exactly formulate a variety of NPHard 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 nonCP 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 nonCP. We also describe a generalization that applies to larger DNN but nonCP 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. Download: [PDF] Entry Submitted: 03/04/2010 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  