2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – batwing Jul 19 '20 at 2:16
  • $\begingroup$ @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.) $\endgroup$ – kanso37 Jul 19 '20 at 2:27
  • 1
    $\begingroup$ 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. $\endgroup$ – batwing Jul 19 '20 at 2:40
  • $\begingroup$ @batwing Thanks! I will take a look. $\endgroup$ – kanso37 Jul 19 '20 at 3:00
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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