Let $X \in \mathbb{R}^{n \times n}$ be symmetric matrix. Consider the following set $$ \mathcal{C} = \{ X: X \succeq 0, \quad 0 \le X_{ij} \le 1, \forall i,j\} $$ What are the extreme points of this set? What is changed if we also add the constraints $\sum_{j} X_{ij} = m$ for some integer $m < n$ and $\forall i$?
$\begingroup$
$\endgroup$
11
-
$\begingroup$ This site is not for homework. $\endgroup$– Anthony QuasFeb 20, 2014 at 14:05
-
1$\begingroup$ Maybe I'm missing something, but I would not expect this question to have a simple answer or to be homework. The set $\mathcal{C}$ is not (for general $n$) polyhedral, so there must be more extreme points than just the binary matrices. Also, the cone of doubly nonnegative matrices (positive semidefinite and elementwise nonnegative) is strictly larger than the cone of completely positive matrices (the convex hull of $xx^T$ for $x\geq 0$), so the extreme points are not just $xx^T$ for appropriately scaled $x$... $\endgroup$– Noah SteinFeb 20, 2014 at 20:50
-
1$\begingroup$ ... This problem asks about the intersection of the doubly nonnegative cone with some halfspaces; as far as I know the extreme rays of the doubly nonnegative cone have not been nicely characterized. $\endgroup$– Noah SteinFeb 20, 2014 at 20:51
-
1$\begingroup$ I haven't heard "doubly nonnegative cone" before but in the convex optimization world, $\succeq$ applied to symmetric matrices implies a linear matrix inequality; i.e., $X$ above lies in the semidefinite cone. I'm inclined to leave this closed myself, though (not that I have the points in this SE to have a say). It's not off-topic, but I don't think it's concrete or specific enough. $\endgroup$– Michael GrantFeb 22, 2014 at 15:43
-
1$\begingroup$ Also there is the cone of completely positive matrices (which I defined above). The doubly nonnegative matrices are a tractable outer approximation to this cone while the copositive matrices ($A$ such that $x^TAx\geq 0$ for $x\geq 0$) are the dual of the completely positive matrices. There is also a tractable inner approximation to the copositive matrices, though I don't think it has a name: it is given by sums of positive semidefinite and elementwise nonnegative matrices. $\endgroup$– Noah SteinFeb 22, 2014 at 16:17
|
Show 6 more comments