最近在学习CVX的使用， 也得知了其最核心的点在于需要掌握 如何判断 目标函数是否为凸。 这篇博客就是基于Boyd的凸优化经典教材，对凸函数判断的一些整理， 也记录几个私以为极为重要的证明。
基本定义对于定义域为凸集 ，且对于
x
,
y
∈
dom
f
x, y \in \operatorname{dom} f
x,y∈domf，
0
⩽
θ
⩽
1
0 \leqslant \theta \leqslant 1
0⩽θ⩽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) 则称函数
f
f
f为凸函数。 几何上的解释则如下图： 
任意两点连线均在函数图像之上。 这是凸函数最基本的定义， 有相当一部分的凸函数，其凸性可以直接由定义得。 但这里要强调的是另一个基本的、极为重要的且易被忽视的性质：
当且仅当函数在与其定义域相交的所有直线上均为凸， 该函数为凸函数。
用数学语言来表示则是： g ( t ) = f ( x + t v ) , ∀ x ∈ d o m f ， ∀ v g(t) = f(x+tv) , \forall x \in \mathrm{dom}f， \forall v g(t)=f(x+tv),∀x∈domf，∀v 当且仅当 g ( t ) g(t) g(t) 为凸时， f ( x ) f(x) f(x) 为凸。
遗憾的是，我尚未找到这条性质对应的清晰显明的几何性质。 然而并不妨碍其重要性的昭然若揭：
任意一个高维函数 f f f， 其凸性可以通过验证一个对应的 标量函数 的凸性来得到。
因为 g ( t ) g(t) g(t) 的变量是步长， 是一个标量。
我们对这一性质进行简单的证明：
先证明必要性， 即可以通过 f ( x ) f(x) f(x) 的 凸性 得到 g ( t ) g(t) g(t) 的凸性。 我们首先有 g ( t 1 ) = f ( x + t 1 v ) g(t_1) =f(x+t_1v) g(t1)=f(x+t1v) 和 g ( t 2 ) = f ( x + t 2 v ) g(t_2) = f(x+t_2v) g(t2)=f(x+t2v), 此时，
g ( θ t 1 + ( 1 − θ ) t 2 ) = f ( x + ( θ t 1 + ( 1 − θ ) t 2 ) v ) = f ( θ ( x + t 1 v ) + ( 1 − θ ) ( x + t 2 v ) ) ≤ θ f ( x + t 1 v ) + ( 1 − θ ) f ( x + t 2 v ) = θ g ( t 1 ) + ( 1 − θ ) g ( t 2 ) 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+t1v)+(1−θ)(x+t2v))≤θf(x+t1v)+(1−θ)f(x+t2v)=θg(t1)+(1−θ)g(t2)
不等号来源于 f ( x ) f(x) f(x) 的 凸性。 根据定义， g ( x ) g(x) g(x) 凸性得证。
而充分性则更容易验证了 （毕竟 g ( t ) g(t) g(t) 对于任意初始点 x x x 和 v v v都要满足）， 令 x = x 1 x=x_1 x=x1, v = x 2 − x 1 v=x_2-x_1 v=x2−x1， 我们有：
f ( θ x 1 + ( 1 − θ ) x 2 ) = g ( 1 − θ ) ≤ θ g ( 0 ) + ( 1 − θ ) g ( 1 ) = θ f ( x 1 ) + ( 1 − θ ) f ( x 2 ) 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)
这个性质在后续会发挥重大作用。
一阶条件除去定义， 一阶条件也可以作为凸性的判断。
f
f
f 为凸函数的充要条件为：
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) 其几何解释可以表示为： 
即函数上任意一点的切线均在函数下方。
我们先给出其严格的证明。 首先考虑标量情况， 即 x x x 为一维标量， 那么一阶条件将简化为： 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 ) + t f ( 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) 两边同时除以 t t t 得到： 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 → 0 t\rightarrow 0 t→0时， 即为一阶条件。
再证明其充分性， 对于任意两点 x x x, y y y， 令 z = θ x + ( 1 − θ ) y z=\theta x+(1-\theta) y z=θ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-\theta 1−θ， 有： θ 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 , y x, y x,y (均为多维向量)， 考虑过这两点的直线上的函数 f f f ， 即 g ( t ) = f ( x + t ( y − x ) ) = f ( t y + ( 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) 的凸性即可。
先证明必要性： 由于 f f f 是凸的， 那么 g g g 也是凸的，那么对 g g g其的一阶条件就是我们刚推导的标量形式， 也就是有 ： g ( 1 ) ⩾ g ( 0 ) + g ′ ( 0 ) g(1) \geqslant g(0)+g^{\prime}(0) g(1)⩾g(0)+g′(0) 又由于 g ′ ( t ) = ∇ f ( t y + ( 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 ( t y + ( 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) 满足一阶条件，为凸。 这个证明中， 清晰地展示了如何从标量形式拓展为多维场景的精彩论证。
二阶条件相比于一阶条件， 二阶条件更为简单明了： 当且仅当函数 f f f 的 二阶导： ∇ 2 f ( x ) ⪰ 0 \nabla^{2} f(x) \succeq 0 ∇2f(x)⪰0 则函数 f f f为凸。 当 f f f为标量函数时， 事实上这就是我们高中常说的开口向上的函数。
同样的， 我们给出证明。 站于巨人肩膀之上， 二阶的证明需要一阶条件。
首先证明充分性， 即二阶条件可以推导出一阶条件。 不妨设 y > x y>x y>x， 有： ∫ x y f ′ ′ ( z ) ( y − z ) d z ≥ 0 \int_x^y f^{\prime\prime}(z)(y-z)dz\ge0 ∫xyf′′(z)(y−z)dz≥0 这是因为 f ′ ′ ( z ) f^{\prime\prime}(z) f′′(z)始终不小于0. 根据分部积分法， 即：
∫ u v ′ d x = u v − ∫ u ′ v d x \int uv^\prime dx=uv-\int u^\prime v dx ∫uv′dx=uv−∫u′vdx 其中 u , v u,v u,v均为 x x x的函数。 这个常用于当 u v ′ uv^\prime uv′不好求而 u ′ v u^\prime v u′v好求的情况下。 此时， 我们可以把上式转化为： ∫ x y f ′ ′ ( z ) ( y − z ) d z = f ′ ( z ) ( y − z ) ∣ z = x z = y + ∫ x y f ′ ( z ) d z ≥ 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 ∫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 即得证。 再证明必要性， 即由一阶条件推二阶， 根据一阶条件有： 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 ≥ 0 f^\prime(x)(y-x)\le f^\prime(y)(y-x)\Rightarrow \frac{f^\prime(y)-f^\prime(x)}{y-x}\ge 0 f′(x)(y−x)≤f′(y)(y−x)⇒y−xf′(y)−f′(x)≥0 得证。
再通过基本性质， 将结论拓展至高维。 令 g ( t ) = f ( x 0 + t v ) 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 ) = v T ∇ 2 f ( x 0 + t v ) v ≥ 0 g^{\prime\prime}(t) = v^T\nabla^2f(x_0+tv)v\ge0 g′′(t)=vT∇2f(x0+tv)v≥0 因此 ∇ 2 f ( x ) ⪰ 0 \nabla^{2} f(x) \succeq 0 ∇2f(x)⪰0。 充分性的证明也类似。
至此，我们介绍了凸函数的一些基本判别和重要性质。 在下一节欸，我们结合经典凸优化工具包CVX，再来看如何快速判断一个函数是否为凸。
