凸函數

本文的閱讀等級:中級

K\subset\mathbb{R}^n 為一個非空凸集,也就是說,給定任意兩點 \mathbf{x}_1,\mathbf{x}_2\in K0\le\lambda\le 1,點 \lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2 屬於 K (見“凸組合、凸包與凸集”)。凸函數 (convex function) 是一個實函數 f:K\to\mathbb{R} 滿足下列性質:對於任意 \mathbf{x}_1,\mathbf{x}_2\in K0\le\lambda\le 1

\displaystyle  f\left(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2\right)\le \lambda f(\mathbf{x}_1)+(1-\lambda)f(\mathbf{x}_2)

若定義式等號僅發生於 \lambda=0\lambda=1,我們稱 f 是一個嚴格凸函數。相反的,若 -f 是一個 (嚴格) 凸函數,則 f 稱為 (嚴格) 凹函數。圖一顯示一個單變量凸函數 f(x),任一弦 (連結點 (x_1,f(x_1))(x_2,f(x_2)) 的紅色線段) 必位於函數 (藍色曲線) 的上方。下面列舉一些單變量凸函數:ax+bx^2e^{3x}x\ln x (x>0)。對於 \mathbf{x}\in\mathbb{R}^n,仿射函數 f(\mathbf{x})=\mathbf{a}^T\mathbf{x}+b 和向量 p-範數 \Vert\mathbf{x}\Vert_p=(\sum_{i=1}^n\vert x_i\vert^p)^{1/p}p\ge 1,都是凸函數 (見“向量範數”)。本文將討論凸函數的一些性質和判別方法。

Convex function

圖一:凸函數

 
凸函數組合

多個凸函數可以組合成新的凸函數,見定理一和定理二。

定理一:若 f_1:K\to\mathbb{R}f_2:K\to\mathbb{R} 是凸函數,則 f_1+f_2 是定義於 K 的凸函數。

定理二:若 f:K\to\mathbb{R} 是一個凸函數且 a\ge 0,則 af 是定義於 K 的凸函數。

下面提供定理一的證明,定理二的證法亦同。設 \mathbf{x}_1,\mathbf{x}_2\in K0\le\lambda\le 1,使用 f_1f_2 的凸函數定義即得

\displaystyle\begin{aligned}  &f_1\left(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2\right)+f_2\left(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2\right)\\  &\le\lambda\left(f_1(\mathbf{x}_1)+f_2(\mathbf{x}_1)\right)+(1-\lambda)\left(f_1(\mathbf{x}_2)+f_2(\mathbf{x}_2)\right).\end{aligned}

 
上境圖

給定一實函數 f:K\to\mathbb{R}K\subset\mathbb{R}^n,我們定義 f 的上境圖 (epigraph) 為 \mathbb{R}^{n+1} 中一個集合:

\displaystyle  \hbox{epi}(f)=\left\{(\mathbf{x},\mu)\vert\mathbf{x}\in K,\mu\in\mathbb{R},f(\mathbf{x})\le\mu\right\}

圖二顯示一個凸函數的上境圖 (在函數圖像上方的黃色區域) 為凸集。事實上,凸上境圖和凸函數是兩個等價的概念。

Epigraph

圖二:上境圖

 
定理三:若 f:K\to\mathbb{R} (K\subset\mathbb{R}^n) 是一個凸函數,則 \hbox{epi}(f)\subset\mathbb{R}^{n+1} 是凸集。反之亦然。

(\Rightarrow) 假設 f:K\to\mathbb{R} 是一個凸函數。設 (\mathbf{x},\alpha), (\mathbf{y},\beta)\in\hbox{epi}(f),即 \mathbf{x},\mathbf{y}\in Kf(\mathbf{x})\le\alphaf(\mathbf{y})\le\beta。當 0\le\lambda\le 1

\displaystyle\begin{aligned}  f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)&\le\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})\\  &\le\lambda\alpha+(1-\lambda)\beta.  \end{aligned}

上式表明 \lambda(\mathbf{x},\alpha)+(1-\lambda)(\mathbf{y},\beta)=\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y},\lambda\alpha+(1-\lambda)\beta\right) 屬於 \hbox{epi}(f),故 \hbox{epi}(f) 是凸集。

(\Leftarrow) 假設 \hbox{epi}(f)\subset\mathbb{R}^{n+1} 是一個凸集。明顯地,(\mathbf{x},f(\mathbf{x})),(\mathbf{y},f(\mathbf{y}))\in\hbox{epi}(f),所以任一 0\le\lambda\le 1 都有 \lambda(\mathbf{x},f(\mathbf{x}))+(1-\lambda)(\mathbf{y},f(\mathbf{y}))\in\hbox{epi}(f),即 (\lambda\mathbf{x}+(1-\lambda)\mathbf{y},\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y}))\in\hbox{epi}(f),故

\displaystyle  f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)\le\lambda f(\mathbf{x})+(1-\lambda) f(\mathbf{y})

證明 f 具有凸性。

 
Jensen 不等式

給定一個凸函數 f:K\to\mathbb{R},若 \mathbf{x}_1,\ldots,\mathbf{x}_m\in K,Jensen 不等式說:

\displaystyle  f\left(\sum_{i=1}^m\lambda_i\mathbf{x}_i\right)\le\sum_{i=1}^m\lambda_if(\mathbf{x}_i)

其中 \lambda_1+\cdots+\lambda_m=1\lambda_i\ge 0i=1,\ldots,m。Jensen 不等式可以視為凸函數定義式的一種推廣。

我們用數學歸納法來證明。當 m=2,由凸函數定義可知命題成立。假設當 m=k 時,Jensen 不等式成立。考慮 m=k+1 的情況。因為 \lambda_1+\cdots+\lambda_{k+1}=1,在不失一般性的原則下,可設 \lambda_{k+1}>0。使用定義與假設,推導如下:

\displaystyle\begin{aligned}  f\left(\sum_{i=1}^{k+1}\lambda_i\mathbf{x}_i\right)&=f\left((1-\lambda_{k+1})\sum_{i=1}^{k}\frac{\lambda_i}{1-\lambda_{k+1}}\mathbf{x}_i+\lambda_{k+1}\mathbf{x}_{k+1}\right)\\  &\le(1-\lambda_{k+1})f\left(\sum_{i=1}^k\frac{\lambda_i}{1-\lambda_{k+1}}\mathbf{x}_i\right)+\lambda_{k+1}f(\mathbf{x}_{k+1})\\  &\le(1-\lambda_{k+1})\sum_{i=1}^k\frac{\lambda_i}{1-\lambda_{k+1}}f(\mathbf{x}_i)+\lambda_{k+1}f(\mathbf{x}_{k+1})\\  &=\sum_{i=1}^{k+1}\lambda_if(\mathbf{x}_i),  \end{aligned}

其中第二個不等式係因 \sum_{i=1}^k\lambda_i/(1-\lambda_{k+1})=1,故可套用歸納假設。

 
下面展示另一個運用上境圖 \hbox{epi}(f) 的證法。若 \mathbf{x}_1,\ldots,\mathbf{x}_m\in K,則 (\mathbf{x}_1,f(\mathbf{x}_1)),\ldots,(\mathbf{x}_m,f(\mathbf{x}_m))\in\hbox{epi}(f)。定理三說明了 f 是凸函數等價於 \hbox{epi}(f) 是凸集,也就是說,(\mathbf{x}_1,f(\mathbf{x}_1)),\ldots,(\mathbf{x}_m,f(\mathbf{x}_m)) 的凸組合必屬於 \hbox{epi}(f),表示如下:

\displaystyle  \sum_{i=1}^m\lambda_i(\mathbf{x}_i,f(\mathbf{x}_i))=\left(\sum_{i=1}^m\lambda_i\mathbf{x}_i,\sum_{i=1}^m\lambda_if(\mathbf{x}_i)\right)\in\hbox{epi}(f)

其中每一 \lambda_i\ge 0\lambda_1+\cdots+\lambda_m=1。使用 \hbox{epi}(f) 定義,即得 Jensen 不等式。

 
水平集

對於一個實函數 f:K\to\mathbb{R}\alpha\in\mathbb{R},水平集 (level set) 定義為

L_\alpha(f)=\{\mathbf{x}\vert f(\mathbf{x})=\alpha,\mathbf{x}\in K\}

上水平集 (superlevel set) L_\alpha^+(f) 和下水平集 (sublevel set) L_\alpha^-(f) 分別為

\displaystyle  L_\alpha^+(f)=\{\mathbf{x}\vert f(\mathbf{x})\ge\alpha,\mathbf{x}\in K\},~~~  L_\alpha^-(f)=\{\mathbf{x}\vert f(\mathbf{x})\le\alpha,\mathbf{x}\in K\}

 
定理四:若 f:K\to\mathbb{R} 為一個凸函數,則 L_\alpha^-(f)\subset K 是凸集,其中 \alpha 是任一實數。

\mathbf{x},\mathbf{y}\in L_\alpha^-(f)0\le\lambda\le 1,使用定義立即可得

\displaystyle  f\left(\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\right)\le\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})\le\lambda\alpha+(1-\lambda)\alpha=\alpha

\lambda\mathbf{x}+(1-\lambda)\mathbf{y}\in L_\alpha^-(f)。不過,L_\alpha^-(f) 是凸集並不能保證 f 是一個凸函數 (見維基百科圖例)。如定理三所示,凸上境圖才是有效的凸函數界定方法。

 
可導函數

若一個函數是連續的,我們稱其為 C^0 函數 (這裡 C 表示連續,而非複數);若一函數存在連續的導函數,即連續可導,則稱為 C^1 函數;若一個函數是 n 階可導 (n\ge 1),且其 n 階導函數連續,則稱為 C^n 函數。光滑函數 (smooth functions) 是指無窮可導的函數,因此也稱為 C^\infty 函數,譬如指數函數 e^x

 
定理五:令 f:K\to\mathbb{R}^nK\subset\mathbb{R}^n 是一個凸集,且 f\in C^1。若對於任意 \mathbf{x},\mathbf{y}\in K

\displaystyle  f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})

f 是凸函數。反之亦然。

定理五中,\nabla f(\mathbf{x})=(\partial f/\partial x_1,\ldots,\partial f/\partial x_n)^Tf 在點 \mathbf{x} 的梯度 (gradient)。

(\Rightarrow):假設所有 \mathbf{x},\mathbf{y}\in K 使得 f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})。固定 \mathbf{x}_1,\mathbf{x}_2\in K0\le\lambda\le 1。設 \mathbf{x}=\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2,另分別設 \mathbf{y}=\mathbf{x}_1\mathbf{y}=\mathbf{x}_2,就有

\displaystyle\begin{aligned}  f(\mathbf{x}_1)&\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{x}_1-\mathbf{x})\\  f(\mathbf{x}_2)&\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{x}_2-\mathbf{x}).  \end{aligned}

令第一式乘以 \lambda,第二式乘以 (1-\lambda),合併如下:

\displaystyle  \lambda f(\mathbf{x}_1)+(1-\lambda)f(\mathbf{x}_2)\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2-\mathbf{x})

再將 \mathbf{x}=\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2 代入上式,可得

\displaystyle  \lambda f(\mathbf{x}_1)+(1-\lambda)f(\mathbf{x}_2)\ge f(\lambda\mathbf{x}_1+(1-\lambda)\mathbf{x}_2)

(\Leftarrow):假設 f 是一個凸函數,則任一 0\le\lambda\le 1

\displaystyle  \lambda f(\mathbf{y})+(1-\lambda)f(\mathbf{x})\ge f(\lambda\mathbf{y}+(1-\lambda)\mathbf{x})

0<\lambda\le 1,上式可寫成

\displaystyle  \frac{f(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))-f(\mathbf{x})}{\lambda}\le f(\mathbf{y})-f(\mathbf{x})

\lambda\to 0,寫出 f(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))\mathbf{x} 的泰勒展開式可推得

\displaystyle  \nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})\le f(\mathbf{y})-f(\mathbf{x})

 
圖三顯示定理五描述的不等性質。與圖一比較,梯度 \nabla f(\mathbf{x}) 給出的不等式也可以用來取代凸函數定義,它說:凸函數 (藍色曲線) 必位於任一切線 (紅色支撐線) 的上方。

Illustration of Proposition 5

圖三:定理五的圖示

 
定理六:令 f:K\to\mathbb{R}^nK\subset\mathbb{R}^n 是一個凸集 (包含一個內點),且 f\in C^2。若每一 \mathbf{x}\in Kf 的 Hessian H(\mathbf{x}) 為一個半正定矩陣,則 f 是凸函數。反之亦然。

實函數 f(x) 的 Hessian H(\mathbf{x})=[h_{ij}] 為一個 n\times n 階實對稱矩陣,(i,j) 元為 h_{ij}=\frac{\partial^2 f}{\partial x_i\partial x_j}。若每一個非零向量 \mathbf{y}\in\mathbb{R}^n 都有 \mathbf{y}^TH\mathbf{y}\ge 0,我們稱 H 為一個半正定矩陣 (見“半正定矩陣的判別方法”)。

(\Rightarrow):假設 \mathbf{x}\in K\mathbf{z}\in\mathbb{R}^n 都有 \mathbf{z}^TH(\mathbf{x})\mathbf{z}\ge 0,我們要證明 f 是一個凸函數。根據泰勒定理,存在 0\le\lambda\le 1,使得

\displaystyle  f(\mathbf{y})=f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})+\frac{1}{2}(\mathbf{y}-\mathbf{x})^TH(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))(\mathbf{y}-\mathbf{x})

因為 H(\mathbf{x}) 是半正定矩陣,

\displaystyle  f(\mathbf{y})\ge f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x})

使用定理五即證得所求。

(\Leftarrow):假設 \mathbf{x}\in K 使得 H(\mathbf{x}) 不為半正定矩陣。在不失一般性的前提下,設 \mathbf{x}K 的一個內點 (interior point)。因為 Hessian 是連續函數,故存在鄰近 \mathbf{x} 的點 \mathbf{y}\in K,使得每一 0\le\lambda<1

\displaystyle  (\mathbf{y}-\mathbf{x})^TH(\mathbf{x}+\lambda(\mathbf{y}-\mathbf{x}))(\mathbf{y}-\mathbf{x})<0

上式迫使 f(\mathbf{y})<f(\mathbf{x})+\nabla f(\mathbf{x})^T(\mathbf{y}-\mathbf{x}),由定理五可推論 f 不具備凸性。

 
凸函數與最佳化問題有著密切的關係。若 \nabla f(\mathbf{x}_\ast)=\mathbf{0} 且 Hessian H(\mathbf{x})\mathbf{x}_\ast 的鄰近區域是半正定,則 \mathbf{x}_\astf 的一個局部最小值 (local minimum),即存在 \delta>0,使得所有 \{\mathbf{x}\vert\Vert\mathbf{x}-\mathbf{x}_\ast\Vert<\delta\} 都滿足 f(\mathbf{x}_\ast)\le f(\mathbf{x}) (見“最佳化理論與正定矩陣”)。換個說法,如果 f\mathbf{x}_\ast 的鄰近區域是一個凸函數,則 \mathbf{x}_\ast 是局部最小值的充要條件即為 \nabla f(\mathbf{x}_\ast)=\mathbf{0}。如果鄰近區域擴大為整個定義域 K,即 f:K\to\mathbb{R} 是一個凸函數,那麼局部最小值其實就是全域最小值 (global minimum)。

This entry was posted in 線性代數專欄, 仿射幾何 and tagged , , , , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

你正使用 WordPress.com 帳號留言。 登出 / 變更 )

Twitter picture

你正使用 Twitter 帳號留言。 登出 / 變更 )

Facebook照片

你正使用 Facebook 帳號留言。 登出 / 變更 )

Google+ photo

你正使用 Google+ 帳號留言。 登出 / 變更 )

連結到 %s