P10

• 凸函数的定义
• 凸函数的扩展
• 示性函数是凸函数
• 一阶条件

凸函数的定义

一个函数$f: R^n \mapsto R$f:Rn↦R 为凸,等价于
$dom f$domf为凸集
且对所有的 $x,y \in domf, 0 \leq \theta \leq 1$x,y∈domf,0≤θ≤1 有 $f(\theta x + (1-\theta) y) \leq \theta f(x) + (1-\theta)f(y)$f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y)

凸函数的扩展

$f: R^n \mapsto R$f:Rn↦R 为凸 $dom \; f = C \subseteq R^n$domf=C⊆Rn

定义
$\hat{f} =\begin{cases} f(x), & \text { $x \in domf$} \\ + \infty , & \text{$x \notin domf$} \end{cases}$f^​={f(x),+∞,​ x∈domfx∈/​domf​
$\hat{f}: R^n \mapsto R \quad dom \hat{f}= R^n$f^​:Rn↦Rdomf^​=Rn

示性函数是凸函数

突击 $C \subseteq R^n$C⊆Rn
$f_c(x) = \begin{cases} 无定义, & \text { $x \notin C$} \\ 0 , & \text{$x \in C$} \end{cases}$fc​(x)={无定义,0,​ x∈/​Cx∈C​
$I_c(x) = \begin{cases} + \infty, & \text { $x \notin C$} \\ 0 , & \text{$x \in C$} \end{cases}$Ic​(x)={+∞,0,​ x∈/​Cx∈C​

$f_c(x)、I_c(x)$fc​(x)、Ic​(x) 都是凸函数 $+\infty/2=+\infty$+∞/2=+∞

$J_c(x) = \begin{cases} 1, & \text { $x \notin C$} \\ 0 , & \text{$x \in C$} \end{cases}$Jc​(x)={1,0,​ x∈/​Cx∈C​

$J_c(x)$Jc​(x) 不是凸函数也不是凹函数

一阶条件

设$f: R^n \mapsto R$f:Rn↦R 可微，即梯度 $\triangledown f在domf上均存在$▽f在domf上均存在，则$f$f为凸等价于：
$domf$domf为凸
$f(y)\geq f(x)+\triangledown f^T(x)(y-x) \quad \forall x,y \in domf$f(y)≥f(x)+▽fT(x)(y−x)∀x,y∈domf

证明:一阶条件
考虑一维情况$f: R \mapsto R$f:R↦R 为凸,
等价于$dom f$domf为凸集，且 $f(y) \geq f(x) + f'(x)(y-x)$f(y)≥f(x)+f′(x)(y−x)
证：$\Rightarrow$⇒
$f$f为凸,$\forall x,y \in domf$∀x,y∈domf 为凸
$\forall t,0<t \leq t,x+t(y-x) \in domf$∀t,0<t≤t,x+t(y−x)∈domf

$f(x+t(y-x)) \leq (1-t)f(x) + tf(y)$f(x+t(y−x))≤(1−t)f(x)+tf(y)
$tf(y) \geq tf(x) + f(x+(y-x)) - f(x)$tf(y)≥tf(x)+f(x+(y−x))−f(x)
$f(y) \geq f(x) + \frac{ f(x+(y-x)) - f(x)}{t}$f(y)≥f(x)+tf(x+(y−x))−f(x)​
设 $lim_{t \rightarrow 0_+}$limt→0+​​
$f(y) \geq f(x) + f'(x)(y-x)$f(y)≥f(x)+f′(x)(y−x)

证: $\Leftarrow$⇐
设 $\forall x \not= y$∀x​=y $x,y \in domf$x,y∈domf
$0 \leq \theta \leq 1$0≤θ≤1 构造 $z = \theta x +(1-\theta)y \in domf$z=θx+(1−θ)y∈domf
$f(x) \geq f(z) + f'(z)(x-z)$f(x)≥f(z)+f′(z)(x−z)
$f(y) \geq f(z)+ f'(z)(y-z)$f(y)≥f(z)+f′(z)(y−z)

$\theta f(x) + (1-\theta)f(y) \geq f(z) + (\theta(x-z)+(1-\theta)(y-z))f'(z)$θf(x)+(1−θ)f(y)≥f(z)+(θ(x−z)+(1−θ)(y−z))f′(z)
$\theta f(x) + (1-\theta)f(y) \geq f(z) + (\theta x +(1-\theta)y -z)f'(z)$θf(x)+(1−θ)f(y)≥f(z)+(θx+(1−θ)y−z)f′(z)
$\theta f(x) + (1-\theta)f(y) \geq f(z)$θf(x)+(1−θ)f(y)≥f(z)