Operations Research Asked on August 19, 2021
Consider this to be our SDP problem:
Minimize $langle C, X rangle$ such that
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.
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
1 Asked on January 5, 2022
1 Asked on January 1, 2022 by ehsank
1 Asked on January 1, 2022
1 Asked on December 20, 2021 by cesar-canassa
1 Asked on December 18, 2021 by neverletgo
2 Asked on December 9, 2021 by farouk-hammami
3 Asked on November 24, 2021
1 Asked on November 17, 2021
15 Asked on August 19, 2021
3 Asked on August 19, 2021
4 Asked on August 19, 2021 by marco-lbbecke
2 Asked on August 19, 2021 by matheus-digenes-andrade
2 Asked on August 19, 2021
2 Asked on August 19, 2021 by user3831
3 Asked on August 19, 2021 by josh-allen
2 Asked on August 19, 2021 by ehsan
1 Asked on August 19, 2021
Get help from others!