凸優化筆記(4)Semi-Definite Programming簡介

05-18

來自專欄凸優化與非線性優化

本文主要參考卡耐基梅隆大學(CMU)的Ryan Tibshirani教授在Convex Optimization(Course 10-725/36-725)課上(課程網站鏈接：Convex Optimization)的Lecture Notes。以及參考了現任職牛津大學的Dr. Paul Goulart，以前在ETH任教時Convex Optimization課的Lecture Notes。如有錯誤疏漏，煩請指出。如需付費轉載，請聯繫筆者，zhu.hathaway@gmail.com。

我們在凸優化筆記(2)幾類標準問題以及Linear Programming簡介中講到：

凸優化的標準問題有四類：

1. Linear Programming(LP)
2. Quadratic Programming(QP)
3. Semi-Definite Programming(SDP)
4. Cone Programming(CP)

今天我們繼續第三類問題——Semidefinite Programming(SDP)，它的形式如下：

$min_{xin D}{kern 25pt}c^Tx\ old{subject{kern 3pt} to:} {kern 3pt} x_1F_1+x_2F_2+cdots+x_nF_nle F_0\ {kern 53pt} Ax= b$

其中 $x=(x_1,x_2,cdots,x_n)^Tinmathbb{R}^n$ ， $F_iin mathbb{R}^{d imes d}$ 是對稱矩陣， $Ain mathbb{R}^{m imes n}$ 。以上形式可以換寫成SDP的standard form：

$min_{Xin D}{kern 25pt}Cullet X\ old{subject{kern 3pt} to:} {kern 3pt} A_iullet X= b_i,i=1,2,cdots,n\ {kern 53pt} Xsucceq 0$

其中 $Cullet X=sum_{j=1}^{n}sum_{i=1}^{n}{c_{ij}x_{ij}}$ (Frobenius inner product)， $C,{kern 3pt}Xin mathbb{R}^{n imes n}$ 都是對稱矩陣， $b_iin mathbb{R}$ 。

這是大家可能會有疑惑，以上兩式怎麼等價的？

首先在SDP的standard form中，要尋找對稱矩陣X，本質上其實還是尋找矩陣X里的 $n^2$ 個元素 $x_{ij}$ ，由於X是對稱的，所以其實是尋找X裡面上三角的 $frac{n(n+1)}{2}$ 個元素。而 $Cullet X=sum_{j=1}^{n}sum_{i=1}^{n}{c_{ij}x_{ij}}$ 就是這 $frac{n(n+1)}{2}$ 個元素 $x_{ij}$ 的線性方程，所以目標函數是convex的，standard form跟第一個SDP的formulation是等價的。那可行域也是convex的嗎？首先同理 $Cullet X$ 的展開， $A_iullet X= b_i$ 是 $x_{ij}$ 的affine函數。 $Xsucceq 0$ 代表的區域也是convex的。舉個例子，我們不妨看看 $X=left( {egin{array}{*{20}{c}} x_{11}&x_{12}\ x_{12}&x_{22}\ end{array}} ight)$ 為2x2對稱矩陣時 $Xsucceq 0$ 所代表的區域，也就是 $x_{11}geq 0, x_{22}geq 0, x_{11}x_{22}-x_{12}^2geq 0$ 的區域，如下圖中曲面所包裹整個內部區域（圖中 $x_{11}$ 是x軸， $x_{12}$ 為y軸， $x_{22}$ 為z軸）：

我們可以看到，上圖的區域是convex的。

我們在凸優化筆記(2)幾類標準問題以及Linear Programming簡介提到：

LP是QP的一種特殊情況，QP又是SDP的一種特殊情況

SDP又是跟LP和QP怎麼聯繫的？LP問題是SDP的特殊情況，相當於以上SDP的standard form中的C矩陣為不僅僅是對稱的，還是對角的。X同樣，即： $C=left( {egin{array}{*{20}{c}} c_1&0&cdots&0\ 0&c_2&cdots&0\:&:&cdots&:\0&0&cdots&c_n end{array}} ight),X=left( {egin{array}{*{20}{c}} x_1&0&cdots&0\ 0&x_2&cdots&0\:&:&cdots&:\0&0&cdots&x_n end{array}} ight)$

QP又為什麼會是SDP問題？我們可以引入一個新的variable，把凸優化筆記(3)Quadratic Programming簡介與SVM中的QP的standard form寫成：

$min_{x, heta}{kern 25pt} heta\ old{subject{kern 3pt} to:} {kern 3pt} c^Tx+frac{1}{2}x^TQxle heta\{kern 53pt}Ax= b\ {kern 53pt} xge 0$

進一步，Q可以分解成 $Q=M^TM$ (Cholesky factorization)，於是 $c^Tx+frac{1}{2}x^TQxle heta$ 就等價於 $left( {egin{array}{*{20}{c}} I&Mx\ (Mx)^T&-c^Tx+ heta\ end{array}} ight)succeq 0$ (Schur補引理)。所以QP是SDP的特殊情況。控制理論求解的Linear matrix inequality(LMI)就是SDP問題。用類似的方法可以推出QCQP(Quadratic Constrained Quadratic Programming)與SOCP(Second Order Conic Programing)是SDP的一種特殊情況，這裡暫時不細講( $LPsubseteq convex{kern 3pt}QP subseteq convex{kern 3pt}QCQP subseteq SOCP subseteq SDP$ )。

為什麼要研究SDP問題呢？

SDP覆蓋的問題比LP和QP更為廣泛，但依然是一個凸優化問題
面對非凸的問題，可以利用SDP更方便地做relaxation