首页 » 学习 » 凸函数的基本性质和例子

凸函数的基本性质和例子

  1. 定义
  2. 扩展值延伸(extended-value extension)
  3. 一阶条件(first-order condition)
  4. 二阶条件(second-order condition)
  5. 典型凸函数
  6. 下水平集(sublevel set)
  7. 上镜图(epigraph)
  8. Jensen不等式及其拓展形式
  9. 其他类型的不等式
  10. 参考

1 定义

如果函数f:R^n\rightarrow R的定义域和值域都是凸集,而且对任意\theta\in[0,1]都满足f(\theta x+(1-\theta)y)\leqslant\theta f(x)+(1-\theta)f(y)那么称函数f是一个凸函数(convex function)。如果将上式中的小于等于修改为小于,定义域内任意不等的x和y仍然满足,那么称函数f是一个严格凸函数(strictly convex function)。

形象的理解凸函数就是任取定义域内两点x_1,x_2,那么(x_1,f(x_1)),(x_2,f(x_2))的连线在区间(x_1,x_2)所对应的函数值上。所以凸函数是我们通常意义上的凹。

如果-f为凸函数,那么函数f为凹函数。如果-f为严格凸函数,那么函数f为严格凹函数。

2 扩展值延伸(extended-value extension)

如果f为凸函数,那么通过下式定义扩展值延伸\tilde{f}:R^n\rightarrow R \cup\{\infty\}:
\tilde{f}(x)=\begin{cases}f(x) &x\in \mathbf{dom}f\\ \infty &x\notin\mathbf{dom}f\end{cases}
也就是如果在f定义域内则\tilde{f}函数值与f相同,如果不在f定义域内则\tilde{f}函数值为无穷。

使用扩展值延伸的好处是函数计算时不需要考虑定义域。考虑f=f_1+f_2,那么\mathbf{dom}f=\mathbf{dom}f_1\cup\mathbf{dom}f_2。但是如果使用扩展值延伸则任意x都在定义域内.即使不在f_1,f_2定义域的x仍然在\cup{f}的定义域内,只不过函数值为无穷。

3 一阶条件(first-order condition)

如果函数f是可微的,那么它是凸函数的充要条件是它的定义域为凸集且满足f(y)\geqslant f(x)+\triangledown f(x)^T(y-x)其中x,y是定义域内任意的两个点。如果式中为严格大于那么将会对应严格凸函数的充要条件。同样,也可以死用类似的方法判断凹函数和严格凹函数。

4 二阶条件(second-order condition)

如果函数f二阶可微,那么f是凸函数的充要条件是对于定义域为凸集,且定义域内任意x都满足\triangledown^2f(x)\succeq0二阶微分有时还被称为Hessian derivative。类似的,如果\triangledown^2f(x)\succ 0则f为严格凸函数,\triangledown^2f(x)\preceq0则f为凹函数,\triangledown^2f(x)\prec则f为严格凹函数。

5 典型凸函数

本节将给出一些典型的凸函数,受篇幅限制不予证明。首先给出一些值域为实数的凸函数:

  • 指数函数(exponential):e^{ax},x\in R,a\in R
  • 幂函数(power):x^a,x\in R_{++}a\in (-\infty,0]\cup[1,\infty)上为凸函数,在a\in[0,1]上为凹函数
  • 绝对值幂函数(power of absolute calue):\mid x \mid^p,p\geqslant1,x\in R
  • 对数函数(logarithm):\text{log} x,x\in R_++
  • 负熵(negative entropy):x\text{log}x,x\in R_{++}\text{ or }x\in R_+\text{ and defined as 0 for }x=0

这些函数计算二阶导大于零就可以证明他们是凸函数。还有些值域在R^n上的凸函数:

  • 范数(Norm):R^n上所有的范数都是凸函数
  • 最大值函数(max function):f(x)=max\{x_1,\ldots,x_n\}R^n上是凸函数
  • 二次线性分式函数(Quadratic-over-llinear function):函数f(x,y)=x^2/y\mathbf{dom}f=R\times R_{++}={(x,y)\in R^2\mid y>0}是凸函数
  • 指数和的对数(log-sum-exp):f(x)=log(e^{x^1}+\cdots+e^{x^n})R^n上是凸函数
  • 几何平均(Geometric mean):(\textstyle \prod_{i=1}^nx_i)^{1/n}R_{++}^n上为凸函数
  • 对数行列式(log-determinant):f(X)=\text{ log det }XS_{++}^n上为凸函数。S_{++}^nn\times n的对称正定矩阵

6 下水平集(sublevel set)

\alpha\text{-下水平集}f:R^n\rightarrow R定义为C_\alpha=\{x\in\mathbf{dom}f\mid f(x)\leqslant\alpha\}即函数值小于alpha的集合。一个凸函数的任意alpha下水平集都是凸的,但不能反过来使用,也就是任意下水平集都是凸的不能说明函数是凸函数(例如f(x)=-e^x)。

如果函数f是凹函数,那么它的上水平集(\{x\in\mathbf{dom}f\mid f(x)\geqslant \alpha \})是一个凸集。

7 上镜图(epigraph)

函数f:R^n\rightarrow R的图像(graph)定义为\{(x,f(x))\mid x\in \mathbf{dom}f\}函数f的上镜图定义为\mathbf{epi}f=\{(x,t)\mid x\in \mathbf{dom}f,f(x)\leqslant t\}通俗的说上镜图就是函数图像以上的部分。与上镜图对应的是亚图(hypograph):\mathbf{hypo}f=\{(x,t)\mid t \leqslant f(x)\}一个函数是凸函数的充要条件是它的上镜图是一个凸集,是凹函数的充要条件是它的亚图是一个凸集。

8 Jensen不等式及其拓展形式

本文开头的用于定义凸函数的不等式也被成为Jensen不等式f(\theta x+(1-\theta)y)\leqslant\theta f(x)+(1-\theta)f(y)如果函数f为凸函数,那么我们可以将两个点扩展到k个点:x_1,\ldots,x_k\in \mathbf{dom}f,\theta_1,\ldots,\theta_k\geqslant 0,\theta_1+\cdots+\theta_k=1,那么有f(\theta_1x_1+\cdots+\theta_kx_k)\leqslant\theta_1f(x_1)+\cdots+\theta_kf(x_k)我们可以进一步扩展到无限个点,这时求和变为积分:f(\int_Sp(x)xdx)\leqslant\int_Sf(x)p(x)dx如果x\in f(x)是一个随机数,f是一个凸函数,那么有 f(\mathbf{E}x)\leqslant\mathbf{E}f(x)其中\mathbf{E}表示期望。有趣的是尽管上面这些都被称为Jensen不等式,但Jensen本人研究是最简单的f(\frac{x+y}{2})\leqslant\frac{f(x)+f(y)}{2}

9 其他类型的不等式

对Jensen不等式取\theta=1/2可以得到算数几何平均值不等式(arithmetic-geometric mean inequality)\sqrt{ab}\leqslant(a+b)/2其中a,b\geqslant0。不等式两面再同时做log运算得到-log(\frac{a+b}{2})\leqslant\frac{-loga-logb}{2}下面介绍两个不那么常见的例子,Holder不等式:对p>1,1/p+1/q=1,x,y\in R^n,有\sum_{i=1}^nx_iy_i\leqslant(\sum_{i=1}^n\mid x_i\mid^p)^{1/p}(\sum_{i=1}^n\mid y_i\mid^q)^{1/q}另一个例子是形式更加通用的算数几何平均值不等式a^\theta b^{1-\theta}\leqslant \theta a+(1-\theta)b其中a,b\geqslant 0,0\leqslant\theta\leqslant1

10 参考

标签:

发表评论

电子邮件地址不会被公开。 必填项已用*标注