凸函数和凹函数

设 $f:S ightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则如果 $f\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )\leq \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight ), \forall \lambda \in \left ( 0,1 ight )$，则称 $f\left ( x ight )$ 在 S 上是凸的。

另一方面，设 $f:S ightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则如果 $f\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )\geq \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight ), \forall \lambda \in \left ( 0, 1 ight )$，则称 $f\left ( x ight )$ 在 S 上为凹集。

设 $f:S ightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则称 $f\left ( x ight )$ 在 S 上为严格凸集，如果 $f\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )< \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight ), \forall \lambda \in \left ( 0, 1 ight )$。

设 $f:S ightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则如果 $f\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )> \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight )f\left ( x_2 ight ), \forall \lambda \in \left ( 0, 1 ight )，则称 $f\left ( x ight )$ 在 S 上严格凹。 )$。

示例

• 线性函数既是凸函数又是凹函数。

• $f\left ( x ight )=\left | x ight |$ 是凸函数。

• $f\left ( x ight )= \frac{1}{x}$ 是凸函数。

定理

设 $f_1,f_2,...,f_k:\mathbb{R}^n ightarrow \mathbb{R}$ 为凸函数。考虑函数 $f\left ( x ight )=\displaystyle\sum\limits_{j=1}^k \alpha_jf_j\left ( x ight )$，其中 $\alpha_j>0,j=1, 2, ...k,$，则 $f\left ( x ight )$ 为凸函数。

证明

由于 $f_1,f_2,...f_k$ 为凸函数

因此，$f_i\left ( \lambda x_1+\left ( 1-\lambda ight )x_2 ight )\leq \lambda f_i\left ( x_1 ight )+\left ( 1-\lambda ight )f_i\left ( x_2 ight )，\forall \lambda \in \left ( 0, 1 ight )$ 和 $i=1, 2,....,k$

考虑函数 $f\left ( x ight )$。

因此，

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

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

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

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

因此，$f\left ( x ight )$ 是凸函数。

定理

设 $f\left ( x ight )$ 是凸集 $S\subset \mathbb{R}^n$ 上的凸函数，则局部$f\left ( x ight )$ 在 S 上的最小值是全局最小值。

证明

设 $\hat{x}$ 是 $f\left ( x ight )$ 的局部最小值，且 $\hat{x}$ 不是全局最小值。

因此，$\exists \hat{x} \in S$ 使得 $f\left ( \bar{x} ight )< f\left ( \hat{x} ight )$

由于 $\hat{x}$ 是局部最小值，因此存在邻域 $N_\varepsilon \left ( \hat{x} ight )$ 使得 $f\left ( \hat{x} ight )\leq f\left ( x ight )，\forall x \in N_\varepsilon \left ( \hat{x} ight )\cap S$

但 $f\left ( x ight )$ 是 S 上的凸函数，因此对于 $\lambda \in \left ( 0, 1 ight )$

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

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

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

但对于某些 $\lambda<1$ 但接近 1 的，我们有

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

这是一个矛盾。

因此，$\bar{x}$ 是全局最小值。

上图

设 S 是 $\mathbb{R}^n$ 中的非空子集，且设 $f:S ightarrow \mathbb{R}$，则 f 的上图表示为 epi(f) 或 $E_f$，是 $\mathbb{R}^n+1$ 的子集，其定义为 $E_f=\left \{ \left ( x,\alpha ight ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x ight )\leq \alpha ight \}$

下图

设 S 是 $\mathbb{R}^n$ 中的非空子集，且设 $f:S ightarrow \mathbb{R}$，则 f 的下标表示为 hyp(f) 或 $H_f=\left \{ \left ( x, \alpha ight ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x ight )\geq \alpha ight \}$

定理

设 S 为 $\mathbb{R}^n$ 中的非空凸集，且设 $f:S ightarrow \mathbb{R}^n$，则 f 为凸当且仅当其上标 $E_f$ 为凸集。

证明

设 f 为凸函数。

为了证明$E_f$ 是凸集。

设 $\left ( x_1, \alpha_1 ight ),\left ( x_2, \alpha_2 ight ) \in E_f,\lambda \in\left ( 0, 1 ight )$

示 $\lambda \left ( x_1,\alpha_1 ight )+\left ( 1-\lambda ight )\left ( x_2, \alpha_2 ight ) \in E_f$

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

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

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

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

逆

设 $E_f$ 为凸集。

证明 f 是凸的。

即，证明如果 $x_1, x_2 \in S,\lambda \left ( 0, 1 ight )$

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

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

由于 $E_f$ 是凸集，$\left ( \lambda x_1+\left ( 1-\lambda ight )x_2, \lambda f\left ( x_1 ight )+\left ( 1-\lambda ight ) ight )f\left ( x_2 ight )\in E_f$

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