理解凸優化

06-03

理解凸優化

導言凸優化（convex optimization）是最優化問題中非常重要的一類，也是被研究的很透徹的一類。對於機器學習來說，如果要優化的問題被證明是凸優化問題，則說明此問題可以被比較好的解決。在本文中，SIGAI將為大家深入淺出的介紹凸優化的概念以及在機器學習中的應用。

凸優化簡介

在SIGAI之前的公眾號文章「理解梯度下降法」中我們介紹了最優化的基本概念以及梯度下降法。如果讀者對目標函數，優化變數，可行域，等式約束，不等式約束，局部極小值，全局極小值的概念還不清楚，請先閱讀那篇文章。

求解一個一般性的最優化問題的全局極小值是非常困難的，至少要面臨的問題是：函數可能有多個局部極值點，另外還有鞍點問題。對於第一個問題，我們找到了一個梯度為0的點，它是極值點，但不是全局極值，如果一個問題有多個局部極值，則我們要把所有局部極值找出來，然後比較，得到全局極值，這非常困難，而且計算成本相當高。第二個問題更嚴重，我們找到了梯度為0的點，但它連局部極值都不是，典型的是 $X^{3}$ 這個函數，在0點處，它的導數等於0，但這根本不是極值點：

梯度下降法和牛頓法等基於導數作為判據的優化演算法，找到的都導數/梯度為0的點，而梯度等於0隻是取得極值的必要條件而不是充分條件。如果我們將這個必要條件變成充分條件，即：

問題將會得到簡化。如果對問題加以限定，是可以保證上面這個條件成立的。其中的一種限制方案是：

對於目標函數，我們限定是凸函數；對於優化變數的可行域（注意，還要包括目標函數定義域的約束），我們限定它是凸集。

同時滿足這兩個限制條件的最優化問題稱為凸優化問題，這類問題有一個非常好性質，那就是局部最優解一定是全局最優解。接下來我們先介紹凸集和凸函數的概念。

凸集

對於n維空間中點的集合C，如果對集合中的任意兩點x和y，以及實數 $0leq hetaleq1$ ，都有：

則稱該集合稱為凸集。如果把這個集合畫出來，其邊界是凸的，沒有凹進去的地方。直觀來看，把該集合中的任意兩點用直線連起來，直線上的點都屬於該集合。相應的，點：

稱為點x和y的凸組合。下圖是凸集和非凸集的示意圖，左邊是一個凸集，右邊是一個非凸集：

下面是實際問題中一些常見的凸集例子，記住它們對理解後面的演算法非常有幫助：

n維實向量空間 $R^{n}$ 。顯然如果 $x，yin R_{n}$ ，則有：

這一結論的意義在於如果一個優化問題是不帶約束的優化，則其優化變數的可行域是一個凸集。

仿射子空間。給定m行n列的矩陣A和m維向量b，仿射子空間定義為如下向量的集合：

回憶一下線性代數中所學的，它就是非齊次線性方程組的解。下面我們給出證明。假設 $x，yin R^{n}$ 並且：

對於任意 $0leq hetaleq1$ ，有：

這一結論的意義在於，如果一組約束是線性等式約束，則它確定的可行域是一個凸集。

多面體。多面體定義為如下向量的集合：

它就是線性不等式圍成的區域。下面我們給出證明。對於任意的 $x，yin R^{n}$ ，並且 $AXleq b，AYleq b$ ，如果 $0leq hetaleq1$ ，則有：

這一結論的意義在於，如果一組約束是線性不等式約束，則它定義的可行域是凸集。在實際應用中，我們遇到的等式和不等式約束一般是線性的，因此非常幸運，它們定義的可行域是凸集。

一個重要的結論是：多個凸集的交集還是凸集。證明如下：

假設為 $C_{1},...,C_{k}$ 凸集，它們的交集為 $igcap_{i=1}^{k}$ $C_{i}$ 。對於任意點 $x，yin igcap_{i=1}^{k}C_{i}$ ，並且 $0leq hetaleq1$ ，由於 $C_{1},...,C_{k}$ 為凸集，所以有：

由此：

這個結論的實際價值是如果每個等式或者不等式約束條件定義的集合都是凸集，那麼這些條件聯合起來定義的集合還是凸集，而我們遇到的優化問題中，可能有多個等式和不等式約束，只要每個約束條件定義的可行域是凸集，則同時滿足這下約束條件的可行域還是凸集。需要注意的是，凸集的並集並不是凸集。

凸函數

在微積分中我們學習過凸函數的定義，下面來回憶一下。在函數的定義域內，如果對於任意的x和y，以及實數 $0leq hetaleq1$ ，都滿足如下條件：

則函數為凸函數。這個不等式和凸集的定義類似。從圖像上看，一個函數如果是凸函數，那麼它是向下凸出去的。用直線連接函數上的任何兩點A和B，線段AB上的點都在函數的上方，如下圖所示：

如果把上面不等式中的等號去掉，即：

則稱函數是嚴格凸函數。凸函數的一階判定規則為：

其幾何解釋為函數在任何點處的切線都位於函數的下方。對於一元函數，凸函數的判定規則為其二階導數大於等於0，即：

如果去掉上面的等號，則函數是嚴格凸的。對於多元函數，如果它是凸函數，則其Hessian矩陣為半正定矩陣。如果Hessian矩陣是正定的，則函數是嚴格凸函數。

Hessian矩陣是由多元函數的二階偏導數組成的矩陣。如果函數 $f(x_{1},...,x_{n})$ 二階可導，Hessian矩陣定義為：

這是一個n階矩陣。一般情況下，多元函數的混合二階偏導數與求導次序無關，即：

因此Hessian矩陣是一個對稱矩陣，它可以看作二階導數對多元函數的推廣。Hessian矩陣簡寫為 $?^{2}f(x)$ 。對於如下多元函數：

它的Hessian矩陣為：

根據多元函數極值判別法，假設多元函數在點M的梯度為0，即M是函數的駐點，則有：

1.如果Hessian矩陣正定，函數在該點有極小值

2.如果Hessian矩陣負定，函數在該點有極大值

3.如果Hessian矩陣不定，還需要看更高階的導數

這可以看做是一元函數極值判別法對多元函數對推廣，Hessian矩陣正定類似於二階導數大於0，其他的以此類推。對於n階矩陣A，對於任意非0的n維向量x都有：

則稱矩陣A為正定矩陣。判定矩陣正定的常用方法有以下幾種：

1.矩陣的特徵值全大於0。

2.矩陣的所有順序主子式都大於0。

3.矩陣合同於單位陣I。

類似的，如果一個n階矩陣A，對於任何非0的n維向量x，都有：

則稱矩陣A為負定矩陣。如果滿足：

則稱矩陣A為半正定矩陣。

一個重要結論是凸函數的非負線性組合是凸函數，假設 $f_{i}$ 是凸函數，並且 $W_{i}geq0$ ，則：

是凸函數。可以根據凸函數的定義進行證明，非常簡單，讀者可以自己實現。

下水平集

給定一個凸函數以及一個實數 $alpha$ ，函數的 $alpha$ 下水平集（sub-level set）定義為函數值小於等於 $alpha$ 的點構成的集合：

根據凸函數的定義，很容易證明該集合是一個凸集。這個概念的用途在於我們需要確保優化問題中一些不等式約束條件定義的可行域是凸集，如果是凸函數構成的不等式，則是凸集。

凸優化

有了凸集和凸函數的定義之後，我們就可以給出凸優化的定義。如果一個最優化問題的可行域是凸集，並且目標函數是凸函數，則該問題為凸優化問題。凸優化問題可以形式化的寫成：

其中x為優化變數；f為凸目標函數；C是優化變數的可行域，是一個凸集。這個定義給了我們證明一個問題是凸優化問題的思路，即證明目標函數是凸函數（一般是證明它的Hessian矩陣半正定），可行域是凸集。凸優化問題的另一種通用寫法是：

其中 $g_{i}(x)$ 是不等式約束函數，為凸函數； $h_{i}(x)$ 是等式約束函數，為仿射函數。上面的定義中不等式的方向非常重要，因為一個凸函數的0-下水平集是凸集。因此這些不等式共同定義的可行域是一些凸集的交集，仍然為凸集。通過將不等式兩邊同時乘以-1，可以保證把不等式寫成小於號的形式。前面已經證明仿射空間是凸集，因此加上這些等式約束後可行域還是凸集。

局部最優解與全局最優解

對於一個可行點x，如果在其鄰域內沒有其他點的函數值比該點小，則稱該點為局部最優，下面給出這個概念的嚴格定義：對於一個可行點，如果存在一個大於0的實數 $delta$ ，對於所有滿足：

即x的 $delta$ 鄰域內的點z，都有：

則稱x為局部最優點。對於一個可行點x，如果可行域內所有點z處的函數值都比在這點處大，即：

則稱x為全局最優點，全局最優解可能不止一個。凸優化問題有一個重要的特性：所有局部最優解都是全局最優解。這個特性可以保證我們在求解時不會陷入局部最優解，即如果找到了問題的一個局部最優解，則它一定也是全局最優解，這極大的簡化了問題的求解。下面證明上面的結論，採用反證法，具體證明如下：

假設x是一個局部最優解但不是全局最優解，即存在一個可行解y，有：

根據局部最優解的定義，不存在滿足：

並且

的點。選擇一個點：

其中：

則有：

即該點在x的 $delta$ 鄰域內。另外：

這與x是局部最優解矛盾。如果一個局部最優解不是全局最優解，在它的任何鄰域內還可以找到函數值比該點更小的點，這與該點是局部最優解矛盾。

之所以凸優化問題的定義要求目標函數是凸函數而且優化變數的可行域是凸集，是因為缺其中任何一個條件都不能保證局部最優解是全局最優解。下面來看兩個反例。

情況1：可行域是凸集，函數不是凸函數。這樣的例子如下圖所示：

上圖中優化變數的可行域是整個實數集，顯然是凸集，目標函數不是凸函數，有兩個局部最小值，這不能保證局部最小值就是全局最小值。

情況2：可行域不是凸集，函數是凸函數。這樣的例子如下圖所示：

在上圖中可行域不是凸集，中間有斷裂，目標函數還是凸函數。在曲線的左邊和右邊各有一個最小值，不能保證局部最小值就是全局最小值。可以很容易把這個例子推廣到3維空間里的2元函數（曲面）。由於凸優化的的目標函數是凸函數，Hessian矩陣半正定，因此不會出現鞍點，所以找到的梯度為0的點一定是極值點。

求解演算法

對於凸優化問題，可以使用的求解演算法很多，包括最常用的梯度下降法，牛頓法，擬牛頓法等，它們都能保證收斂到全局極小值點。梯度下降法在之前的文章中已經介紹，牛頓法和擬牛頓法在接下來將會介紹，請關注SIGAI的公眾號。

機器學習中的凸優化問題

下來我們來列舉一些機器學習中典型的凸優化問題。

線性回歸

線性回歸是最簡單的有監督學習演算法，它擬合的目標函數是一個線性函數。假設有l個訓練樣本 $(x_{i},y_{i})$ ，其中 $x_{i}$ 為特徵向量， $y_{i}$ 為實數標籤值。線性回歸的預測函數定義為：

其中權重向量w和偏置項b是訓練要確定的參數。定義損失函數為誤差平方和的均值：

將回歸函數代入，可以得到如下的損失函數：

如果將權重向量和特徵向量進行增廣，即將w和b進行合併：

目標函數可以簡化為：

可以證明這個目標函數是凸函數。目標函數展開之後為：

它的二階偏導數為：

因此它的Hessian矩陣為：

寫成矩陣形式為：

其中X是所有樣本的特徵向量按照列構成的矩陣。對於任意不為0的向量x，有：

因此Hessian矩陣是半正定矩陣，上面的優化問題是一個不帶約束條件的凸優化問題。可以用梯度下降法或牛頓法求解。

嶺回歸

嶺回歸是加上正則化項之後的線性回歸。加上L2正則化之後，訓練時優化的問題變為：

同樣的，我們可以證明這個函數的Hessian矩陣半正定，事實上，如果正則化項的係數大於0，它是嚴格正定的。限於篇幅，我們在這裡不給出詳細證明。

支持向量機

在SIGAI之前的公眾號文章「通過一張圖理解SVM的脈絡」中我們介紹了支持向量機的推導過程，如果讀者對支持向量機沒有基本的概念，請先閱讀那篇文章。支持向量機訓練時求解的原問題為：

顯然，這些不等式約束都是線性的，因此定義的可行域是凸集，另外我們可以證明目標函數是凸函數，因此這是一個凸優化問題。

通過拉格朗日對偶，我們轉換為對偶問題，加上核函數後的對偶問題為：

這裡的等式約束和不等式約束都是線性的，因此可行域是凸集。根據核函數的性質，我們可以證明目標函數是凸函數。如果讀者感興趣，我們後面的公眾號文章中會給出證明過程。

logistic回歸

logistic回歸也是一種常用的有監督學習演算法。加上L2正則化項之後，訓練時求解的問題為：

這是一個不帶約束的優化問題，我們可以證明這個函數的Hessian矩陣半正定。如果讀者對證明過程感興趣，我們以後的公眾號文章中會給出。

softamx回歸

softamx回歸是logistic回歸對多分類問題的推廣。它在訓練時求解的問題為：

這是一個不帶約束的優化問題，同樣的可以證明這個目標函數是凸函數。除此之外，機器學習中還有很多問題是凸優化問題，限於篇幅，我們不能一一列出。由於是凸優化問題，這些演算法是能保證找到全局最優解的。而神經網路訓練時優化的目標函數不是凸函數，因此有陷入局部極小值和鞍點的風險，這是之前長期被人詬病的。

原創聲明

本文為 SIGAI 原創文章，僅供個人學習使用，未經允許，不能用於商業目的。