端点(凸集合)

同義語:極点(凸集合)extreme point

概要

端点(凸集合)(extreme point)とは、凸集合 $K$ の点 $a$ で、$K$ の異なる 2 点を結ぶ線分の内部の点にならないもの、すなわち $a=(1-t)x+ty$($x,y\in K$、$0< t< 1$)なら $x=y=a$ となるものである。中点の形や有限個の正の係数の凸結合の形で言いかえられ、1 点からなる面にあたり、線形汎関数の最大値の集合(露出面)の端点はもとの集合の端点になるが、端点は露出点とは限らない。ノルム空間の単位球では、端点は単位球面にあり、すべての球面の点が端点であることは狭義凸性と同値で、$1< p<\infty$ の $\ell^p$ がその例である。一方 $c_0$ や $L^1(\mathbb{R})$ の単位球には端点がなく、Krein–Milman の定理と合わせると、これらが双対空間と等長同型でないことが分かる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 凸集合, 凸包, ノルム空間

三角形の 3 つの頂点は、三角形のどの線分の内部にも現れない「角」の点である。辺の途中の点や内部の点は、三角形の 2 点を結ぶ線分の内部にある。円板では、円周上のすべての点がこの意味の角の点になる。凸集合のこのような点を 端点 という。
端点は凸集合を復元する材料になる。$\mathbb{R}^n$ のコンパクト凸集合は端点の凸包に等しく(凸包 の定理「Minkowskiの定理」)、局所凸空間のコンパクト凸集合は端点の閉凸包に等しい(Krein–Milmanの定理)。線形な関数の最大値は端点でとられるので、線形計画法では頂点だけを調べればよい。無限次元では、単位球の端点の有無が空間の幾何を映す。$\ell^1$ の単位球には端点がある一方、$c_0$ や $L^1(\mathbb{R})$ の単位球には端点がない。
この記事では、端点の定義と言いかえを述べ、端点を一般化した面の性質、露出点と端点の違いを証明する。続いて $\ell^\infty$・収束列の空間 $c$・$\ell^p$($1< p< \infty$)・$L^1(\mathbb{R})$ の単位球の端点を決定し、コンパクト凸集合の端集合についての補足を述べる。Krein–Milman の定理そのものとその証明は Krein–Milmanの定理 で扱う。

定義と言いかえ

以下、$V$ を実数体または複素数体上のベクトル空間とする。凸結合はどちらの場合も実数の係数でとる。

端点

$K\subset V$ を凸集合とする。$a\in K$ が $K$ の 端点(extreme point)であるとは、
$$ a=(1-t)x+ty,\quad x,y\in K,\quad 0< t< 1\ \Longrightarrow\ x=y=a $$
が成り立つことをいう。$K$ の端点の全体を $\operatorname{ext}K$ と書く。

すなわち、$a$ は $K$ の異なる 2 点を結ぶ線分の内部の点にならない。端点を「極点」と呼ぶ文献もある。凸多面体の端点は頂点と呼ばれる(凸包 の定義「端点」)。

端点の言いかえ

$K\subset V$ を凸集合、$a\in K$ とする。次の 4 条件は同値である。

  1. $a$ は $K$ の端点である。
  2. $K\setminus\{a\}$ は凸である。
  3. $a=\frac12(x+y)$、$x,y\in K$ なら $x=y$ である。
  4. $a=\sum_{i=1}^n\alpha_ix_i$($n\ge1$、$x_i\in K$、$\alpha_i>0$、$\sum_i\alpha_i=1$)なら、すべての $i$ で $x_i=a$ である。

1 ⇔ 2 は Krein–Milmanの定理 の節「端点と端集合」で、定義のすぐ後に示されている。
1 ⇒ 3 は $t=\frac12$ の場合である($x=y=a$ となる)。
3 ⇒ 1:$a=(1-t)x+ty$($x,y\in K$、$0< t< 1$)とし、$x\neq y$ と仮定して矛盾を導く($x=y$ なら $a=x=y$ で結論が成り立つ)。$x,y$ と $t,1-t$ を入れかえてよいので $t\le\frac12$ とする。$y':=(1-2t)x+2ty$ は $x,y$ の凸結合なので $K$ に属し、
$$ \tfrac12(x+y')=\tfrac12\bigl((2-2t)x+2ty\bigr)=(1-t)x+ty=a $$
である。$y'-x=2t(y-x)\neq0$ なので $x\neq y'$ となり、3 に反する。
1 ⇒ 4:$n$ についての帰納法で示す。$n=1$ なら $x_1=a$ である。$n\ge2$ とすると $0< \alpha_1< 1$ であり、$z:=\sum_{i\ge2}\frac{\alpha_i}{1-\alpha_1}x_i$ は $K$ の点の凸結合なので $K$ に属し、$a=\alpha_1x_1+(1-\alpha_1)z$ である。$a$ は端点なので $x_1=z=a$ であり、$a=z$ は $n-1$ 個の点の正の係数の凸結合なので、帰納法の仮定により $x_i=a$($i\ge2$)である。
4 ⇒ 1 は $n=2$ の場合である。$\square$

4 は Bre11 Problem 1 の 2(p. 435)に問題として挙げられている。3 は、端点でないことを示すには、$a$ を中点とする $K$ の異なる 2 点を見つければよいことを意味する。以下の例の計算はこの形で行う。

基本的な例
  1. $\mathbb{R}^2$ の閉円板の端点は円周上の点全体、開円板・閉半平面には端点がない(凸包 の定理「Minkowskiの定理」の後の反例の表)。
  2. 確率ベクトルの集合 $\{t\in\mathbb{R}^n\mid t_i\ge0,\ \sum_it_i=1\}$ の端点は標準基底 $e_1,\dots,e_n$ である(Krein–Milmanの定理 の例「有限次元の例」)。
  3. 有限個の 1 次不等式で定まる $\mathbb{R}^n$ の多面体 $P=\{x\mid Ax\le b\}$ では、$v\in P$ が端点であることと、$v$ で等号になる不等式の係数ベクトルが $\mathbb{R}^n$ を張ることが同値であり、端点は有限個である(多面体 の定理「頂点の特徴づけ」と系「頂点は有限個」)。

面と露出点

端点は 1 点からなる「面」である。面は、線分の内部の点を含めば線分全体を含む部分集合である。

面

$K\subset V$ を凸集合とする。凸部分集合 $F\subset K$ が $K$ の 面(face)であるとは、
$$ x,y\in K,\quad 0< t< 1,\quad (1-t)x+ty\in F\ \Longrightarrow\ x,y\in F $$
が成り立つことをいう。

定義から、$a\in K$ が端点であることと $\{a\}$ が面であることは同値である。正方形では、空集合・4 頂点・4 辺・正方形全体が面である。

面の基本性質

$K\subset V$ を凸集合とする。

  1. $K$ の面の族の共通部分は $K$ の面である。
  2. $F$ が $K$ の面で、$G$ が $F$ の面なら、$G$ は $K$ の面である。
  3. $F$ が $K$ の面なら、$\operatorname{ext}F=F\cap\operatorname{ext}K$ である。
  4. $u\colon V\to\mathbb{R}$ を実線形汎関数とし、$u$ が $K$ 上で最大値 $M$ をとるとする。このとき $K_u:=\{x\in K\mid u(x)=M\}$ は $K$ の面である。

1:凸集合の共通部分は凸で、面の条件は各成員で成り立つ。
2:$G$ は凸である。$x,y\in K$、$0< t< 1$、$(1-t)x+ty\in G$ とする。$G\subset F$ で $F$ は $K$ の面なので $x,y\in F$ であり、$G$ は $F$ の面なので $x,y\in G$ である。
3:$a\in F$ が $K$ の端点なら、$F\subset K$ なので $F$ の端点でもある。逆に $a\in\operatorname{ext}F$ とし、$a=(1-t)x+ty$($x,y\in K$、$0< t< 1$)とする。$F$ は面なので $x,y\in F$ であり、$a$ は $F$ の端点なので $x=y=a$ である。よって $a\in\operatorname{ext}K$ である。
4:$K_u$ は凸である。$x,y\in K$、$0< t< 1$、$(1-t)x+ty\in K_u$ なら $M=(1-t)u(x)+tu(y)$ で $u(x),u(y)\le M$ なので、$u(x)=u(y)=M$、すなわち $x,y\in K_u$ である。$\square$

4 の形の面を 露出面 という。$V=E$ がノルム空間で $u=\langle f,\cdot\rangle$($f\in E^*$)のとき、$M$ は 支持関数 の値 $h_K(f)$ であり、$K_u$ は支持超平面 $\{\langle f,\cdot\rangle=h_K(f)\}$ と $K$ の共通部分である。凸包 の定理「Minkowskiの定理」と 線形計画法 の定理「最適解は頂点でとれる」の証明は、3 と 4 を組み合わせて端点を見つけている。

露出点

$E$ をノルム空間、$K\subset E$ を凸集合とする。$a\in K$ が $K$ の 露出点(exposed point)であるとは、$f\in E^*$ で、すべての $x\in K\setminus\{a\}$ について $\langle f,x\rangle< \langle f,a\rangle$ となるもの(実数の場合。複素数の場合は実部で考える)が存在することをいう。

露出点 $a$ では $\{a\}$ が露出面なので、prop-ep-face の 4 により露出点は端点である。逆は成り立たない。

端点だが露出点でない点

$\mathbb{R}^2$ で、線分 $S=[-1,1]\times\{0\}$ と閉単位円板 $D$ の和 $K:=S+D=\{s+w\mid s\in S,\ w\in D\}$(陸上競技場のトラックの形)を考え、$p=(1,1)$ とする。$K$ は凸集合の和なので凸である。

  • $p$ は端点:$K$ の点の第 2 座標は $1$ 以下で、第 2 座標が $1$ の点 $s+w$ では $w=(0,1)$ なので、そのような点は $[-1,1]\times\{1\}$ の点である。$p=\frac12(x+y)$($x,y\in K$)なら $x,y$ の第 2 座標はどちらも $1$ で、第 1 座標は $1$ 以下で平均が $1$ だから $x=y=p$ である。prop-ep-equiv の 3 により $p$ は端点である。
  • $p$ は露出点でない:支持関数 の命題「支持関数の基本性質」の 4 と例「凸多面体と楕円体」・例「球の支持関数」により、$f=(f_1,f_2)\neq0$ について $h_K(f)=h_S(f)+h_D(f)=|f_1|+\sqrt{f_1^2+f_2^2}$ である。$f\cdot p=f_1+f_2$ が $h_K(f)$ に等しくなるには $f_1=|f_1|$ かつ $f_2=\sqrt{f_1^2+f_2^2}$、すなわち $f_1=0$、$f_2>0$ が必要である。このとき $f\cdot x$ は $[-1,1]\times\{1\}$ 上で一定の最大値をとるので、最大値をとる点は $p$ だけではない。

単位球の端点

ノルム空間 $E\neq\{0\}$ の閉単位球を $B_E$、単位球面を $S_E:=\{\|x\|=1\}$ と書く。$\|x\|=\|y\|=1$、$x\neq y$ から $\|\frac12(x+y)\|< 1$ が従うとき、$E$ は 狭義凸 であるという(一様凸Banach空間 の定義「狭義凸」。狭義凸ノルム も参照)。

単位球の端点と狭義凸性

$E\neq\{0\}$ をノルム空間とする。$\operatorname{ext}B_E\subset S_E$ であり、$\operatorname{ext}B_E=S_E$ であることと $E$ が狭義凸であることは同値である。

$\|a\|< 1$ とする。$a=0$ なら、$\|u\|=1$ となる $u$ について $a=\frac12(u+(-u))$ である。$a\neq0$ なら、$\varepsilon>0$ を $(1+\varepsilon)\|a\|\le1$ にとると $a=\frac12((1+\varepsilon)a+(1-\varepsilon)a)$ である。どちらも $B_E$ の異なる 2 点の中点なので、$a$ は端点でない。
$E$ が狭義凸とし、$a\in S_E$、$a=\frac12(x+y)$($x,y\in B_E$)とする。$1=\|a\|\le\frac12(\|x\|+\|y\|)$ から $\|x\|=\|y\|=1$ であり、$x\neq y$ なら狭義凸性から $\|a\|< 1$ となって矛盾するので $x=y$ である。よって $a$ は端点である。逆に $\operatorname{ext}B_E=S_E$ とし、$\|x\|=\|y\|=1$、$x\neq y$ とする。$a=\frac12(x+y)$ は $B_E$ の異なる 2 点の中点なので端点でなく、$\|a\|\neq1$、すなわち $\|a\|< 1$ である。$\square$

Krein–Milmanの定理 の例「$\ell^1$ の閉単位球の端点」は、実数値の $\ell^1$ では $\operatorname{ext}B=\{\pm e_n\}$ であること、例「$c_0$ の閉単位球は端点をもたない」は $c_0$ の単位球に端点がないことを示している。残りの古典的な空間を決定する。

古典的な空間の単位球の端点

実数値の数列空間・関数空間について、閉単位球 $B$ の端点は次のとおりである。

  1. $\ell^\infty$(有界数列、上限ノルム)では $\operatorname{ext}B=\{x\mid|x_n|=1\ (n\ge1)\}$ である。
  2. 収束する数列の空間 $c$(上限ノルム)では、$\operatorname{ext}B$ は、各項が $\pm1$ で、ある番号から先は一定である数列の全体である。
  3. $1< p< \infty$ なら、$\ell^p$ では $\operatorname{ext}B=S_{\ell^p}$ である。
  4. $L^1(\mathbb{R})$(Lebesgue 測度)では $\operatorname{ext}B=\emptyset$ である。

1・2:$X=\ell^\infty$ または $c$ とする。$x\in B$ で $|x_N|< 1$ となる $N$ があれば、$\varepsilon:=1-|x_N|$ について $x\pm\varepsilon e_N$ は $X$ の点で($e_N\in c$ である)、ノルムは $1$ 以下であり、$x$ はその中点なので端点でない。逆に $|x_n|=1$ がすべての $n$ で成り立ち、$x=\frac12(y+z)$($y,z\in B$)とすると、各 $n$ で $|y_n|,|z_n|\le1$ と $|\frac12(y_n+z_n)|=1$ から $y_n=z_n=x_n$ であり、$y=z$ である。prop-ep-equiv の 3 により $x$ は端点である。$X=c$ のとき、各項が $\pm1$ の数列が収束するなら、Cauchy 列なので $|x_n-x_m|< 2$ がある番号から先で成り立ち、$|x_n-x_m|\in\{0,2\}$ から $x_n=x_m$ となる。逆に、ある番号から先が一定なら収束する。
3:lem-ep-ball により、$\ell^p$ が狭義凸であることを示せばよい。まず $\varphi(u)=u^p$ は $[0,\infty)$ で狭義凸である。実際 $0\le a< b$、$m=\frac12(a+b)$ とすると、平均値の定理により $\varphi(m)-\varphi(a)=\varphi'(\xi)(m-a)$、$\varphi(b)-\varphi(m)=\varphi'(\eta)(b-m)$($a< \xi< m< \eta< b$)であり、$\varphi'(u)=pu^{p-1}$ は狭義単調増加なので $\varphi(m)-\varphi(a)< \varphi(b)-\varphi(m)$、すなわち $\varphi(m)< \frac12(\varphi(a)+\varphi(b))$ である。よって実数 $s,t$ について
$$ \Bigl|\frac{s+t}2\Bigr|^p\le\Bigl(\frac{|s|+|t|}2\Bigr)^p\le\frac{|s|^p+|t|^p}2 $$
であり、等号が成り立つのは、1 つ目では $s,t$ が同符号(または一方が $0$)、2 つ目では $|s|=|t|$ のとき、合わせて $s=t$ のときに限る。$\|x\|_p=\|y\|_p=1$、$x\neq y$ とし、$x_N\neq y_N$ とすると、各項の不等式を足して、$N$ の項で真の不等号が成り立つので
$$ \Bigl\|\frac{x+y}2\Bigr\|_p^p=\sum_n\Bigl|\frac{x_n+y_n}2\Bigr|^p< \sum_n\frac{|x_n|^p+|y_n|^p}2=1 $$
である。
4:lem-ep-ball により、$\|f\|_1=1$ の $f$ が端点でないことを示せばよい。$F(s):=\int_{(-\infty,s)}|f|\,dx$ とおく。優収束定理 により、$F$ は連続で、$s\to-\infty$ で $0$、$s\to+\infty$ で $1$ に収束する(被積分関数 $|f|\mathbf 1_{(-\infty,s)}$ は $|f|$ で押さえられる)。中間値の定理により $F(s_0)=\frac12$ となる $s_0$ がある。$g:=2f\mathbf 1_{(-\infty,s_0)}$、$h:=2f\mathbf 1_{[s_0,\infty)}$ とおくと、$\|g\|_1=2F(s_0)=1$、$\|h\|_1=2(1-F(s_0))=1$、$f=\frac12(g+h)$ であり、$|g-h|=2|f|$ なので $\|g-h\|_1=2$、とくに $g\neq h$ である。よって $f$ は端点でない。$\square$

1〜4 と $\ell^1$・$c_0$ の場合は、Bre11 Problem 1 の 9(p. 436)に問題として挙げられている。$\ell^1$ は計数測度に関する $L^1$ であり、$e_n$ は 1 点という「それ以上分けられない」集合に台をもつ。$L^1(\mathbb{R})$ では、どの関数もその質量を 2 等分できるので端点がない。この差から、Krein–Milmanの定理 の命題「$c_0$ は双対空間と等長同型でない」と同じ論法で次が分かる。

$L^1(\mathbb{R})$ は双対空間と等長同型でない

どのノルム空間 $Y$ についても、$L^1(\mathbb{R})$ から $Y^*$ への全射な線形等長写像は存在しない。

そのような写像 $T$ があれば、$T$ は閉単位球を閉単位球の上へ写し、凸結合を保つ全単射なので端点を端点へ一対一に写す。$Y^*\neq\{0\}$ の閉単位球は、弱スター位相を入れた $Y^*$(Hausdorff な局所凸空間)のコンパクトな凸集合なので(Banach–Alaogluの定理、Krein–Milmanの定理 の節「双対空間の閉単位球と $c_0$」)、Krein–Milmanの定理 の定理「Krein–Milmanの定理」により端点をもつ。これは thm-ep-balls の 4 に反する。$\square$

一方 $\ell^\infty=(\ell^1)^*$ の単位球には、各項が $\pm1$ の数列という端点が非可算個あり、Krein–Milman の定理と合っている。

端集合

コンパクト凸集合では、面の代わりに 端集合 がよく使われる。Krein–Milmanの定理 の定義「端集合」のとおり、Hausdorff 位相ベクトル空間のコンパクト凸集合 $K$ について、$S\subset K$ が端集合であるとは、$S$ が空でない閉集合で、$x,y\in K$、$0< t< 1$、$(1-t)x+ty\in S$ なら $x,y\in S$ となることをいう。この定義は $S$ が凸であることを要求しない(Bre11 Problem 1、p. 435 の定義と同じ)。

端集合の作り方

$K$ を Hausdorff 位相ベクトル空間のコンパクト凸集合とする。

  1. 空でない閉な面は端集合である。
  2. 端集合の族の共通部分は、空でなければ端集合である。有限個の端集合の和集合は端集合である。
  3. $a\in K$ について、$\{a\}$ が端集合であることと $a$ が端点であることは同値である。

1 は定義を比べればよい。2:閉集合の共通部分・有限和は閉である。$(1-t)x+ty$ が共通部分に属すれば各端集合に属するので $x,y$ も各端集合に属する。和集合 $S_1\cup\cdots\cup S_m$ に属すればある $S_j$ に属するので $x,y\in S_j$ である。3 は Krein–Milmanの定理 の補題「端集合の基本性質」の 1 である。$\square$

凸でない端集合

正方形 $K=[-1,1]^2$ の対角の 2 頂点 $a=(1,1)$、$c=(-1,-1)$ について、$\{a\}$、$\{c\}$ は端集合なので、prop-ep-extreme-set の 2 により $\{a,c\}$ も端集合である。これは凸でなく、面でもない。その凸包の対角線も面でない。実際、中心 $0$ は対角線上にあるが、対角線上にない 2 頂点 $(1,-1)$、$(-1,1)$ の中点である。

空間が局所凸なら、どの端集合も $K$ の端点を含む。これが Krein–Milman の定理の証明の第 1 段である(Krein–Milmanの定理 の定理「Krein–Milmanの定理」の 1)。凸でない端集合を許すと、端点 1 点からなる集合や、prop-ep-face の 4 の形の集合をそのまま扱える。

反例の表

thm-ep-balls の 3・4 と prop-ep-face の 3 の仮定を 1 つずつ外す。各行は 1 つの条件だけを破る。

外す条件反例成り立たなくなること
$p>1$(3)$\ell^1$単位球面の点 $\frac12(e_1+e_2)$ は $e_1,e_2$ の中点で端点でない
$p< \infty$(3)$\ell^\infty$単位球面の点 $e_1$ は $e_1\pm e_2$ の中点で端点でない
測度が原子をもたないこと(4)$\ell^1$($\mathbb{N}$ 上の計数測度の $L^1$)$\pm e_n$ が端点で、$\operatorname{ext}B\neq\emptyset$
$F$ が面であること(prop-ep-face の 3)$K=[-1,1]^2$、$F=\{0\}\times[-1,1]$$(0,1)$ は $F$ の端点だが、$(\pm1,1)$ の中点で $K$ の端点でない

3 行目の $\ell^1$ の端点は Krein–Milmanの定理 の例「$\ell^1$ の閉単位球の端点」で確かめられている。4 行目の $F$ は凸だが、$K$ の面でない($(0,1)\in F$ だが $(\pm1,1)\notin F$)。

関連項目

参考文献

[1]
Haim Brezis, Functional Analysis, Sobolev Spaces and Partial Differential Equations, Springer, 2011, Problem 1(pp. 435–436、端点・端集合の定義、端点の言いかえ(問 1・2)、古典的な空間の単位球の端点(問 9))

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する