凸函数（补）

                     

贡献者： 吴鑫

定义 1　凸集

　　 对于一个集合 $C\subseteq\mathbb{R}^n,\forall\boldsymbol{x}_1,\cdot,\boldsymbol{x}_n,\theta_k\in[0,1], \sum_{k=1}^n\theta_k=1$ 满足

\begin{equation} \theta_1\boldsymbol{x}_1+\cdots+\theta_n\boldsymbol{x}_n\in C~ \end{equation}
称 $C$ 是凸集.

定义 2　凸集

　　 对于一个集合 $C\subseteq\mathbb{R}^n,$ 存在映射 $p:\mathbb{R}^n\to\mathbb{R},p(\boldsymbol{x}),\int_Cp(\boldsymbol{x})\mathrm{d}\boldsymbol{x}=1,\forall\boldsymbol{x}\in C,$ 满足

\begin{equation} \int_C\boldsymbol{x}p(\boldsymbol{x})\mathrm{d}\boldsymbol{x}\in C~ \end{equation}
称 $C$ 是凸集.

定义 3　凸函数

　　 存在映射 $f:\mathbb{R}^n\to\mathbb{R},\mathrm{dom} f$ 是凸集合，如果 $\forall\boldsymbol{x_1},\boldsymbol{x_2}\in\mathrm{dom} f, \theta\in[0,1],$ 满足

\begin{equation} f(\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2)\leqslant\theta f(\boldsymbol{x}_1) + (1-\theta)f(\boldsymbol{x}_2)~ \end{equation}

　　 称映射 $f$ 是定义在 $\mathrm{dom} f$ 上的凸函数.如果满足

\begin{equation} f(\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2)<\theta f(\boldsymbol{x}_1) + (1-\theta)f(\boldsymbol{x}_2)~ \end{equation}
称映射 $f$ 是定义在 $\mathrm{dom} f$ 上的强凸函数.

定义 4　凹函数

　　 存在映射 $f:\mathbb{R}^n\to\mathbb{R},\mathrm{dom} f$ 是凸集合，如果 $\forall\boldsymbol{x_1},\boldsymbol{x_2}\in\mathrm{dom} f, \theta\in[0,1],$ 满足

\begin{equation} f(\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2)\geqslant\theta f(\boldsymbol{x}_1) + (1-\theta)f(\boldsymbol{x}_2)~ \end{equation}

　　 称映射 $f$ 是定义在 $\mathrm{dom} f$ 上的凹函数.如果满足

\begin{equation} f(\theta\boldsymbol{x}_1+(1-\theta)\boldsymbol{x}_2)>\theta f(\boldsymbol{x}_1) + (1-\theta)f(\boldsymbol{x}_2)~ \end{equation}
称映射 $f$ 是定义在 $\mathrm{dom} f$ 上的强凹函数.

定理 1　凸函数判定

　　 $f:\mathbb{R}^n\to\mathbb{R}$ 是凸函数，当且仅当 $g:\mathbb{R}\to\mathbb{R},g(t)=f(\boldsymbol{x}+t\boldsymbol{v}),t=\{t|\boldsymbol{x}+t\boldsymbol{v}\in\mathrm{dom} f,\boldsymbol{v}\in\mathbb{R}^n\}$ 是凸函数.

　　 证明:(1)必要性

　　 $f(\boldsymbol{x})$ 是凸函数，令 $g(t)=f(\boldsymbol{x}+t\boldsymbol{v}),$ 那么对 $\forall t_1,t_2,$ 有以下关系: $$ \begin{aligned} g\left( \theta t_1+\left( 1-\theta \right) t_2 \right) &=f\left( \boldsymbol{x}+\left( \theta t_1+\left( 1-\theta \right) t_2 \right) \boldsymbol{v} \right)\\ &=f\left( \boldsymbol{x}+\theta t_1\boldsymbol{v}+\left( 1-\theta \right) t_2\boldsymbol{v} \right)\\ &=f\left( \theta \left( \boldsymbol{x}+t_1\boldsymbol{v} \right) +\left( 1-\theta \right) \left( \boldsymbol{x}+t_2\boldsymbol{v} \right) \right) \\ &\leqslant \theta f\left( \boldsymbol{x}+t_1\boldsymbol{v} \right) +\left( 1-\theta \right) f\left( \boldsymbol{x}+t_2\boldsymbol{v} \right) =\theta g\left( t_1 \right) +\left( 1-\theta \right) g\left( t_2 \right) \end{aligned}~ $$ 由此可知，$g(t)$ 是凸函数.

　　 (2)充分性

　　 $g(t)=f(\boldsymbol{x}+t\boldsymbol{v})$ 是凸函数，因此，\forall \theta \in \left[ 0,1 \right] $$ \begin{aligned} g\left( \theta t_1+\left( 1-\theta \right) t_2 \right) &=f\left( \boldsymbol{x}+\left( \theta t_1+\left( 1-\theta \right) t_2 \right) \boldsymbol{v} \right) \\ &=f\left( \boldsymbol{x}+\theta t_1\boldsymbol{v}+\left( 1-\theta \right) t_2\boldsymbol{v} \right) =f\left( \theta \left( \boldsymbol{x}+t_1\boldsymbol{v} \right) +\left( 1-\theta \right) \left( \boldsymbol{x}+t_2\boldsymbol{v} \right) \right) \\ &\leqslant \theta g\left( t_1 \right) +\left( 1-\theta \right) g\left( t_2 \right)\\ &=\theta f\left( \boldsymbol{x}+t_1\boldsymbol{v} \right) +\left( 1-\theta \right) f\left( \boldsymbol{x}+t_2\boldsymbol{v} \right) \end{aligned}~ $$ 令 $\boldsymbol{z}_1=\boldsymbol{x}+t_1\boldsymbol{v},\boldsymbol{z}_2=\boldsymbol{x}+t_2\boldsymbol{v},$ 上述不等式等价为 $$ f\left( \theta \boldsymbol{z}_1+\left( 1-\theta \right) \boldsymbol{z}_2 \right) \leqslant \theta f\left( \boldsymbol{z}_1 \right) +\left( 1-\theta \right) f\left( \boldsymbol{z}_2 \right)~ $$ 由此可知，$f(\boldsymbol{x})$ 是凸函数.

定理 2　一阶条件

　　 假设 $f:\mathbb{R}^n\to\mathbb{R}$ 一阶可微，$f:\mathbb{R}^n\to\mathbb{R}$ 是凸函数，当且仅当

\begin{equation} f(\boldsymbol{y})\geqslant f(\boldsymbol{x})+\nabla^\top f(\boldsymbol{x})(\boldsymbol{y}-\boldsymbol{x})~ \end{equation}
对 $\forall\boldsymbol{x},\boldsymbol{y}\in\mathrm{dom} f$ 成立.

　　 证明:(1)必要性

　　 令 $\boldsymbol{z}=\theta \boldsymbol{y}+\left( 1-\theta \right) \boldsymbol{x}=\boldsymbol{x}+\theta \left( \boldsymbol{y}-\boldsymbol{x} \right),$ 由凸函数定位可知， $$ f\left( \theta \boldsymbol{y}+\left( 1-\theta \right) \boldsymbol{x} \right) =f\left( \boldsymbol{x}+\theta \left( \boldsymbol{y}-\boldsymbol{x} \right) \right) \leqslant \theta f\left( \boldsymbol{y} \right) +\left( 1-\theta \right) f\left( \boldsymbol{x} \right)~ $$ 整理得， $$ f\left( \boldsymbol{y} \right) \geqslant \frac{f\left( \boldsymbol{x}+\theta \left( \boldsymbol{y}-\boldsymbol{x} \right) \right) -\left( 1-\theta \right) f\left( \boldsymbol{x} \right)}{\theta}=f\left( \boldsymbol{x} \right) +\frac{f\left( \boldsymbol{x}+\theta \left( \boldsymbol{y}-\boldsymbol{x} \right) \right) -f\left( \boldsymbol{x} \right)}{\theta}~ $$ 让 $\theta\to 0$ 可得 $$ f\left( \boldsymbol{y} \right) \geqslant f\left( \boldsymbol{x} \right) +\lim_{\theta \rightarrow 0} \frac{f\left( \boldsymbol{x}+\theta \left( \boldsymbol{y}-\boldsymbol{x} \right) \right) -f\left( \boldsymbol{x} \right)}{\theta}=f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right)~ $$

　　 (2)充分性

　　 令 $z=\theta\boldsymbol{x}+(1-\theta)\boldsymbol{y},$ 于是可以得到 $$ f\left( \boldsymbol{x} \right) \geqslant f\left( \boldsymbol{z} \right) +\nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{x}-\boldsymbol{z} \right)~ $$ $$ f\left( \boldsymbol{y} \right) \geqslant f\left( \boldsymbol{z} \right) +\nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{y}-\boldsymbol{z} \right)~ $$ 也即是 $$ \theta f\left( \boldsymbol{x} \right) +\left( 1-\theta \right) f\left( \boldsymbol{y} \right) \geqslant \theta \left( f\left( \boldsymbol{z} \right) +\nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{x}-\boldsymbol{z} \right) \right) +\left( 1-\theta \right) \left( f\left( \boldsymbol{z} \right) +\nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{y}-\boldsymbol{z} \right) \right)~ $$ 展开得 $$ \theta f\left( \boldsymbol{x} \right) +\left( 1-\theta \right) f\left( \boldsymbol{y} \right) \geqslant \theta f\left( \boldsymbol{z} \right) +\theta \nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{x}-\boldsymbol{z} \right) +\left( 1-\theta \right) f\left( \boldsymbol{z} \right) +\left( 1-\theta \right) \nabla ^{\top}f\left( \boldsymbol{z} \right) \left( \boldsymbol{y}-\boldsymbol{z} \right)~ $$ 进一步得到 $$ \theta f\left( \boldsymbol{x} \right) +\left( 1-\theta \right) f\left( \boldsymbol{y} \right) \geqslant \nabla ^{\top}f\left( \boldsymbol{z} \right) \left[ \theta \left( \boldsymbol{x}-\boldsymbol{z} \right) +\left( 1-\theta \right) \left( \boldsymbol{y}-\boldsymbol{z} \right) \right] +f\left( \boldsymbol{z} \right)~ $$ 也即是 $$ f\left( \boldsymbol{z} \right) \leqslant \theta f\left( \boldsymbol{x} \right) +\left( 1-\theta \right) f\left( \boldsymbol{y} \right)~ $$ 即 $$ f\left( \theta \boldsymbol{x}+\left( 1-\theta \right) \boldsymbol{y} \right) \leqslant \theta f\left( \boldsymbol{x} \right) +\left( 1-\theta \right) f\left( \boldsymbol{y} \right)~ $$ 因此，$f(\boldsymbol{x})$ 是凸函数.

定理 3　二阶条件

　　 假设 $f:\mathbb{R}^n\to\mathbb{R}$ 二阶可微，$f:\mathbb{R}^n\to\mathbb{R}$ 是凸函数，当且仅当

\begin{equation} \nabla^2 f(\boldsymbol{x})\succeq 0~ \end{equation}
对 $\forall\boldsymbol{x}\in\mathrm{dom} f$ 成立.

　　 证明:(1)必要性

　　 由函数的泰勒展开, $$ f\left( \boldsymbol{y} \right) =f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +\frac{1}{2}\left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +o\left( \left\| \boldsymbol{y}-\boldsymbol{x} \right\| ^2 \right)~ $$ 再由定理 2 可知, $$ f\left( \boldsymbol{y} \right) \geqslant f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right)~ $$ 于是可得, $$ f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +\frac{1}{2}\left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +o\left( \left\| \boldsymbol{y}-\boldsymbol{x} \right\| ^2 \right) \geqslant f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right)~ $$ 因此, $$ \frac{1}{2}\left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +o\left( \left\| \boldsymbol{y}-\boldsymbol{x} \right\| ^2 \right) \geqslant 0~ $$ 也即 $$ \left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) \geqslant 0~ $$ 由此可知 $$ \nabla ^2f\left( \boldsymbol{x} \right) \succeq 0~ $$

　　 (2)充分性

　　 由函数的泰勒展开, $$ f\left( \boldsymbol{y} \right) =f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +\frac{1}{2}\left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +o\left( \left\| \boldsymbol{y}-\boldsymbol{x}\right\| ^2 \right)~ $$ 由 $\nabla ^2f\left( \boldsymbol{x} \right) \succeq$,因此 $$ \left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) \geqslant 0~ $$ 也即 $$ f\left( \boldsymbol{y} \right) =f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +\frac{1}{2}\left( \boldsymbol{y}-\boldsymbol{x} \right) ^{\top}\nabla ^2f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right) +o\left( \left\| \boldsymbol{y}-\boldsymbol{x} \right\| ^2 \right) \geqslant f\left( \boldsymbol{x} \right) +\nabla ^{\top}f\left( \boldsymbol{x} \right) \left( \boldsymbol{y}-\boldsymbol{x} \right)~ $$ 由定理 2 可知，$f(\boldsymbol{x})$ 是凸函数.

习题 1　判断下列函数的凹凸性

  1. $f(\boldsymbol{x})=\max\{x_1,\cdots,x_n\}$
  2. $f(\boldsymbol{x})=\min\{x_1,\cdots,x_n\}$
  3. $f\left( \boldsymbol{x} \right) =\frac{1}{2}\boldsymbol{x}^{\top}P\boldsymbol{x}+\boldsymbol{q}^{\top}\boldsymbol{x}+r,P\succeq 0$
  4. $f\left( \boldsymbol{x} \right) =\left\| A\boldsymbol{x}-b \right\| _{2}^{2},A\in \mathbb{R} ^{m\times n}$
  5. $f\left( \boldsymbol{x} \right) =\log \sum_{k=1}^n{\exp \,x_k}$
  6. $f\left( \boldsymbol{x} \right) =\prod_{k=1}^n{\left( x_k \right) ^{\frac{1}{n}}}$

习题 2　

　　 存在映射 $f:\mathbb{R}^n\to\mathbb{R}$,另有映射 $g:\mathbb{R}^m\to\mathbb{R}$,且 $g(\boldsymbol{x})=f(A\boldsymbol{x}+\boldsymbol{b})$,其中 $A\in\mathbb{R}^{n\times m},\boldsymbol{b}\in\mathbb{R}^m$,证明 $f$ 和 $g$ 的凸凹性一致.

                     

© 小时科技 保留一切权利