Relationship between extreme points and optimal solutions of SDPs

Operations Research Asked on August 19, 2021

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.

One 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.

Answered by kanso37 on August 19, 2021

Add your own answers!

Related Questions

Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa


How to simulate computational execution time?

2  Asked on August 19, 2021 by matheus-digenes-andrade


Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen


Error evalution for linear fits

1  Asked on August 19, 2021 by jane


Ask a Question

Get help from others!

© 2022 All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP