凸函数和凹函数
设 $f:S \rightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x \right )$ 被称为 S 上的凸集if $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 ), \forall \lambda \in \left ( 0,1 \right )$。
另一方面，设 $f:S\rightarrow \mathbb{R}$，其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则表示 $f\left ( x \right )$在 S 上凹 如果 $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 ), \forall \lambda \in \left ( 0, 1 \right )$。
设 $f:S \rightarrow \mathbb{R}$ 其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x\right )$ 被称为 S 上的严格凸集if $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 ), \forall \lambda \in \left ( 0, 1 \right )$。
令 $f:S \rightarrow \mathbb{R}$ 其中 S 是 $\mathbb{R}^n$ 中的非空凸集，则 $f\left ( x\right )$ 被称为 S 上的严格凹集if $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 ), \forall \lambda \in \left ( 0, 1 \right )$。
例子
线性函数既是凸函数又是凹函数。
$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$ 是凸函数
因此， $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 ), \forall \lambda \in \left ( 0, 1 \right )$ 和 $i=1, 2,....,k$
考虑函数 $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 \right )x_2\leq \displaystyle\sum\limits_{j=1}^k\alpha_j\ lambda f_j\left ( x_1 \right )+\left ( 1-\lambda \right )f_j\left ( x_2 \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 ( \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_2 \right )\leq \left ( 1-\lambda \right )f\左 ( x_2 \右 )$
因此，$f\left ( x\right )$ 是凸函数。
定理
设 $f\left ( x\right )$ 为凸集 $S\subset \mathbb{R}^n$ 上的凸函数，则 S 上 $f\left ( x\right )$ 的局部最小值为全局最小值。
证明
令 $\hat{x}$ 为 $f\left ( x \right )$ 的局部最小值，并且 $\hat{x}$ 不是全局最小值。
因此，$\hat{x} \在 S$ 中，使得 $f\left ( \bar{x} \right )< f\left ( \hat{x} \right )$
由于 $\hat{x}$ 是局部最小值，因此存在邻域 $N_\varepsilon \left ( \hat{x} \right )$ 使得 $f\left ( \hat{x} \right )\leq f \left ( x \right ), \forall x \in N_\varepsilon \left ( \hat{x} \right )\cap S$
但 $f\left ( x \right )$ 是 S 上的凸函数，因此对于 $\lambda \in \left ( 0, 1 \right )$
我们有 $\lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}\leq \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \right )f\left ( \bar{x} \right )$
$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< \lambda f\left ( \hat{x} \right )+\left ( 1-\lambda \右 )f\左 (\hat{x} \右 )$
$\Rightarrow \lambda \hat{x}+\left ( 1-\lambda \right )\bar{x}< f\left (\hat{x} \right ), \forall \lambda \in \left ( 0 ,1 \右)$
但对于一些 $\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 ( \bar{x} \right )$
这是一个矛盾。
因此，$\bar{x}$ 是全局最小值。
铭文
设 S 为 $\mathbb{R}^n$ 中的非空子集，并令 $f:S \rightarrow \mathbb{R}$ 则由 epi(f) 或 $E_f$ 表示的 f 的铭文是一个子集$\mathbb{R}^n+1$ 的定义为 $E_f=\left \{ \left ( x,\alpha \right ):x \in \mathbb{R}^n, \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=\left \{ \left ( x, \alpha \right ):x \in \mathbb{R}^n, \alpha \in \mathbb{R}^n, \alpha \in \mathbb{R}, f\left ( x \right )\geq \alpha \right \}$
定理
设 S 为 $\mathbb{R}^n$ 中的非空凸集，并设 $f:S \rightarrow \mathbb{R}^n$，则 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 )$
在 E_f$ 中显示 $\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 \右)$
$\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 \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 \右）$
设 $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\左 ( x_2 \右 )\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 \右)$