凹函数是一种实值函数:在任意两点的加权平均处,其函数值不小于这两点的函数值按相同权重求得的加权平均。从几何上看,连接其图像上任意两点的线段,都位于图像上或图像下方。凹性与凸性通过符号反转相互对应:f 为凹函数,当且仅当 −f 为凸函数。凹性是优化、概率论、经济学和数学分析中的核心概念。
定义
设 C 是实向量空间中的一个凸集。若对任意 x,y∈C 和任意 t∈[0,1],都有
f((1−t)x+ty)≥(1−t)f(x)+tf(y),
则称函数 f:C→R 为凹函数。
要求 C 为凸集,是为了保证 (1−t)x+ty 属于定义域。
更一般地,上述两点不等式意味着,对于任意有限个点 x1,…,xm∈C 以及满足 ∑iλi=1 的非负权重 λ1,…,λm,都有
f(i=1∑mλixi)≥i=1∑mλif(xi).
左侧函数的自变量是这些点的凸组合。因此,凹性意味着先取平均再求函数值,所得结果不小于先求函数值再取平均的结果。
凹性描述的是函数的形状,而不是函数的增减性。凹函数可以递增、递减,也可以在定义域的一部分上递增,在另一部分上递减。
严格凹性
如果只要 x=y 且 0<t<1,就有
f((1−t)x+ty)>(1−t)f(x)+tf(y),
则称该函数为严格凹函数。
严格凹性排除了图像中一切非平凡的直线段。仿射映射,例如 f(x)=aTx+b,既是凹函数,也是凸函数,但在任何包含两个不同点的定义域上都不是严格凹函数。
强凹性
在欧几里得空间的凸子集上,如果对所有符合条件的 x,y,t,都有
f((1−t)x+ty)≥(1−t)f(x)+tf(y)+2μt(1−t)∥x−y∥2,
则称 f 为参数为 μ>0 的强凹函数,其中 ∥⋅∥ 为欧几里得范数。
等价地,函数
x⟼f(x)+2μ∥x∥2
为凹函数。强凹性为函数图像与其弦之间的差距提供了一个统一的二次下界。强凹性蕴含严格凹性,但严格凹性未必蕴含强凹性。
几何刻画
弦与下图集
对于一元函数,凹性意味着图像的每一条弦,在两个端点之间都位于图像上或图像下方。
在任意维度中,f 的**下图集**定义为
hypof={(x,r):x∈C, r≤f(x)}.
一个函数为凹函数,当且仅当其下图集是凸集。这一刻画完全通过集合的几何性质来描述凹性,不要求函数可微。
切平面上界
设 f 在 Rn 的一个开凸子集上可微。那么,f 为凹函数,当且仅当对其定义域中的任意 x,y,都有
f(y)≤f(x)+∇f(x)T(y−x),
其中 ∇f(x) 是其梯度。
因此,任意一点处的切仿射函数都是全局上界。这与凸函数的切平面下界性质相反。
对于不可微的函数,若向量 g 满足
f(y)≤f(x)+gT(y−x)for all y∈C,
则称其为 x 处的**超梯度**。对于有限维凸定义域上的有限值凹函数,在定义域相对内部的每一点处,都存在支撑仿射上界;边界点处是否存在这样的上界,则需要额外考察。
导数判别法
一元函数
开区间上的可微函数为凹函数,当且仅当其导数单调不增。如果该函数二阶可微,这又等价于在整个区间上都有
f′′(x)≤0.
若在整个区间上满足更强的条件
f′′(x)<0,
则可保证严格凹性,但这并非严格凹性的必要条件。例如,f(x)=−x4 在 R 上严格凹,尽管 f′′(0)=0。
也可以不借助导数来描述凹性。对于定义域中满足 a<b<c 的点,有
b−af(b)−f(a)≥c−af(c)−f(a)≥c−bf(c)−f(b).
这些不等式表明,随着区间向右移动,割线斜率逐渐减小。
多元函数
对于 Rn 的开凸子集上的二阶连续可微函数,凹性等价于其海森矩阵处处为半负定矩阵:
vT∇2f(x)v≤0for every v∈Rn.
等价地,海森矩阵的每个特征值都非正。
海森矩阵处处负定,可以保证严格凹性。与一维情形一样,这一条件是充分条件,但不是必要条件。
在相同的光滑性假设下,参数为 μ 的强凹性等价于对所有 x 和 v,都有
vT∇2f(x)v≤−μ∥v∥2.
如果定义域位于一个较低维的仿射子空间中,则相关曲率条件只需沿平行于该子空间的方向成立。
例子
对数。 自然对数在 (0,∞) 上严格凹,因为
dx2d2logx=−x21<0.
它在整个正半轴上并非强凹,因为当 x→∞ 时,这一曲率趋于零。
分数次幂。 当 0<α<1 时,函数 f(x)=xα 在 [0,∞) 上严格凹。平方根函数就是一个常见的例子。
负二次函数。 若 Q 是对称半正定矩阵,则
f(x)=−21xTQx+bTx+c
为凹函数。若 Q 为正定矩阵,则该函数为强凹函数,其参数可取为 Q 的最小特征值。
绝对值的负值。 函数 f(x)=−∣x∣ 在 R 上为凹函数,但它在零点不可微,在整个定义域上也不是严格凹函数。
坐标的最小值。 函数
f(x1,…,xn)=min{x1,…,xn}
为凹函数,在多个坐标同时取得最小值的点处通常不可微。
熵。 对于有限维概率向量 p=(p1,…,pn),香农信息熵
H(p)=−i=1∑npilogpi,
其中约定 0log0=0,在概率单纯形上严格凹。
保持凹性的运算与正则性质
多种运算都能保持凹性:
- 凹函数以非负系数加权求和,所得函数仍为凹函数。
- 加上仿射函数后,凹性保持不变。
- 将凹函数与仿射映射复合,所得函数在相应的凸定义域上仍为凹函数。
- 若 g 为凹函数且单调不减,f 也为凹函数,则 g∘f 在复合有定义的范围内为凹函数。
- 在同一个凸定义域上,一族凹函数的逐点下确界仍为凹函数,前提是该下确界在此定义域上处处取有限值。
相比之下,凹函数的逐点最大值未必为凹函数。例如,x 和 −x 都是凹函数,但它们的最大值 ∣x∣ 不是凹函数。凹函数的乘积通常也不保持凹性。
有限维凸定义域上的有限值凹函数,在定义域的相对内部是连续的,并且在那里局部满足 Lipschitz 条件。仅凭凹性无法保证边界点处的连续性。例如,在 [0,1] 上定义的函数
f(0)=0,f(x)=1for 0<x≤1
为凹函数,但在零点不连续。
詹森不等式
詹森不等式将有限加权平均不等式推广到概率分布。若 X 是取值于凸定义域的可积随机向量,且相关期望均为有限值,则
f(E[X])≥E[f(X)].
这里,E 表示期望值。该不等式比较了均值处的函数值与函数值的均值。
若 f 严格凹,则等号成立仅当 X 几乎必然为常量。对于一般的凹函数,如果分布的支撑位于函数呈仿射性的区域中,也可能出现等号。
对于对数函数,其有限形式为
log(i∑λixi)≥i∑λilogxi,
两边取指数后,即得到加权算术—几何平均不等式。
在优化中的作用
在凸可行集上最大化凹目标函数,是凸优化的一种标准形式,因为这等价于最小化凸函数 −f。
凹性提供了若干重要保证:
- 每个局部最大值都是全局最大值。
- 最大值点的集合是凸集。
- 严格凹函数在凸定义域上至多有一个最大值点。
- 对于可微凹函数,梯度为零的内点必为全局最大值点。
更一般地,若可行点 x∗ 满足
∇f(x∗)T(y−x∗)≤0for all feasible y,
则它是全局最大值点。
这些结论并不保证最大值点存在。例如,logx 在 (0,∞) 上为凹函数,但无上界。根据极值定理,非空紧可行集上的连续函数一定能取得最大值。
强凹性还给出了定量界。对于可微的 μ-强凹函数,若 x∗ 是其无约束最大值点,则
f(x∗)−f(x)≥2μ∥x−x∗∥2.
因此,较小的目标函数值差距,可以给出到最优解距离的上界。
应用与相关概念
在经济学中,凹效用函数用于刻画边际效用递减:在导数存在的地方,边际效用不会随着消费量增加而上升。在期望效用模型中,凹性还通过詹森不等式导出体现风险厌恶的不等式。
在最大似然估计中,某些统计模型的对数似然函数是凹函数。当这一性质在凸参数域上成立时,便能简化优化过程,并排除非全局的局部最大值。对数似然的凹性取决于具体模型,并非似然函数普遍具有的性质。
在信息论中,熵的凹性描述了混合概率分布的效果:混合分布的熵,不小于各组成分布的熵按相应权重求得的平均值。
一个相关但更弱的性质是**拟凹性**。若函数满足
f((1−t)x+ty)≥min{f(x),f(y)},
则称其为拟凹函数。
等价地,其所有上水平集都是凸集。每个凹函数都是拟凹函数,但反过来不成立。例如,R 上的指数函数由于单调递增而具有拟凹性,但它是严格凸函数,而不是凹函数。凹性对线段上各点的函数值施加了定量约束,而拟凹性仅约束上水平集的几何形状。