凸优化理论（3）

前情回顾

上篇文章给出了凸函数二阶条件，即对于凸集 S S S上的函数 f f f为凸函数的充要条件为

▽ f ( x ) ⪰ 0 ( x ∈ d o m f ) \triangledown f(x)\succeq0\left(x\in domf\right) ▽f(x)⪰0(x∈domf)

在次给出个人推导的证明，如有错误还请指出。

证明：

充分性：

首先列出凸函数定义式和一阶条件式

f ( λ x + ( 1 − λ ) y ) ≤ λ f ( x ) + ( 1 − λ ) f ( y ) f(\lambda x+(1-\lambda)y)\leq \lambda f(x)+(1-\lambda)f(y) f(λx+(1−λ)y)≤λf(x)+(1−λ)f(y)

f ( y ) ≥ f ( x ) + ▽ f ( x ) T ( y − x ) f(y)\geq f(x)+\triangledown f(x)^T (y-x) f(y)≥f(x)+▽f(x)T(y−x)

由一阶条件可得 f ( x ) ≤ f ( y ) − ▽ f ( x ) T ( y − x ) f(x)\leq f(y)-\triangledown f(x)^T(y-x) f(x)≤f(y)−▽f(x)T(y−x)

将其代入凸函数定义式得 f ( λ x + ( 1 − λ ) y ) − f ( y ) ≤ − λ ▽ f ( x ) T ( y − x ) f(\lambda x+(1-\lambda)y)-f(y)\leq -\lambda \triangledown f(x)^T(y-x) f(λx+(1−λ)y)−f(y)≤−λ▽f(x)T(y−x)

接下来假设 y > x y>x y>x， λ \lambda λ不为0，则有

f ( y ) − f ( λ x + ( 1 − λ ) y ) λ ( y − x ) ≥ ▽ f ( x ) T \frac{f(y)-f(\lambda x+(1-\lambda)y)}{\lambda (y-x)}\geq\triangledown f(x)^T λ(y−x)f(y)−f(λx+(1−λ)y)​≥▽f(x)T

对任意 y > x y>x y>x都成立，则固定 y y y，求极限

lim ⁡ x → y f ( y ) − f ( λ x + ( 1 − λ ) y ) λ ( y − x ) = ▽ f ( y ) T \lim \limits_{x\rightarrow y}\frac{f(y)-f(\lambda x+(1-\lambda)y)}{\lambda (y-x)}=\triangledown f(y)^T x→ylim​λ(y−x)f(y)−f(λx+(1−λ)y)​=▽f(y)T

则可得到 ▽ f ( y ) T − ▽ f ( x ) T y − x ⪰ 0 \frac{\triangledown f(y)^T-\triangledown f(x)^T}{y-x}\succeq0 y−x▽f(y)T−▽f(x)T​⪰0

即 ▽ 2 f ( x ) ⪰ 0 \triangledown ^2f(x)\succeq0 ▽2f(x)⪰0

必要性：

使用一阶泰勒展开式，余项使用拉格朗日余项，可得

f ( y ) = f ( x ) + ▽ f ( x ) T ( y − x ) + 1 2 ( y − x ) ▽ 2 f ( z ) T ( y − x ) f(y)=f(x)+\triangledown f(x)^T(y-x)+\frac{1}{2}(y-x)\triangledown^2f(z)^T(y-x) f(y)=f(x)+▽f(x)T(y−x)+21​(y−x)▽2f(z)T(y−x)

对于任意的 x , y ∈ d o m f , z ∈ [ x , y ] x,y\in domf,z\in[x,y] x,y∈domf,z∈[x,y]成立

则可得一阶条件式 f ( y ) ≥ f ( x ) + ▽ f ( x ) T ( y − x ) f(y)\geq f(x)+\triangledown f(x)^T(y-x) f(y)≥f(x)+▽f(x)T(y−x)

再按照之前由一阶条件式推出凸函数定义即得证。