8
$\begingroup$

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.

$\endgroup$

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you for those bilbiographic hints, exactly what I was looking for. $\endgroup$ Jul 25, 2012 at 8:25
  • $\begingroup$ @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). $\endgroup$
    – Noah Stein
    Jul 25, 2012 at 8:55
6
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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