凸优化 [2]：什么是凸函数——一阶与二阶条件
定义：∀ x , y ∈ X \forall x,y\in X∀x,y∈X ，∀ α ∈ [ 0 , 1 ] \forall \alpha \in [0,1]∀α∈[0,1] 使得：
f ( α x + ( 1 − α ) y ) ≤ α f ( x ) + ( 1 − α ) f ( y ) convex f ( α x + ( 1 − α ) y ) < α f ( x ) + ( 1 − α ) f ( y ) strictly convex \begin{aligned} f(\alpha x+(1-\alpha)y)\le \alpha f(x)+(1-\alpha)f(y)&&\text{convex}\\ f(\alpha x+(1-\alpha)y)< \alpha f(x)+(1-\alpha)f(y)&&\text{strictly convex} \end{aligned}f(αx+(1−α)y)≤αf(x)+(1−α)f(y)f(αx+(1−α)y)<αf(x)+(1−α)f(y)convexstrictly convex
凸函数扩充到 R n \R^nRn 中：
f ~ ( x ) = { f ( x ) if x ∈ X ∞ otherwise \tilde f(x)=\begin{cases} f(x)&\text{if $x\in X$}\\ \infty&\text{otherwise} \end{cases}f~(x)={f(x)∞if x∈Xotherwise
凸函数：函数为凸的条件
一阶充要条件：
f ( x ) ≥ f ( y ) + ∇ f ( y ) T ( x − y ) f(x)\ge f(y)+\nabla f(y)^T(x-y)f(x)≥f(y)+∇f(y)T(x−y)
必要性：
由凸性可得：
f ( ( α x − α y ) + y ) ≤ α f ( x ) + ( 1 − α ) f ( y ) ⇓ ⇓ α f ( x ) ≥ f ( α ( x − y ) + y ) − ( 1 − α ) f ( y ) \begin{aligned} f((\alpha x - \alpha y) + y)&\le \alpha f(x)+(1-\alpha)f(y)\\ \Downarrow \Downarrow\\ \alpha f(x)&\ge f(\alpha (x-y) + y)-(1-\alpha) f(y) \end{aligned}f((αx−αy)+y)⇓⇓αf(x)≤αf(x)+(1−α)f(y)≥f(α(x−y)+y)−(1−α)f(y)
两端除以 α \alphaα ：
f ( x ) ≥ f ( α ( x − y ) + y ) − ( 1 − α ) f ( y ) α = f ( y ) + f ( y + α ( x − y ) ) − f ( y ) α f(x)\ge \frac{f(\alpha (x-y) + y)-(1-\alpha) f(y)}{\alpha}=f(y)+\frac{f(y+\alpha (x-y))- f(y)}{\alpha}f(x)≥αf(α(x−y)+y)−(1−α)f(y)=f(y)+αf(y+α(x−y))−f(y)
因为：（由一阶 Taylor 展开）
lim α → 0 f ( y + α ( x − y ) ) − f ( y ) α = f ( y ) + α ∇ f ( y ) T ( x − y ) − f ( y ) α = ∇ f ( y ) T ( x − y ) \lim_{\alpha\rightarrow 0} \frac{f(y+\alpha (x-y))- f(y)}{\alpha}=\frac{f(y)+\alpha \nabla f(y)^T(x-y)- f(y)}{\alpha}=\nabla f(y)^T(x-y)α→0limαf(y+α(x−y))−f(y)=αf(y)+α∇f(y)T(x−y)−f(y)=∇f(y)T(x−y)
因此：
f ( x ) ≥ f ( y ) + ∇ f ( y ) T ( x − y ) f(x)\ge f(y)+\nabla f(y)^T(x-y)f(x)≥f(y)+∇f(y)T(x−y)
得证 □ \square□
充分性：
令 z = θ x + ( 1 − θ ) y z=\theta x+(1-\theta)yz=θx+(1−θ)y
f ( x ) ≥ f ( z ) + ∇ f ( z ) T ( x − z ) f ( y ) ≥ f ( z ) + ∇ f ( z ) T ( y − z ) f(x)\ge f(z)+\nabla f(z)^T(x-z)\\ f(y)\ge f(z)+\nabla f(z)^T(y-z)f(x)≥f(z)+∇f(z)T(x−z)f(y)≥f(z)+∇f(z)T(y−z)
则：
θ f ( x ) + ( 1 − θ ) f ( y ) ≥ [ θ f ( z ) + θ ∇ f ( z ) T ( x − z ) ] + [ ( 1 − θ ) f ( z ) + ( 1 − θ ) ∇ f ( z ) T ( y − z ) ] ⇓ θ f ( x ) + ( 1 − θ ) f ( y ) ≥ f ( z ) \theta f(x)+(1-\theta)f(y)\ge\left[\theta f(z)+\theta\nabla f(z)^T(x-z)\right]+\left[(1-\theta) f(z)+(1-\theta)\nabla f(z)^T(y-z)\right]\\ \Downarrow\\ \theta f(x)+(1-\theta)f(y)\ge f(z)θf(x)+(1−θ)f(y)≥[θf(z)+θ∇f(z)T(x−z)]+[(1−θ)f(z)+(1−θ)∇f(z)T(y−z)]⇓θf(x)+(1−θ)f(y)≥f(z)
因此有：
θ f ( x ) + ( 1 − θ ) f ( y ) ≥ f ( θ x + ( 1 − θ ) y ) \theta f(x)+(1-\theta)f(y)\ge f(\theta x+(1-\theta)y)θf(x)+(1−θ)f(y)≥f(θx+(1−θ)y)
得证 □ \square□
二阶充要条件：
∇ 2 f ( x ) ⪰ 0 \nabla^2 f(x) \succeq 0∇2f(x)⪰0
充分性：
由二阶 Taylor 展开：
f ( y ) = f ( x ) + ∇ f ( x ) T ( y − x ) + 1 2 ( y − x ) T ∇ 2 f ( x ) ( y − x ) + o ( ∥ y − x ∥ 2 ) f(y)=f(x)+\nabla f(x)^T (y-x) + \frac{1}{2}(y-x)^T \nabla^2f(x)(y-x)+o(\|y-x\|^2)f(y)=f(x)+∇f(x)T(y−x)+21(y−x)T∇2f(x)(y−x)+o(∥y−x∥2)
因为 ∇ 2 f ( x ) ⪰ 0 \nabla^2 f(x) \succeq 0∇2f(x)⪰0 ，恒成立：
1 2 ( y − x ) T ∇ 2 f ( x ) ( y − x ) ≥ 0 \frac{1}{2}(y-x)^T \nabla^2f(x)(y-x)\ge 021(y−x)T∇2f(x)(y−x)≥0
因此：
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) f(y)\ge f(x) +\nabla f(x)^T(y-x)f(y)≥f(x)+∇f(x)T(y−x)
由一阶条件，推出 f ff 为凸函数。□ \square□
必要性：
由二阶 Taylor 展开：
f ( y ) = f ( x ) + ∇ f ( x ) T ( y − x ) + 1 2 ( y − x ) T ∇ 2 f ( x ) ( y − x ) + o ( ∥ y − x ∥ 2 ) f(y)=f(x)+\nabla f(x)^T (y-x) + \frac{1}{2}(y-x)^T \nabla^2f(x)(y-x)+o(\|y-x\|^2)f(y)=f(x)+∇f(x)T(y−x)+21(y−x)T∇2f(x)(y−x)+o(∥y−x∥2)
已知函数 f ff 为凸函数，则由一阶充要条件：
f ( y ) ≥ f ( x ) + ∇ f ( x ) T ( y − x ) f(y)\ge f(x)+\nabla f(x)^T (y-x)f(y)≥f(x)+∇f(x)T(y−x)
因此：
1 2 ( y − x ) T ∇ 2 f ( x ) ( y − x ) + o ( ∥ y − x ∥ 2 ) ≥ 0 \frac{1}{2}(y-x)^T \nabla^2f(x)(y-x)+o(\|y-x\|^2)\ge 021(y−x)T∇2f(x)(y−x)+o(∥y−x∥2)≥0
Taylor 展开余项可忽略，因此 Hessian 矩阵要满足 ∀ ( y − x ) ∈ R n \forall (y-x)\in \R^n∀(y−x)∈Rn 都成立，因此 ∇ 2 f ( x ) ⪰ 0 \nabla^2f(x)\succeq 0∇2f(x)⪰0 。
得证 □ \square□
将不等式的等号去掉，就是严格凸函数的证明。