凸函数

作者: 微斯人_吾谁与归 | 来源:发表于2019-05-20 19:53 被阅读0次

Convex Relaxation, Convex Conjug
最优化理论
凸函数
凸函数
凸函数
2019-02-25
Expectation Maximum Algorithm(EM
《模型思维》之非线性模型
微积分基础
Hoeffding 不等式

凸函数

一.基本性质和例子

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\}$ 是一个凸函数。

三.共轭函数

四.拟凸函数

五.对数-凹函数和对数-凸函数

六.关于广义不等式的凸性

Convex Relaxation, Convex Conjug
了解机器学习的人应该都知道，在优化非凸函数的时候，希望用一个凸函数来代替这个非凸函数，以获取凸函数在优化过程中良好...
最优化理论
凸函数若函数满足其中，，则称是凸函数。可以是多元函数。 Jensen不等式若为凸函数，则对于任意点集，若，【...
凸函数
凸集：如果集合中任意2个元素连线上的点也在集合中，那么这个集合就是凸集。显然，上图中的左图是一个凸集，上图中的右...
凸函数
定义凸函数： f(x)对于定义域S（凸集）上任意两点,如果,则称f是凸的。强凸函数: 函数f可微，若对任意x,...
凸函数
凸函数一.基本性质和例子 1.定义定义一：函数f:是凸的，如果是凸集，且对于任意的和任意的0，有。定义二：函...
2019-02-25
@[TOC](2.25机器学习数学基础笔记之二) 1. 凸函数的判定（开口往上凸函数开口往下凹函数） ![在这里...
Expectation Maximum Algorithm(EM
1. 预备知识 1.1 凸函数的性质假设定义在实数域上的函数，对于任意的实数，都有则函数称为凸函数，反之，为凹...
《模型思维》之非线性模型
非线性函数可以向下或向上弯曲，可以形成S形，还可以扭结、跳跃和波动。一、凸函数凸函数的斜率是递增的：函数值随度量...
微积分基础
写在前面知识点函数导数微积分偏导数凸函数定义凸函数的性质泰勒展开式泰勒公式的应用泰勒公式的推导总结...
Hoeffding 不等式
基础准备 1.定比分点公式点为上一点，则设，则证明： 2.凸函数性质设，为凸函数，则 3.markov不等式...

凸函数

凸函数

一.基本性质和例子

1.定义

2.拓展值延伸

3.一阶条件

4.二阶条件

5.例子

二.保凸运算

1.非负加权和

2.复合仿射映射

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

三.共轭函数

四.拟凸函数

五.对数-凹函数和对数-凸函数

六.关于广义不等式的凸性

相关文章

Convex Relaxation, Convex Conjug

最优化理论

凸函数

凸函数

凸函数

2019-02-25

Expectation Maximum Algorithm(EM

《模型思维》之非线性模型

微积分基础

Hoeffding 不等式

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

凸函数

凸函数

一.基本性质和例子

1.定义

2.拓展值延伸

3.一阶条件

4.二阶条件

5.例子

二.保凸运算

1.非负加权和

2.复合仿射映射

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

三.共轭函数

四.拟凸函数

五.对数-凹函数 和 对数-凸函数

六.关于广义不等式的凸性

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

五.对数-凹函数和对数-凸函数