本文主要是介绍凸函数成立的一阶与二阶条件，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
文章目录
- 1、凸函数成立的一阶条件
- 2、凸函数成立的二阶条件
本文主要是针对凸函数成立的一阶和二阶充要条件进行描述和简单证明。
1、凸函数成立的一阶条件
【定理1】对于函数 J : Ω → R J:\Omega \rightarrow \mathbb{R} J:Ω→R， J J J为凸函数，当且仅当 ∀ x , y ∈ Ω \forall \bf{x},\bf{y}\in \Omega ∀x,y∈Ω，有
J ( y ) ≥ J ( x ) + ▽ J ( x ) T ( y − x ) . J({\bf y})\ge J({\bf x})+\triangledown J({\bf x})^{\rm T}(\bf{y}-\bf{x}). J(y)≥J(x)+▽J(x)T(y−x).
【证明】
（1）必要性证明。
设 z = t y + ( 1 − t ) x = x + t ( y − x ) {\bf z}=t {\bf y}+(1-t){\bf x}={\bf x}+t(\bf y-x) z=ty+(1−t)x=x+t(y−x)，由于 J J J为凸函数，因此
J [ x + t ( y − x ) ] ≤ t J ( y ) + ( 1 − t ) J ( x ) , J[{\bf x}+t({\bf y-x})]\le tJ({\bf y})+(1-t)J({\bf x}), J[x+t(y−x)]≤tJ(y)+(1−t)J(x),进一步有
J ( y ) ≥ J ( x ) + lim t → 0 J [ x + t ( y − x ) ] − J ( x ) t , J({\bf y})\ge J({\bf x})+\lim_{t\rightarrow 0}\frac{J[{\bf x}+t({\bf y-x})] -J({\bf x})}{t}, J(y)≥J(x)+t→0limtJ[x+t(y−x)]−J(x),故
J ( y ) ≥ J ( x ) + ▽ J ( x ) T ( y − x ) . J({\bf y})\ge J({\bf x})+\triangledown J({\bf x})^{\rm T}(\bf{y}-\bf{x}). J(y)≥J(x)+▽J(x)T(y−x).
（2）充分性证明。
设 z = θ y + ( 1 − θ ) x {\bf z}=\theta {\bf y}+(1-\theta){\bf x} z=θy+(1−θ)x，将
J ( x ) ≥ J ( z ) + ▽ J ( z ) T ( x − z ) J({\bf x})\ge J({\bf z})+\triangledown J({\bf z})^{\rm T}(\bf{x}-\bf{z}) J(x)≥J(z)+▽J(z)T(x−z) J ( y ) ≥ J ( z ) + ▽ J ( z ) T ( y − z ) J({\bf y})\ge J({\bf z})+\triangledown J({\bf z})^{\rm T}(\bf{y}-\bf{z}) J(y)≥J(z)+▽J(z)T(y−z)分别乘以 1 − θ 1-\theta 1−θ和 θ \theta θ，则有
θ J ( y ) + ( 1 − θ ) J ( x ) ≥ J ( z ) + θ ▽ J ( z ) T [ θ y + ( 1 − θ ) x − z ] = J ( z ) \theta J({\bf y})+(1-\theta)J({\bf x})\ge J({\bf z})+\theta \triangledown J({\bf z})^{\rm T}[\theta {\bf y}+(1-\theta) {\bf x}-{\bf z}]=J({\bf z}) θJ(y)+(1−θ)J(x)≥J(z)+θ▽J(z)T[θy+(1−θ)x−z]=J(z)由此可以得到
J [ θ y + ( 1 − θ ) x ] ≤ θ J ( y ) + ( 1 − θ ) J ( x ) . J[\theta {\bf y}+(1-\theta){\bf x}]\le \theta J({\bf y})+(1-\theta)J({\bf x}). J[θy+(1−θ)x]≤θJ(y)+(1−θ)J(x).
2、凸函数成立的二阶条件
【定理2】对于函数 J : Ω → R J:\Omega \rightarrow \mathbb{R} J:Ω→R， J J J为凸函数，当且仅当 ∀ x ∈ Ω \forall {\bf x} \in \Omega ∀x∈Ω，其Hessian矩阵 ▽ 2 J ( x ) \triangledown^2J({\bf x}) ▽2J(x)半正定。
【证明】
（1）必要性证明。
根据泰勒级数展开，对于小的实数 λ > 0 \lambda>0 λ>0，我们可以得到
J ( x + λ d ) = J ( x ) + λ ▽ J ( x ) T d + λ 2 2 d T ▽ 2 J ( x ) T d + o ( ∣ ∣ λ d ∣ ∣ 2 ) J({\bf x+\lambda d})=J({\bf x})+\lambda\triangledown J({\bf x})^{\rm T}{\bf d}+\frac{\lambda^2}{2}{\bf d}^{\rm T}\triangledown^2 J({\bf x})^{\rm T}{\bf d}+{\mathcal o}(||\lambda{\bf d}||^2) J(x+λd)=J(x)+λ▽J(x)Td+2λ2dT▽2J(x)Td+o(∣∣λd∣∣2)
由于 J J J为凸函数，根据定理1有
J ( x + λ d ) ≥ J ( x ) + λ ▽ J ( x ) T d J({\bf x+\lambda d})\ge J({\bf x})+\lambda\triangledown J({\bf x})^{\rm T}{\bf d} J(x+λd)≥J(x)+λ▽J(x)Td因此， λ 2 2 d T ▽ 2 J ( x ) T d + o ( ∣ ∣ λ d ∣ ∣ 2 ) ≥ 0 \frac{\lambda^2}{2}{\bf d}^{\rm T}\triangledown^2 J({\bf x})^{\rm T}{\bf d}+{\mathcal o}(||\lambda{\bf d}||^2)\ge 0 2λ2dT▽2J(x)Td+o(∣∣λd∣∣2)≥0
将上式除以 λ 2 \lambda ^2 λ2并使得 λ → 0 + \lambda \rightarrow 0^+ λ→0+，可以得到对于任意的 d ∈ R n : d T ▽ 2 J ( x ) T d ≥ 0 {\bf d} \in {\mathbb R^n}:{\bf d}^{\rm T}\triangledown^2 J({\bf x})^{\rm T}{\bf d}\ge 0 d∈Rn:dT▽2J(x)Td≥0。
（2）充分性证明。
J ( y ) = J ( x ) + ▽ J ( x ) T ( y − x ) + 1 2 ( y − x ) T ▽ 2 J ( x ) T ( y − x ) J({\bf y})=J({\bf x})+\triangledown J({\bf x})^{\rm T}({\bf y}-{\bf x})+\frac{1}{2}({\bf y}-{\bf x})^{\rm T}\triangledown^2 J({\bf x})^{\rm T}({\bf y}-{\bf x}) J(y)=J(x)+▽J(x)T(y−x)+21(y−x)T▽2J(x)T(y−x)由于Hessian矩阵半正定，因此
J ( y ) ≥ J ( x ) + ▽ J ( x ) T ( y − x ) J({\bf y})\ge J({\bf x})+\triangledown J({\bf x})^{\rm T}({\bf y}-{\bf x}) J(y)≥J(x)+▽J(x)T(y−x)由定理1可证 J J J为凸函数。
【参考文献】
[1] S.Boyd etc., Convex Optimization.
[2] Yaron Singer, Lecture 10, AM 221: Advanced Optimization.
这篇关于凸函数成立的一阶与二阶条件的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
