凸函式與凹函式

---

---

設$f:S \rightarrow \mathbb{R}$，其中S是$\mathbb{R}^n$中的非空凸集，則如果對於所有$\lambda \in \left ( 0,1 \right )$，都有$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$，則稱$f\left ( x \right )$在S上是凸函式。

另一方面，設$f:S\rightarrow \mathbb{R}$，其中S是$\mathbb{R}^n$中的非空凸集，則如果對於所有$\lambda \in \left ( 0, 1 \right )$，都有$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\geq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$，則稱$f\left ( x \right )$在S上是凹函式。

設$f:S \rightarrow \mathbb{R}$，其中S是$\mathbb{R}^n$中的非空凸集，則如果對於所有$\lambda \in \left ( 0, 1 \right )$，都有$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )< \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$，則稱$f\left ( x\right )$在S上是嚴格凸函式。

設$f:S \rightarrow \mathbb{R}$，其中S是$\mathbb{R}^n$中的非空凸集，則如果對於所有$\lambda \in \left ( 0, 1 \right )$，都有$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )> \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$，則稱$f\left ( x\right )$在S上是嚴格凹函式。

例子

• 線性函式既是凸函式又是凹函式。

• $f\left ( x \right )=\left | x \right |$是一個凸函式。

• $f\left ( x \right )= \frac{1}{x}$是一個凸函式。

定理

設$f_1,f_2,...,f_k:\mathbb{R}^n \rightarrow \mathbb{R}$是凸函式。考慮函式$f\left ( x \right )=\displaystyle\sum\limits_{j=1}^k \alpha_jf_j\left ( x \right )$，其中$\alpha_j>0,j=1, 2, ...k,$ 則$f\left ( x \right )$是一個凸函式。

證明

因為$f_1,f_2,...f_k$是凸函式

所以，對於所有$\lambda \in \left ( 0, 1 \right )$和$i=1, 2,....,k$，都有$f_i\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f_i\left ( x_1 \right )+\left ( 1-\lambda \right )f_i\left ( x_2 \right )$。

考慮函式$f\left ( x \right )$。

所以，

$ f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right ) $

$=\displaystyle\sum\limits_{j=1}^k \alpha_jf_j\left ( \lambda x_1 + (1-\lambda)x_2 \right )\leq \displaystyle\sum\limits_{j=1}^k\alpha_j\left[ \lambda f_j\left ( x_1 \right )+\left ( 1-\lambda \right )f_j\left ( x_2 \right ) \right]$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \left ( \displaystyle\sum\limits_{j=1}^k \alpha _jf_j\left ( x_1 \right ) \right )+\left ( 1-\lambda \right )\left ( \displaystyle\sum\limits_{j=1}^k \alpha _jf_j\left ( x_2 \right ) \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

因此，$f\left ( x\right )$是一個凸函式。

定理

設$f\left ( x\right )$是$\mathbb{R}^n$中凸集$S$上的凸函式，則$f\left ( x\right )$在S上的區域性極小值是全域性極小值。

證明

設$\hat{x}$是$f\left ( x \right )$的區域性極小值，且$\hat{x}$不是全域性極小值。

因此，存在$\bar{x} \in S$使得$f\left ( \bar{x} \right )< f\left ( \hat{x} \right )$。

由於$\hat{x}$是區域性極小值，存在鄰域$N_\varepsilon \left ( \hat{x} \right )$使得對於所有$x \in N_\varepsilon \left ( \hat{x} \right )\cap S$，都有$f\left ( \hat{x} \right )\leq f\left ( x \right )$。

但$f\left ( x \right )$是S上的凸函式，因此對於$\lambda \in \left ( 0, 1 \right )$

我們有$f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$

$\Rightarrow f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left (\hat{x} \right )$

$\Rightarrow f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0,1 \right )$

但是對於某個$\lambda$接近1但小於1，我們有

$\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \in N_\varepsilon \left ( \hat{x} \right )\cap S$且$f\left ( \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x} \right )< f\left ( \hat{x} \right )$

這與假設矛盾。

因此，$\hat{x}$是全域性極小值。

上圖

設S是$\mathbb{R}^n$中的非空子集，設$f:S \rightarrow \mathbb{R}$，則f的上圖，記為epi(f)或$E_f$，是$\mathbb{R}^{n+1}$的一個子集，定義為$E_f=\left \{ \left ( x,\alpha \right ):x \in S, \alpha \in \mathbb{R}, f\left ( x \right )\leq \alpha \right \}$

下圖

設S是$\mathbb{R}^n$中的非空子集，設$f:S \rightarrow \mathbb{R}$，則f的下圖，記為hyp(f)或$H_f$，是$\mathbb{R}^{n+1}$的一個子集，定義為$H_f=\left \{ \left ( x, \alpha \right ):x \in S, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$

定理

設S是$\mathbb{R}^n$中的非空凸集，設$f:S \rightarrow \mathbb{R}$，則f是凸函式當且僅當其上圖$E_f$是一個凸集。

證明

設f是一個凸函式。

要證明$E_f$是一個凸集。

設$\left ( x_1, \alpha_1 \right ),\left ( x_2, \alpha_2 \right ) \in E_f,\lambda \in\left ( 0, 1 \right )$

要證明$\lambda \left ( x_1,\alpha_1 \right )+\left ( 1-\lambda \right )\left ( x_2, \alpha_2 \right ) \in E_f$

$\Rightarrow \left [ \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2 \right ]\in E_f$

$f\left ( x_1 \right )\leq \alpha _1, f\left ( x_2\right )\leq \alpha _2$

因此，$f\left (\lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f \left ( x_2 \right )$

$\Rightarrow f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda \alpha_1+\left ( 1-\lambda \right )\alpha_2$

逆命題

設$E_f$是一個凸集。

要證明f是凸函式。

即，要證明如果$x_1, x_2 \in S,\lambda \in \left ( 0, 1 \right )$，

$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$

設$x_1,x_2 \in S, \lambda \in \left ( 0, 1 \right ),f\left ( x_1 \right ), f\left ( x_2 \right ) \in \mathbb{R}$

由於$E_f$是一個凸集，$\left ( \lambda x_1+\left ( 1-\lambda \right )x_2, \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right ) \right )\in E_f$

因此，$f\left ( \lambda x_1+\left ( 1-\lambda \right )x_2 \right )\leq \lambda f\left ( x_1 \right )+\left ( 1-\lambda \right )f\left ( x_2 \right )$