Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 8 down vote accepted

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.

share|improve this answer
    
Thank you for those bilbiographic hints, exactly what I was looking for. –  kaleidoscop Jul 25 '12 at 8:25
    
@Raphael Lachieze-Rey: You're welcome! If you'll allow me some shameless self-promotion, I'll also mention that I worked out the details of some generalizations of these ideas to higher order tensors in Ch. $2$ of my thesis: mit.edu/~nstein/documents/DoctoralThesis.pdf (specifically the parts on complete positivity and double nonnegativity). –  Noah Stein Jul 25 '12 at 8:55

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

share|improve this answer

(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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.