Optimization Online


The Difference Between 5x5 Doubly Nonnegative and Completely Positive Matrices

Samuel Burer (samuel-burer***at***uiowa.edu)
Kurt M. Anstreicher (kurt-anstreicher***at***uiowa.edu)
Mirjam Duer (M.E.Dur***at***rug.nl)

Abstract: The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. In this paper, we investigate the difference between $5\times 5$ DNN and CPP matrices. Defining a {\em bad\/} matrix to be one which is DNN but not CPP, we: (i) characterize all $5 \times 5$ extreme DNN matrices, in particular bad ones; (ii) design a finite procedure to decompose any $n \times n$ DNN matrix into the sum of a CPP matrix and a bad matrix, which itself cannot be further decomposed; (iii) show that every bad $5 \times 5$ DNN matrix is the sum of a CPP matrix and a single bad extreme matrix; and (iv) demonstrate how to separate bad extreme matrices from the cone of $5 \times 5$ CPP matrices.

Keywords: completely positive matrices, doubly nonnegative matrices, copositive matrices

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Global Optimization (Theory )

Citation: Linear Algebra and its Applications 431 (2009), 1539-1552.

Download: [PDF]

Entry Submitted: 05/27/2008
Entry Accepted: 05/27/2008
Entry Last Modified: 08/17/2009

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