2
大学数学基礎解説
文献あり

凸集合と基本性質

655
0
$$\newcommand{convex}[2]{\lambda {#1} + (1- \lambda ){#2}} \newcommand{lambdarange}[0]{0 \leq \lambda \leq 1} \newcommand{lambdax}[1]{\lambda #1} \newcommand{lambday}[1]{(1 - \lambda ) #1} $$

凸集合の定義と基本性質

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

はじめに

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

凸集合

convex,cone

集合$C$$convex$(凸集合)である
$\Leftrightarrow \forall x,y \in C, \lambdarange に対して \convex{x}{y} \in C をみたす。$

集合$C$$cone$(錐)である
$\Leftrightarrow x \in C,\lambda \geq 0 に対して \lambda x \in C をみたす。$

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

平面で図示した例

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

convex set(凸集合) convex set(凸集合)

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


non-convex set(凸でない集合) non-convex set(凸でない集合)

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


cone(錐) cone(錐)

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


convex cone(凸錐) convex cone(凸錐)

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

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

$$C:cone(錐)について、次が成り立つ。$$
$$C:convex(凸) \Leftrightarrow \forall x,y \in C, x+y \in C。$$

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

$$(\Leftarrow)について。$$
$$\convex{x}{y} を示したいので、まず \lambdax{x}, \lambday{y} \in C を示す。$$

$$(\Rightarrow)を示す。$$
$$C:convexより、\forall x,y \in C, \lambdarange に対して、\convex{x}{y} \in Cである。$$
$$\lambda = \frac{1}{2}とすると\frac{1}{2} x + \frac{1}{2} y \in Cとなる。$$
$$C:coneより、2(\frac{1}{2} x + \frac{1}{2} y) \in Cである。$$
$$すなわち、x + y \in C となり(\Rightarrow)が示せた。$$

$$(\Leftarrow)を示す。$$
$$C:coneより、\forall x,y \in C, \lambdarange に対して、$$
$$\lambdax{x}, \lambday{y} \in Cである。$$
$$すると条件より、\convex{x}{y} \in Cとなる。$$
$$よって、C:convexを示せた。$$

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

cone, non convex(凸でない錐) cone, non convex(凸でない錐)

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

convex cone(凸錐) convex cone(凸錐)

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

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

  1. $$C_1,C_2:convex$$
    $$\Rightarrow C_1 + C_2 :convex$$
  2. $$C:convex$$
    $$\Rightarrow tC :convex \ (t \in \mathbb{R})$$

<証明の考え方>
どちらについても、convex(凸)の定義をみたすことを確認すればOKなので、集合から任意の2点$x,y$を選び、$\convex{x}{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:convex より、 \lambdarange に対して$$
$$\convex{x_1}{y_1} \in C_1,\convex{x_2}{y_2} \in C_2 である。$$
$$このことより、\convex{x_1}{y_1} + \convex{x_2}{y_2} \in C_1 + C_2 となる。$$
$$ここで要素の式を変形していくと、$$
$$\convex{x_1}{y_1} + \convex{x_2}{y_2}$$
$$=\convex{(x_1 + x_2)}{(y_1 + y_2)}$$
$$=\convex{x}{y} \in C_1 + C_2$$
$$よって、C_1 + C_2 :convexを示すことができた。$$

(ii) を示す。
$$\forall x,y \in tC を考える。$$
$$すると、\exists \bar{x}, \bar{y} \in C \ s.t. \ x = t \bar{x} ,y = t \bar{y} \ である。$$
$$C:convexより、\lambdarange に対して、 \convex{\bar{x}}{\bar{y}} \in C である。$$
$$このことより、t (\convex{\bar{x}}{\bar{y}}) \in tC となる。$$
$$ここで要素の式を変形していくと、$$
$$t (\convex{\bar{x}}{\bar{y}})$$
$$= \convex{t \bar{x}}{t \bar{y}}$$
$$= \convex{x}{y} \in tC$$
$$よって、tC:convexを示すことができた。$$

この問題を図で確認してみます。
凸集合!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] $スカラー倍tC$

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

$$C_\alpha:任意の凸集合族$$
$$\Rightarrow \bigcap_{\alpha} :convex$$

$$\forall x,y \in \bigcap_{\alpha} C_\alphaを考えると、\forall \alpha に対して x,y \in C_\alpha である。$$
$$C_\alpha :convex より、\lambdarange に対して、\convex{x}{y} \in C_\alphaとなる。$$
$$\forall \alpha に対して\convex{x}{y} \in C_\alpha となるので、 \convex{x}{y} \in \bigcap_{\alpha} C_\alpha 、$$
$$すなわち\bigcap_{\alpha} C_\alpha :convexを示すことができた。$$

おわりに

ご覧いただきありがとうございます。本記事では凸集合の定義の説明といくつかの演習問題を解きました。また少しでも分かりやすくなればと思い、図を載せました。間違いなどございましたらご指摘いただけますとありがたいです。

書籍「Convexity and Well-Posed Problems」の内容をベースに記事にしております。

参考文献

[1]
Roberto Lucchetti, Convexity and Well-Posed Problems, CMSBM, Springer
投稿日:2023619

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

くっく
くっく
9
34059
趣味数学家。 大学院時代には凸解析学を専攻。 多くの人が数学を好きになるためのサポート。 アイコンはdesmosを使用した関数アート。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中