凸集合と凸結合

816

凸集合と凸結合

この記事では凸結合の定義と凸集合と関連する命題について扱います。

凸結合の定義

凸結合の定義と図による解釈を説明していきます。

$x_{1}, \dots, x_{n}$ の $c o n v e x c o m b i n a t i o n$ （凸結合）
$\Leftrightarrow x = λ_{1} x_{1} + \dots + λ_{n} x_{n} (λ_{1}, \dots, λ_{n} \geq 0, \sum_{i = 1}^{n} λ_{i} = 1)$
$(x = \sum_{i = 1}^{n} λ_{i} x_{i} (λ_{1}, \dots, λ_{n} \geq 0, \sum_{i = 1}^{n} λ_{i} = 1))$

凸結合とは任意の点に対して、各係数の和が $1$ となる正の係数でスカラー倍した点の和となります。このように書いても全くイメージがしにくいので、まず2つの点で考えてみることにします。

凸結合（2点）

この図の点 $x_{1}, x_{2}$ で考えてみると、 $λ_{1}, λ_{2} \geq 0, λ_{1} + λ_{2} = 1$ に対して、 $λ_{1} x_{1} + λ_{2} x_{2}$ は橙色の線分となります。ここで $λ_{2} = 1 - λ_{1}$ であることに注目すると、2点の凸結合は $λ_{1} x_{1} + (1 - λ_{1}) x_{2}$ となります。この式には見覚えがあると思いますが、これは凸集合の定義に出てきた式と同じですね。同様に3点で考えてみましょう。

凸結合（3点）

この図では $λ_{1}, λ_{2}$ を固定しているようなイメージとなります。先ほどの2点 $x_{1}, x_{2}$ の凸結合を利用し、 $x_{3}$ との凸結合を考えてみましょう。先ほどの $λ_{1}, λ_{2}$ を $\hat{λ_{1}}, \hat{λ_{2}}$ とし、新しく $0 \leq λ_{3} \leq 1$ を考えると、 $(1 - λ_{3}) (\hat{λ_{1}} x_{1} + \hat{λ_{2}} x_{2}) + λ_{3} x_{3}$ が3点の凸結合となります。ここで $λ_{1} = (1 - λ_{3}) \hat{λ_{1}}, λ_{2} = (1 - λ_{3}) \hat{λ_{2}}$ とおけば、3点の凸結合は $λ_{1} x_{1} + λ_{2} x_{2} + λ_{3} x_{3}$ と書けます。 $λ_{1} + λ_{2} + λ_{3} = (1 - λ_{3}) \hat{λ_{1}} + (1 - λ_{3}) \hat{λ_{2}} + λ_{3} = (1 - λ_{3}) + λ_{3} = 1$ となることも確認できます。

凸結合（3点）2

先ほどは $λ_{1}, λ_{2}$ を固定しているようなイメージでしたが、この $λ_{1}, λ_{2}$ を $0 \leq λ_{1}, λ_{2} \leq 1$ の範囲で動かしてみた図となります。3点 $x_{1}, x_{2}, x_{3}$ を頂点とする三角形内を占めるように見えますね。さらに同じように $x_{4}, x_{5}, x_{6}$ と点を増やして見てみましょう。

凸結合（6点）

少しごちゃごちゃしているような感じですが、 $x_{1}, x_{2}$ から順々に考えていった場合の凸結合です。

凸結合（6点）2

3点の場合と同じように、各 $λ$ を動かしてみた場合の図です。この6点の凸結合をそれなりに表しているので、ある程度どのあたりが凸結合 $\sum_{i = 1}^{6} λ_{i} x_{i}$ で表せる範囲なのかを見ることができます。この図から $x_{3}$ は中にありますが、 $x_{1}, x_{2}, x_{4}, x_{5}, x_{6}$ を頂点とする多角形内を占めるように見えます。

凸結合と凸集合

ある集合が凸であることと、集合内の任意の点の凸結合がその集合に含まれることは同値となります。このことを示しているのが下記の命題です。

$C : c o n v e x$
$\Leftrightarrow \forall c_{1}, \dots, c_{n} \in C, \sum_{i = 1}^{n} λ_{i} c_{i} \in C (λ_{1}, \dots, λ_{n} \geq 0, \sum_{i = 1}^{n} λ_{i} = 1)$

＜証明の考え方＞
$(\Rightarrow)$ について。
任意の $n$ 個の点について示したいので、数学的帰納法で示す。

$(\Leftarrow)$ については凸集合の定義を思い出してみる。

$(\Rightarrow)$ を示す。
数学的帰納法で証明する。

$i = 1$ のとき
$\forall c_{1} \in C, λ_{1} = 1$ を考えると、
$λ_{1} c_{1} = c_{1} \in C$ より明らか。
$i = 2$ のとき
$\forall c_{1}, c_{2} \in C, λ_{1}, λ_{2} \geq 0, λ_{1} + λ_{2} = 1$ を考えると、
$C : c o n v e x$ より $λ_{1} c_{1} + λ_{2} c_{2} \in C$ となる。
$i = n - 1$ のとき成り立つと仮定すると、
$\sum_{i = 1}^{n - 1} λ_{i} c_{i} \in C (λ_{1}, \dots, λ_{n - 1} \geq 0, \sum_{i = 1}^{n - 1} λ_{i} = 1)$
が成り立つ。
$c_{n} \in C, 0 \leq \hat{λ_{n}} \leq 1$ をとると、 $C : c o n v e x$ より、
$\hat{λ_{n}} c_{n} + (1 - \hat{λ_{n}}) \sum_{i = 1}^{n - 1} λ_{i} c_{i} \in C となる。$
$(\hat{λ_{n}} + (1 - \hat{λ_{n}}) \sum_{i = 1}^{n - 1} λ_{i} = \hat{λ_{n}} + (1 - \hat{λ_{n}}) = 1,$
$(1 - \hat{λ_{n}}) λ_{i} \geq 0 (\forall i = 1, \dots, n - 1) となっている。)$
新しく $\hat{λ_{i}} = (1 - \hat{λ_{n}}) λ_{i}$ とおくと、
$\sum_{i = 1}^{n} \hat{λ_{i}} c_{i} \in C (\sum_{i = 1}^{n} \hat{λ_{i}} = 1, \hat{λ_{1}}, \dots, \hat{λ_{n}} \geq 0)$
となるため、 $i = n$ でも成り立つことを示せた。

$(\Leftarrow)$ を示す。
$n = 2$ として考えると、
$\forall c_{1}, c_{2} \in C, λ_{1} + λ_{2} = 1, λ_{1}, λ_{2} \geq 0$ に対して、 $λ_{1} c_{1} + λ_{2} c_{2} \in C$ となる。
これは $c o n v e x$ の定義なので、 $C : c o n v e x$ を示すことができた。