凸函数与凹函数

---

---

设$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 )$