凸集合と基本性質

凸解析学,凸集合

822

凸集合の定義と基本性質

この記事では凸解析学の中でも、基礎となる凸集合の定義から記載していきます。

はじめに

凸集合について、定義や基本性質などを図を交えてまとめていきます。

凸集合

convex,cone

集合 $C$ が $c o n v e x$ （凸集合）である
$\Leftrightarrow \forall x, y \in C, 0 \leq λ \leq 1 に対して λ x + (1 - λ) y \in C をみたす。$

集合 $C$ が $c o n e$ （錐）である
$\Leftrightarrow x \in C, λ \geq 0 に対して λ x \in C をみたす。$

集合 $C$ がconvex（凸）、cone（錐）であるという定義は上のとおりです。凸集合というのは、ある集合からどのような2点を選んでも、その2点間のすべての点が集合に含まれているということになります。錐であるというのは、集合から選んだ点と原点を結んだ半直線（原点を始点とする）を考え、その半直線が集合に含まれていることをいいます。またconvex（凸）でもcone（錐）でもある集合をconvex coneといいます。定義から空集合はconvex（凸集合）とみなされます。

平面で図示した例

集合 $C$ は橙色の部分で示し、原点を $O$ としています。

convex set（凸集合）

2点 $x, y$ を集合 $C$ 内のどこに移動させても、2点を結ぶ線分（赤色）は $C$ の外にはみ出ることはありません。この線分が $λ x + (1 - λ) y (0 \leq λ \leq 1)$ です。

non-convex set（凸でない集合）

2点 $x, y$ を結ぶ線分が $C$ に含まれるように選ぶこともできますが、この図においては線分が $C$ からはみ出る部分ができてしまいます。なので凸集合ではありません。

cone（錐）

点 $x$ を正の実数倍した点、つまり $λ x (λ \geq 0)$ となる点を緑色で示しています。これらのすべての点が $C$ に含まれ、点 $y$ でも同様に考えることができるのでcone（錐）といえます。しかし点 $x, y$ を結ぶ線分は $C$ からはみ出ているのでconvex（凸）ではありません。

convex cone（凸錐）

$λ x (λ \geq 0)$ が $C$ に含まれていて、点 $x, y$ を結ぶ線分も $C$ に含まれているので、convex（凸）でもありcone（錐）でもある集合です。

凸集合に関するの演習問題

$C : c o n e （錐）について、次が成り立つ。$
$C : c o n v e x （凸） \Leftrightarrow \forall x, y \in C, x + y \in C 。$

＜証明の考え方＞
$(\Rightarrow) について。$
$x + y = 2 (\frac{1}{2} x + \frac{1}{2} y) であることに着目する。$

$(\Leftarrow) について。$
$λ x + (1 - λ) y を示したいので、まず λ x, (1 - λ) y \in C を示す。$

$(\Rightarrow) を示す。$
$C : c o n v e x より、 \forall x, y \in C, 0 \leq λ \leq 1 に対して、 λ x + (1 - λ) y \in C である。$
$λ = \frac{1}{2} とすると \frac{1}{2} x + \frac{1}{2} y \in C となる。$
$C : c o n e より、 2 (\frac{1}{2} x + \frac{1}{2} y) \in C である。$
$すなわち、 x + y \in C となり (\Rightarrow) が示せた。$

$(\Leftarrow) を示す。$
$C : c o n e より、 \forall x, y \in C, 0 \leq λ \leq 1 に対して、$
$λ x, (1 - λ) y \in C である。$
$すると条件より、 λ x + (1 - λ) y \in C となる。$
$よって、 C : c o n v e x を示せた。$

この問題を図で確認してみることにします。

cone, non convex（凸でない錐）

上の図では $x, y \in C$ の凸結合の一部が集合 $C$ からはみ出ているのでconvexではありません。またこの図のように $x, y$ をおくと、 $x + y$ も集合 $C$ に含まれていません。 $x + y \in C$ となるようにうまく $x, y$ を取ることもできますが、任意の点でそうはいきません。

convex cone（凸錐）

一方で上の図では集合 $C$ :coneはconvexでもあります。そしてどのように $x, y$ をとっても $x + y$ は $C$ に含まれます。

$A + B = {a + b | a \in A, b \in B}$
$t A = {t a | a \in A, t \in R}$

$C_{1}, C_{2} : c o n v e x$
$\Rightarrow C_{1} + C_{2} : c o n v e x$
$C : c o n v e x$
$\Rightarrow t C : c o n v e x (t \in R)$

＜証明の考え方＞
どちらについても、convex（凸）の定義をみたすことを確認すればOKなので、集合から任意の2点 $x, y$ を選び、 $λ x + (1 - λ) y$ がその集合に含まれることを示すことを目指します。

(i) を示す。
$\forall x, y \in C_{1} + C_{2} を考える。$
$すると、 \exists x_{1}, y_{1} \in C_{1}, \exists x_{2}, y_{2} \in C_{2} s . t . x = x_{1} + x_{2}, y = y_{1} + y_{2} である。$
$C_{1}, C_{2} : c o n v e x より、 0 \leq λ \leq 1 に対して$
$λ x_{1} + (1 - λ) y_{1} \in C_{1}, λ x_{2} + (1 - λ) y_{2} \in C_{2} である。$
$このことより、 λ x_{1} + (1 - λ) y_{1} + λ x_{2} + (1 - λ) y_{2} \in C_{1} + C_{2} となる。$
$ここで要素の式を変形していくと、$
$λ x_{1} + (1 - λ) y_{1} + λ x_{2} + (1 - λ) y_{2}$
$= λ (x_{1} + x_{2}) + (1 - λ) (y_{1} + y_{2})$
$= λ x + (1 - λ) y \in C_{1} + C_{2}$
$よって、 C_{1} + C_{2} : c o n v e x を示すことができた。$

(ii) を示す。
$\forall x, y \in t C を考える。$
$すると、 \exists \bar{x}, \bar{y} \in C s . t . x = t \bar{x}, y = t \bar{y} である。$
$C : c o n v e x より、 0 \leq λ \leq 1 に対して、 λ \bar{x} + (1 - λ) \bar{y} \in C である。$
$このことより、 t (λ \bar{x} + (1 - λ) \bar{y}) \in t C となる。$
$ここで要素の式を変形していくと、$
$t (λ \bar{x} + (1 - λ) \bar{y})$
$= λ t \bar{x} + (1 - λ) t \bar{y}$
$= λ x + (1 - λ) y \in t C$
$よって、 t C : c o n v e x を示すことができた。$

この問題を図で確認してみます。
凸集合!FORMULA[80][19380201][0] 凸集合 $C_{1}, C_{2}$
!FORMULA[81][-1360322318][0] $C_{1} + C_{2}$

上の図のような凸集合 $C_{1}, C_{2}$ を考えると、 $C_{1} + C_{2}$ は緑色の集合となります。そして $C_{1} + C_{2}$ もまた凸集合となっていることが分かります。

!FORMULA[85][-242467343][0] $スカラー倍 t C$

この問題から見えることは集合の凸性については、和とスカラー倍をしても維持されるということです。

$C_{α} : 任意の凸集合族$
$\Rightarrow ⋂_{α} : c o n v e x$

$\forall x, y \in ⋂_{α} C_{α} を考えると、 \forall α に対して x, y \in C_{α} である。$
$C_{α} : c o n v e x より、 0 \leq λ \leq 1 に対して、 λ x + (1 - λ) y \in C_{α} となる。$
$\forall α に対して λ x + (1 - λ) y \in C_{α} となるので、 λ x + (1 - λ) y \in ⋂_{α} C_{α} 、$
$すなわち ⋂_{α} C_{α} : c o n v e x を示すことができた。$