凸函数

2019-05-20 本文已影响0人微斯人_吾谁与归

凸函数

一.基本性质和例子

1.定义

定义一：函数f: $f : \mathbf{R}^{n} \rightarrow \mathbf{R}$ 是凸的，如果 $\operatorname{dom} f$ 是凸集，且对于任意的 $x,y \in domf$ 和任意的0 $\leqslant \theta \leqslant 1$ ，有 $f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)$ 。
定义二：函数f是凸函数，当且仅当与其定义域相交的任意函数都是凸函数。或者说，函数f是凸函数，当且仅当对于任意的 $x \in \operatorname{dom} f$ 和任意向量 $v$ ,函数 $g(t)=f(x+t v)$ 是凸函数（其定义域为 $\{t | x+t v \in \operatorname{dom} f\}$ ）
几何意义：上述不等式意味着 $和(x, f(x)) 和(y, f(y))$ 的线段，即从x到y的弦在图像上方。
严格凸：当 $x \neq y$ 且 $0<\theta<1$ 时，有 $f(\theta x+(1-\theta) y) < \theta f(x)+(1-\theta) f(y)$ 总成立。
函数f是凸函数，当-f是凹函数；f是凹函数，当-f是凸函数。

2.拓展值延伸

定义：
image.png
扩展值延伸的意义：将在函数 $f$ 定义域外的值定义为无穷大，将函数延伸至全空间 $R^n$ 上，这种延伸可以简化符号表示，且延伸后凸性不变。对于延伸函数 $\tilde{f}$ ，可以描述为：

对任意的 $x,y \in R^n$ 及 $0<\theta<1$ 有 $\tilde{f}(\theta x+(1-\theta) y) \leqslant \theta \tilde{f}(x)+(1-\theta) \tilde{f}(y)$ 。（当 $\theta=0、1$ 时，总成立）
- 当 $x,y \in \operatorname{dom} f$ 时， $\theta x+(1-\theta) y \in dom f$ ,因为 $f$ 为凸函数，上述不等式成立。
- 如果 $x,y$ 任一个在 $domf$ 外，不等式右面为正无穷，左面 $\theta x+(1-\theta) y$ 在
例子：
- 凸集的示性函数，设 $C \subseteq \mathbf{R}^{n}$ 是一个凸集，考虑凸函数 $I_{C}$ ，其定义域为C,对于所有 $x \in C$ ,有 $I_{C}(x)=0$ ，换言之，此函数在集合C上一直为零。其扩展延伸可以描述如下 $\tilde{I}_{C}(x)=\left\{\begin{array}{ll}{0} & {x \in C} \\ {\infty} & {x \not \in C}\end{array}\right.$ 。凸函数 $\tilde{I}_{C}$ 被称为集合C的示性函数。利用示性函数我们更加灵活的定义符号描述：例如求 $f(x)$ 在C上的极小值，可以描述为求极小化 $f+\tilde{I}_{C}$
- 延伸函数一定要扩展到无穷，不然无法保持凸性。

3.一阶条件

一阶条件：假设f可微（即其梯度 $\nabla f$ 在开集 $domf$ 内处处存在），则函数 $f$ 是凸函数的充分必要条件是 $domf$ 是凸集且对于任意的 $x, y \in \operatorname{dom} f$ ，下式成立 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
几何意义：
- 快照57.png
- $\nabla f(x)^{T}(y-x)$ 是仿射函数y即为函数 $f$ 在点 $x$ 附近的Taylor近似，在这里Taylor近似其实是原函数的一个全局下估计
- 极值点：如果 $\nabla f(x)=0$ ，那么对于所有的 $y \in \operatorname{dom} f$ ，存在 $f(y) \geqslant f(x)$ ，所以x是全局最小点
- 严格凸：函数f严格凸的充分必要条件是
证明：一阶条件是指在任意维凸集中均成立
- 我们首先在证明在一维的情况下成立:即可微函数 $f : \mathbf{R} \rightarrow \mathbf{R}$ 是凸函数的充分必要条件是 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
  - 必要性：
    
    首先假设f是凸函数，由凸函数的定义我们可以得到 $domf$ 是一个凸集
    
    假设 $x, y \in \operatorname{dom} f$ ，则对于任意的 $0<t \leqslant 1$ ，有 $x+t(y-x) \in \operatorname{dom} f$ ，
    
    由凸函数的定义一可得 $f(x+t(y-x)) \leqslant(1-t) f(x)+t f(y)$
    
    上式两端同除以t得 $f(y) \geqslant f(x)+\frac{f(x+t(y-x))-f(x)}{t}$
    
    因为f是可微函数，所以令 $t \rightarrow 0$ ，可得到 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
    
    (当t=0时显然成立。)
  - 充分性
    
    假设 $dom f$ 内的任意x,y在定义域中，满足 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
    
    假设 $x \neq y, 0 \leqslant \theta \leqslant 1$ ， $z=\theta x+(1-\theta) y$ 由上述不等式可得：
    
    $f(x) \geqslant f(z)+f^{\prime}(z)(x-z), \quad f(y) \geqslant f(z)+f^{\prime}(z)(y-z)$
    
    将第一个不等式同乘 $\theta$ ,第二个不等式同乘 $1-\theta$ ，并将二者相加可得：
    
    $\theta f(x)+(1-\theta) f(y) \geqslant f(z)$
    
    得证
- 下边利用定义二由一维推理一般情况：
  
  对于高维空间的函数f: $\mathbf{R}^{n} \rightarrow \mathbf{R}$ ,假设 $x, y \in \mathbf{R}^{n}$ ，构造一个一维的函数 $g(t)=f(t y+(1-t) x)$ ，
  
  此函数的导数为 $g^{\prime}(t)=\nabla f(t y+(1-t ) x )^{T}(y-x)$ 。
  - 首先假设f是凸函数，证明 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$
    
    因为f是凸函数，由定义二可得g是凸函数。
    
    由g是一个一维空间的凸函数，由第一步证明可得对于任意的， $x,y \in dom g$ 可得:
    
    $g(y) \geqslant g(x)+\nabla g(x)^{T}(y-x)$ ,
    
    取 $y=1,x=0$ ,带入 $g^{\prime}(t)=\nabla f(t y+(1-t ) x )^{T}(y-x)$ ，化简
    
    $g(1)\geqslant g(0)+\nabla g(0)$
    
    $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 。
    
    得证
  - 其次，假设若对于任意的 $x,y \in dom f$ ,有 $f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)$ 则f是一个凸函数
    
    因为 $domf$ 是一个凸集，
    
    所以对于任意的 $x,y \in domf$ ,有 $t y+(1-t) x \in \operatorname{dom} f$ ， $\tilde{t} y+(1-\tilde{t}) x \in \operatorname{dom} f$
    
    所以有 $f(t y+(1-t) x) \geqslant f(\tilde{t} y+(1-\tilde{t}) x)+\nabla f(\tilde{t} y+(1-\tilde{t}) x)^{T}(y-x)(t-\tilde{t})$
    
    化简得 $g(t) \geqslant g(\tilde{t})+g^{\prime}(\tilde{t})(t-\tilde{t})$ 。

4.二阶条件

定义：若函数 $f : \mathbf{R} \rightarrow \mathbf{R^n}$ 二阶可微，则f为凸函数的充分必要条件是：
1. $domf$ 为凸集
2. $\nabla^{2} f(x) \succeq 0$ ，对于任意的 $x \in domf$
几何意义，二阶导数大于零，曲率为正，一阶导数为增函数。为了更好理解，可以局限在一维情况下，参照一下数学分析。
证明：

书上说让自己证明哦！

显然可得。
严格凸：对于任意的 $x \in domf$ ,若 $\nabla^{2} f(x)>0$ ，则函数f是严格凸函数。

若函数f是严格凸函数，那么对于任意的 $x \in domf$ ， $\nabla^{2} f(x)>0$ 未必成立。

也就是说 $\nabla^{2} f(x)>0$ 大于零是严格凸的充分不必要条件。
- 例如：函数 $f : \mathbf{R} \rightarrow \mathbf{R}$ ， $f=x^4$ 二阶可导， $f''(x)=12x^2 \geqslant0$ ,然而从图像可知此函数还是一个严格凸函数。
例题:特殊情况：二次函数严格凸的充分必要条件是 $\nabla^{2} f(x)>0$

快照58.png

注：关于Hessian矩阵：联想一下二次型就可以理解了，特征值，特征向量。

5.例子

快照69.png

补充：

范数定义：的范数满足
1. $P(ax)=|a|P(x)$
2. $P(x+y)\leqslant P(x)+P(y)$
3. 若 $P(x)=0$ ，则 $x=0$
零范数： $非零元素的数目||x||_0=非零元素的数目$ ，不是一个凸函数。它也不满足范数定义。

二.保凸运算

1.非负加权和

非负加权和：凸函数集合本身是一个凸锥：凸函数的非负加权和任然是凸函数。若为凸 $f_1,f_2...f_m$ 为凸，则 $f(x)=\sum_{i=1}^{m} w_if_{i}（x）$ 为凸函数。其中 $w_i >=0$

证明：首先 $domf$ 为所有 $f_i$ 定义域的交集，所以定义域为凸集。其次，显然。
非负加权和拓展: 若 $f(x,y)$ 对任意固定的 $y \in A,f(x,y)$ 均为关于 $x$ 凸函数，设 $w(y)>=0$ ,那么

$g(x)=\int_{y \in A} w(y) f(x, y) d y$ 为关于x的凸函数。

2.复合仿射映射

定义:假设函数 $f : \mathbf{R}^{n} \rightarrow \mathbf{R}, A \in \mathbf{R}^{n \times m}$ ，以及 $b \in \mathbf{R}^{n}$ ，定义 $g : \mathbf{R}^{m} \rightarrow \mathbf{R}$ 为 $g(x)=f(A x+b)$ ，其中 $\operatorname{dom} g=\{x | A x+b \in \operatorname{dom} f\}$ 。若函数f是凸函数，那么g是凸函数；如果函数f是凹函数，那么函数g是凹函数。
- 证明：
  
  1.证明 $\operatorname{dom} g=\{x | A x+b \in \operatorname{dom} f\}$ 是一个凸集
  
  对于任意的 $x,y \in domg,0 \leqslant \theta \leqslant 1$ , $A(\theta x+(1-\theta )y)+b=\theta (Ax+b)+(1- \theta)(Ay+b)$ ,
  
  已知 $domf$ 是一个凸集且 $A x+b \in \operatorname{dom} f,A y+b \in \operatorname{dom} f$
  
  由凸集的定义可得 $\theta (Ax+b)+(1- \theta)(Ay+b) \in domf$
  
  所以 $\theta x+(1-\theta )y \in domg$
  
  2.证明： $g(x)=f(A x+b)$ 是凸函数。
  
  因为 $f(x)$ 是凸函数，那么可得 $f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)$
  
  $g(\theta x+(1-\theta) y) =f(A(\theta x+(1-\theta)) y+b)=f(\theta (Ax+b)+(1-\theta)(Ay+b))$
  
  $\leqslant \theta f(Ax+b)+\theta f(Ay+b)=\theta g(x)+ (1-\theta) g(y)$
  
  得证，所以复合仿射映射是一个凸函数。

3.逐点最大和逐点上确界

逐点最大和
- 定义：如果函数 $f_1$ 和 $f_2$ 均为凸函数，则二者的逐点最大函数 $f$ , $f(x)=\max \left\{f_{1}(x), f_{2}(x)\right\}$ ,定义域是 $\operatorname{dom} f=\operatorname{dom} f_{1} \cap \operatorname{dom} f_{2}$ ，仍然是个凸函数。
- 证明：任取0 $\leqslant \theta \leqslant 1$ 以及 $x, y \in \operatorname{dom} f$ ，有
  
  $\begin{aligned} f(\theta x+(1-\theta) y) &=\max \left\{f_{1}(\theta x+(1-\theta) y), f_{2}(\theta x+(1-\theta) y)\right\} \\ & \leqslant \max \left\{\theta f_{1}(x)+(1-\theta) f_{1}(y), \theta f_{2}(x)+(1-\theta) f_{2}(y)\right\} \\ & \leqslant \max \left\{\theta f_{1}(x)+\theta f_{2}(x)\right\}+ \max \left\{(1-\theta) f_{1}(y), (1-\theta)f_{2}(y)\right\} \\ & \leqslant \theta \max \left\{f_{1}(x), f_{2}(x)\right\}+(1-\theta) \max \left\{f_{1}(y), f_{2}(y)\right\} \\ &=\theta f(x)+(1-\theta) f(y) \end{aligned}$
- 例题： $f(x)=max\{x^2,x\}$
- 推广：如果函数 $f_{1}, \cdots, f_{m}$ 是凸函数，那么他们的逐点最大和 $f(x)=\max \left\{f_{1}(x), \cdots, f_{m}(x)\right\}$ 也是凸函数。
最大的r个分量之和：
- 定义：对任意 $x \in \mathbf{R}^{n}$ ，用 $x_i$ 表示 $x$ 中第i大的分量，即将 $x$ 中分量按照非降序排列得到下式： $x_{[1]} \geqslant x_{[2]} \geqslant \cdots \geqslant x_{[n]}$ ，对x中前r个大的分量进行求和得到 $f(x)=\sum_{i=1}^{r} x_{[i]}$ 是一个凸函数。
  
  此函数可以描述为 $f(x)=\sum_{i=1}^{r} x_{[i]}=\max \left\{x_{i_{1}}+\cdots+x_{i_{r}} | 1 \leqslant i_{1}<i_{2}<\cdots<i_{r} \leqslant n\right\}$
- 理解：即从 $x$ 中随机选择r个元素求和可能组合中的最大值，这种取法共有 $n ! /(r !(n-r) !)$ 可能。将每一种可能看做一个函数，那个最大的r个分量之和相当于对这 $n ! /(r !(n-r) !)$ 逐点求和。而随机取值求和函数又是关于 $x$ 的仿射映射，一定是一个凸函数，所以最大的r个分量之和也是凸函数。
- 推广： $w_{1} \geqslant w_{2} \geqslant \cdots \geqslant w_{r} \geqslant 0$ ， $\sum_{i=1}^{r} w_{i} x_{[i]}$ 也是一个凸函数
- 推广：无限个凸函数的逐点上确界：如果对任意的 $y \in \mathcal{A}$ ，函数 $f(x, y)$ 关于 $x$ 是凸的，则函数 $g(x)=\sup _{y \in \mathcal{A}} f(x, y)$ 也是凸的，定义域为 $\operatorname{dom} g=\left\{x |(x, y) \in \operatorname{dom} f \forall y \in \mathcal{A}, \sup _{y \in \mathcal{A}} f(x, y)<\infty\right\}$
实对称阵的最大特征值：

$f(X)=\lambda_{max}(X),domf=S^m$ , $y$ 是特征向量，

$Xy=\lambda y$

$y^TXy=y^T\lambda y$

$\lambda=y^TXy/||y||_2$

当 $时，||y||_2=1时，\lambda_{max}(x)=sup\{y^TXy| ||y||_2=1\}$

由上述定理可知若对于每一个y, $是一个凸函数y^TXy是一个凸函数$ ，那么 $\lambda_{max}(x)=sup\{y^TXy| ||y||_2=1\}$ 是一个凸函数。