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.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for those bilbiographic hints, exactly what I was looking for. $\endgroup$
    – kaleidoscop
    Commented 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
    Commented 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.

Improve this answer
$\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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .