$ \ langle C,X \ rangle $ 最小化,使

  1. $ \ langle A_i,X \ rangle \ ge b_i $ 對於所有 $ i \ in [m] $
  2. $ X \ succcurlyeq 0 $

對於SDP,可行區域的極點與最優解之間是否存在關係? 特別是,至少有一個最優解位於一個極點上嗎?點?(我知道這對於LP來說是正確的,但它是否適用於SDP?)




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.