Characterising semi-definite positiveness on vectors with non-negative entries - MathOverflow

Characterising semi-definite positiveness on vectors with non-negative entries

2012-07-24T16:10:33Z

My problem is to characterise (or find useful information on) the cone $C$ of $N\times N$ matrices $M$ ($N\geq 1$) such that $$V^t M V\geq 0$$ for every vector $V $ with non-negative entries. Is this cone of matrices familiar to anyone?

Remark 1: $C$ clearly contains the convex cone $S$ of semi-definite positive matrices, and that of matrices $P$ with non-negative entries. Even though it looks too easy, I could not prove that $C$ is not the convex hull of $S$ and $P$.

Remark 2: My original problem is to characterise the dual cone of $C$, containing the covariances of random vectors of $\mathbb{R}^N$ with a.s. non-negative entries.

Answer by Brian Borchers for Characterising semi-definite positiveness on vectors with non-negative entries

2012-07-24T17:10:28Z

Your cone $C$ is the cone of copositive matrices. The dual of C is the cone of compeltely positive matrices. See e.g.

http://mathworld.wolfram.com/CopositiveMatrix.html

Answer by Noah Stein for Characterising semi-definite positiveness on vectors with non-negative entries

2012-07-24T17:37:51Z

The cone $C$ is called the cone of copositive matrices and its dual $C^*$ is called the cone of completely positive matrices. Here are some references.

The paper most relevant to your question is probably "On Non-Negative Forms In Real Variables Some Or All Of Which Are Non-Negative," in which P. H. Diananda shows that $C$ does in fact take the simple form you stated in Remark 1 in the case $n\leq 4$. As mentioned in a note at the end of that paper, a counterexample called the Horn Form shows that $C$ does not have this form when $n\geq 5$.

Another important paper in this area is "Some NP-Complete Problems In Quadratic And Nonlinear Programming" by K. G. Murty and S. N. Kabadi. There the authors show that checking membership in $C$ is co-NP-complete. In "Semidefinite programming based tests for matrix copositivity," P. A. Parrilo constructs a hierarchy of outer approximations to $C$ defined via SDPs; their duals give inner approximations to $C^*$. By combining these ideas one can easily construct semidefinite program approximations to a variety NP-complete optimization problems.

Answer by Denis Serre for Characterising semi-definite positiveness on vectors with non-negative entries

2012-07-25T07:06:22Z

(After Noah Stein's answer) By definition, the dual cone $C^\star$ is spanned by matrices $v\otimes v$ with $v\ge0$. The following counter-example is due to Hall. The $5\times5$ symmetric matrix $$S=\begin{pmatrix} 4 & 0 & 0 & 2 & 2 \\ 0 & 4 & 3 & 0 & 2 \\ 0 & 3 & 4 & 2 & 0 \\ 2 & 0 & 2 & 4 & 0 \\ 2 & 2 & 0 & 0 & 4 \end{pmatrix}$$ has non-negative entries and is positive semi-definite. Therefore, it belongs to $(S\cup P)^\star$. Yet, it cannot be written as the sum of $v_j\otimes v_j$ where the vectors $v_j$ are non-negative. Therefore $A\not\in C^\star$. By duality, this proves that $C$ is not the convex hull of $S\cup P$.

The example is analyzed in details in Exercise 347 of my list.