Timeline for Extreme points of a set related to semidefinite cone
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 24, 2014 at 15:36 | history | reopened |
Noah Stein Ricardo Andrade Stefan Kohl♦ Suvrit Steven Landsburg |
||
| Feb 22, 2014 at 16:17 | comment | added | Noah Stein | 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. | |
| Feb 22, 2014 at 15:47 | comment | added | passerby51 | @MichaelC.Grant: Yes, that is true. I haven't heard of it before, and apparently there is a sizable literature talking about optimization over such cone (and a related object, the cone of co-positive matrices.) | |
| Feb 22, 2014 at 15:44 | comment | added | Michael Grant | Ah, I see now: the doubly nonnegative cone is the set of semidefinite matrices whose elements are all nonnegative. | |
| Feb 22, 2014 at 15:43 | comment | added | passerby51 | @Noah Stein: Thanks again, pointing to that keyword was very helpful indeed. | |
| Feb 22, 2014 at 15:43 | comment | added | Michael Grant | 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. | |
| Feb 21, 2014 at 0:45 | comment | added | Noah Stein | @passerby51: You're welcome. I voted to reopen this question, but I'm not sure whether others will join. In any case, I'd bet that you can derive some partial results to your question from the partial results available by googling for "doubly nonnegative extreme ray" and probably not much else can be said at present. | |
| Feb 21, 2014 at 0:00 | comment | added | passerby51 | @Noah Stein: Thanks for pointing to "doubly nonnegative cone", I didn't know that it has a name! I also doubt that the question has a simple answer. The only case that it seems obvious to me is the $n=2$ case, where I can visualize how it looks. | |
| Feb 20, 2014 at 20:51 | comment | added | Noah Stein | ... 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. | |
| Feb 20, 2014 at 20:50 | comment | added | Noah Stein | 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$... | |
| Feb 20, 2014 at 20:21 | review | Reopen votes | |||
| Feb 24, 2014 at 15:36 | |||||
| Feb 20, 2014 at 17:49 | history | closed |
Anthony Quas Stefan Waldmann Daniel Moskovich Chris Godsil Andrey Rekalo |
Not suitable for this site | |
| Feb 20, 2014 at 15:21 | comment | added | passerby51 | That is interesting, because it seems to be a homework I have assigned to myself. Good to know that it feels like a homework problem to you. My specific question is that is there anything besides binary matrices an extreme point? | |
| Feb 20, 2014 at 14:22 | review | Close votes | |||
| Feb 20, 2014 at 17:49 | |||||
| Feb 20, 2014 at 14:05 | comment | added | Anthony Quas | This site is not for homework. | |
| Feb 20, 2014 at 12:23 | history | asked | passerby51 | CC BY-SA 3.0 |