2

1

I want to check under what conditions a matrix of the form $\alpha J -Q$ is copositive, where $J$ is the all-ones matrix and $Q$ is doubly nonegative (i.e. entrywise nonnegative and positive semidefinite). Talking about theory here, not an algorithm. I scanned the literature but didn't find anything to build on. Do you have suggestions?

flag
3 
 I believe the answer is that this is true if and only if $\alpha$ is at least the largest diagonal entry of $Q$, and this holds just under the assumption that $Q$ is nonnegative definite. This follows from the following two facts: (i) a matrix $A$ is copositive if and only if $x^T A x \geq 0$ for all $x$ in the simplex $S_n$. (ii) if $Q$ is nonnegative definite, then $x^T Q X$ is convex and $\max_{x \in S_n} x^T Q x$ is achieved at the extreme points $e_i$ of the simplex. – alex o. May 4 2012 at 5:55
Alex, thanks for the answer! Can you give a reference for fact (ii) - it seems true to me but I can't nail it? Thanks again! – Felix Goldberg May 4 2012 at 9:14
I've now proved Alex's statement to myself, deriving it from the general Motzkin-Straus theorem. But would still love to get a textbook reference. Thanks once again, Alex. – Felix Goldberg May 4 2012 at 10:15
1 
 Felix, if $Q$ is nonnegative definite, then it has a symmetric square root $L$ and $x^T Q x = ||Lx||_2^2$, so $x^T Q x$ is the composition of a linear function ($x \rightarrow Lx$) and a convex function ($x \rightarrow ||x||_2^2$). Consequently, it is convex. Next, for every convex function $f$, we have that by definition of convexity, $f(\sum_i \alpha_i x_i) \leq \sum_i \alpha_i f(x_i) \leq \max_i f(x_i)$, where $\alpha_i$ are nonnegative and add up to $1$. Finally, every point in the simplex is a convex combination of the vectors $e_i$. – alex o. May 4 2012 at 18:56
Thanks, this is a nice argument. – Felix Goldberg May 6 2012 at 23:29

Your Answer

Get an OpenID
or

Browse other questions tagged or ask your own question.