2
$\begingroup$

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?

$\endgroup$
4
  • 3
    $\begingroup$ 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. $\endgroup$
    – alex o.
    May 4, 2012 at 5:55
  • $\begingroup$ 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! $\endgroup$ May 4, 2012 at 9:14
  • $\begingroup$ 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. $\endgroup$ May 4, 2012 at 10:15
  • 1
    $\begingroup$ 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$. $\endgroup$
    – alex o.
    May 4, 2012 at 18:56

0

Your Answer

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