凸優化筆記(3)Quadratic Programming簡介

05-09

本文主要參考卡耐基梅隆大學(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)

今天我們繼續第二類問題——Quadratic Programming，它的形式如下：

$min_{xin D}{kern 25pt}c^Tx+frac{1}{2}x^TQx\ old{subject{kern 3pt} to:} {kern 3pt} Dxle d\ {kern 53pt} Ax= b$

顯然，如果矩陣 $Qgeq 0$ 就是凸優化問題；如果 $Q<0$ ，那麼就不是凸優化問題(當然了，我們可以通過一些tricks把它重新寫成凸問題，這裡先不討論)。下圖給出如果Q是positive definite與negative definite的區別：

通常我們說QP問題，就默認是指 $Qgeq 0$ 。在凸優化筆記(2)幾類標準問題以及Linear Programming簡介提過，LP是QP的一種特殊情況，所以從以上的定義，可以看出當Q=0時，就degrade為LP問題了。同樣地，如同在凸優化筆記(2)幾類標準問題以及Linear Programming簡介所說，為了方便計算機求解，通常重新寫成以下的standard form【跟筆記(2)中一樣，通過引入slack varibles，把不等式約束轉換成等式約束寫進 $Ax=b$ ， $x$ 多了一些slack varibles】：

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

下圖給出了Quadratic Programming的例子，虛線是objective function【同一條虛線上 $f(x)$ 的值是相等的，可以看出與linear programming時的不同：一個是一階的直線，一個是二階的曲線】，最優值在 $x^{star}$ ，順便思考下圖的虛線為什麼是橢圓:

舉個栗子：

機器學習演算法之SVM(Support Vector Machine)

在監督學習中，支持向量機是一種分類演算法，它就是一個QP問題。已知下圖中的紅點類和綠點類是兩個不同的類，怎麼找到一個hyperplane將兩類數據分開，並使得該hyperplane到兩邊的margin最大【The simplest way to separate two groups of data is with a straight line (1 dimension), flat plane (2 dimensions) or an N-dimensional hyperplane】，也就是找到圖中的黑線: $w^Tx+b=0$ ，使得綠色類所有的點(假設有p個)滿足 $w^Tx_{green}+bge 1$ ，紅色類所有的點(假設有q個)滿足 $w^Tx_{red}+ble -1$ （以下圖片均來自: https://blog.statsbot.co/support-vector-machines-tutorial-c1618e635e93） :

by Abhishek Ghose

圖中灰色的陰影部分就是margin，有兩個support vector(離黑線最近的兩個點)。如果要最大化兩個類的margin，就相當於： $max{kern 3pt} frac{2}{|w|}$ (因為margin= $frac{w}{|w|}cdot(x_{green}-x_{red})=frac{2}{|w|}$ )，而最大化 $frac{2}{|w|}$ 等價於最小化 $frac{1}{2}{|w|}^2$ ，於是問題就可以formulate為：

$min_{win D}{kern 25pt}frac{1}{2}{w^Tw}\ old{subject{kern 3pt} to:} {kern 3pt} w^Tx_{green}+bge 1\ {kern 56pt} -w^Tx_{red}-bge 1$

其中決策變數是 $w$ ，而 $x_{green},x_{red}$ 都是已知的點，代入不等式即可，因為綠色類有p個點，所以代入 $x_{green}$ 點的坐標就有p個不等式 $w^Tx_{green}+bge 1$ ，同理對於紅色類有q個不等式。而在實際大數據訓練集中，兩個類之間通常沒有像上圖那樣明確的界限，但是我們知道其實是依然可以分類的，如下圖：

by Abhishek Ghose

那麼這時候怎麼辦？我們只好在能把兩類分開的前提下，同時盡量減少錯誤的分類。那麼怎麼用數學表達？引入了一個額外的參數C，並將兩個 $w^Tx_{green}+bge 1， w^Tx_{red}+ble -1$ 放寬要求為: $w^Tx_{green}+bge 1-epsilon(p個不等式，所以要有p個epsilon)， -w^Tx_{red}-bge 1-varepsilon(q個不等式，所以要有q個varepsilon)$ ，重新formulate為下式：

$min_{w,epsilon,varepsilon}{kern 25pt}frac{1}{2}{w^Tw}+C(sum_{i=1}^{p}{epsilon}+sum_{i=1}^{q}{varepsilon})\ old{subject{kern 3pt} to:} {kern 3pt} w^Tx_{green}+bge 1-epsilon\ {kern 56pt} -w^Tx_{red}-bge 1-varepsilon\ {kern 56pt} epsilonge 0,varepsilonge 0$

上式中的決策變數不再單單是 $w$ ，而是( $w,epsilon,varepsilon$ )，擴維了，顯然objective function是決策變數的quadractic形式，並且不等式約束也是線性的，所以是QP問題。下圖給出了選取不同參數C的分類效果圖，C越大，灰色陰影部分的margin就越小，錯誤分類(misclassification)的概率越小。由於C不是決策變數，而是手動調節的參數，機器學習里稱這類參數是超參數(hyper-parameter)：

by Abhishek Ghose

以上分析了SVM如何工作的，與QP問題的聯繫。

接下來拓展一下SVM的關於kernel method的知識【Kernel-based learning algorithms work by embedding the data into a Hilbert space, and searching for linear relations in such a space. The embedding is performed implicitly, by specifying the inner product between each pair of points rather than by giving their coordinates explicitly. This approach has several advantages, the most important deriving from the fact that the inner product in the embedding space can often be computed much more easily than the coordinates of the points themselves】，具體請見Wikipedia。如果繼續用直線來分類如下圖的數據集，顯然是不合理的。

那麼，這時候怎麼辦？可以採用SVM一個新的kernel(數據點 $x_{green},x_{red}$ 映射到更高維的 $X$ ，第一個例子用的是linear kernel )，在更高維的空間可以找到直線對數據分類，然後映射回來到原始的 $x$ ，因為涉及到非線性，這裡就不細講了。下圖是個示意圖：

左圖是將原數據投影到三維空間，然後找到了直的分類線，再映射回到原來的空間，得到右圖中的分類曲線。SVM的kernel常用的有Linear, Polynomial,Radial Basis Function (RBF)等。