半正定規劃

半正定規劃，且其定義在半正定矩陣構成的與仿射空間的交集上，即。在最佳化理論中，半正定規劃是一個相對較年輕的領域，並且基於各種原因，學界不斷的增加對它的興趣：許多作業研究和組合最佳化的問題都能建模成半正定規劃問題，或以半正定規劃的方式得到近似解；在自動控制理論中，半正定規劃用於處理線性矩陣不等式。此外，半正定規劃是的特例，因此實際上可以內點法快速解掉。所有線性規劃問題都可以表示成半正定規劃，此外，多項式最佳化問題的解也可以透由半正定規劃逼近。半正定規劃經常用於處理複雜系統的最佳化，而近年來，量子查詢複雜性理論的問題也經常被建模成半正定規劃。動機與定義.初始動機.一個線性規劃問題是要求在一個多面體上最大或最小化一個實數值線性函式；在半正定規劃問題中，則是將線性規劃的實變數改成向量內積。以數學的語言來說，一般的半正定規劃問題可以被表示成以下型式：formula_1其中 formula_2、formula_3 和 formula_4 是實數，formula_5 是 formula_6 和 formula_7 的內積，subject to 後面是需滿足的限制式。等價描述.從上節中看不出半正定這個名稱從何而來，事實上，從下面的等價描述會發現，半正定這個詞來自於將線性規劃中的實變數的非負限制式改為矩陣變數的半正定限制式。定義一個 formula_8 矩陣 formula_9 是半正定的，若其為一些向量的格拉姆矩陣，換言之，存在向量 formula_10 使得對所有 formula_11、formula_12 都有 formula_13。若上述發生，則記做 formula_14。此外，半正定矩陣還有許多常見的等價定義，例如，一個半正定矩陣是對稱的，並且所有特徵值都是非負的。將 formula_15 設為收集所有對稱矩陣所形成的空間，並且在空間上賦予內積formula_16其中 formula_17 代表矩陣的跡。因此上節的半正定規劃可以改寫成formula_18注意到原本的性質不保證 formula_19 和 formula_20 是對稱的，因此必需它們對稱化：將 formula_19 的第 formula_22 項修正成 formula_23，將 formula_20 的第 formula_22 項修正成 formula_26。如此一來，上述的內積就會是良好定義的。如果適度的新增，半正定規劃可以被寫成formula_27此外如果得出上述形式的最佳解 formula_28，將其還原成原本名命題的最佳解 formula_29 只需耗費至多 formula_30 的時間。有眾多演演算法可以辦到以上過程，例如科列斯基分解是其中一個較為常見的。其他變形.有時為了方便，會不妨稍微修改半正定規劃的形式。舉例來說，如果想要在 formula_31 後面加 formula_32 幾項非負變數，只要將 formula_33 擴充成 formula_34 矩陣，並且新增額外條件 formula_35 對所有 formula_36。對偶理論.定義.與線性規劃相似的，一個形式如formula_37的半正定規劃問題被稱為原問題；不過對偶問題的形式就與原問題不大相同，寫作formula_38其中兩個矩陣 formula_39、formula_40 被寫成 formula_41 的意思是 formula_42。弱對偶性.半正定規劃的弱對偶定理是說，對偶問題的最大值必然小於等於原問題的最小值，因此，任何對偶問題的可行解都是原問題的一個下界，反之，任何原問題的可行解也都是對偶問題的一個上界。具體的原因是如果 formula_33 和 formula_44 分別是原問題和對偶問題的其中一個可行解，則有formula_45其中最後一個不等式成立的原因是兩個半正定矩陣的內積是非負的。原問題和對偶問題的值的差距常被稱為對偶間隙。強對偶性.與線性規劃不同的是，不是所有的半正定規劃問題都有強對偶性，有時候對偶問題的值會嚴格小於原問題的值。不過，強對偶定理敘述說，如果半正定規劃滿足，則原問題和對偶問題的值會相同，換言之，沒有對偶間隙。更確切的說明如下(一) 若原問題有下界，並且有嚴格可行解，也就是存在正定的對稱矩陣 formula_46 使得 formula_47 對所有 formula_48，則原問題存在最佳解 formula_28、對偶問題存在最佳解 formula_50，且formula_51(二) 若對偶問題有上界，並且有嚴格可行解，也就是存在 formula_52 使得 formula_53，則原問題存在最佳解 formula_28、對偶問題存在最佳解 formula_50，且formula_51例子.例一.考慮三個隨機變數 formula_57, formula_58 和 formula_19，那麼根據定義，它們兩兩之間的相關係數 formula_60 的所有可能性恰好就是所有滿足formula_61的 formula_62，formula_63、formula_64，而式子的左手邊稱作相關矩陣。假設根據實驗或其他經驗法則得知 formula_65 及 formula_66，想得知 formula_67 的可能極大極小值則只需將 formula_62，formula_63、formula_64 分別設為變數 formula_71、formula_72、formula_73，並解下面的半正定規劃原問題formula_74透過求解半正定規劃問題可以得出 formula_75 的最大最小值分別約等於 0.872 與 -0.978。例二.假設當 formula_76 時，恆有 formula_77。考慮下述問題formula_78引入一個任意實變數 formula_79，並將問題化成formula_80在這個形式中，目標函式已是 formula_81 和 formula_79 的線性函式，因此僅剩下限制式待處理。第一條限制式等價於formula_83其中 formula_84 代表對角線是 formula_85 的對角矩陣。而第二條限制式則等價於formula_86若將 formula_87 定義為formula_88那麼第二條限制式又等價於formula_89總的來說，原先的問題可以被化約成formula_90經過仔細觀察可以發現，上述形式已是一個半正定規劃的對偶問題了。例三 (格曼–威廉森最大割逼近演演算法).半正定規劃是解 NP困難的最佳化問題重要的工具，而格曼–威廉森最大割逼近演演算法是第一個基於半正定規劃的逼近演演算法 (JACM, 1995)。邁克爾·格曼和戴維·保羅·威廉森的研究聚焦在最大割問題：給定一個圖 formula_91，目標是將頂點集 formula_92 分割成兩個互斥部分，使得橫跨兩部分的邊的個數達到最大值。該問題可以被表示成以下的整數二次規劃問題：formula_93由於二次規劃問題是NP困難的，除非證明 P = NP，否則上述整數二次規劃的最佳值是不可能在多項式時間內被解出的。然而格曼和威廉森經由嘗試得出處理這類問題的三步驟方針：對於最大割問題，最自然的辦法是放鬆成以下形式formula_95注意到此時的變數 formula_96 已從整數變成向量了。因為目標函式及所有線制式都已是向量變數的內積的線性組合，因此此時問題已變成一個半正定規劃，而最佳解是一組 formula_97 中的向量。由於這些向量不見得共線性，放鬆後的半正定規劃問題的佳最值必定大於等於原本的整數二次規劃問題。格曼和威廉森於此需要採取一個方法將這些向量分成兩類：隨機生成一個透過原點的超平面，超平面的兩側自然的就將向量分成兩類，其中一類在原問題中代表 1，而另一類則代表 -1。可以證明，透過此方式所得到的近似值的其望值至少是真實數值的 0.87856 倍；換言之，當隨機取用超平面足夠多次，就可以得到至少是真實數值的 0.87856 - ε 倍的近似值。0.87856 這個數字來自於，兩向量 formula_98、formula_99 會被切在不同的半平面的機率是 formula_100，而此機率與 formula_101 的比值的最大值就是 0.87856。此外，如果是正確的，則也不會有比 0.87856 更佳的方案了。演演算法.目前已有許多針對半正規劃的演演算法，而這些演演算法都是可以規劃問題的最佳值帶一個誤差項 ε，計算都花費問題資訊尺寸與 formula_102 的多項式時間。此外有許多對於半正定規劃問題的表面預處理演演算法，這些演演算法往往都是檢查限制式之間的關係，例如消去多餘的行或列，或是移除代入最佳解存在時等號不會成立的鬆弛限制式。如此一來可能可以大大降低問題的資料量。內點法.內點法是解線性半正定規劃對偶問題的一個相對穩健的方法，許多程式碼都是根據內點法設計的，如 CSDP、MOSEK、SeDuMi、SDPT3、DSDP 及 SDPA。然而，內點法的缺點是會用到二階法，而且經常會需要儲存和分解矩陣，而且該矩陣往往是稠密而非稀疏的。一階法.與內點法不同的，運用的一階法可以避免儲存及分解巨大的黑塞矩陣，然而付出的代價是，要求相同的精確度之下，需要面對更大的尺寸的問題資料。一階法於分裂錐解算器(SCS) 及交替方向乘子法(ADMM) 中有所應用，其中後者在施行時會將每一步伐走到的新資料投影回半正定矩陣錐。譜叢分析法.程式錐叢 (ConicBundle) 將半正定規劃問題轉換成非光滑最佳化問題，並且使用譜叢分析法處理此非光滑問題。這個方法處理特殊種類的半正定規劃問題格外的有效率。其他處理方法.演演算法 PENSDP 建立在增廣拉格朗日懲罰函式法的基礎之上，而其表現大致上與內點法相去不遠，但是對於某些極大值尺度的問題上處理得非常快速。其他演演算法諸如 SDPLR 則運用半正定規劃的低秩資訊及將該規劃重構成一個非線性規劃問題。近似解法.有時只需要一定程度的解的精確度，但是希望可以有計算的複雜度最低值，因此許許多多的近似解法就此應運而生。其中一個重要的方法是應用在多輸入多輸出系統 (MIMO) 的半正定放鬆三角近似(TASER)，其特色在於對半正定矩陣的科列斯基分解矩陣而非半正定矩陣本身，處理類似最大割的問題往往只需 10 至 20 次疊代就可得到幾乎等於精確解的解答。應用.除了最大割問題之外，半正定規劃在幾何上被用來判斷一個圖是否為張拉整體圖，在控制理論中則應用線上性矩陣不等式的相關題材之中。