在前面兩篇文章中，我們介紹了凸集的定義與基本性質，以及一些保留凸性的操作。對於凸集的研究是學習凸函數以及後面凸優化問題的基礎。從這篇文章開始，我們進入凸函數的世界，預計用5、6篇文章對凸函數相關的內容進行介紹。本文主要介紹凸函數的概念以及一些基本性質。

凸函數定義

一個函數 f:mathbf{R}^n ightarrow mathbf{R} 是一個凸函數，當且僅當以上兩個條件成立：

  1. 函數 f 的定義域 dom f 是一個凸集；
  2. f( heta x + (1- heta)y)le heta f(x) + (1 - heta)f(y) heta in (0,1)

一個函數是嚴格凸函數當且僅當條件二當且僅當 x=y 時才取等號。凸函數的圖像使用下圖舉例。

由上圖來看，凸函數的幾何意義在於，定義域中任意兩點連線組成的線段都在這兩點的函數曲線（面）上方。由凸函數的定義可以類似地引出凹函數的定義：如果函數 f 是凸函數，那麼函數 -f 是凹函數。從凸函數與凹函數的定義，我們可以發現所有的仿射函數（Affine Function）即滿足凸函數的性質，又滿足凹函數的性質，因此是「既凸又凹」的。

我們也可以從另一個解釋凸函數的定義。在上文關於凸函數的定義中，我們要求凸性對於定義域中任意兩點 x,y 成立，結合凸性（條件2）的定義，我們可以發現凸性從幾何上來說描述的是函數曲面（線）上任意兩點間的超平面（直線）與函數曲面之間的相對關係。因此從這個角度。我們可以給出凸函數的另一個定義：

給任意x 、 v 以及 t ，如果函數 f(x) 是凸函數，當且僅當函數 g(t) = f(x+tv) 也是其定義域（ {t|x+tv in dom f} ）內的凸函數。

這個定義在判斷函數凸性時與前一個定義一樣都有廣泛的應用。

擴展值函數（Extended-value extensions）

在實際中，我們常常將凸函數的定義域推廣至 mathbf{R}^n ，推廣的方式是將原函數定義域以外的部分定義為 infty ，即：

widehat{f}(x)=egin{cases}f(x) xin dom f\infty x otin dom fend{cases}

其中 widehat{f}(x) 稱為擴展值函數，它定義在 mathbf{R}^n上。我們也可以從擴展值函數中恢復出原函數的定義域：

dom f = {x | widehat{f}(x) < infty }

利用擴展值函數，我們可以簡化對函數的描述，因為此時不必再描述函數的定義域。

我們很容易地可以驗證擴展值函數同樣適用於上述關於凸函數的定義。考慮凸性的定義：

widehat{f}( heta x + (1- heta)y)le heta widehat{f}(x) + (1 - heta)widehat{f} (y) heta in (0,1)

如果， x in dom f 且 y in dom f ，那麼如果原函數 f 是凸函數，擴展值函數 widehat{f}(x) 也是凸函數。如果 x in dom f 但是 y otin dom f 。由拓展函數的定義，上式右邊等於無窮大，那麼如果原函數 f 是凸函數，擴展值函數 widehat{f}(x) 也是凸函數。因此，我們可以說，如果一個如果原函數 f 是凸函數，那麼擴展值函數 widehat{f}(x) 不改變函數的凸性。因此，為了簡化對凸函數的描述，在之後的所有文章中，我們對於都默認所有的凸函數都取其對應的擴展值函數的形式，而不再對其的定義域做過多強調。

凸函數判定條件

介紹完凸函數的定義後，顯然我們可以使用定義來判斷一個函數時候是凸函數，事實上很多時候我們也的確是這麼做的。但是，實際上關於凸函數的判定方法有更簡單直觀的方法。下面兩小節介紹凸函數判定的一階與二階條件。

一階條件

考慮一個可微函數 f ，即 f 的梯度 abla f 在 dom f 中處處存在，函數 f 是凸函數當且僅當對於 forall x,y in dom f ，有下式成立：

f(y) ge f(x) + abla f(x)^T(y-x) 上述條件成為凸函數判定的一階條件。一階條件有清晰的幾何意義：凸函數永遠位於其切線的上方。這一點可以使用下圖闡釋：

進一步分析上式，可以發現 f(x) + abla f(x)^T(y-x) 是函數 f 在 x 處的一階泰勒近似，那麼上述條件就說明了對於凸函數而言，其任意位置處的一階泰勒展開總是其本身的全局下界（global under-estimator）。而泰勒展開描述的是函數 f 的局部性質，由此我們得到有關凸函數的一個重要性質：凸函數是一類可以由局部信息推導出全局信息的函數。為了解釋這一點，我們考慮 abla f(x)=0 的位置，對於凸函數 f 有， f(y)ge f(x) forall x,y in dom f ，說明 x 是函數 f 的全局最小值。而我們導出 x 是全局最小值只使用了 f(x) 的局部性質—— abla f(x)=0 。這說明了凸函數可以「管中窺豹」的優良特性。在數學分析中，我們總是去分析函數的局部信息（微分），以此去分析函數的特性，而凸函數的這種優良特性使得我們只需要分析函數的局部性質就可以獲知其全局特性，這大大簡化了研究難度，因此使得凸函數與凸優化問題成為了最先受到學者廣泛研究的問題。類似於條件一，我們可以給出嚴格凸函數與凹函數的判斷條件。

二階條件

現在我們假設函數 f 是二階可微的，即函數 f 的Hessian矩陣在定義域內處處存在，那麼函數 f 是凸函數當且僅當對於定義域內的任意一點 x ，該點處的Hessian矩陣是半正定的,即：

abla^2f(x)succeq0

對於標量函數而言，Hessian矩陣半正定退化為： f^{}(x)ge0 ，意味著函數 f 的導函數是非遞減的。從幾何上來說，Hessian矩陣處處半正定意味著函數 f 處處曲率非負。

類似地，我們可以發現對於嚴格凸函數有 abla^2f(x)succ0 ，對於凹函數有 abla^2f(x)preceq0 。

一些常見凸函數

在本節中，我們將介紹一些常見的凸函數，我們首先從標量函數開始介紹：

  1. 指數函數： e^{ax} 是 mathbf{R} 上的凸函數，對 forall a in mathbf{R} 。
  2. 冪函數： x^{a} 當 age1,or a<0 時是凸函數，當 0le x <1 是凹函數。
  3. 絕對值冪函數： |x|^a 在 age1 時是凸函數。
  4. 對數函數： log x 是凹函數。
  5. 負熵函數： xlog x 是凸函數。

上面幾個函數通過凸函數判定的二階條件很容易地可以驗證它們的凸性。下面介紹一些矢量凸函數：

  1. 範數（Norm）：任意 mathbf{R}^n 上的範數函數都是凸函數（可以由範數的三角不等式結合凸函數定義得證）。
  2. 最大值函數： max{x_1,x_2,...,x_n} 是 mathbf{R}^n 上的凸函數。
  3. Quadratic-over-linear function：例如函數 f(x,y)=frac{x^2}{y} 就是凸函數，這一點可以通過求其Hessian矩陣驗證其正定性看出，也可以從函數圖像中直觀看出。

4. Log-sum-exp函數：函數 f(x)=log(e^{x_1}+e^{x_2}+e^{x_3}+...+e^{x_n}) 是凸函數。該函數可以可以看出是最大值函數的可微近似：

max{x_1,x_2,...,x_n} le f(x) le max{x_1,x_2,...,x_n} + log n

對於 n=2 的情況，繪製出函數圖像如下：

5. 幾何平均函數：函數 f(x)=(prod_{i=1}^n x_i)^{frac{1}{n}} 是凹函數。

6. 對數行列式函數（log-determinant）：對於對稱正定矩陣，函數 f(x) = log detX 是凸函數。因為 det X=prod_{i}lambda_i ，對於對稱正定矩陣，所有特徵值 lambda_i 都是大於0的，因此 log det X = log ( prod_ilambda_i)=sum_{i} log lambda_i ，由於對數函數是凸函數，其線性組合依然是凸函數（這一點在下一篇保凸運算中會有所介紹），因此 f(x) = log detX 是凸函數。

上述的矢量凸函數的凸性證明均可以在書上找到，這裡不對具體的證明細節進行敘述，感興趣的讀者可以參考Convex Optimization 73-74頁的證明。

子水平集（Sublevel Set）

函數 f: mathbf{R}_n ightarrow mathbf{R} 的 alpha -子水平集定義為：

C_{alpha}={xin dom f|f(x) le alpha}

從定義中可以看出，子水平集指的是定義域中滿足對應條件的部分。一個凸函數的任意子水平集都是凸集：假設 x,y in alpha-sublevel set ，因此 f(x)le alpha, f(y) le alpha ，因此 f( heta x + (1- heta)y)le heta f(x) + (1- heta)f(y) le heta alpha + (1- heta)alpha=alpha ，因此 heta x + (1- heta)y in alpha-sublevel set 。

Epigraph

函數 f: mathbf{R}_n ightarrow mathbf{R} 的 Epigraph定義為：

epi f = {(x,t)|xin dom f , f(x) le t}

是 mathbf{R}^{n+1} 的子集。Epigraph的定義可以由下圖闡釋。

從幾何上來說， epi f 可以認為是函數 f 曲面（線）以上的部分。因此，Epigraph是聯繫凸函數與凸集的紐帶——函數 f 是凸函數當且僅當它的Epigraph是凸集。

詹森不等式及其拓展

凸函數的定義式：

f( heta x + (1 - heta)y) le heta f(x) + (1 - heta)f(y)

又被稱為詹森不等式。上面的基本詹森不等式可以被拓展為高維乃至無窮維的情況：

  • 如果函數 f 是凸函數，那麼對於 x_1, x_2,...x_n in dom f ，以及任意 sum_{i} heta_i=1, hetasucceq0 ，有下式成立：

f(sum_{i} heta_i x_i)le sum_{i} heta_if(x_i)

  • 如果函數 f 是凸函數，且 int_{S}p(x)dx=1 ,那麼有下式成立：

f(int_{S}xp(x)dx)le int_{S}p(x)f(x)dx

如果 p(x) 看作是隨機矢量 x 的概率密度分布，那麼上面的積分不等式可以寫作下式：

f( ext{E} x) le ext{E} f(x)

利用詹森不等式可以證明一些重要的不等式，比如Holder不等式、幾何平均與算數平均關係不等式等等，這些在Convex Optimization的78頁有所闡述，這裡不進行仔細說明，只是對詹森不等式的形式以及它與凸函數的關係進行闡述，意在對詹森不等式有所了解。

本文介紹了凸函數的基本定義、判定方法、一些與凸函數相關的概念與常見凸函數，下一篇文章將會介紹一些保凸運算。


推薦閱讀：
相关文章