以下考える関数はすべて$C^{\infty}$級とする。
(狭義)凸関数の定義
$f$が凸関数である:
\forall x, y \in \mathbb{R}^n, t \in (0,1), f(ta + (1-t)b) \leq tf(a) + (1-t)f(b).
$f$が狭義凸関数である:
\forall x, y \in \mathbb{R}^n, \ x \neq y, \ t \in (0,1), f(ta + (1-t)b) < tf(a) + (1-t)f(b).
ちなみに$f, g$がそれぞれ凸関数なら、$f+g$も凸関数。定義からすぐでる。しかしながら$fg$という積をとると必ずしもそうでない(多分。反例も証明も知らないので多分。)
一変数の凸関数の性質
以下$g: \mathbb{R} \rightarrow \mathbb{R}$とする。
同値命題
以下はすべて同値
- $g$は凸関数である。
- $g'$は単調増加関数である。
- $g'' \geq 0$.
証明(3. -> 1.)
テイラーの定理により、$\forall z, w \in \mathbb{R}, \ \exists c \in \mathbb{R}, \ \text{s.t.} $
g(w) = g(z) + g'(z) (w - z) + g''(c) \frac{(w-z)^2}{2}.
仮定$g''(x) \geq 0, \ \forall x \in \mathbb{R}$より、
g(w) \geq g(z) + g'(z)(w-z).
特に$x=a, b, z=ta + (1-t)b, t \in (0,1)$に関する式をそれぞれたてると、
\begin{align}
g(a) \geq g(z) + g'(z)(a-z) \\
g(b) \geq g(z) + g'(z)(b-z).
\end{align}
それぞれに$t, 1-t$をかけて足すと、
\begin{align}
tg(a) + (1-t)g(b) &\geq g(z) + tg'(z)(a-z) + (1-t)g'(z)(b-z) \\
&= g(z) + tg'(z)(a - ta - (1-t)b) + (1-t)g'(z)(b- ta - (1-t)b) \\
&= g(z) + g'(z)(ta - t^2 a - t(1-t)b + (1-t)b - (1-t)ta - (1-t)^2b) \\
&= g(z) + g'(z)(ta - t^2 a - tb + t^2 b + b - tb - ta + t^2 a - b + 2tb - t^2 b) \\
&= g(z).
\end{align}
証明(1. -> 2.)
$a < x < b$なる$a, b, x$に対して以下の式が成立する。
\frac{g(x) - g(a)}{x - a} \leq \frac{g(b) - g(a)}{b-a} \leq \frac{g(b) - g(x)}{b-x}.
なぜなら、仮定の$g$の凸性により$x=ta + (1-t)b$と表せることに注意すれば、
\begin{align}
\frac{g(x) - g(a)}{x-a} &\leq \frac{(1-t)(g(b) - g(a))}{(1-t)(b-a)} \\
&= \frac{g(b) - g(a)}{b-a}. \\
\frac{g(b) - g(x)}{b-x} &\geq \frac{t(f(b) - f(a))}{t(b-a)} \\
&= \frac{g(b) - g(a)}{b-a}.
\end{align}
ここで最左辺を$x \rightarrow a$, 最右辺を$x \rightarrow b$とすれば、
f'(a) \leq \frac{f(b) - f(a)}{b-a} \leq f'(b).
証明(2. -> 3.)
$f'$が単調増加関数であることから明らか。
同値命題(特に狭義凸関数の場合)
- $g$は狭義凸関数である。
- $g'$は狭義単調増加関数である。
- $g'' > 0$.
証明(3. -> 1. -> 2. -> 3.)
上の証明を繰り返せばOK.
狭義凸関数の最小値まわりの話
狭義凸関数だからと言って、一般に最小値を持つわけではない。たとえば$g(x) = e^{x}$.
しかしながら、もし最小値$\min_x g(x) = g(c)$が存在すれば、以下が成立する。
- 最小値は$c$ただ一つである。
また最小値の存在性そのものは、以下が確かめられればいい。
- $g'(x) = 0$ならば$g(x)$は最小値。
証明(最小値はただ一つ)
最小値が2つ存在するとする, i.e. $\exists a, b \in \mathbb{R}, \ a \neq b, \ \text{s.t.} g(a) = g(b) = \min_x g(x)$.
$z= ta + (1-t)b, t \in \mathbb{R}$とすると、狭義凸性により、
g(z) < tg(a) + (1-t)g(b) = \min_x g(x).
矛盾。
証明(微分係数=0)
$g'(c) = 0$とする。任意の$x \in \mathbb{R}$に対してテイラーの定理を適用すると、
\exists d \in \mathbb{R}\ \text{s.t.} \ g(x) = g(c) + g'(c) (x-c) + \frac12 g''(d) (x-c)^2 \\
が成立する。$g$の狭義凸性から$g'' > 0$であることと仮定$g'(c) = 0$を考慮すれば
g(x) > g(c).
n変数の凸関数の性質
$f: \mathbb{R}^n \rightarrow \mathbb{R}$とする。
同値命題
以下はすべて同値。
- $f$は凸関数である。
- $\nabla^2 f$は半正定値。
証明(1. <-> 2.)
まず$\forall x, y \in \mathbb{R}^n$, $t \in (0,1)$に対して、$h: [0,1] \rightarrow \mathbb{R}$を以下のように定義する：
h(t) = f(ta + (1-t)b).
$h$は凸関数である。なぜなら$\forall z,w,p \in [0,1]$に対し$t=pz + (1-p)w$とすれば、
\begin{align}
h(t) &= f((pz + (1-p)w)a + (1-(pz + (1-p)w))b) \\
&\leq ph(z) + (1-p)h(w).
\end{align}
細かい計算は略。$f$の凸性を考慮すればよい。
$h(t) = f(b + t(a-b))$とすれば、連鎖律により以下が成立する。
\begin{align}
\frac{d^2 h(t)}{d t^2} &= \sum_{i,j=1}^{n} \frac{\partial f(b + t(a-b))}{\partial a_i \partial a_j} (a_i - b_i)(a_j - b_j)
\end{align}
ここで以下のように置きなおす。
\begin{align}
u &= b + t(a-b) \\
v &= a - b
\end{align}
すると以下のようにかける。
\frac{d^2 h(t)}{d t^2} = v^T \nabla^2 f(u) v.
$h$の凸性により$h \geq 0$である。ゆえに半正定値。
逆は証明を後ろからたどればよい。
同値命題(特に狭義凸関数の場合)
以下は同値
- $f$は狭義凸関数である。
- $\nabla^2 f$は正定値。
証明(1. <-> 2.)
上の証明を真に不等式が成立するとして考えればOK。
狭義凸関数の最小値まわりの話
やはり狭義凸関数だからといって必ずしも最小値を持つわけではない。例えば$e^{x+y}$.
しかし最小値を持つとしたらただ一つである。また最小値の存在性は$\nabla f(x) = 0$となることで示せる。
最小値のユニーク性は1次変数のときと全く同じ。勾配ベクトルが0となる場合のみ示す。
$\nabla f(c) = 0$とする。この$0$はスカラーではなくベクトルである。雰囲気でわかると思うが。
任意の$x \in \mathbb{R}^n$に対しテイラーの定理により
\begin{align}
f(x) &= f(c) + \nabla f(c)^T (x - c) + \frac12 (x-c)^T \nabla^2 f(d) (x-c) \\
&> f(c).
\end{align}
ここでは$\nabla f(c) =0$と正定値性を考慮した。