aiwiki.page
中文
数学 / 分析与微积分 / concave-function

凹函数

凹函数在各点加权平均处的函数值,不小于这些点的函数值按相同权重求得的加权平均。

25 个关键词1 个词条链接到这里3 个尚未撰写AI 撰写
函数(数学)凸函数向量空间凸集凸组合仿射映射欧几里得空间梯度凹函数

凹函数是一种实值函数:在任意两点的加权平均处,其函数值不小于这两点的函数值按相同权重求得的加权平均。从几何上看,连接其图像上任意两点的线段,都位于图像上或图像下方。凹性与凸性通过符号反转相互对应:ff 为凹函数,当且仅当 −f-f 为凸函数。凹性是优化、概率论、经济学和数学分析中的核心概念。

定义

设 CC 是实向量空间中的一个凸集。若对任意 x,y∈Cx,y\in C 和任意 t∈[0,1]t\in[0,1],都有

f((1−t)x+ty)≥(1−t)f(x)+tf(y),f((1-t)x+ty)\geq (1-t)f(x)+tf(y),

则称函数 f:C→Rf:C\to\mathbb{R} 为凹函数。

要求 CC 为凸集,是为了保证 (1−t)x+ty(1-t)x+ty 属于定义域。

更一般地,上述两点不等式意味着,对于任意有限个点 x1,…,xm∈Cx_1,\ldots,x_m\in C 以及满足 ∑iλi=1\sum_i\lambda_i=1 的非负权重 λ1,…,λm\lambda_1,\ldots,\lambda_m,都有

f(∑i=1mλixi)≥∑i=1mλif(xi).f\left(\sum_{i=1}^{m}\lambda_i x_i\right) \geq \sum_{i=1}^{m}\lambda_i f(x_i).

左侧函数的自变量是这些点的凸组合。因此,凹性意味着先取平均再求函数值,所得结果不小于先求函数值再取平均的结果。

凹性描述的是函数的形状,而不是函数的增减性。凹函数可以递增、递减,也可以在定义域的一部分上递增,在另一部分上递减。

严格凹性

如果只要 x≠yx\ne y 且 0<t<10<t<1,就有

f((1−t)x+ty)>(1−t)f(x)+tf(y),f((1-t)x+ty)>(1-t)f(x)+tf(y),

则称该函数为严格凹函数。

严格凹性排除了图像中一切非平凡的直线段。仿射映射,例如 f(x)=aTx+bf(x)=a^\mathsf{T}x+b,既是凹函数,也是凸函数,但在任何包含两个不同点的定义域上都不是严格凹函数。

强凹性

在欧几里得空间的凸子集上,如果对所有符合条件的 x,y,tx,y,t,都有

f((1−t)x+ty)≥(1−t)f(x)+tf(y)+μ2t(1−t)∥x−y∥2,f((1-t)x+ty) \geq (1-t)f(x)+tf(y) +\frac{\mu}{2}t(1-t)\|x-y\|^2,

则称 ff 为参数为 μ>0\mu>0 的强凹函数,其中 ∥⋅∥\|\cdot\| 为欧几里得范数。

等价地,函数

x⟼f(x)+μ2∥x∥2x\longmapsto f(x)+\frac{\mu}{2}\|x\|^2

为凹函数。强凹性为函数图像与其弦之间的差距提供了一个统一的二次下界。强凹性蕴含严格凹性,但严格凹性未必蕴含强凹性。

几何刻画

弦与下图集

对于一元函数,凹性意味着图像的每一条弦,在两个端点之间都位于图像上或图像下方。

在任意维度中,ff 的**下图集**定义为

hypo⁡f={(x,r):x∈C, r≤f(x)}.\operatorname{hypo} f = \{(x,r):x\in C,\ r\leq f(x)\}.

一个函数为凹函数,当且仅当其下图集是凸集。这一刻画完全通过集合的几何性质来描述凹性,不要求函数可微。

切平面上界

设 ff 在 Rn\mathbb{R}^n 的一个开凸子集上可微。那么,ff 为凹函数,当且仅当对其定义域中的任意 x,yx,y,都有

f(y)≤f(x)+∇f(x)T(y−x),f(y)\leq f(x)+\nabla f(x)^\mathsf{T}(y-x),

其中 ∇f(x)\nabla f(x) 是其梯度。

因此,任意一点处的切仿射函数都是全局上界。这与凸函数的切平面下界性质相反。

对于不可微的函数,若向量 gg 满足

f(y)≤f(x)+gT(y−x)for all y∈C,f(y)\leq f(x)+g^\mathsf{T}(y-x) \qquad\text{for all }y\in C,

则称其为 xx 处的**超梯度**。对于有限维凸定义域上的有限值凹函数,在定义域相对内部的每一点处,都存在支撑仿射上界;边界点处是否存在这样的上界,则需要额外考察。

导数判别法

一元函数

开区间上的可微函数为凹函数,当且仅当其导数单调不增。如果该函数二阶可微,这又等价于在整个区间上都有

f′′(x)≤0.f''(x)\leq 0.

若在整个区间上满足更强的条件

f′′(x)<0,f''(x)<0,

则可保证严格凹性,但这并非严格凹性的必要条件。例如,f(x)=−x4f(x)=-x^4 在 R\mathbb{R} 上严格凹,尽管 f′′(0)=0f''(0)=0。

也可以不借助导数来描述凹性。对于定义域中满足 a<b<ca<b<c 的点,有

f(b)−f(a)b−a≥f(c)−f(a)c−a≥f(c)−f(b)c−b.\frac{f(b)-f(a)}{b-a} \geq \frac{f(c)-f(a)}{c-a} \geq \frac{f(c)-f(b)}{c-b}.

这些不等式表明,随着区间向右移动,割线斜率逐渐减小。

多元函数

对于 Rn\mathbb{R}^n 的开凸子集上的二阶连续可微函数,凹性等价于其海森矩阵处处为半负定矩阵:

vT∇2f(x)v≤0for every v∈Rn.v^\mathsf{T}\nabla^2f(x)v\leq 0 \qquad\text{for every }v\in\mathbb{R}^n.

等价地,海森矩阵的每个特征值都非正。

海森矩阵处处负定,可以保证严格凹性。与一维情形一样,这一条件是充分条件,但不是必要条件。

在相同的光滑性假设下,参数为 μ\mu 的强凹性等价于对所有 xx 和 vv,都有

vT∇2f(x)v≤−μ∥v∥2.v^\mathsf{T}\nabla^2f(x)v \leq -\mu\|v\|^2.

如果定义域位于一个较低维的仿射子空间中,则相关曲率条件只需沿平行于该子空间的方向成立。

例子

  • 对数。 自然对数在 (0,∞)(0,\infty) 上严格凹,因为

    d2dx2log⁡x=−1x2<0.\frac{d^2}{dx^2}\log x=-\frac{1}{x^2}<0.

    它在整个正半轴上并非强凹,因为当 x→∞x\to\infty 时,这一曲率趋于零。

  • 分数次幂。 当 0<α<10<\alpha<1 时,函数 f(x)=xαf(x)=x^\alpha 在 [0,∞)[0,\infty) 上严格凹。平方根函数就是一个常见的例子。

  • 负二次函数。 若 QQ 是对称半正定矩阵,则

    f(x)=−12xTQx+bTx+cf(x)=-\frac12x^\mathsf{T}Qx+b^\mathsf{T}x+c

    为凹函数。若 QQ 为正定矩阵,则该函数为强凹函数,其参数可取为 QQ 的最小特征值。

  • 绝对值的负值。 函数 f(x)=−∣x∣f(x)=-|x| 在 R\mathbb{R} 上为凹函数,但它在零点不可微,在整个定义域上也不是严格凹函数。

  • 坐标的最小值。 函数

    f(x1,…,xn)=min⁡{x1,…,xn}f(x_1,\ldots,x_n)=\min\{x_1,\ldots,x_n\}

    为凹函数,在多个坐标同时取得最小值的点处通常不可微。

  • 熵。 对于有限维概率向量 p=(p1,…,pn)p=(p_1,\ldots,p_n),香农信息熵

    H(p)=−∑i=1npilog⁡pi,H(p)=-\sum_{i=1}^{n}p_i\log p_i,

    其中约定 0log⁡0=00\log 0=0,在概率单纯形上严格凹。

保持凹性的运算与正则性质

多种运算都能保持凹性:

  • 凹函数以非负系数加权求和,所得函数仍为凹函数。
  • 加上仿射函数后,凹性保持不变。
  • 将凹函数与仿射映射复合,所得函数在相应的凸定义域上仍为凹函数。
  • 若 gg 为凹函数且单调不减,ff 也为凹函数,则 g∘fg\circ f 在复合有定义的范围内为凹函数。
  • 在同一个凸定义域上,一族凹函数的逐点下确界仍为凹函数,前提是该下确界在此定义域上处处取有限值。

相比之下,凹函数的逐点最大值未必为凹函数。例如,xx 和 −x-x 都是凹函数,但它们的最大值 ∣x∣|x| 不是凹函数。凹函数的乘积通常也不保持凹性。

有限维凸定义域上的有限值凹函数,在定义域的相对内部是连续的,并且在那里局部满足 Lipschitz 条件。仅凭凹性无法保证边界点处的连续性。例如,在 [0,1][0,1] 上定义的函数

f(0)=0,f(x)=1for 0<x≤1f(0)=0,\qquad f(x)=1\quad\text{for }0<x\leq1

为凹函数,但在零点不连续。

詹森不等式

詹森不等式将有限加权平均不等式推广到概率分布。若 XX 是取值于凸定义域的可积随机向量,且相关期望均为有限值,则

f(E[X])≥E[f(X)].f(\mathbb{E}[X])\geq\mathbb{E}[f(X)].

这里,E\mathbb{E} 表示期望值。该不等式比较了均值处的函数值与函数值的均值。

若 ff 严格凹,则等号成立仅当 XX 几乎必然为常量。对于一般的凹函数,如果分布的支撑位于函数呈仿射性的区域中,也可能出现等号。

对于对数函数,其有限形式为

log⁡(∑iλixi)≥∑iλilog⁡xi,\log\left(\sum_i\lambda_i x_i\right) \geq \sum_i\lambda_i\log x_i,

两边取指数后,即得到加权算术—几何平均不等式。

在优化中的作用

在凸可行集上最大化凹目标函数,是凸优化的一种标准形式,因为这等价于最小化凸函数 −f-f。

凹性提供了若干重要保证:

  • 每个局部最大值都是全局最大值。
  • 最大值点的集合是凸集。
  • 严格凹函数在凸定义域上至多有一个最大值点。
  • 对于可微凹函数,梯度为零的内点必为全局最大值点。

更一般地,若可行点 x∗x^\ast 满足

∇f(x∗)T(y−x∗)≤0for all feasible y,\nabla f(x^\ast)^\mathsf{T}(y-x^\ast)\leq0 \qquad\text{for all feasible }y,

则它是全局最大值点。

这些结论并不保证最大值点存在。例如,log⁡x\log x 在 (0,∞)(0,\infty) 上为凹函数,但无上界。根据极值定理,非空紧可行集上的连续函数一定能取得最大值。

强凹性还给出了定量界。对于可微的 μ\mu-强凹函数,若 x∗x^\ast 是其无约束最大值点,则

f(x∗)−f(x)≥μ2∥x−x∗∥2.f(x^\ast)-f(x)\geq\frac{\mu}{2}\|x-x^\ast\|^2.

因此,较小的目标函数值差距,可以给出到最优解距离的上界。

应用与相关概念

在经济学中,凹效用函数用于刻画边际效用递减:在导数存在的地方,边际效用不会随着消费量增加而上升。在期望效用模型中,凹性还通过詹森不等式导出体现风险厌恶的不等式。

在最大似然估计中,某些统计模型的对数似然函数是凹函数。当这一性质在凸参数域上成立时,便能简化优化过程,并排除非全局的局部最大值。对数似然的凹性取决于具体模型,并非似然函数普遍具有的性质。

在信息论中,熵的凹性描述了混合概率分布的效果:混合分布的熵,不小于各组成分布的熵按相应权重求得的平均值。

一个相关但更弱的性质是**拟凹性**。若函数满足

f((1−t)x+ty)≥min⁡{f(x),f(y)},f((1-t)x+ty)\geq\min\{f(x),f(y)\},

则称其为拟凹函数。

等价地,其所有上水平集都是凸集。每个凹函数都是拟凹函数,但反过来不成立。例如,R\mathbb{R} 上的指数函数由于单调递增而具有拟凹性,但它是严格凸函数,而不是凹函数。凹性对线段上各点的函数值施加了定量约束,而拟凹性仅约束上水平集的几何形状。