本文主要參考卡耐基梅隆大學（CMU）的Ryan Tibshirani教授在Convex Optimization（Course 10-725/36-725）課上（課程網站連結：Convex Optimization）的Lecture Notes。以及參考了現任職牛津大學的Dr。 Paul Goulart，以前在ETH任教時Convex Optimization課的Lecture Notes。如有錯誤疏漏，煩請指出。

如需付費轉載，請聯絡筆者

。

我們在凸最佳化筆記（2）幾類標準問題以及Linear Programming簡介中講到：

凸最佳化的標準問題有四類：

1。 Linear Programming（LP）

2。 Quadratic Programming（QP）

3。 Semi-Definite Programming（SDP）

4。 Cone Programming（CP）

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

\min_{x\in D}{\kern 25pt}c^Tx\\ \bold{subject{\kern 3pt} to:} {\kern 3pt} x_1F_1+x_2F_2+\cdots+x_nF_n\le F_0\\ {\kern 53pt} Ax= b

其中

x=(x_1,x_2,\cdots,x_n)^T\in\mathbb{R}^n

，

F_i\in \mathbb{R}^{d\times d}

是對稱矩陣，

A\in \mathbb{R}^{m\times n}

。以上形式可以換寫成

SDP的standard form

：

\min_{X\in D}{\kern 25pt}C\bullet X\\ \bold{subject{\kern 3pt} to:} {\kern 3pt} A_i\bullet X= b_i,i=1,2,\cdots,n\\ {\kern 53pt} X\succeq 0

其中

C\bullet X=\sum_{j=1}^{n}\sum_{i=1}^{n}{c_{ij}x_{ij}}

（Frobenius inner product），

C,{\kern 3pt}X\in \mathbb{R}^{n\times n}

是對稱矩陣，

b_i\in \mathbb{R}

。

這時大家可能會有疑惑，以上兩個form怎麼等價的？

首先在SDP的standard form中，要尋找本最佳化問題的decision variable即對稱矩陣

X

，本質上其實還是尋找矩陣

X

裡的

n^2

個元素

x_{ij}

，由於

X

是對稱的，所以其實是尋找X裡面上三角的

\frac{n(n+1)}{2}

個元素。而

C\bullet 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的嗎？首先同理

C\bullet X

的展開，

A_i\bullet X= b_i

是

x_{ij}

的affine函式。而且，

X\succeq 0

代表的區域也是convex的，為什麼？舉個例子，我們不妨看看

X=\left( {\begin{array}{*{20}{c}} x_{11}&x_{12}\\ x_{12}&x_{22}\\ \end{array}} \right)

為2x2對稱矩陣時

X\succeq 0

所代表的區域，也就是

x_{11}\geq 0, x_{22}\geq 0, x_{11}x_{22}-x_{12}^2\geq 0

的區域，如下圖中曲面所包裹整個內部區域（圖中

x_{11}

是

x

軸，

x_{12}

為

y

軸，

x_{22}

為

z

軸），即

y^2<xz

區域：

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

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

SDP跟LP和QP之間的關係

我們在凸最佳化筆記（2）幾類標準問題以及Linear Programming簡介提到：

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

SDP又是跟LP和QP怎麼聯絡的？LP問題是SDP的特殊情況，相當於以上SDP的standard form中的C矩陣為不僅僅是對稱的，還是對角的。矩陣

X

同樣，即：

C=\left( {\begin{array}{*{20}{c}} c_1&0&\cdots&0\\ 0&c_2&\cdots&0\\:&:&\cdots&:\\0&0&\cdots&c_n \end{array}} \right),X=\left( {\begin{array}{*{20}{c}} x_1&0&\cdots&0\\ 0&x_2&\cdots&0\\:&:&\cdots&:\\0&0&\cdots&x_n \end{array}} \right)\\

QP又為什麼會是SDP問題？我們可以引入一個新的variable

--\theta

，把凸最佳化筆記（3）Quadratic Programming簡介與SVM中的QP的standard form寫成：

\min_{x,\theta}{\kern 25pt}\theta\\ \bold{subject{\kern 3pt} to:} {\kern 3pt} c^Tx+\frac{1}{2}x^TQx\le \theta\\{\kern 53pt}Ax= b\\ {\kern 53pt} x\ge 0

進一步，Q可以分解成

Q=M^TM

（Cholesky factorization），於是

c^Tx+\frac{1}{2}x^TQx\le \theta

就等價於

\left( {\begin{array}{*{20}{c}} I&Mx\\ (Mx)^T&-c^Tx+\theta\\ \end{array}} \right)\succeq 0

（Schur補引理）。所以QP是SDP的特殊情況。控制理論求解的Linear matrix inequality（LMI）就是SDP問題。用類似的方法可以推出QCQP（Quadratic Constrained Quadratic Programming）與SOCP（Second Order Conic Programing）是SDP的一種特殊情況，這裡暫時不細講（

LP\subseteq convex{\kern 3pt}QP \subseteq convex{\kern 3pt}QCQP \subseteq SOCP \subseteq SDP

）。

為什麼要研究SDP問題呢？

SDP覆蓋的問題比LP和QP更為廣泛，但依然是一個凸最佳化問題

面對非凸的問題，可以利用SDP更方便地做relaxation