📂関数

一般的な凸関数の定義

定義

ベクトル空間 $V$ で定義された関数 $f : V \to \mathbb{R}$ が全ての $\mathbf{x}, \mathbf{y} \in V$ と全ての $t \in [0,1]$ に対して次を満たす時、凸関数^{convex function}と言われる。 $$ f \left( (1-t) \mathbf{x} + t \mathbf{y} \right) \le (1-t) f \left( \mathbf{x} \right) + t f \left( \mathbf{y} \right) $$

説明

実は、学部レベル以上の数学を学ぶと、凹や凸の表現はほとんど使わず、凸^convexという用語だけをほぼ排他的に使用する。上で紹介された凸関数は、ユークリッド空間 $X = \mathbb{R}$ で定義された凸関数の一般化である。

例

解の集合が放物線を形成する $f(x,y) := x^{2} + y^{2}$ は凸関数であり、その値が最小になる点は $(x,y) = (0,0)$ である。

定理

凸集合における凸関数の最適解

$f : \mathbb{R}^{n} \to \mathbb{R}$ が微分可能な凸関数であり、凸集合 $C \subset \mathbb{R}^{n}$ が凸集合である場合、次の二つは等価である。

• $\mathbf{x}^{\ast} \in C$ は $C$ で $f$ を最小化する最適解である。
• 全ての $\mathbf{x} \in C$ に対して $$ \nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0 $$

証明 ¹

$(\implies)$

$$ \mathbf{x}(t) := \mathbf{x}^{\ast} + t \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \in C \qquad , t \in [0,1] $$ $C$ は凸集合と仮定されるので、任意の $\mathbf{x} \in C$ と $\mathbf{x}^{\ast}$ のある内分点 $\mathbf{x}(t)$ は上記のように表される。一方で

• $\mathbf{x}^{\ast} = \argmin_{\mathbf{x} \in C} f$ なので全ての $\mathbf{x} \in C$ に対して $f \left( \mathbf{x}(t) \right) - f \left( \mathbf{x}^{\ast} \right) \ge 0$ であり
• $f \left( \mathbf{x}(t) \right)$ の $t = 0$ での偏微分係数は連鎖律により $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right)$ なので

$$ \begin{align*} & \nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \\ =& \left[ {{ \partial } \over { \partial t }} f \left( \mathbf{x} (t) \right) \right]_{t = 0} \\ =& \lim_{t \to 0} {{ f \left( \mathbf{x} (t) \right) - f \left( \mathbf{x}^{\ast} \right) } \over { t }} \\ \ge & 0 \end{align*} $$ 結果として $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0$ を得る。

---

$(\impliedby)$

$$ f \left( (1-t) \mathbf{z} + t \mathbf{y} \right) \le (1-t) f \left( \mathbf{z} \right) + t f \left( \mathbf{y} \right) $$ 両辺を $t$ で微分すると $$ \left( - \mathbf{z} + \mathbf{y} \right) \nabla f \left( (1-t) \mathbf{z} + t \mathbf{y} \right) \le - f \left( \mathbf{z} \right) + f \left( \mathbf{y} \right) $$ なので、$t = 0$ 時に次を得る。 $$ f \left( \mathbf{z} \right) + \nabla f \left( \mathbf{z} \right) \left( \mathbf{y} - \mathbf{z} \right) \le f \left( \mathbf{y} \right) $$ 仮定で $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0$ なので、$\mathbf{y} = \mathbf{x}$ と $\mathbf{z} = \mathbf{x}^{\ast}$ に対して次を得る。 $$ \begin{align*} & f \left( \mathbf{x}^{\ast} \right) + 0 \\ \le & f \left( \mathbf{x}^{\ast} \right) + \nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \\ \le & f \left( \mathbf{x} \right) \end{align*} $$ つまり $f \left( \mathbf{x}^{\ast} \right) \le f \left( \mathbf{x} \right)$ であり、これは全ての $\mathbf{x} \in C$ に対して成立するので $\mathbf{x}^{\ast}$ は $C$ で $f$ の最小解となる。

■