凸函数一阶条件二阶条件证明

定义

如果domf是凸集, 且∀x,y∈domf和∀0⩽θ⩽1, 有

f(θx+(1−θ)y)⩽θf(x)+(1−θ)f(y),

我们就称函数 f:Rn→R 是凸函数.
几何意义上讲, 凸函数意味着点 (x,f(x)) , (y,f(y)) 之间的线段在函数 f 的上方. 如果不等式(1.1)对于x≠y及 0<θ<1 严格成立, 我们就称函数 f 是严格凸的. 如果函数−f是凸的(严格凸)的, 则函数 f 是凹(严格凹)的.
对于仿射函数f(x)=Ax+b(线性函数与常数的和), 不等式(1.1)总成立, 因此所有的仿射函数(包括线性函数)既是凸的, 又是凹的. 反之也成立, 即如果函数既凸又凹, 则其一定是仿射函数.
函数是凸的, 当且仅当其在与其定义域相交的任意直线上都是凸的. 也就是说, 函数 f 是凸的当且仅当∀x∈domf和任意向量 v , 函数g(t)=f(x+tv)是凸的, 其定义域是 {t|x+tv∈domf} . 根据这个性质, 我们可以将函数限制在直线上判断其是否是凸函数.

一阶条件

假设f可微, 则函数f是凸函数的充要条件是domf是凸集, 且∀x,y∈domf, 下式成立

f(y)⩾f(x)+∇f(x)T(y−x).

这里关于 y 的仿射函数f(x)+∇f(x)T(y−x)是函数 f 在x附近的Taylor近似. 从不等式(1.2)可以看出, 对于一个凸函数, 其一阶Taylor展开实际上是该函数的一个全局下估计. 反之, 如果一个函数的一阶Taylor展开总是其全局下估计, 那么这个函数是凸的.
不等式(1.2)还说明从一个函数的 局部信息 可以得到函数的一些 全局信息 . 由不等式可以知道, 如果 ∇f(x)=0 , 那么 ∀y∈domf 都有 f(y)⩾f(x) , 即 x 是函数f的全局极小点.
严格凸性也可以由一阶条件刻画: 函数 f 严格凸的充要条件是domf是凸集且 ∀x,y∈domf,x≠y , 下式成立

f(y)>f(x)+∇f(x)T(y−x).

证明

先考虑n=1的情况. 我们证明可微函数f:R→R是凸函数的充要条件是对于domf内的任意x,y, 有

f(y)⩾f(x)+f′(x)(y−x).

必要性: 假设 f 凸, 且x,y∈domf. 因为 domf 凸, ∀0⩽t⩽ , 我们有 x+t(y−x)∈domf , 由函数的凸性可以得出

f(x+t(y−x))⩽(1−t)f(x)+tf(y).

两端同时除 t 并移项可得

f(y)⩾f(x)+f(x+t(y−x))−f(x)t,

令 t→0 , 可得不等式(1.4).
充分性：假设 domf 中任意两点 x,y(x≠y) , 对于任意的 0⩽θ⩽1 , 令 z=θx+(1−θ)y . 分别对 x,y 应用不等式(1.4), 可得

f(x)⩾f(z)+f′(z)(x−z),f(y)⩾f(z)+f′(z)(y−z).

将(1.7)乘以 θ , (1.8)乘以 1−θ 然后相加可得

θf(x)+(1−θ)f(y)⩾f(z),

这就说明函数 f 是凸的.
对于一般情况, 即f:Rn→R. 设 x,y∈Rn , 考虑将 f 限制在穿过x,y的直线, 即 g(t)=f(ty+(1−t)x) , 该函数对 t 求导可得

g′(t)=∇f(ty+(1−t)x)T(y−x).

首先假设 f 是凸的, 则函数g是凸的, 由 n=1 时的结论可知 g(1)⩾g(0)+g′(0) , 即

f(y)⩾f(x)+∇f(x)T(y−x).

再假设此不等式 ∀x,y 均成立, 因此若 ty+(1−t)x∈domf 以及 ˜ty+(1−˜t)x∈domf , 我们有

f(ty+(1−t)x)⩾f(˜ty+(1−˜t)x)+∇f(˜ty+(1−˜t)x)T(y−x)(t−˜t).

即 g(t)⩾g(˜t)+g′(˜t)(t−˜t) , 说明函数 g 是凸的, 也就是说f是凸的.

二阶条件

现假设f二阶可微, 即对于开集domf内的任意一点, f的二阶导或者Hessian矩阵存在, 则函数f是凸函数的充要条件是, 其Hessian矩阵半正定, 即∀x∈domf, 有

∇2f(x)⪰0.

对于 R 上的函数, 上式退化为 f″(x)⩾0 . 该条件表明函数 f 的导数非减, 从几何上解释就是函数f在点 x 处具有向上(正)的曲率.

证明

先证n=1时的情况.
必要性: 假设 f:R→R 是凸函数, 取 x,y∈domf , 且 x<y . 根据一阶条件我们有

f′(x)(y−x)⩽f(y)−f(x)⩽f′(y)(y−x).

左右两边同时除 y−x 有,

f′(y)−f′(x)y−x⩾0.

令 y→x 可得 f″(x)⩾0 .
充分性: 假设 ∀z∈domf 都有 f″(z)⩾0 . 考虑任意的 x,y∈domf , 且 x<y . 我们有

∫yxf″(z)(y−z)dz⩾0,(f′(z)(y−z))|z=yz=x+∫yxf′(z)dz⩾0,f(y)−f(x)−f′(x)(y−x)⩾0.

同样, 对于一般情况, 我们注意到一个函数是凸函数当且仅当它在与定义域相交的所有直线上都是凸函数, 比如函数 g(t)=f(x0+tv) 对于任意的 x0∈f 和任意的 v 是关于t的凸函数.
所以说, 函数 f 是凸函数当且仅当对于任意的x0∈domf,v∈Rn, 以及 t|x0+tv∈domf 有

g″(t)=vt∇2f(x0+tv)v⩾0.

也就是说, 对于任意的 x∈domf ∇2f(x)⪰0 是函数 <script type="math/tex" >f</script>凸的充分必要条件.