凸函数的判断（上）： 重要的基本性质

前言

最近在学习CVX的使用， 也得知了其最核心的点在于需要掌握 如何判断 目标函数是否为凸。 这篇博客就是基于Boyd的凸优化经典教材，对凸函数判断的一些整理， 也记录几个私以为极为重要的证明。

基本定义

对于定义域为凸集 ，且对于 x,y∈dom⁡fx, y \in \operatorname{dom} fx,y∈domf， 0⩽θ⩽10 \leqslant \theta \leqslant 10⩽θ⩽1时， 满足

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

f(\theta x+(1-\theta) y) \leqslant \theta f(x)+(1-\theta) f(y)

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

则称函数fff为凸函数。 几何上的解释则如下图：

任意两点连线均在函数图像之上。 这是凸函数最基本的定义， 有相当一部分的凸函数，其凸性可以直接由定义得。 但这里要强调的是另一个基本的、极为重要的且易被忽视的性质：

当且仅当函数在与其定义域相交的所有直线上均为凸， 该函数为凸函数。

用数学语言来表示则是：

g(t)=f(x+tv),∀x∈domf，∀vg(t) = f(x+tv) , \forall x \in \mathrm{dom}f， \forall vg(t)=f(x+tv),∀x∈domf，∀v

当且仅当 g(t)g(t)g(t) 为凸时， f(x)f(x)f(x) 为凸。

遗憾的是，我尚未找到这条性质对应的清晰显明的几何性质。 然而并不妨碍其重要性的昭然若揭：

任意一个高维函数fff， 其凸性可以通过验证一个对应的 标量函数 的凸性来得到。

因为 g(t)g(t)g(t) 的变量是步长， 是一个标量。

我们对这一性质进行简单的证明：

先证明必要性， 即可以通过 f(x)f(x)f(x) 的 凸性 得到 g(t)g(t)g(t) 的凸性。 我们首先有 g(t1)=f(x+t1v)g(t_1) =f(x+t_1v)g(t1​)=f(x+t1​v) 和 g(t2)=f(x+t2v)g(t_2) = f(x+t_2v)g(t2​)=f(x+t2​v), 此时，

g(θt1+(1−θ)t2)=f(x+(θt1+(1−θ)t2)v)=f(θ(x+t1v)+(1−θ)(x+t2v))≤θf(x+t1v)+(1−θ)f(x+t2v)=θg(t1)+(1−θ)g(t2)g(\theta t_1 + (1-\theta)t_2)=f(x + (\theta t_1 + (1-\theta)t_2)v)=f(\theta(x+t_1v)+(1-\theta)(x+t_2v))\\ \le\theta f(x+t_1v)+(1-\theta)f(x+t_2v)=\theta g(t_1) +(1-\theta)g(t_2)g(θt1​+(1−θ)t2​)=f(x+(θt1​+(1−θ)t2​)v)=f(θ(x+t1​v)+(1−θ)(x+t2​v))≤θf(x+t1​v)+(1−θ)f(x+t2​v)=θg(t1​)+(1−θ)g(t2​)

不等号来源于 f(x)f(x)f(x) 的 凸性。 根据定义， g(x)g(x)g(x) 凸性得证。

而充分性则更容易验证了 （毕竟 g(t)g(t)g(t) 对于任意初始点xxx 和 vvv都要满足）， 令x=x1x=x_1x=x1​, v=x2−x1v=x_2-x_1v=x2​−x1​， 我们有：

f(θx1+(1−θ)x2)=g(1−θ)≤θg(0)+(1−θ)g(1)=θf(x1)+(1−θ)f(x2)f(\theta x_1 + (1-\theta)x_2)=g(1-\theta)\le \theta g(0) + (1-\theta)g(1)=\theta f(x_1)+(1-\theta)f(x_2)f(θx1​+(1−θ)x2​)=g(1−θ)≤θg(0)+(1−θ)g(1)=θf(x1​)+(1−θ)f(x2​)

这个性质在后续会发挥重大作用。

一阶条件

除去定义， 一阶条件也可以作为凸性的判断。 fff 为凸函数的充要条件为：

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

f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)

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

其几何解释可以表示为：

即函数上任意一点的切线均在函数下方。

我们先给出其严格的证明。 首先考虑标量情况， 即 xxx 为一维标量， 那么一阶条件将简化为：

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

f(y) \geqslant f(x)+f^{\prime}(x)(y-x)

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

先证明其必要性： 即通过f(x)f(x)f(x)的凸性推导一阶条件。根据凸性， 有：

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

f(x+t(y-x)) \leqslant(1-t) f(x)+t f(y)

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

两边同时除以 ttt 得到：

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

f(y) \geqslant f(x)+\frac{f(x+t(y-x))-f(x)}{t}

f(y)⩾f(x)+tf(x+t(y−x))−f(x)​

当 t→0t\rightarrow 0t→0时， 即为一阶条件。

再证明其充分性， 对于任意两点 xxx, yyy， 令 z=θx+(1−θ)yz=\theta x+(1-\theta) yz=θx+(1−θ)y, 由一阶条件有：

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

f(x) \geqslant f(z)+f^{\prime}(z)(x-z), \quad f(y) \geqslant f(z)+f^{\prime}(z)(y-z)

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

将第一个不等式乘以 θ\thetaθ ， 第二个乘以 1−θ1-\theta1−θ， 有：

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

\theta f(x)+(1-\theta) f(y) \geqslant f(z)

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

重点来了， 标量形式的一阶条件极为简单， 但对于更普遍的向量形式呢？ 这就需要刚提到的重要基本性质了。

对于任意两点 x,yx, yx,y (均为多维向量)， 考虑过这两点的直线上的函数 fff ， 即 g(t)=f(x+t(y−x))=f(ty+(1−t)x)g(t) = f(x + t(y-x)) = f(ty + (1-t)x)g(t)=f(x+t(y−x))=f(ty+(1−t)x), 我们只需要考察 g(t)g(t)g(t) 的凸性即可。

先证明必要性： 由于 fff 是凸的， 那么 ggg 也是凸的，那么对 ggg其的一阶条件就是我们刚推导的标量形式， 也就是有 ：g(1)⩾g(0)+g′(0)

g(1) \geqslant g(0)+g^{\prime}(0)

g(1)⩾g(0)+g′(0)

又由于

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

g^{\prime}(t)=\nabla f(t y+(1-t) x)^{T}(y-x)

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

代入上式， 有：

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

f(y) \geqslant f(x)+\nabla f(x)^{T}(y-x)

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

再证明其充分性： 若一阶条件成立， 则我们有：

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

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})

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

即 g(t)⩾g(t~)+g′(t~)(t−t~)

g(t) \geqslant g(\tilde{t})+g^{\prime}(\tilde{t})(t-\tilde{t})

g(t)⩾g(t~)+g′(t~)(t−t~)

因此， g(t)g(t)g(t) 满足一阶条件，为凸。

这个证明中， 清晰地展示了如何从标量形式拓展为多维场景的精彩论证。

二阶条件

相比于一阶条件， 二阶条件更为简单明了： 当且仅当函数fff 的 二阶导：

∇2f(x)⪰0

\nabla^{2} f(x) \succeq 0

∇2f(x)⪰0

则函数fff为凸。 当fff为标量函数时， 事实上这就是我们高中常说的开口向上的函数。

同样的， 我们给出证明。 站于巨人肩膀之上， 二阶的证明需要一阶条件。

首先证明充分性， 即二阶条件可以推导出一阶条件。 不妨设 y>xy>xy>x， 有：

∫xyf′′(z)(y−z)dz≥0 \int_x^y f^{\prime\prime}(z)(y-z)dz\ge0∫xy​f′′(z)(y−z)dz≥0

这是因为f′′(z)f^{\prime\prime}(z)f′′(z)始终不小于0. 根据分部积分法， 即：

∫uv′dx=uv−∫u′vdx\int uv^\prime dx=uv-\int u^\prime v dx∫uv′dx=uv−∫u′vdx

其中 u,vu,vu,v均为xxx的函数。 这个常用于当 uv′uv^\primeuv′不好求而 u′vu^\prime vu′v好求的情况下。 此时， 我们可以把上式转化为：

∫xyf′′(z)(y−z)dz=f′(z)(y−z)∣z=xz=y+∫xyf′(z)dz≥0⇒−f′(x)(y−x)+f(y)−f(x)≥0\int_x^y f^{\prime\prime}(z)(y-z)dz= f^\prime(z)(y-z)|_{z=x}^{z=y}+\int_x^yf^\prime(z)dz\ge0 \\ \Rightarrow-f^\prime(x)(y-x)+f(y)-f(x)\ge 0∫xy​f′′(z)(y−z)dz=f′(z)(y−z)∣z=xz=y​+∫xy​f′(z)dz≥0⇒−f′(x)(y−x)+f(y)−f(x)≥0

即得证。 再证明必要性， 即由一阶条件推二阶， 根据一阶条件有：

f(y)≥f(x)+f′(x)(y−x)⇒f(y)−f(x)≥f′(x)(y−x)f(x)≥f(y)+f′(y)(x−y)⇒f(y)−f(x)≤f′(y)(y−x) f(y) \ge f(x) + f^\prime(x)(y-x)\Rightarrow f(y) - f(x)\ge f^\prime(x)(y-x)\\f(x) \ge f(y) + f^\prime(y)(x-y)\Rightarrow f(y) - f(x)\le f^\prime(y)(y-x)f(y)≥f(x)+f′(x)(y−x)⇒f(y)−f(x)≥f′(x)(y−x)f(x)≥f(y)+f′(y)(x−y)⇒f(y)−f(x)≤f′(y)(y−x)

结合既有：

f′(x)(y−x)≤f′(y)(y−x)⇒f′(y)−f′(x)y−x≥0f^\prime(x)(y-x)\le f^\prime(y)(y-x)\Rightarrow \frac{f^\prime(y)-f^\prime(x)}{y-x}\ge 0f′(x)(y−x)≤f′(y)(y−x)⇒y−xf′(y)−f′(x)​≥0

得证。

再通过基本性质， 将结论拓展至高维。 令 g(t)=f(x0+tv)g(t) = f(x_0 + tv)g(t)=f(x0​+tv), 若 f(x)f(x)f(x)为凸， 则g(t)g(t)g(t) 为凸， 我们有：

g′′(t)=vT∇2f(x0+tv)v≥0 g^{\prime\prime}(t) = v^T\nabla^2f(x_0+tv)v\ge0g′′(t)=vT∇2f(x0​+tv)v≥0

因此 ∇2f(x)⪰0\nabla^{2} f(x) \succeq 0∇2f(x)⪰0。 充分性的证明也类似。

至此，我们介绍了凸函数的一些基本判别和重要性质。 在下一节欸，我们结合经典凸优化工具包CVX，再来看如何快速判断一个函数是否为凸。