查看“︁半正定规划”︁的源代码

'''半正定规划'''（Semidefinite programming，SDP）是[[凸优化]]问题的一个分支，它具有线性[[损失函数|目标函数]]（由用户指定的最大化或最小化函数），且其定义在[[半正定矩阵]]构成的[[凸锥]]与[[仿射空间]]的交集上，即{{le|光谱面|spectrahedron}}。

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

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

== 動機與定義 ==

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

:<math>
\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}
</math>
其中 <math>c_{i,j}</math>、<math>a_{i,j,k}</math> 和 <math> b_k </math> 是實數，<math>x^i \cdot x^j</math> 是 <math>x^i</math> 和 <math>x^j</math> 的[[內積]]，subject to 後面是需滿足的限制式。

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

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

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

:<math>
  \langle A,B\rangle_{\mathbb{S}^n} = {\rm tr}(A^T B) = \sum_{i,j=1}^n
  A_{ij}B_{ij}
</math>
其中 <math>{\rm tr}</math> 代表矩陣的[[跡]]。

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

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

如果適度的添加{{Translink|en|Slack variable|鬆弛變量}}，半正定規劃可以被寫成

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

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

== 對偶理論 ==
{{main|對偶性 (最佳化)}}
=== 定義 ===

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

:<math>
\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}
</math>

的半正定規劃問題被稱為原問題；不過對偶問題的形式就與原問題不大相同，寫作
:<math>
\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}
</math>

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

=== 弱對偶性 ===

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

:<math>
\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}
</math>

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

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

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

(一) 若原問題有下界，並且有嚴格可行解，也就是存在正定的對稱矩陣 <math>X_0</math> 使得 <math>\langle
A_i,X_0\rangle_{\mathbb{S}^n} = b_i</math> 對所有 <math>i=1,\ldots,m</math>，則原問題存在最佳解 <math>X^*</math>、對偶問題存在最佳解 <math>y^*</math>，且
:<math>\langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}</math>

(二) 若對偶問題有上界，並且有嚴格可行解，也就是存在 <math>y^0\in\R^m</math> 使得 <math>\sum_{i=1}^m y^0_i A_i
\prec C</math>，則原問題存在最佳解 <math>X^*</math>、對偶問題存在最佳解 <math>y^*</math>，且
:<math>\langle C,X^*\rangle_{\mathbb{S}^n} = \langle b,y^*\rangle_{\R^m}</math>

== 例子 ==

=== 例一 ===
考慮三個隨機變數 <math>A</math>, <math>B</math> 和 <math>C</math>，那麼根據定義，它們兩兩之間的[[相關係數]] <math>\rho_{AB}, \ \rho_{AC}, \rho_{BC} </math> 的所有可能性恰好就是所有滿足

:<math>\begin{pmatrix}
  1 & \rho_{AB} & \rho_{AC} \\
  \rho_{AB} & 1 & \rho_{BC} \\
  \rho_{AC} & \rho_{BC} & 1
\end{pmatrix} \succeq 0,</math>

的 <math>\rho_{AB} </math>，<math>\rho_{BC} </math>、<math>\rho_{AC} </math>，而式子的左手邊稱作相關矩陣。

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

:<math>
\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}
</math>

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

=== 例二 ===

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

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

引入一個任意實變數 <math>t</math>，並將問題化成

: <math>
\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}
</math>

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

第一條限制式等價於

: <math>\textbf{diag}(Ax+b)\succeq 0</math>

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

而第二條限制式則等價於

: <math>td^\top x-(c^\top x)^2\geq 0</math>

若將 <math>D</math> 定義為

: <math>D=\left[\begin{array}{cc}t&c^Tx\\c^Tx&d^Tx\end{array}\right]</math>

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

:<math>D \succeq 0</math>
總的來說，原先的問題可以被化約成

: <math>
\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}
</math>
經過仔細觀察可以發現，上述形式已是一個半正定規劃的對偶問題了。
=== 例三 (格曼–威廉森最大割逼近演算法) ===

<!-- this section is linked to from [[Randomized_rounding]], please update that link there if you change the section title here --nealeyoung May 31, 2010 -->

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

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

:<math>\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}</math>

由於二次規劃問題是[[NP困難]]的，除非證明 [[P/NP问题|P = NP]]，否則上述整數二次規劃的最佳值是不可能在多項式時間內被解出的。然而格曼和威廉森經由嘗試得出處理這類問題的三步驟方針：
# 將整數二次規劃問題先放鬆成半正定規劃問題。
# 解半正定規劃問題 (可能會與正解有些許誤差項 <math>\epsilon</math>)。
# 用半正定規劃問題的最佳解回推出一個原先整數二次規劃問題的近似解。
對於最大割問題，最自然的辦法是放鬆成以下形式
:<math>\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}</math>

注意到此時的變數 <math>v_i</math> 已從整數變成向量了。

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

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

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

此外有許多對於半正定規劃問題的表面預處理演算法，這些演算法往往都是檢查限制式之間的關係，例如消去多餘的行或列，或是移除代入最佳解存在時等號不會成立的鬆弛限制式。如此一來可能可以大大降低問題的資料量。
<ref>{{citation|last1=Zhu|first1=Yuzixuan|last2=Pataki|first2=Gábor|last3=Tran-Dinh|first3=Quoc|date=2019|title=Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs|url=http://link.springer.com/10.1007/s12532-019-00164-4|journal=Mathematical Programming Computation|language=en|volume=11|issue=3|pages=503–586|doi=10.1007/s12532-019-00164-4|issn=1867-2949|arxiv=1710.08954|s2cid=53645581}}</ref>

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

=== 一階法 ===
與內點法不同的，運用{{Translink|en|conic optimization|錐最佳化}}的一階法可以避免儲存及分解巨大的[[黑塞矩陣]]，然而付出的代價是，要求相同的精確度之下，需要面對更大的尺寸的問題資料。一階法於分裂錐解算器<ref>Brendan O'Donoghue, Eric Chu,
Neal Parikh, Stephen Boyd, "Conic Optimization via Operator Splitting and
Homogeneous Self-Dual Embedding",
Journal of Optimization Theory and Applications,
2016,
pp 1042--1068,
https://web.stanford.edu/~boyd/papers/pdf/scs.pdf {{Wayback|url=https://web.stanford.edu/~boyd/papers/pdf/scs.pdf |date=20210308015231 }}.</ref>(SCS) 及[[增广拉格朗日惩罚函数法#交替方向乘子法|交替方向乘子法]]<ref>Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.</ref>(ADMM) 中有所應用，其中後者在施行時會將每一步伐走到的新資料投影回半正定矩陣錐。

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

=== 其他處理方法 ===
演算法 PENSDP 建立在[[增廣拉格朗日懲罰函數法]]的基礎之上，而其表現大致上與內點法相去不遠，但是對於某些極大值尺度的問題上處理得非常快速。其他演算法諸如 SDPLR 則運用半正定規劃的低[[秩 (线性代数)|秩]]資訊及將該規劃重構成一個[[非線性規劃]]問題<ref>{{citation|last1=Monteiro|first1=Renato D. C.|last2=Burer|first2=Samuel|date=2003|title=A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization|journal=Mathematical Programming|language=en|volume=95|issue=2|pages=329–357|doi=10.1007/s10107-002-0352-8|issn=1436-4646|citeseerx=10.1.1.682.1520|s2cid=7691228}}</ref>。

=== 近似解法 ===
有時只需要一定程度的解的精確度，但是希望可以有計算的複雜度最低值，因此許許多多的近似解法就此應運而生。其中一個重要的方法是應用在[[多輸入多輸出系統]] (MIMO) 的半正定放鬆三角近似<ref>{{Cite journal|last=Castañeda|first=O.|last2=Goldstein|first2=T.|last3=Studer|first3=C.|date=December 2016|title=Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation|url=https://ieeexplore.ieee.org/document/7733153/|journal=IEEE Transactions on Circuits and Systems I: Regular Papers|volume=63|issue=12|pages=2334–2346|doi=10.1109/TCSI.2016.2607198|issn=1558-0806|doi-access=free|access-date=2021-05-11|archive-date=2021-05-12|archive-url=https://web.archive.org/web/20210512060244/https://ieeexplore.ieee.org/document/7733153/|dead-url=no}}</ref>(TASER)，其特色在於對半正定矩陣的[[科列斯基分解|科列斯基分解矩陣]]而非半正定矩陣本身，處理類似最大割的問題往往只需 10 至 20 次疊代就可得到幾乎等於精確解的解答。

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

== 參考資料 ==
{{reflist}}
* Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, March 1996, pp.&nbsp;49–95. [https://stanford.edu/~boyd/papers/pdf/semidef_prog.pdf pdf] {{Wayback|url=https://stanford.edu/~boyd/papers/pdf/semidef_prog.pdf |date=20210308103236 }}
* Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Report PNA-R0210, CWI, Amsterdam, April 2002. [http://www.optimization-online.org/DB_HTML/2002/12/585.html optimization-online] {{Wayback|url=http://www.optimization-online.org/DB_HTML/2002/12/585.html |date=20210224145625 }}
* 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), [http://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/sdp094_digest.pdf SDP-Introduction] {{Wayback|url=http://ocw.mit.edu/courses/sloan-school-of-management/15-094j-systems-optimization-models-and-computation-sma-5223-spring-2004/lecture-notes/sdp094_digest.pdf |date=20210303114229 }}

== 外部連結 ==
*[http://www-user.tu-chemnitz.de/~helmberg/semidef.html Links to introductions and events in the field]{{Wayback|url=http://www-user.tu-chemnitz.de/~helmberg/semidef.html |date=20191218203438 }}
*[http://www.cs.elte.hu/~lovasz/semidef.ps Lecture notes from László Lovász]{{Wayback|url=http://www.cs.elte.hu/~lovasz/semidef.ps |date=20170314173946 }} on Semidefinite Programming

[[Category:凸优化]]
[[Category:線性規劃]]