轉(zhuǎn)載 https://blog.csdn.net/SIGAI_CSDN/article/details/80695179
導(dǎo)言
凸優(yōu)化（convex optimization）是最優(yōu)化問題中非常重要的一類，也是被研究的很透徹的一類。對(duì)于機(jī)器學(xué)習(xí)來說，如果要優(yōu)化的問題被證明是凸優(yōu)化問題，則說明此問題可以被比較好的解決。在本文中，SIGAI將為大家深入淺出的介紹凸優(yōu)化的概念以及在機(jī)器學(xué)習(xí)中的應(yīng)用。
凸優(yōu)化簡介
在SIGAI之前的公眾號(hào)文章“理解梯度下降法”中我們介紹了最優(yōu)化的基本概念以及梯度下降法。如果讀者對(duì)目標(biāo)函數(shù)，優(yōu)化變量，可行域，等式約束，不等式約束，局部極小值，全局極小值的概念還不清楚，請(qǐng)先閱讀那篇文章。
求解一個(gè)一般性的最優(yōu)化問題的全局極小值是非常困難的，至少要面臨的問題是：函數(shù)可能有多個(gè)局部極值點(diǎn)，另外還有鞍點(diǎn)問題。對(duì)于第一個(gè)問題，我們找到了一個(gè)梯度為0的點(diǎn)，它是極值點(diǎn)，但不是全局極值，如果一個(gè)問題有多個(gè)局部極值，則我們要把所有局部極值找出來，然后比較，得到全局極值，這非常困難，而且計(jì)算成本相當(dāng)高。第二個(gè)問題更嚴(yán)重，我們找到了梯度為0的點(diǎn)，但它連局部極值都不是，典型的是這個(gè)函數(shù)，在0點(diǎn)處，它的導(dǎo)數(shù)等于0，但這根本不是極值點(diǎn)：
梯度下降法和牛頓法等基于導(dǎo)數(shù)作為判據(jù)的優(yōu)化算法，找到的都導(dǎo)數(shù)/梯度為0的點(diǎn)，而梯度等于0只是取得極值的必要條件而不是充分條件。如果我們將這個(gè)必要條件變成充分條件，即：
問題將會(huì)得到簡化。如果對(duì)問題加以限定，是可以保證上面這個(gè)條件成立的。其中的一種限制方案是：
對(duì)于目標(biāo)函數(shù)，我們限定是凸函數(shù)；對(duì)于優(yōu)化變量的可行域（注意，還要包括目標(biāo)函數(shù)定義域的約束），我們限定它是凸集。
同時(shí)滿足這兩個(gè)限制條件的最優(yōu)化問題稱為凸優(yōu)化問題，這類問題有一個(gè)非常好性質(zhì)，那就是局部最優(yōu)解一定是全局最優(yōu)解。接下來我們先介紹凸集和凸函數(shù)的概念。
凸集
![]()
image.png
則稱該集合稱為凸集。如果把這個(gè)集合畫出來，其邊界是凸的，沒有凹進(jìn)去的地方。直觀來看，把該集合中的任意兩點(diǎn)用直線連起來，直線上的點(diǎn)都屬于該集合。相應(yīng)的點(diǎn)：
稱為點(diǎn)x和y的凸組合。下圖是凸集和非凸集的示意圖，左邊是一個(gè)凸集，右邊是一個(gè)非凸集：
下面是實(shí)際問題中一些常見的凸集例子，記住它們對(duì)理解后面的算法非常有幫助：
這一結(jié)論的意義在于如果一個(gè)優(yōu)化問題是不帶約束的優(yōu)化，則其優(yōu)化變量的可行域是一個(gè)凸集。
仿射子空間。給定m行n列的矩陣A和m維向量b，仿射子空間定義為如下向量的集合：
并且：
這一結(jié)論的意義在于，如果一組約束是線性等式約束，則它確定的可行域是一個(gè)凸集。
多面體。多面體定義為如下向量的集合：
這一結(jié)論的意義在于，如果一組約束是線性不等式約束，則它定義的可行域是凸集。在實(shí)際應(yīng)用中，我們遇到的等式和不等式約束一般是線性的，因此非常幸運(yùn)，它們定義的可行域是凸集。
一個(gè)重要的結(jié)論是：多個(gè)凸集的交集還是凸集。證明如下：
這個(gè)結(jié)論的實(shí)際價(jià)值是如果每個(gè)等式或者不等式約束條件定義的集合都是凸集，那么這些條件聯(lián)合起來定義的集合還是凸集，而我們遇到的優(yōu)化問題中，可能有多個(gè)等式和不等式約束，只要每個(gè)約束條件定義的可行域是凸集，則同時(shí)滿足這下約束條件的可行域還是凸集。需要注意的是，凸集的并集并不是凸集。
凸函數(shù)
在微積分中我們學(xué)習(xí)過凸函數(shù)的定義，下面來回憶一下。在函數(shù)的定義域內(nèi)，如果對(duì)于任意的x和y，以及實(shí)數(shù)，都滿足如下條件
則函數(shù)為凸函數(shù)。這個(gè)不等式和凸集的定義類似。從圖像上看，一個(gè)函數(shù)如果是凸函數(shù)，那么它是向下凸出去的。用直線連接函數(shù)上的任何兩點(diǎn)A和B，線段AB上的點(diǎn)都在函數(shù)的上方，如下圖所示
如果把上面不等式中的等號(hào)去掉，即：
則稱函數(shù)是嚴(yán)格凸函數(shù)。凸函數(shù)的一階判定規(guī)則為：
其幾何解釋為函數(shù)在任何點(diǎn)處的切線都位于函數(shù)的下方。對(duì)于一元函數(shù)，凸函數(shù)的判定規(guī)則為其二階導(dǎo)數(shù)大于等于0，即：
如果去掉上面的等號(hào)，則函數(shù)是嚴(yán)格凸的。對(duì)于多元函數(shù)，如果它是凸函數(shù)，則其Hessian矩陣為半正定矩陣。如果Hessian矩陣是正定的，則函數(shù)是嚴(yán)格凸函數(shù)。 Hessian矩陣是由多元函數(shù)的二階偏導(dǎo)數(shù)組成的矩陣。如果函數(shù)
二階可導(dǎo)，Hessian矩陣定義為
這是一個(gè)n階矩陣。一般情況下，多元函數(shù)的混合二階偏導(dǎo)數(shù)與求導(dǎo)次序無關(guān)，即：
因此Hessian矩陣是一個(gè)對(duì)稱矩陣，它可以看作二階導(dǎo)數(shù)對(duì)多元函數(shù)的推廣。Hessian矩陣簡寫為
。對(duì)于如下多元函數(shù)：
它的Hessian矩陣為：
根據(jù)多元函數(shù)極值判別法，假設(shè)多元函數(shù)在點(diǎn)M的梯度為0，即M是函數(shù)的駐點(diǎn)，則有：
1.如果Hessian矩陣正定，函數(shù)在該點(diǎn)有極小值
2.如果Hessian矩陣負(fù)定，函數(shù)在該點(diǎn)有極大值
3.如果Hessian矩陣不定，還需要看更高階的導(dǎo)數(shù)
這可以看做是一元函數(shù)極值判別法對(duì)多元函數(shù)對(duì)推廣，Hessian矩陣正定類似于二階導(dǎo)數(shù)大于0，其他的以此類推。對(duì)于n階矩陣A，對(duì)于任意非0的n維向量x都有
則稱矩陣A為正定矩陣。判定矩陣正定的常用方法有以下幾種：
1.矩陣的特征值全大于0。
2.矩陣的所有順序主子式都大于0。
3.矩陣合同于單位陣I。
類似的，如果一個(gè)n階矩陣A，對(duì)于任何非0的n維向量x，都有：
則稱矩陣A為負(fù)定矩陣。如果滿足：
則稱矩陣A為半正定矩陣。
是凸函數(shù)。可以根據(jù)凸函數(shù)的定義進(jìn)行證明，非常簡單，讀者可以自己實(shí)現(xiàn)
下水平集
凸優(yōu)化
有了凸集和凸函數(shù)的定義之后，我們就可以給出凸優(yōu)化的定義。如果一個(gè)最優(yōu)化問題的可行域是凸集，并且目標(biāo)函數(shù)是凸函數(shù)，則該問題為凸優(yōu)化問題。凸優(yōu)化問題可以形式化的寫成：
局部最優(yōu)解與全局最優(yōu)解
則稱x為全局最優(yōu)點(diǎn)，全局最優(yōu)解可能不止一個(gè)。凸優(yōu)化問題有一個(gè)重要的特性：所有局部最優(yōu)解都是全局最優(yōu)解。這個(gè)特性可以保證我們?cè)谇蠼鈺r(shí)不會(huì)陷入局部最優(yōu)解，即如果找到了問題的一個(gè)局部最優(yōu)解，則它一定也是全局最優(yōu)解，這極大的簡化了問題的求解。下面證明上面的結(jié)論，采用反證法，具體證明如下：
假設(shè)x是一個(gè)局部最優(yōu)解但不是全局最優(yōu)解，即存在一個(gè)可行解y，有：
這與x是局部最優(yōu)解矛盾。如果一個(gè)局部最優(yōu)解不是全局最優(yōu)解，在它的任何鄰域內(nèi)還可以找到函數(shù)值比該點(diǎn)更小的點(diǎn)，這與該點(diǎn)是局部最優(yōu)解矛盾。
之所以凸優(yōu)化問題的定義要求目標(biāo)函數(shù)是凸函數(shù)而且優(yōu)化變量的可行域是凸集，是因?yàn)槿逼渲腥魏我粋€(gè)條件都不能保證局部最優(yōu)解是全局最優(yōu)解。下面來看兩個(gè)反例。
情況1：可行域是凸集，函數(shù)不是凸函數(shù)。這樣的例子如下圖所示：
上圖中優(yōu)化變量的可行域是整個(gè)實(shí)數(shù)集，顯然是凸集，目標(biāo)函數(shù)不是凸函數(shù)，有兩個(gè)局部最小值，這不能保證局部最小值就是全局最小值。
情況2：可行域不是凸集，函數(shù)是凸函數(shù)。這樣的例子如下圖所示：
在上圖中可行域不是凸集，中間有斷裂，目標(biāo)函數(shù)還是凸函數(shù)。在曲線的左邊和右邊各有一個(gè)最小值，不能保證局部最小值就是全局最小值?？梢院苋菀装堰@個(gè)例子推廣到3維空間里的2元函數(shù)（曲面）。由于凸優(yōu)化的的目標(biāo)函數(shù)是凸函數(shù)，Hessian矩陣半正定，因此不會(huì)出現(xiàn)鞍點(diǎn)，所以找到的梯度為0的點(diǎn)一定是極值點(diǎn)。
求解算法
對(duì)于凸優(yōu)化問題，可以使用的求解算法很多，包括最常用的梯度下降法，牛頓法，擬牛頓法等，它們都能保證收斂到全局極小值點(diǎn)。梯度下降法在之前的文章中已經(jīng)介紹，牛頓法和擬牛頓法在接下來將會(huì)介紹，請(qǐng)關(guān)注SIGAI的公眾號(hào)。
機(jī)器學(xué)習(xí)中的凸優(yōu)化問題
下來我們來列舉一些機(jī)器學(xué)習(xí)中典型的凸優(yōu)化問題。
線性回歸
其中權(quán)重向量w和偏置項(xiàng)b是訓(xùn)練要確定的參數(shù)。定義損失函數(shù)為誤差平方和的均值：
將回歸函數(shù)代入，可以得到如下的損失函數(shù)：
如果將權(quán)重向量和特征向量進(jìn)行增廣，即將w和b進(jìn)行合并：
目標(biāo)函數(shù)可以簡化為：
可以證明這個(gè)目標(biāo)函數(shù)是凸函數(shù)。目標(biāo)函數(shù)展開之后為：
它的二階偏導(dǎo)數(shù)為：
因此它的Hessian矩陣為：
寫成矩陣形式為：
其中X是所有樣本的特征向量按照列構(gòu)成的矩陣。對(duì)于任意不為0的向量x，有：
因此Hessian矩陣是半正定矩陣，上面的優(yōu)化問題是一個(gè)不帶約束條件的凸優(yōu)化問題?？梢杂锰荻认陆捣ɑ蚺ｎD法求解。
嶺回歸
嶺回歸是加上正則化項(xiàng)之后的線性回歸。加上L2正則化之后，訓(xùn)練時(shí)優(yōu)化的問題變?yōu)椋?/p>
同樣的，我們可以證明這個(gè)函數(shù)的Hessian矩陣半正定，事實(shí)上，如果正則化項(xiàng)的系數(shù)大于0，它是嚴(yán)格正定的。限于篇幅，我們?cè)谶@里不給出詳細(xì)證明。
支持向量機(jī)
在SIGAI之前的公眾號(hào)文章“通過一張圖理解SVM的脈絡(luò)”中我們介紹了支持向量機(jī)的推導(dǎo)過程，如果讀者對(duì)支持向量機(jī)沒有基本的概念，請(qǐng)先閱讀那篇文章。支持向量機(jī)訓(xùn)練時(shí)求解的原問題為：
顯然，這些不等式約束都是線性的，因此定義的可行域是凸集，另外我們可以證明目標(biāo)函數(shù)是凸函數(shù)，因此這是一個(gè)凸優(yōu)化問題。
通過拉格朗日對(duì)偶，我們轉(zhuǎn)換為對(duì)偶問題，加上核函數(shù)后的對(duì)偶問題為：
這里的等式約束和不等式約束都是線性的，因此可行域是凸集。根據(jù)核函數(shù)的性質(zhì)，我們可以證明目標(biāo)函數(shù)是凸函數(shù)。如果讀者感興趣，我們后面的公眾號(hào)文章中會(huì)給出證明過程。
logistic回歸
logistic回歸也是一種常用的有監(jiān)督學(xué)習(xí)算法。加上L2正則化項(xiàng)之后，訓(xùn)練時(shí)求解的問題為：
這是一個(gè)不帶約束的優(yōu)化問題，我們可以證明這個(gè)函數(shù)的Hessian矩陣半正定。如果讀者對(duì)證明過程感興趣，我們以后的公眾號(hào)文章中會(huì)給出。
softamx回歸
softamx回歸是logistic回歸對(duì)多分類問題的推廣。它在訓(xùn)練時(shí)求解的問題為：
這是一個(gè)不帶約束的優(yōu)化問題，同樣的可以證明這個(gè)目標(biāo)函數(shù)是凸函數(shù)。除此之外，機(jī)器學(xué)習(xí)中還有很多問題是凸優(yōu)化問題，限于篇幅，我們不能一一列出。由于是凸優(yōu)化問題，這些算法是能保證找到全局最優(yōu)解的。而神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)優(yōu)化的目標(biāo)函數(shù)不是凸函數(shù)，因此有陷入局部極小值和鞍點(diǎn)的風(fēng)險(xiǎn)，這是之前長期被人詬病的。
