凸優化－凸集和凸函數 | CMU經典課程 | 附課件 |機器學習基礎

點擊藍色字體，關註：九三智能控

作者：Longfei Han，CMU牛人

0. CMU：Convex Optimization課程

Convex Optimization課程，該課程介紹了凸優化問題的基礎知識、一階方法、最優化和對偶、 二階方法、一些特別問題的探討等內容。本文是該課程基礎知識中凸集和凸函數部分的課程筆記。

課程網址（包括所有課件、視頻和作業）：http://www.stat.cmu.edu/~ryantibs/convexopt/

介紹PPT和預備知識介紹材料下載，請在公眾號回復：20180402

1. 優化理論

對於優化理論的定義，Ryan教授給出了一副很好理解優化理論是做什麼的圖，優化理論就是用於求解某個函數的極值，至於極值體現的含義就跟你要解決的問題相關了，與機器學習的「沒有天生優越的分類器」的理論類似，優化演算法也沒有好壞之分，只有適合還是不適合解決某一問題。

2. 凸集和凸錐

a. 凸集

仿射集和凸集的概念在凸優化－凸集一文中做了詳細介紹。凸集為 C?Rn，使得x,y∈C→tx+(1?t)y∈C，其中0≤t≤1。具體表現為下圖，左邊第一個為凸集，第二個則不是凸集。

任何凸集的線性組合仍為凸集，所有凸集的集合為Convex hull。空集、點、線、球體（Norm ball:{x:∥x∥≤r}）、超平面（Hyperplane:{x:aTx=b}）、半空間（Halfspace:{x:aTx≤b}）、仿射空間（Affine space:{x:Ax=b}）和多面體（Polyhedron{x:Ax≤b}）均為凸集。

下面證明為什麼Norm ball是凸集：

對於Norm ball中的任意兩點x和y，可以根據三角不等式獲得：

∥tx+(1?t)y∥leqt∥x∥+(1?t)∥y∥≤tr+(1?t)r≤r

所以，Norm ball中的任意兩點x和y的線性組合仍在集合內，證明Norm ball為凸集。

其中，Ryan還提到一個問題就是關於多面體，集合{x:Ax≤b,Cx=d}是否仍是Polyhedron？

結果是顯然的，仍然是多面體，因為平面Cx=d可以寫成Cx≤d和?Cx≤?d，滿足Polyhedron的定義，即{x:Ax≤b}。

b. 凸錐

錐（cone）是指x∈C→tx∈C，其中t≥0，而凸錐（convex cone）的定義則是x1,x2∈C→t1x1+t2x2∈C，其中t1,t2≥0，凸錐的實例如下圖：

但是，是否可以舉一個例子，使得集合C為錐，但不是凸錐呢？如下圖，如果兩條直線組成的錐，分別從直線上選兩點，則亮點的線性組合不一定在這兩條直線上。

對於凸錐，其中兩個重要的實例為Norm cone和Normal cone，接下來著重介紹這兩個凸錐的概念。

Norm cone是指{(x,t):∥x∥≤t}，而second-order cone則是使用2階範數norm∥?∥2，如果只看定義的話不太好理解Norm cone是什麼，下面給出了matlab模擬得到的三維下的Norm Cone實例：

Normal cone是指給定任意集合C和點x∈C，NC(x)={g:gTx≥gTy}，其中y∈C。無論集合C是否是凸集，滿足該定義的點的集合都是Normal cone，其含義是指Normal cone中的點與集合C內的點x的內積永遠大於集合C內任意點與其點x的內積。具體實例如下圖，x′normal cone是集合C邊緣切線向量之間的點的集合：

normal cone的定義將會在subgradient descent演算法中應用到。

c. 凸集的性質

凸集有兩個重要的性質，這對機器學習的分類問題，或者更進一步說，對SVM等演算法理論有著重要的支撐作用。

（1）Separating hyperplane理論：兩個不相交的凸集之間必然存在一個分割超平面，使得兩個凸集可以分開。即如果C和D都是非空凸集，且C∩D=?，則必然存在a,b使得C?{x:aT≤b} 和 D?{x:aTx≥b}。如下圖：

（2）Supporting hyperplane理論：凸集邊界上的一點必然存在一個支撐超平面穿過該點，即如果C都是非空凸集，x0∈bd(C)，那麼必然存在一個超平面a，使得C?{x:aTx≤aTx0}，如下圖：

d. Operations preserving convexity

凸集經過以下幾個操作，仍會是凸集：

（1）Intersection： 凸集交集仍然是凸集。

（2）Scaling and translation：如果C都是凸集，那麼對於?a,b，aC+b={ax+b:x∈C}仍是凸集。

（3）Affine images and preimages：如果f(x)=Ax+b，C和D是凸集，那麼f(C)={f(x):x∈C}和f?1(D)={x:f(x)∈D}仍是凸集。

這裡需要注意的是，第二點和第三點的區別在於，第二點僅相對於凸集做了尺度或平移變換，而第三點則是A為矩陣，b為向量，可以對凸集做矩陣變換，這在圖像里可以看成是旋轉、壓縮、或者是降維操作，而不僅僅是簡單的平移變換。

3. 凸函數

a. 凸函數的定義

總體而言，凸函數跟凸集的定義和性質基本一致，凸函數的性質都可以通過凸集來證明。

函數f為凸函數，如果其滿足f:R→R，使得函數f的定義域為凸集，dom(f)?Rn，且f(tx+(1?t)y)≤tf(x)+(1?t)f(y),其中0≤t≤1。也就是說凸函數上任意兩點的連線都在兩點區間的函數之上。具體表現為下圖：

當然，如果函數f為凸函數，那麼相應的－f則為凹函數。

如果凸函數滿足f(tx+(1?t)y)<tf(x)+(1?t)f(y),其中0<t<1，則該函數為嚴格凸函數（strictly convex）；如果嚴格凸函數還滿足?m>0:f?m2∥x∥22，則該函數為強凸函數（strongly convex），即函數f至少是像二次函數一樣的凸函數。所以，根據定義，強凸函數一定是嚴格凸函數，嚴格凸函數一定是凸函數，反之，則不成立。

例如：單變數函數中的指數函數eax、仿射函數aTx+b、二次函數12xTQx+bTx+c（其中Q?0半正定）、平方誤差函數∥y?Ax∥22、p-範數函數∥x∥p=(∑ni=1xpi)1/p、Indicator function和Max function（f(x)=maxx1,…,xn）均是凸函數，相反，對數函數則為凹函數。其中，Indicator function定義為：

IC(x)={0x∈C∞x?C

b. 凸函數的性質

與凸集類似，凸函數具有以下的性質：

（1）Epigraph characterization：函數f為凸函數當且僅當，它的epigraph（epi(f)={(x,t)∈dom(f)×R:f(x)≤t}）為凸集。其中，函數的epigraph是指在函數上方的所有點的集合，如下圖所示，我們可以繪製圖像的曲線並採用該方法來確定一個函數是否屬於凸函數：

（2）Convex sublevel sets：如果函數f為凸函數，那麼它的sublevel sets（{x∈dom(f):f(x)≤t}）為凸集，反之，則不成立。如下圖，函數值域小於t的下方的定義域區間（XXX位置）為凸集。

（3）First-order characterization：如果函數f可微，那麼當且僅當dom(f)為凸集，且對於?x,y∈dom(f)，使得f(y)≥f(x)+?f(x)T(y?x)，則函數f為凸函數。這一點很易於理解，即在函數某點切線上的點的值小於該點在函數上的值，如下：

根據凸函數一階導的性質，我們可以看出，如果當我們找到某一點使得?f(x)=0，那麼就會使得函數上所有點f(y)≥f(x)，即點f(x)為函數的極小值。這一點，對於接下來將要介紹的優化問題極為重要，闡明我們求解函數極小值的方法。

（4）Second-order characterization：函數f二階可微，那麼當且僅當dom(f)為凸集，且對於?x∈dom(f)，使得?2f(x)?0，則函數f為凸函數。

（5）Jensen』s inequality：如果函數f為凸函數，則f(E[X])≤E[f(X)])

c. 凸函數變換

與凸集類似，凸函數經過一些變換後仍能為凸函數，例如：

（1）Nonnegative linear combination；

（2）Pointwise maximization：如果?s∈S,fs為凸函數，那麼f(x)=maxs∈Sfs(x)仍為凸函數；

（3）Partial minimization：如果g(x,y)是凸函數，集合C也為凸集，那麼f(x)=miny∈Cg(x,y)仍為凸集；

（4）Affine composition：如果函數f為凸函數，那麼經過矩陣變換的函數g(x)=f(Ax+b)也為凸函數。

4. softmax函數

實例：對於softmax函數，作為機器學習中logistic回歸的泛化形式，也成為log-sun-exp函數，什麼是softmax函數呢？如何證明該函數為凸函數呢？

假設函數g(x)=log∑i=1keaTix+bi，從表面上可以看出該函數就像估計函數maxi=1,…,k(aTix+bi)的最大值，為什麼呢？如果?i,aTix+bi，則會得到k個數值，如果其中某一個數值比較大，那麼通過指數運算會放大該數值在求和運算中的比例，導致求和運算的最終結果受到該較大數值的影響，所以再求對數縮小數值，最後求得的結果基本上就類似於找到aTix+bi的最大值。但是與直接求最大值不同，該函數是光滑函數，便於運用優化演算法求解，因此稱為softmax函數。

接下來證明為什麼log-sun-exp函數是凸函數：

首先，利用之前提到的affine composition，我們可以知道如果f(x)=log(∑i=1nexi)為凸函數，那麼softmax肯定為凸函數；

然後，利用凸函數的二階微分的性質，計算f(x)=log(∑i=1nexi)的一階微分和二階微分：

?if(x)=exi∑nl=1exl

?2ijf(x)=exi∑nl=1exlli=j?exiexj(∑nl=1exl)2＝diag(z)?zzT

其中，zi=exi/(∑nl=1exl)，通過計算我們可以獲得?2f(x)為diagonally dominant矩陣，diagonally dominant是指矩陣A，滿足Aii≥∑i≠j∣Aij∣，即矩陣對角線上的元素大於該行非對角線元素之和。

因此，證明該矩陣是半正定p.s.d.的（positive semidefinite）。滿足上面介紹的凸函數性質的第四點，因此，該softmax函數為凸函數。

Ryan還提到一個例子，這個例子我就不詳細闡述為什麼是凸函數，大家可以根據上面講解的知識來判斷下面的函數是否是凸函數：

max{log(1(aTx+b)7),∥Ax+b∥31}

引用網址

http://www.hanlongfei.com/%E5%87%B8%E4%BC%98%E5%8C%96/2015/09/24/cmu-10725-convexset/

微信群&商業合作

• 加入微信群：不定期分享資料，拓展行業人脈請在公眾號留言：「微信號+名字+研究領域/專業/學校/公司」，我們將很快與您聯繫。
• 投稿（無稿費）、商業合作請留言聯繫。

http://weixin.qq.com/r/AC91bd-EloLprZsO93oS (二維碼自動識別)

推薦閱讀：