半正定規劃

半正定規劃（Semidefinite programming，SDP）是凸優化問題的一個分支，它具有線性目標函數（由用戶指定的最大化或最小化函數），且其定義在半正定矩陣構成的凸錐與仿射空間的交集上，即光譜面。

在最佳化理論中，半正定規劃是一個相對較年輕的領域，並且基於各種原因，學界不斷的增加對它的興趣：許多作業研究和組合最佳化的問題都能建模成半正定規劃問題，或以半正定規劃的方式得到近似解；在自動控制理論中，半正定規劃用於處理線性矩陣不等式。此外，半正定規劃是錐規劃的特例，因此實際上可以內點法快速解掉。所有線性規劃問題都可以表示成半正定規劃，此外，多項式最佳化問題的解也可以透由半正定規劃逼近。

半正定規劃經常用於處理複雜系統的最佳化，而近年來，量子查詢複雜性理論的問題也經常被建模成半正定規劃。

動機與定義

初始動機

一個線性規劃問題是要求在一個多面體上最大或最小化一個實數值線性函數；在半正定規劃問題中，則是將線性規劃的實變數改成向量內積。以數學的語言來說，一般的半正定規劃問題可以被表示成以下型式：

${\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n}}}&{\displaystyle \sum _{i,j=1}^{n}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{subject to}}&{\displaystyle \sum _{i,j=1}^{n}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}},\quad k=1,\ldots ,m\\\end{array}}$

其中 $c_{i,j}$、$a_{i,j,k}$ 和 $b_{k}$ 是實數，$x^{i}\cdot x^{j}$ 是 $x^{i}$ 和 $x^{j}$ 的內積，subject to 後面是需滿足的限制式。

等價描述

從上節中看不出半正定這個名稱從何而來，事實上，從下面的等價描述會發現，半正定這個詞來自於將線性規劃中的實變數的非負限制式改為矩陣變數的半正定限制式。

定義一個 $n\times n$ 矩陣 $M$ 是半正定的，若其為一些向量的格拉姆矩陣，換言之，存在向量 $x^{1},\ldots ,x^{n}$ 使得對所有 $i$、$j$ 都有 $m_{i,j}=x^{i}\cdot x^{j}$。若上述發生，則記做 $M\succeq 0$。此外，半正定矩陣還有許多常見的等價定義，例如，一個半正定矩陣是對稱的，並且所有特徵值都是非負的。

將 $\mathbb {S} ^{n}$ 設為收集所有對稱矩陣所形成的空間，並且在空間上賦予內積

$\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i,j=1}^{n}A_{ij}B_{ij}$

其中 ${\rm {tr}}$ 代表矩陣的跡。

因此上節的半正定規劃可以改寫成

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

注意到原本的性質不保證 $C$ 和 $A_{k}$ 是對稱的，因此必需它們對稱化：將 $C$ 的第 $i,j$ 項修正成 ${\frac {c_{i,j}+c_{j,i}}{2}}$，將 $A_{k}$ 的第 $i,j$ 項修正成 ${\frac {a_{i,j,k}+a_{j,i,k}}{2}}$。如此一來，上述的內積就會是良好定義的。

如果適度的添加鬆弛變量，半正定規劃可以被寫成

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\&X\succeq 0\end{array}}$

此外如果得出上述形式的最佳解 $X^{*}$，將其還原成原本名命題的最佳解 ${x^{1}}^{*},\ldots ,{x^{n}}^{*}$ 只需耗費至多 $O(n^{3})$ 的時間。有眾多演算法可以辦到以上過程，例如科列斯基分解是其中一個較為常見的。

其他變形

有時為了方便，會不妨稍微修改半正定規劃的形式。舉例來說，如果想要在 $\langle C,X\rangle _{\mathbb {S} ^{n}}$ 後面加 $l$ 幾項非負變數，只要將 $X$ 擴充成 $(n+l)\times (n+l)$ 矩陣，並且添加額外條件 $X_{ij}=0$ 對所有 $j\neq i>n$。

對偶理論

主條目：對偶性 (最佳化)

定義

與線性規劃相似的，一個形式如

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{subject to}}&\langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}$

的半正定規劃問題被稱為原問題；不過對偶問題的形式就與原問題不大相同，寫作

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb {R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{subject to}}&{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}$

其中兩個矩陣 $P$、$Q$ 被寫成 $P\succeq Q$ 的意思是 $P-Q\succeq 0$。

弱對偶性

半正定規劃的弱對偶定理是說，對偶問題的最大值必然小於等於原問題的最小值，因此，任何對偶問題的可行解都是原問題的一個下界，反之，任何原問題的可行解也都是對偶問題的一個上界。具體的原因是如果 $X$ 和 $y$ 分別是原問題和對偶問題的其中一個可行解，則有

${\begin{aligned}\langle C,X\rangle -\langle b,y\rangle &=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}\\&=\langle C,X\rangle -\sum _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\sum _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0\end{aligned}}$

其中最後一個不等式成立的原因是兩個半正定矩陣的內積是非負的。

原問題和對偶問題的值的差距常被稱為對偶間隙。

強對偶性

與線性規劃不同的是，不是所有的半正定規劃問題都有強對偶性，有時候對偶問題的值會嚴格小於原問題的值。不過，強對偶定理敘述說，如果半正定規劃滿足斯萊特條件，則原問題和對偶問題的值會相同，換言之，沒有對偶間隙。更確切的說明如下

(一) 若原問題有下界，並且有嚴格可行解，也就是存在正定的對稱矩陣 $X_{0}$ 使得 $\langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_{i}$ 對所有 $i=1,\ldots ,m$，則原問題存在最佳解 $X^{*}$、對偶問題存在最佳解 $y^{*}$，且

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$

(二) 若對偶問題有上界，並且有嚴格可行解，也就是存在 $y^{0}\in \mathbb {R} ^{m}$ 使得 $\sum _{i=1}^{m}y_{i}^{0}A_{i}\prec C$，則原問題存在最佳解 $X^{*}$、對偶問題存在最佳解 $y^{*}$，且

$\langle C,X^{*}\rangle _{\mathbb {S} ^{n}}=\langle b,y^{*}\rangle _{\mathbb {R} ^{m}}$

例子

例一

考慮三個隨機變數 $A$, $B$ 和 $C$，那麼根據定義，它們兩兩之間的相關係數 $\rho _{AB},\ \rho _{AC},\rho _{BC}$ 的所有可能性恰好就是所有滿足

${\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _{BC}&1\end{pmatrix}}\succeq 0,$

的 $\rho _{AB}$，$\rho _{BC}$、$\rho _{AC}$，而式子的左手邊稱作相關矩陣。

假設根據實驗或其他經驗法則得知 $-0.2\leq \rho _{AB}\leq -0.1$ 及 $0.4\leq \rho _{BC}\leq 0.5$，想得知 $\rho _{AC}\$ 的可能極大極小值則只需將 $\rho _{AB}$，$\rho _{BC}$、$\rho _{AC}$ 分別設為變數 $x_{12}$、$x_{23}$、$x_{13}$，並解下面的半正定規劃原問題

${\begin{array}{rl}{\displaystyle \min /\max }&x_{13}\\{\text{subject to}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\displaystyle {\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0}\end{array}}$

通過求解半正定規劃問題可以得出 $\rho _{AC}=x_{13}\$ 的最大最小值分別約等於 0.872 與 -0.978。

例二

假設當 $Ax+b\geq 0$ 時，恆有 $d^{\top }x>0$。考慮下述問題

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle {\frac {(c^{\top }x)^{2}}{d^{\top }x}}}\\{\text{subject to}}&{\displaystyle Ax+b\geq 0}\\\end{array}}$

引入一個任意實變數 $t$，並將問題化成

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle t}\\{\text{subject to}}&\displaystyle Ax+b\geq 0,\\&\displaystyle {\frac {(c^{\top }x)^{2}}{d^{\top }x}}\leq t\\\end{array}}$

在這個形式中，目標函數已是 $x$ 和 $t$ 的線性函數，因此僅剩下限制式待處理。

第一條限制式等價於

${\textbf {diag}}(Ax+b)\succeq 0$

其中 ${\textbf {diag}}(Ax+b)$ 代表對角線是 $Ax+b$ 的對角矩陣。

而第二條限制式則等價於

$td^{\top }x-(c^{\top }x)^{2}\geq 0$

若將 $D$ 定義為

$D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]$

那麼第二條限制式又等價於

$D\succeq 0$

總的來說，原先的問題可以被化約成

${\begin{array}{rl}{\displaystyle \min }&{\displaystyle t}\\{\text{subject to}}&\displaystyle {\displaystyle \left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{\top }x\\0&c^{\top }x&d^{\top }x\end{array}}\right]\succeq 0}\\\end{array}}$

經過仔細觀察可以發現，上述形式已是一個半正定規劃的對偶問題了。

例三 (格曼–威廉森最大割逼近演算法)

半正定規劃是解 NP困難的最佳化問題重要的工具，而格曼–威廉森最大割逼近演算法是第一個基於半正定規劃的逼近演算法 (JACM, 1995)。邁克爾·格曼和戴維·保羅·威廉森的研究聚焦在最大割問題：給定一個圖 $G=(V,E)$，目標是將頂點集 $V$ 分割成兩個互斥部分，使得橫跨兩部分的邊的個數達到最大值。

該問題可以被表示成以下的整數二次規劃問題：

${\begin{array}{rl}\displaystyle \max &\displaystyle \sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}}\\{\text{such that }}&v_{i}\in \{1,-1\}{\text{ for all }}i\end{array}}$

由於二次規劃問題是NP困難的，除非證明 P = NP，否則上述整數二次規劃的最佳值是不可能在多項式時間內被解出的。然而格曼和威廉森經由嘗試得出處理這類問題的三步驟方針：

1. 將整數二次規劃問題先放鬆成半正定規劃問題。
2. 解半正定規劃問題 (可能會與正解有些許誤差項 $\epsilon$)。
3. 用半正定規劃問題的最佳解回推出一個原先整數二次規劃問題的近似解。

對於最大割問題，最自然的辦法是放鬆成以下形式

${\begin{array}{rl}\displaystyle \max &\displaystyle \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2}}\\{\text{subject to }}&\lVert v_{i}\rVert ^{2}=1{\text{ for all }}i\end{array}}$

注意到此時的變數 $v_{i}$ 已從整數變成向量了。

因為目標函數及所有線制式都已是向量變數的內積的線性組合，因此此時問題已變成一個半正定規劃，而最佳解是一組 $\mathbb {R} ^{n}$ 中的向量。由於這些向量不見得共線性，放鬆後的半正定規劃問題的佳最值必定大於等於原本的整數二次規劃問題。格曼和威廉森於此需要採取一個方法將這些向量分成兩類：隨機生成一個通過原點的超平面，超平面的兩側自然的就將向量分成兩類，其中一類在原問題中代表 1，而另一類則代表 -1。可以證明，通過此方式所得到的近似值的其望值至少是真實數值的 0.87856 倍；換言之，當隨機取用超平面足夠多次，就可以得到至少是真實數值的 0.87856 - ε 倍的近似值。

0.87856 這個數字來自於，兩向量 $v_{i}$、$v_{j}$ 會被切在不同的半平面的機率是 ${\frac {\cos ^{-1}\langle v_{i},v_{j}\rangle }{\pi }}$，而此機率與 ${\frac {1-\langle v_{i},v_{j}\rangle }{2}}$ 的比值的最大值就是 0.87856。此外，如果獨立遊戲猜想是正確的，則也不會有比 0.87856 更佳的方案了。

演算法

目前已有許多針對半正規劃的演算法，而這些演算法都是可以規劃問題的最佳值帶一個誤差項 ε，計算都花費問題資訊尺寸與 $\log(1/\epsilon )$ 的多項式時間。

此外有許多對於半正定規劃問題的表面預處理演算法，這些演算法往往都是檢查限制式之間的關係，例如消去多餘的行或列，或是移除代入最佳解存在時等號不會成立的鬆弛限制式。如此一來可能可以大大降低問題的資料量。

內點法

內點法是解線性半正定規劃對偶問題的一個相對穩健的方法，許多程式碼都是根據內點法設計的，如 CSDP、MOSEK、SeDuMi、SDPT3、DSDP 及 SDPA。然而，內點法的缺點是會用到二階法，而且經常會需要儲存和分解矩陣，而且該矩陣往往是稠密而非稀疏的。

一階法

與內點法不同的，運用錐最佳化的一階法可以避免儲存及分解巨大的黑塞矩陣，然而付出的代價是，要求相同的精確度之下，需要面對更大的尺寸的問題資料。一階法於分裂錐解算器(SCS) 及交替方向乘子法(ADMM) 中有所應用，其中後者在施行時會將每一步伐走到的新資料投影回半正定矩陣錐。

譜叢分析法

程式錐叢 (ConicBundle) 將半正定規劃問題轉換成非光滑最佳化問題，並且使用譜叢分析法處理此非光滑問題。這個方法處理特殊種類的半正定規劃問題格外的有效率。

其他處理方法

演算法 PENSDP 建立在增廣拉格朗日懲罰函數法的基礎之上，而其表現大致上與內點法相去不遠，但是對於某些極大值尺度的問題上處理得非常快速。其他演算法諸如 SDPLR 則運用半正定規劃的低秩資訊及將該規劃重構成一個非線性規劃問題。

近似解法

有時只需要一定程度的解的精確度，但是希望可以有計算的複雜度最低值，因此許許多多的近似解法就此應運而生。其中一個重要的方法是應用在多輸入多輸出系統 (MIMO) 的半正定放鬆三角近似(TASER)，其特色在於對半正定矩陣的科列斯基分解矩陣而非半正定矩陣本身，處理類似最大割的問題往往只需 10 至 20 次疊代就可得到幾乎等於精確解的解答。

應用

除了最大割問題之外，半正定規劃在幾何上被用來判斷一個圖是否為張拉整體圖，在控制理論中則應用在線性矩陣不等式的相關題材之中。

參考資料

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp. 49–95. pdf （頁面存檔備份，存於網際網路檔案館）
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. optimization-online （頁面存檔備份，存於網際網路檔案館）
• E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, March 2002, ISBN 1-4020-0547-4.
• Robert M. Freund, "Introduction to Semidefinite Programming (SDP), SDP-Introduction （頁面存檔備份，存於網際網路檔案館）

外部連結

• Links to introductions and events in the field（頁面存檔備份，存於網際網路檔案館）
• Lecture notes from László Lovász（頁面存檔備份，存於網際網路檔案館） on Semidefinite Programming