SDP的極點與最優解之間的關係


2

將其視為我們的SDP問題:

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

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

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

我想問一下,是因為我正在看巴維諾克和帕塔基的一個定理的兩個證明(12),他們用不同的方式陳述了該定理。特別是,這種差異使我懷疑極端值和最佳值之間存在某種關係。

編輯:極端的意思是頂點。

1

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.