Optimization Online


Separating Doubly Nonnegative and Completely Positive Matrices

Hongbo Dong (hongbo-dong***at***uiowa.edu)
Kurt M. Anstreicher (kurt-anstreicher***at***uiowa.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.

Download: [PDF]

Entry Submitted: 03/04/2010
Entry Accepted: 03/05/2010
Entry Last Modified: 03/16/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society