# 半正定规划

## 動機與定義

### 初始動機

${\displaystyle {\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}}}$

### 等價描述

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

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

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

## 對偶理論

### 定義

${\displaystyle {\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}}}$

${\displaystyle {\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}}}$

### 弱對偶性

{\displaystyle {\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}}}

### 強對偶性

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

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

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

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

## 例子

### 例一

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

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

${\displaystyle {\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}}}$

### 例二

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

${\displaystyle {\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}}}$

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

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

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

${\displaystyle D\succeq 0}$

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

${\displaystyle {\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}}}$

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

## 參考資料

1. ^ Zhu, Yuzixuan; Pataki, Gábor; Tran-Dinh, Quoc, Sieve-SDP: a simple facial reduction algorithm to preprocess semidefinite programs, Mathematical Programming Computation, 2019, 11 (3): 503–586, ISSN 1867-2949, S2CID 53645581, , doi:10.1007/s12532-019-00164-4 （英语）
2. ^ 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页面存档备份，存于互联网档案馆）.
3. ^ Wen, Zaiwen, Donald Goldfarb, and Wotao Yin. "Alternating direction augmented Lagrangian methods for semidefinite programming." Mathematical Programming Computation 2.3-4 (2010): 203-230.
4. ^ Monteiro, Renato D. C.; Burer, Samuel, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, 2003, 95 (2): 329–357, , ISSN 1436-4646, S2CID 7691228, doi:10.1007/s10107-002-0352-8 （英语）
5. ^ Castañeda, O.; Goldstein, T.; Studer, C. Data Detection in Large Multi-Antenna Wireless Systems via Approximate Semidefinite Relaxation. IEEE Transactions on Circuits and Systems I: Regular Papers. December 2016, 63 (12): 2334–2346 [2021-05-11]. ISSN 1558-0806. . （原始内容存档于2021-05-12）.
• 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页面存档备份，存于互联网档案馆