凸関数の定義について
凸関数の定義の仕方が3種類あるそうです。よく知られた定義は定義1です。
以下の条件を満たす関数$f$は凸関数である。
$f(\lambda x+(1-\lambda)y) \leq \lambda f(x)+(1-\lambda)f(y) \ \ \ ,\forall x,y \in \mathbb{R}^n, \lambda\in[0,1]$
動画では厳密に定義してないので、細かな設定は必要だとは思うのですが、ざっくりいうと定理1が成り立つそうです。
$f$は凸関数であるとする。以下の条件は同値である。
- $f(\lambda x+(1-\lambda)y) \leq \lambda f(x)+(1-\lambda)f(y),\ \ \ \forall x,y \in \mathbb{R}^n, \lambda\in[0,1]$
- $f(y)\geq f(x)+\langle\nabla f(x),y-x\rangle$ $\forall y$
- $\nabla^2f(x)\succeq 0$
一部のみ証明する。
3が成り立つならば2が成り立つことを証明する。
証明の流れとしては、3が成り立つならば$\nabla f$は単調であることを証明する。その後、$\nabla f$が単調であれば2が成り立つことを証明する。
- 3が成り立つならば$\nabla f$は単調である
$$ \begin{eqnarray} \int_{0}^{1}(x-y)^T\nabla^2 f(tx+(1-t)y)dt &=&\int_{0}^{1}\dfrac{d}{dt}\nabla f(t(x-y)+y)dt\\ &=&\nabla f(x)-\nabla f(y) \end{eqnarray} $$
$$ \begin{eqnarray} 0\leq\int_{0}^{1}(x-y)^T\nabla^2 f(tx+(1-t)y)(x-y)dt &=&\langle\nabla f(x)-\nabla f(y),x-y\rangle \end{eqnarray} $$
よって、3が成り立つならば$\nabla f$は単調である。
- $\nabla f$が単調であれば2が成り立つ
$$ \begin{eqnarray} \int_{0}^{1}\nabla f\left((y-x)t+x\right)^T(y-x)dt &=&\int_{0}^{1}\dfrac{d}{dt}f((y-x)t+x)dt\\ &=&f(y)-f(x) \end{eqnarray} $$
$$ f(y) = f(x)+\int_{0}^{1}\nabla f\left((y-x)t+x\right)^T(y-x)dt $$
関数$h(t)$を以下のように定義する。
$$ h(t):=\nabla f\left((y-x)t+x\right)^T(y-x)\\ h(0):=\nabla f\left(x\right)^T(y-x) $$
$\nabla f$は単調であるので、
$$
\langle\nabla f((y-x)t+x)-\nabla f(x),(y-x)t+x-x\rangle\geq0
$$
つまり、
$$ \langle\nabla f((y-x)t+x)-\nabla f(x),(y-x)t\rangle\geq0 $$
$t\geq0$であるので、
$$ \langle\nabla f((y-x)t+x)-\nabla f(x),y-x\rangle\geq0 $$
よって、
$$
h(t)-h(0)\geq0
$$
両辺を積分して式変形すれば、
$$
\int_{0}^{1}h(t)dt\geq\int_{0}^{1}h(0)dt=h(0)\int_{0}^{1}dt=h(0)
$$
よって、
$$ \begin{eqnarray} f(y) &=& f(x)+\int_{0}^{1}h(t)dt\\ &\geq&f(x)+h(0)\\ &=& f(x)+f\left(x\right)^T(y-x) \end{eqnarray} $$
よって、$\nabla f$が単調であれば2が成り立つ。