凸関数の性質

凸関数,最小値問題

469

はじめに

主成分分析を勉強している中で, 最小性について気になったのでまとめた.
一通り書いた後に凸関数使わなくてもいけるなと思ったけど備忘録.

ゴールは次の命題である((1), (2)は同じことを述べている).

お気持ち命題

$C^{2}$ 級凸関数において, 最小値を求めたければ微分して0となる点を求めればよい.
$f : R^{n} \to R$ が $C^{2}$ 級で $H_{f}$ が半正定値なら, 最小値を求めたければ微分して0となる点を求めればよい.

微分して0になる点を停留点と呼ぶが、一般に停留点は極値点になるとは限らない.
極値であっても極大値か極小値かは分からないし、最大値か最小値かはもっと分からない.
しかし上に挙げた条件を満たせば, 停留点は直ちに最小値を取る点になる(すごい).

凸関数の定義

$f : R^{n} \to R$ が凸関数であるとは,
任意の $u, v \in R^{n}, λ \in (0, 1)$ に対し, 以下が成り立つ：
$\begin{array}{r} f ((1 - λ) u + λ v) \leq (1 - λ) f (u) + λ f (v) \end{array}$
$f : R^{n} \to R$ が狭義凸関数であるとは,
任意の $u \neq v \in R^{n}, λ \in (0, 1)$ に対し, 以下が成り立つ：
$\begin{array}{r} f ((1 - λ) u + λ v) < (1 - λ) f (u) + λ f (v) \end{array}$

一変数における判定条件

一変数凸関数には次の判定条件がある.

$f : R \to R が C^{2}$ 級であるとき, 以下は同値.
(1) $f$ : 凸関数
(2) $f^{'}$ : 非減少関数, すなわち $\forall t_{1} \leq t_{2} \in R, f^{'} (t_{1}) \leq f^{'} (t_{2})$
(3) $\forall t \in R, f^{″} (t) \geq 0$

証明の流れは主に凸関数に倣う.
(1) $\Rightarrow$ (2). $t_{1} < t_{2}$ に対し, $\forall x \in (t_{1}, t_{2})$ について, $x = (1 - λ) t_{1} + λ t_{2}, (\exists λ \in (0, 1))$ と表せることに注意する. 実際, $\forall x \in (t_{1}, t_{2})$ について, $\exists s \in (0, t_{2} - t_{1}), x = t_{1} + s$ . これより $λ = \frac{s}{t_{2} - t_{1}} \in (0, 1)$ とおけばよい. このとき,
$\begin{aligned} \frac{f (x) - f (t_{1})}{x - t_{1}} & = \frac{f ((1 - λ) t_{1} + λ t_{2}) - f (t_{1})}{((1 - λ) t_{1} + λ t_{2}) - t_{1}} \\ \leq \frac{((1 - λ) f (t_{1}) + λ f (t_{2})) - f (t_{1})}{λ (t_{2} - t_{1})} = \frac{λ (f (t_{2}) - f (t_{1}))}{λ (t_{2} - t_{1})} = \frac{f (t_{2}) - f (t_{1})}{t_{2} - t_{1}} \end{aligned}$
$x \to t_{1}$ として, $f^{'} (t_{1}) \leq \frac{f (t_{2}) - f (t_{1})}{t_{2} - t_{1}}$ . 同様に
$\begin{array}{r} \frac{f (t_{2}) - f (x)}{t_{2} - x} \geq \frac{f (t_{2}) - f (t_{1})}{t_{2} - t_{1}} \end{array}$
で $x \to t_{2}$ として, $f^{'} (t_{2}) \geq \frac{f (t_{2}) - f (t_{1})}{t_{2} - t_{1}}$ . よって, $f^{'} (t_{1}) \leq f^{'} (t_{2})$ より $f^{'}$ は非減少である.
(2) $\Rightarrow$ (3). 明らか. 実際に $x < y$ について $f^{'} (x) \leq f^{'} (y)$ より,
$\begin{array}{r} \frac{f^{'} (y) - f^{'} (x)}{y - x} \geq 0. \end{array}$
$y \to x$ とすれば $f^{″} (x) \geq 0$ を得る.
(3) $\Rightarrow$ (1). テイラーの定理(杉浦解析I, 定理2.10)により, $\forall z, w \in R, \exists c \in R, s.t.$
$\begin{array}{r} f (w) = f (z) + f^{'} (z) (w - z) + f^{″} (c) \frac{(w - z)^{2}}{2} . \end{array}$
$f^{″} (c) \geq 0$ から,
$f (w) \geq f (z) + f^{'} (z) (w - z) .$
特に $w = a, b, z = (1 - t) a + t b, t \in (0, 1)$ について,
$\begin{array}{r} f (a) \geq f (z) + f^{'} (z) (a - z) \\ f (b) \geq f (z) + f^{'} (z) (b - z) . \end{array}$
が成り立つ. このとき,
$\begin{aligned} (1 - t) f (a) + t f (b) & \geq (1 - t) {f (z) + f^{'} (z) (a - z)} + t {f (z) + f^{'} (z) (b - z)} \\ = {f (z) + f^{'} (z) (a - z)} + t {- {f (z) + f^{'} (z) (a - z)} + {f (z) + f^{'} (z) (b - z)}} \\ = {f (z) + f^{'} (z) (a - z)} + t f^{'} (z) {- (a - z) + (b - z)} \\ = f (z) + f^{'} (z) {a - {(1 - t) a + t b}} + t f^{'} (z) (b - a) \\ = f (z) + f^{'} (z) t (a - b) + t f^{'} (z) (b - a) \\ = f (z) \\ = f ((1 - t) a + t b) . \end{aligned}$
よって定義より $f$ は凸関数である.

狭義凸関数についても一部類似の命題が成り立つ. (スキップしてもゴールの命題には影響ない)

$f : R \to R が C^{2}$ 級とする. 命題
(1) $f$ : 狭義凸関数
(2) $f^{'}$ : 狭義単調増加関数, すなわち $\forall t_{1} < t_{2} \in R, f^{'} (t_{1}) < f^{'} (t_{2})$
(3) $\forall t \in R, f^{″} (t) > 0$
に対し, (1) $\Leftrightarrow$ (2), (3) $\Rightarrow$ (1)が成り立つ.

(1) $\Rightarrow$ (2). 狭義凸関数は凸関数であるから, 命題2より $f^{'}$ は非減少. $\exists t_{1} < t_{2}$ で, $f^{'} (t_{1}) = f^{'} (t_{2})$ とすると, $f^{'}$ の非減少性から $\forall x \in [t_{1}, t_{2}], f^{'} (x) = f^{'} (t_{1})$ . すなわち $[t_{1}, t_{2}]$ 上で $f^{'}$ は定数. よって $(t_{1}, t_{2})$ 上で $f^{″} = 0$ . これよりテイラーの定理を用いると $\forall x \in (t_{1}, t_{2}] \subset R, \exists c \in (t_{1}, x) \subset (t_{1}, t_{2})$ ,
$\begin{aligned} f (x) & = f (t_{1}) + f^{'} (t_{1}) (x - t_{1}) + \frac{1}{2!} f^{″} (c) (x - t_{1})^{2} \\ = f (t_{1}) + f^{'} (t_{1}) (x - t_{1}) \\ ∴ f^{'} (t_{1}) & = \frac{f (x) - f (t_{1})}{x - t_{1}} \end{aligned}$
さて任意の $x = (1 - λ) t_{1} + λ t_{2}, (λ \in (0, 1))$ に対して, 狭義凸性から
$\begin{aligned} f (x) & < (1 - λ) f (t_{1}) + λ f (t_{2}) . \end{aligned}$
このとき,
$\begin{aligned} f^{'} (t_{1}) & = \frac{f (x) - f (t_{1})}{x - t_{1}} < \frac{(1 - λ) f (t_{1}) + λ f (t_{2}) - f (t_{1})}{(1 - λ) t_{1} + λ t_{2} - t_{1}} \\ = \frac{λ (f (t_{2}) - f (t_{1}))}{λ (t_{2} - t_{1})} = \frac{f (t_{2}) - f (t_{1})}{t_{2} - t_{1}} = f^{'} (t_{1}) \end{aligned}$
これは矛盾. よって $f^{'}$ は狭義単調増加.
(2) $\Rightarrow$ (1). 対偶で示す.
$\begin{array}{r} \exists x \neq y \in R, λ \in (0, 1), f ((1 - λ) x + λ y) = (1 - λ) f (x) + λ f (y) \end{array}$
とする. 必要なら $λ^{'} = 1 - λ$ とおくことで $x < y$ としてよい. $c = (1 - λ) x + λ y$ とおくと, $\frac{f (y) - f (x)}{y - x} = \frac{f (c) - f (x)}{c - x}$ が成り立つ.
ここで, 平均値の定理(杉浦解析I, 定理2.3)よりそれぞれ
$\begin{aligned} \exists t_{1} \in (x, y), f^{'} (t_{1}) = \frac{f (y) - f (x)}{y - x} \\ \exists t_{2} \in (x, c), f^{'} (t_{2}) = \frac{f (c) - f (x)}{c - x} \\ \exists t_{3} \in (c, y), f^{'} (t_{3}) = \frac{f (y) - f (c)}{y - c} \end{aligned}$
が成り立ち, $f^{'} (t_{1}) = f^{'} (t_{2})$ である. $f^{'} (t_{1})$ を変形すると,
$\begin{aligned} f^{'} (t_{1}) = \frac{f (y) - f (x)}{y - x} & = \frac{(f (y) - f (c)) + (f (c) - f (x))}{y - x} \\ = \frac{f (y) - f (c)}{y - x} + \frac{f (c) - f (x)}{c - x} \cdot \frac{c - x}{y - x} \end{aligned}$
したがって,
$\begin{aligned} \frac{f (y) - f (c)}{y - x} + f^{'} (t_{2}) \cdot \frac{c - x}{y - x} & = f^{'} (t_{2}) \\ \frac{f (y) - f (c)}{y - x} & = f^{'} (t_{2}) (1 - \frac{c - x}{y - x}) \\ f (y) - f (c) & = f^{'} (t_{2}) ((y - x) - (c - x)) = f^{'} (t_{2}) (y - c) \\ \frac{f (y) - f (c)}{y - c} & = f^{'} (t_{2}) \\ f^{'} (t_{3}) & = f^{'} (t_{2}) \end{aligned}$
ここで $t_{2} < t_{3}$ であるから $f^{'}$ は狭義単調増加でない.
(3) $\Rightarrow$ (1). 命題2の(3) $\Rightarrow$ (1)と同様にして, $\forall z \neq w \in R$ ,
$f (w) > f (z) + f^{'} (z) (w - z)$
が成り立つ. あとは同様.

命題3において一般に(2) $\Rightarrow$ (3)は成り立たない.
実際に $f (x) = x^{4}$ を考えると, $f^{'} (x) = 4 x^{3}$ は狭義単調増加だが, $f^{″} (x) = 12 x^{2} で f^{″} (0) = 0$ となる.

続いて凸関数とヘッセ行列の関係性をみる.

ヘッセ行列と半正定値

ヘッセ行列

$f : R^{n} \to R$ が $C^{2}$ 級のとき, 2回偏導関数を成分に持つ行列
$\begin{array}{r} H_{f} (x) = (\frac{\partial^{2} f}{\partial x_{i} \partial x_{j}} (x)) \end{array}$
をヘッセ行列と呼ぶ.

半正定値・正定値

$B$ : $n$ 次対称行列に対し, 二次形式 $Q : R^{n} \to R, x \mapsto x^{t} B x$ を考える.
(1) $B$ :半正定値 $\overset{def}{\Leftrightarrow} \forall x \in R^{n}, Q (x) \geq 0$ .
(2) $B$ :正定値 $\overset{def}{\Leftrightarrow} 0 \neq \forall x \in R^{n}, Q (x) > 0$ .

凸関数とヘッセ行列には次の関係性がある.

$f : R^{n} \to R$ に対し, 次が成り立つ.
(1) $f$ :凸関数 $\Leftrightarrow$ $\forall u \in R^{n}$ , ヘッセ行列 $H_{f} (u)$ : 半正定値
(2) $f$ :狭義凸関数 $\Leftarrow$ $\forall u \in R^{n}$ , ヘッセ行列 $H_{f} (u)$ : 正定値

$\forall b, c \in R^{n}$ に対し一変数関数 $h_{b, c}$ を
$\begin{array}{r} h_{b, c} : R \to R, t \mapsto f ((1 - t) b + t c) \end{array}$
で定める(以降添え字を省略してたりする). まず次が成り立つ.
$f$ :凸関数 $⟺$ $\forall b, c \in R^{n}, h_{b, c}$ : $C^{2}$ 級凸関数
証明

$(\Rightarrow)$ . $\forall t_{1}, t_{2} \in R, λ \in (0, 1)$ ,
$\begin{aligned} h_{b, c} ((1 - λ) t_{1} + λ t_{2}) \\ = f ({1 - ((1 - λ) t_{1} + λ t_{2})} b + ((1 - λ) t_{1} + λ t_{2}) c) \\ = f ((1 - λ) (- t_{1} b + t_{1} c) + λ (- t_{2} b + t_{2} c) + b) \\ = f ((1 - λ) ((1 - t_{1}) b + t_{1} c) + λ ((1 - t_{2}) b + t_{2} c)) \\ \leq (1 - λ) f ((1 - t_{1}) b + t_{1} c) + λ f ((1 - t_{2}) b + t_{2} c) \\ = (1 - λ) h_{b, c} (t_{1}) + λ h_{b, c} (t_{2}) \end{aligned}$
よって, $h_{b, c}$ は凸関数. また $f$ が $C^{2}$ 級であることから $h_{b, c}$ も $C^{2}$ 級.
$(\Leftarrow)$ . $\forall b, c \in R^{n}$ に対して, $h_{b, c}$ を考えると $h_{b, c} (0) = f (b), h_{b, c} (1) = f (c)$ より, $\forall t \in (0, 1)$ ,
$\begin{aligned} f ((1 - t) b + t c) = h_{b, c} (t) & = h_{b, c} ((1 - t) \cdot 0 + t \cdot 1) \\ \leq (1 - t) h_{b, c} (0) + t h_{b, c} (1) \\ = (1 - t) f (b) + t f (c) \end{aligned}$
よって, $f$ は凸関数.

また命題2より,
$\begin{array}{r} \forall b, c \in R^{n}, h_{b, c} : C^{2} 級凸関数 ⟺ \forall b, c \in R^{n}, t \in R, h_{b, c}^{″} (t) \geq 0 \end{array}$
さらに任意の $b, c \in R^{n}, t \in R$ に対し, $u = c - b, y = (1 - t) b + t c$ と置くと, $h_{b, c}^{″} (t) = u^{T} H_{f} (y) u$ が成り立つ. 実際,
$\begin{array}{r} g_{b, c} : R \to R^{n}, t \mapsto (1 - t) b + t c \end{array}$
とおくと, $h = f \circ g$ と書ける. $g_{i} = π_{i} \circ g$ を $i$ 番目の射影, $y = g (t)$ とおくと, $h^{'} (t), h^{″} (t)$ は連鎖率によって,
$\begin{aligned} h^{'} (t) & = f^{'} (y) \cdot g^{'} (t) \\ = [\begin{array}{c} \frac{\partial f}{\partial x_{1}} & \dots & \frac{\partial f}{\partial x_{n}} \end{array}] [\begin{array}{c} \frac{\partial g_{1}}{\partial t} \\ ⋮ \\ \frac{\partial g_{n}}{\partial t} \end{array}] \\ = \sum_{i} (c_{i} - b_{i}) \frac{\partial f}{\partial x_{i}} (y) = \sum_{i} (c_{i} - b_{i}) \frac{\partial f}{\partial x_{i}} \circ g (t) \\ h^{″} (t) & = \sum_{i} (c_{i} - b_{i}) {(\frac{\partial f}{\partial x_{i}} \circ g (t))}^{'} \\ = \sum_{i} (c_{i} - b_{i}) [\begin{array}{c} \frac{\partial f}{\partial x_{i} \partial x_{1}} & \dots & \frac{\partial f}{\partial x_{i} \partial x_{n}} \end{array}] [\begin{array}{c} c_{1} - b_{1} \\ ⋮ \\ c_{n} - b_{n} \end{array}] \\ = \sum_{i} (c_{i} - b_{i}) \sum_{j} (c_{j} - b_{j}) \frac{\partial f}{\partial x_{i} \partial x_{j}} (y) \\ = \sum_{i, j} (c_{i} - b_{i}) (c_{j} - b_{j}) \frac{\partial f}{\partial x_{i} \partial x_{j}} (y) \\ = u^{T} H_{f} (y) u \end{aligned}$
よって,
$\begin{array}{r} \forall b, c \in R^{n}, h_{b, c}^{″} (t) \geq 0 \Leftrightarrow \forall y \in R^{n}, H_{f} (y) : 半正定値 \end{array}$
$(\Rightarrow)$ . $\forall y, u \in R^{n}$ に対し $t = 0, b = y, c = y + u$ とおくと, $0 \leq h_{b, c}^{″} (t) = u^{T} H_{f} (y) u$ . よって任意の $y \in R^{n}$ に対し, $H_{f} (y)$ は半正定値.
$(\Leftarrow)$ . 明らか.
以上をまとめて(1)を得る.
$h_{b, c}^{″} (t) = u^{T} H_{f} (y) u$ であることから同様に
$\begin{array}{r} \forall b \neq c \in R^{n}, h_{b, c}^{″} (t) > 0 \Leftrightarrow \forall y \in R^{n}, H_{f} (y) : 正定値 \end{array}$
が成り立つ. よって同様にして $H_{f} (y)$ が正定値なら命題3と合わせて, $f$ は狭義凸.

凸関数の最小性に関する性質

$C^{2}$ 級凸関数における停留点は最小点
狭義凸関数において最小値を持てばただ一つ

多変数のテイラーの定理(杉浦解析I, 定理7.2) より, $\forall y, x \in R^{n}, h := y - x, \exists θ \in (0, 1) s.t.$
$\begin{aligned} f (y) & = f (x) + (d f)_{x} (h) + \frac{1}{2!} (d^{2} f)_{(x + θ h)} (h) \\ = f (x) + f^{'} (x) h + h^{T} H_{f} (x + θ h) h \end{aligned}$
命題3(1)より凸関数のヘッセ行列は半正定値であるから $h^{T} H_{f} (x + θ h) h \geq 0$ . よって,
$\begin{array}{r} f (y) \geq f (x) + f^{'} (x) h \end{array}$
ここで $x$ を $f$ の停留点とすると $f^{'} (x) = 0$ から $f (y) \geq f (x)$ を得る.
したがって, $f$ は $x$ において最小値を取り $x$ は最小点である.
$f$ が $x, y (x \neq y)$ において最小値 $f (x) = f (y)$ を取るとする. 狭義凸性から $\forall λ \in (0, 1)$ ,
$\begin{array}{r} f ((1 - λ) x + λ y) < (1 - λ) f (x) + λ f (y) = f (x) \end{array}$
これは $f (x)$ の最小性に矛盾. よって最小値を取る点は唯一つ.