# Relationship between extreme points and optimal solutions of SDPs

Consider this to be our SDP problem:

Minimize $$\langle C, X \rangle$$ such that

1. $$\langle A_i, X \rangle \ge b_i$$ for all $$i \in [m]$$ and
2. $$X \succcurlyeq 0$$.

For SDPs, is there a relationship between the extreme points of the feasible region and the optimal solutions? In particular, does at least one optimal solution lie at an extreme point? (I know this is true for LPs, but does it extend to SDPs?)

For reference, I am asking because I am looking at two proofs (1 and 2) of a theorem by Barvinok and Pataki, and they formulate their statements of the theorem in different ways. In particular, the difference makes me suspect there is some relationship between extreme points and optima.

Edit: By extreme point I mean vertex.

• What according to you is an extreme point? Is it a vertex of the feasible set or just any point on the boundary. AFAIK, extreme points are always used to refer to vertices. SDPs are capable of modeling convex quadratic programs. The optimal solution of a convex quadratic problem can occur in the relative interior of a convex set. Commented Jul 19, 2020 at 2:16
• @batwing But aren't SDPs just used for relaxations of quadratic programs? I.e., not to solve the original quadratic program itself exactly? (I could very well be wrong; I am saying this based on Chapter 6 of this book where they show how to relax a generic quadratic program using SDP.) Per my answer below, SDPs themselves I think exhibit the traits necessary for us to say that at least one optimal solution occurs at an extreme point. Also, by extreme point, you are correct that I mean vertex! (I added this to the question too.) Commented Jul 19, 2020 at 2:27
• SDPs are a very powerful tool capable of modeling Linear programs, quadratic programs, and second order cone programs. Googling about convex programming hierarchy will help you. SDPs have also been used to provide relaxations for nonconvex programs. The examples in the chapter you cite are nonconvex programs. Commented Jul 19, 2020 at 2:40
• @batwing Thanks! I will take a look. Commented Jul 19, 2020 at 3:00