Relationship between extreme points and optimal solutions of SDPs

Question

Consider this to be our SDP problem:
Minimize $langle C, X rangle$ such that

$langle A_i, X  rangle ge b_i$ for all $i in [m]$ and
$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.

kanso37 · Answer

I now believe the answer is yes. I.e., at least one optimal solution will lie at an extreme point. See Hermann Schichl's answer here. For a minimization problem, you need a convex objective function on a convex domain. For a maximization problem, the objective function must instead be concave. Since SDPs have a linear objective function and a convex feasible region, we are good to go in either case.
The intuition behind my answer in either case is if the optimum is an interior point, you can write it as a convex combination of extreme points/vertices. Then use the appropriate version of Jensen's inequality based on whether the objective function is convex (minimization) or concave (maximization) to show that at least one of the extreme points also achieves the optimum.

Relationship between extreme points and optimal solutions of SDPs

One Answer

Add your own answers!

Ask a Question