Feasible space of SDP - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T09:46:58Z http://mathoverflow.net/feeds/question/66539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66539/feasible-space-of-sdp Feasible space of SDP Pawan Aurora 2011-05-31T12:23:03Z 2011-05-31T17:54:25Z <p>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?</p> http://mathoverflow.net/questions/66539/feasible-space-of-sdp/66577#66577 Answer by Ralph Furmaniak for Feasible space of SDP Ralph Furmaniak 2011-05-31T17:54:25Z 2011-05-31T17:54:25Z <p>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.</p> <p>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)</p>