Typically the non-empty feasible space of a SDP has some curved boundary which is why the feasible space has infinitely many extreme points. Is it ever possible to have a SDP whose non-empty feasible region is the convex hull of a finite (exponential) number of rank-$1$ matrices? If yes, how do we characterize such a SDP? What can we say about the affine hull of these extreme points? Is it somehow related to the affine space defined by the set of equality linear constraints?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I would suggest first thinking about the corresponding questions for linear programs (LPs), which are after all a subclass of semidefinite programs (SDPs). Is there any reason to expect a "nice" characterization? Is there a simple answer to the affine hull question there? $\endgroup$– Noah SteinCommented May 31, 2011 at 14:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
In this case isn't the convex hull simply a simplex? In this case you are looking for SDPs that just reduce to linear programs.
As an aside, curved boundaries are in a way most natural for SDPs: for example it is known that any convex algebraic region whose boundary is everywhere either strictly convex or positively curved is SD representible (see Semidefinite Representation of Convex Sets by Helton and Nie) (nb: the dimension of this representation is astronomical)
