UA MATH567 高維統(tǒng)計II 隨機向量6 亞高斯隨機向量的應(yīng)用: 半正定規(guī)劃

半正定規(guī)劃(semidefinite programming, SDP)是凸優(yōu)化的一個分支：

$$\begin{gathered} \underset{X}{\max }?A,X? \\ s.t.X\ge 0,?B_i,X?=b_i,i=1,?,m \end{gathered}$$

其中$X\ge 0$表示$X$半正定，
$$?A,X?=tr(A^{T}X)=\sum _{i,j=1}^n{A}_{ij}{X}_{ij}$$

顯然目標函數(shù)是線性函數(shù)、可行域是凸集（所有的半正定矩陣形成的集合是凸集）與凸多面體（$?B_i,X?=b_i,i=1,?,m$）的交集，所以可行域也是凸集，因此這是一個凸優(yōu)化。盡管這是一個凸優(yōu)化，但它的求解難度也是非常大的，因為決策變量個數(shù)是隨著$X$的維數(shù)平方增長的，比如$X$是$100\times 100$的矩陣，決策變量就有一萬個，所以半正定規(guī)劃很容易變成高維問題。

---

現(xiàn)在我們想用SDP來解決一個整數(shù)規(guī)劃(integer programming)的問題，記這個問題為(IP)：

$$\begin{gathered} \underset{x}{\max }{x}^{T}Ax \\ x=(x_1,?,x_n),x_i=\pm 1,A^T=A \end{gathered}$$

解決這個問題最粗暴的思路是遍歷所有可能的$x$的取值，一共有$2^n$種，顯然這是一個NP算法，于是我們需要設(shè)計一些更優(yōu)的算法來降低復(fù)雜度。

一種可行的方法是做semidefinite relaxation，考慮
$$\underset{{\Vert X_i\Vert }_2=1,i=1,?,n}{\max }\sum _{i,j=1}^n{A}_{ij}?X_i,X_j?$$

這個問題可以看成是(IP)的一種松弛，接下來我們把這個relaxation改寫為SDP，定義$X=[X_{ij}],X_{ij}=?X_i,X_j?$，于是relaxation等價于(SDP)
$$\begin{gathered} \underset{X\ge 0}{\max }?A,X? \\ s.t.X_{ii}=1=?B_i,X? \end{gathered}$$

其中$B_i$是selection matrix，只有第$i$行第$i$列的元素為1，其他元素為0，作用是選擇某矩陣第$i$行第$i$列的元素。記$INT(A)$為整數(shù)規(guī)劃的解，記$SDP(A)$為它的semidefinite relaxation的解，根據(jù)relaxation的性質(zhì)

$$INT(A)\le SDP(A)$$

定理 $INT(A)\le SDP(A)\le 2K\times INT(A),K\le 1.783$

下界是自然成立的，但上界的證明極其復(fù)雜。為了證明這個定理，我們需要Grothendieck不等式，這里先敘述一下，下一篇給出Grothendieck不等式的證明。

Grothendieck不等式
$A$是$m\times n$的實矩陣，$x_i,y_j\in \{?1,1\}$，假設(shè)$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 1$，則$?H$(Hilbert space)，$?u_i,v_j\in H$，$\Vert u_i\Vert =\Vert v_j\Vert =1$，
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le K,K\le 1.783$$

推論 假設(shè)$A$是對稱矩陣，$x_i\in \{?1,1\}$，假設(shè)$|{\sum }_{i,j}{A}_{ij}{x}_i{x}_j|\le 1$，則$?H$(Hilbert space)，$?u_i,v_j\in H$，$\Vert u_i\Vert =\Vert v_j\Vert =1$，
$$|\sum _{i,j}{A}_{i,j}?u_i,v_j?|\le 2K,K\le 1.783$$

說明
從Grothendieck不等式到它的推論，我們只需要說明$|{\sum }_{i,j}{A}_{ij}{x}_i{x}_j|\le 1$可以推出$|{\sum }_{i,j}{A}_{ij}{x}_i{y}_j|\le 2$，然后根據(jù)Grothendieck不等式就可以得到推論了。

根據(jù)這個推論，我們可以直接得到上面的定理：
$$SDP(A)\le 2K\times INT(A),K\le 1.783$$

總結(jié)

以上是生活随笔為你收集整理的UA MATH567 高维统计II 随机向量6 亚高斯随机向量的应用: 半正定规划的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。