MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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? – Noah Stein May 31 '11 at 14:53
up vote 3 down vote accepted

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)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.