凸函数的一阶条件及其证明

2019-05-04 本文已影响0人坐看云起时zym

判断凸函数的一阶条件如下图所示：

First-order conditions.png
注意到右式为函数在点处的一阶泰勒展开，在n = 1情形下的几何意义如下图：

几何意义.png

具体证明如下：
充分性：
$\forall x,y \in domf$ 令 $z = \theta x + (1- \theta)y, \theta \in [0,1], x \neq y$
$f(x) \geqslant f(z) + \triangledown f(z)^{T}(x -z)$ ①
$f(y) \geqslant f(z) + \triangledown f(z)^{T}(y -z)$ ②
$\theta *$ ① + $(1 - \theta) *$ ② $\Rightarrow$ $\theta f(x) + (1 - \theta) f(y) \geqslant \triangledown f(z)^{T}[\theta x - \theta z + (1 - \theta) y - (1 - \theta) z]$
$\therefore \theta f(x) + (1 - \theta) f(y) \geqslant f(\theta x + (1 - \theta)y)$ #充分性得证

必要性：
令 $g(t) = f(ty + (1-t)x)$ ,根据“Restriction of convex function to a line”, $g(t)$ 与 $f(x)$ 有相同的凸性， $\because f(x)$ 为凸函数， $\therefore g(t)$ 为凸函数
${g(t)}' = \triangledown f(ty + (1-t)x)^{T}y - \triangledown f(ty + (1-t)x)^{T}x = \triangledown f(ty + (1-t)x)^{T}(y-x)$
注意到 $g(t)$ 为直线 $\therefore g(1) - g(0) \geqslant {g(0)}' *1$ ,代入g(1),g(0), ${g(0)}'$ $\Rightarrow$ $f(y) \geqslant f(x) + \triangledown f(z)^{T}(y -x)$
#必要性得证

凸函数的一阶条件及其证明

猜你喜欢

热点阅读