半空間(half-space)とは、$\mathbb{R}^n$ の $0$ でないベクトル $a$ と実数 $\beta$ を用いて $\{x\mid a\cdot x\le\beta\}$(閉半空間)または $\{x\mid a\cdot x< \beta\}$(開半空間)と表される集合のことである。超平面 $\{a\cdot x=\beta\}$ は空間を 2 つの開半空間に分け、閉半空間の内部は開半空間、境界はこの超平面であり、半空間を定める $(a,\beta)$ は正の定数倍を除いて一意である。空でも全体でもない閉集合が閉半空間であることは、その集合と補集合がどちらも凸であることと同値である。有限個の閉半空間の共通部分が多面体であり、上半空間 $\{x_n\ge0\}$ は境界付き多様体の局所的な模型になる。
半空間(half-space)とは、超平面で $\mathbb{R}^n$ を 2 つに分けたときの片側のことである。$n=1$ では半直線 $[0,\infty)$、$n=2$ では上半分の平面 $\{(x,y)\mid y\ge0\}$ のような半平面、$n=3$ では平面の片側がそれに当たる。式で書けば、1 次不等式 $a\cdot x\le\beta$($a\ne0$)を満たす点の全体が閉半空間であり、不等号を $<$ にしたものが開半空間である。
半空間は凸幾何の最小の部品である。有限個の閉半空間の共通部分が 多面体 であり、閉凸集合はそれを含む閉半空間すべての共通部分である(凸包 の定理「点と閉凸集合の分離」)。また上半空間 $\{x_n\ge0\}$ は 境界付き多様体 の局所的な模型であり、開いた上半空間は 双曲空間 の模型の 1 つになる。この記事では、半空間の定義と基本性質(内部・閉包・境界、式の一意性、包含の判定)を示し、主定理として「空でも全体でもない閉集合が閉半空間であることは、それと補集合がどちらも凸であることと同値」を証明する。
以下、$\mathbb{R}^n$($n\ge1$)に標準内積 $a\cdot x=\sum_ia_ix_i$ とノルム $\lvert x\rvert=\sqrt{x\cdot x}$ を入れる。
$a\in\mathbb{R}^n$($a\ne0$)と $\beta\in\mathbb{R}$ について
$$
\overline H_{a,\beta}:=\{x\in\mathbb{R}^n\mid a\cdot x\le\beta\},\qquad H_{a,\beta}:=\{x\in\mathbb{R}^n\mid a\cdot x< \beta\}
$$
をそれぞれ 閉半空間、開半空間 といい、あわせて 半空間 という。超平面 $L_{a,\beta}:=\{x\mid a\cdot x=\beta\}$ を半空間の 境界の超平面、$a$ を 外向きの法線ベクトル という。
$\{x\mid a\cdot x\ge\beta\}=\overline H_{-a,-\beta}$ なので、不等号の向きを逆にした集合も半空間である。超平面 $L_{a,\beta}$ を除いた $\mathbb{R}^n\setminus L_{a,\beta}$ は 2 つの開半空間 $H_{a,\beta}$ と $H_{-a,-\beta}$ の交わらない和であり、この 2 つがちょうど連結成分である(超平面 の定理「点と超平面の距離、超平面の両側」の (R2))。閉半空間は、一方の開半空間に境界の超平面を加えたものである。この定義と、内部が開半空間で境界が超平面であることは BV04 §2.2.1(pp. 27–29)にある。
$a\ne0$ を仮定するのは、$a=0$ だと $\{0\le\beta\}$ が $\beta$ に応じて $\mathbb{R}^n$ か空集合になり、半空間と呼びたい形にならないからである。
$a\in\mathbb{R}^n$($a\ne0$)、$\beta\in\mathbb{R}$ とする。
$f(x):=a\cdot x-\beta$ とおく。$f$ は連続で、$f(tx+(1-t)y)=tf(x)+(1-t)f(y)$ を満たす。
4 は、凸な開集合がいつも $\mathbb{R}^n$ と同相であること(凸集合 の定理「凸開集合は $\mathbb{R}^n$ と同相」)の特別な場合でもある。閉半空間は $\mathbb{R}^n$ と同相でない。$n=1$ では、同相写像 $h\colon[0,\infty)\to\mathbb{R}$ があれば $(0,\infty)$ は $\mathbb{R}\setminus\{h(0)\}$ と同相になるが、前者は連結で後者は連結でないので矛盾する。一般の $n$ でも、閉半空間の境界の点のどの近傍も $\mathbb{R}^n$ の開集合と同相にならないことが、境界付き多様体 の定理「内部の点と境界の点は交わらない」から従う。
$a,a'\in\mathbb{R}^n$ はどちらも $0$ でないとする。
1 により、半空間は境界の超平面と外向きの単位法線ベクトル $a/\lvert a\rvert$ を一意に定める。2 の量 $(a\cdot x-\beta)/\lvert a\rvert$ は、$\lvert a\rvert=1$ に正規化すれば、点が境界の超平面からどれだけ外側にあるかを符号つきで表す。
$a,a'\in\mathbb{R}^n$ はどちらも $0$ でないとする。$\overline H_{a,\beta}\subset\overline H_{a',\beta'}$ であるための必要十分条件は、$\lambda>0$ で $a'=\lambda a$ かつ $\lambda\beta\le\beta'$ となるものがあることである。
十分性:$a\cdot x\le\beta$ なら $a'\cdot x=\lambda a\cdot x\le\lambda\beta\le\beta'$ である。
必要性:$a'$ が $a$ の正の定数倍でないとして、$a\cdot d\le0$ かつ $a'\cdot d>0$ となる $d$ を作る。$a'=\mu a$($\mu< 0$)なら $d:=-a$ とすればよい($\mu=0$ は $a'\ne0$ に反する)。$a'$ が $a$ の定数倍でなければ、$d:=a'-\frac{a'\cdot a}{\lvert a\rvert^2}a\ne0$ は $a\cdot d=0$、$a'\cdot d=\lvert d\rvert^2>0$ を満たす。$x_0\in\overline H_{a,\beta}$ をとると、すべての $t\ge0$ で $x_0+td\in\overline H_{a,\beta}$ だが、$a'\cdot(x_0+td)=a'\cdot x_0+t\,a'\cdot d$ は $t\to\infty$ で $\beta'$ を超えるので、包含に反する。よって $a'=\lambda a$($\lambda>0$)であり、$x_0\in L_{a,\beta}$ をとれば $\lambda\beta=a'\cdot x_0\le\beta'$ である。$\square$
これは「1 つの不等式 $a\cdot x\le\beta$ から $a'\cdot x\le\beta'$ が導かれるのは、正の数を掛けて右辺を緩めた場合に限る」という主張である。不等式が有限個ある系については、解があるかどうかを Farkasの補題 が判定する。
半空間はそれ自身もその補集合も凸である(prop-hsp-basic の 1・3)。閉集合と開集合については、この性質が半空間を特徴づける。
$C\subset\mathbb{R}^n$ を、空でも $\mathbb{R}^n$ でもない閉集合とする。次の 2 条件は同値である。
1 ⇒ 2 は prop-hsp-basic の 1・3 である。
2 ⇒ 1:$D:=\mathbb{R}^n\setminus C$ とおく。$D$ は空でない凸な開集合である。
段 1(候補の半空間)。$d\in D$ を 1 つとる。$C$ は空でない閉凸集合なので、$C$ の点のうち $d$ に最も近い点 $p$ がただ 1 つあり、すべての $x\in C$ について $(d-p)\cdot(x-p)\le0$ が成り立つ(凸錐 の補題「閉凸集合への最短点」)。$a:=d-p$ とおくと $d\notin C$ より $a\ne0$ で、$\beta:=a\cdot p$ とおけば
$$
C\subset\overline H_{a,\beta},\qquad a\cdot d=\beta+\lvert a\rvert^2>\beta
$$
である。あとは $\overline H_{a,\beta}\subset C$ を示せばよい。
段 2(境界の超平面の上の $D$ の点)。$y\in\overline H_{a,\beta}$ で $y\notin C$、すなわち $y\in D$ となる点があったとする。$a\cdot y\le\beta< a\cdot d$ なので、
$$
s:=\frac{\beta-a\cdot y}{a\cdot d-a\cdot y}\in[0,1),\qquad z:=y+s(d-y)
$$
とおくと $a\cdot z=\beta$ であり、$D$ が凸なので $z\in D$ である。
段 3($p$ に関する折り返し)。$D$ は開集合なので、$\varepsilon>0$ を小さくとれば $z':=z-\varepsilon a\in D$ である。$w:=2p-z'$ とおくと
$$
a\cdot w=2\beta-(\beta-\varepsilon\lvert a\rvert^2)=\beta+\varepsilon\lvert a\rvert^2>\beta
$$
なので $w\notin\overline H_{a,\beta}$ であり、$C\subset\overline H_{a,\beta}$ から $w\notin C$、すなわち $w\in D$ である。すると $D$ の凸性から中点 $\frac12(z'+w)=p$ も $D$ に属するが、$p\in C$ なので矛盾する。よって $\overline H_{a,\beta}\subset C$ であり、$C=\overline H_{a,\beta}$ である。
開集合の場合:$U$ と補集合が凸なら、$\mathbb{R}^n\setminus U$ は空でも全体でもない閉集合で、それと補集合 $U$ がどちらも凸なので、前半により閉半空間 $\overline H_{a,\beta}$ である。よって prop-hsp-basic の 3 により $U=H_{-a,-\beta}$ は開半空間である。逆向きは prop-hsp-basic の 1・3 による。$\square$
証明の段 3 は、境界の超平面の上で $p$ の両側に $D$ の点があれば、$D$ の凸性から $p$ 自身が $D$ に入ってしまう、という観察である。段 1 で使った最短点は、点と閉凸集合を分離する超平面を作る標準的な方法でもある(凸包 の定理「点と閉凸集合の分離」の証明)。
位相の仮定(閉または開)は外せない。下の ex-hsp-hemispace のように、境界の超平面の一部だけを含む凸集合は、補集合も凸だが半空間ではない。
$\mathbb{R}^2$ で
$$
S:=\{(x,y)\mid y>0\}\cup\{(x,0)\mid x\ge0\}
$$
とおく。$S$ も補集合 $\{(x,y)\mid y< 0\}\cup\{(x,0)\mid x< 0\}$ も凸だが、$S$ は閉集合でも開集合でもないので、閉半空間でも開半空間でもない(prop-hsp-basic の 1)。
$S$ の 2 点 $P,Q$ を結ぶ線分を考える。どちらかの $y$ 座標が正なら、両端を除く線分の点の $y$ 座標は正なので $S$ に属し、両端も $S$ に属する。どちらの $y$ 座標も $0$ なら、2 点は $x\ge0$ の半直線の上にあり、線分もその上にある。補集合も、$y$ 座標の正負と $x$ の正負を逆にして同じ議論ができる。$S$ は $(-1,1/k)\to(-1,0)\notin S$ となる点列を含むので閉でなく、$(0,0)\in S$ のどの近傍も $y< 0$ の点を含むので開でもない。
共通部分。有限個の閉半空間の共通部分は 多面体 であり、空でなく有界なものは 凸多面体 である。無限個の閉半空間を使えば、空でない閉凸集合はすべて表せる。$C$ を含む閉半空間すべての共通部分は $C$ の閉凸包に等しいからである(凸包 の定理「点と閉凸集合の分離」の 2)。たとえば閉単位円板は、$\theta\in[0,2\pi)$ についての閉半空間 $\{x\cos\theta+y\sin\theta\le1\}$ すべての共通部分であるが、有限個の閉半空間の共通部分としては表せない。有界な多面体は有限個の点の凸包だが(多面体 の定理「Minkowski–Weylの定理(凸多面体の場合)」)、閉円板はそうでないからである(多面体 の反例の表の 2 行目)。
上半空間と境界付き多様体。ex-hsp-low の上半空間 $\mathbb{H}^n$ は 境界付き多様体 の局所座標の値域として使われ、境界の超平面 $\{x_n=0\}$ に写る点が境界の点である。
双曲空間。開いた上半空間 $\{(\xi,y)\mid\xi\in\mathbb{R}^{n-1},\ y>0\}$ に計量 $(\lvert d\xi\rvert^2+dy^2)/y^2$ を入れたものは 双曲空間 の上半空間モデルであり(同記事の定理「上半空間モデルと球体モデル」で $a=1$ とした場合)、$n=2$ の場合が 上半平面 の記事の双曲平面のモデルである。ここで半空間は、計量を入れる土台の集合として使われている。
Siegel上半空間 $\mathfrak{H}_g$ は、複素対称行列 $Z=X+iY$($X,Y$ は実対称行列)で $Y$ が 正定値行列 であるもの全体である。$(X,Y)$ を座標として、これを $\mathbb{R}^{g(g+1)}$ の部分集合とみる。$g=1$ では $\mathfrak{H}_1=\{x+iy\mid y>0\}$ で開半空間である。$g\ge2$ では半空間でない。実際、$Y_1:=\operatorname{diag}(3,-1,1,\dots,1)$、$Y_2:=\operatorname{diag}(-1,3,1,\dots,1)$ はどちらも正定値でないので、$iY_1$、$iY_2$ は $\mathfrak{H}_g$ の補集合に属するが、その中点 $iI_g$ は $\mathfrak{H}_g$ に属する。よって補集合は凸でなく、prop-hsp-basic の 3 により $\mathfrak{H}_g$ は半空間でない。$\mathfrak{H}_g$ は凸な開集合ではある(正定値行列の正の係数の和は正定値)。
無限次元の空間。実ベクトル空間 $X$ の $0$ でない 線形汎関数 $\varphi$ と $\beta\in\mathbb{R}$ についても、$\{\varphi\le\beta\}$、$\{\varphi< \beta\}$ を半空間という。$X=\mathbb{R}^n$ なら $\varphi(x)=a\cdot x$ と書けるので(超平面 の系「超平面の方程式」)、上の定義と一致する。$X$ が無限次元のノルム空間のときは、位相が $\varphi$ の連続性に左右される。
$X$ を実ノルム空間、$\varphi$ を $X$ の $0$ でない線形汎関数、$\beta\in\mathbb{R}$ とする。$\varphi$ が連続なら $\{\varphi\le\beta\}$ は閉集合、$\{\varphi< \beta\}$ は開集合である。$\varphi$ が連続でなければ、$\{\varphi< \beta\}$ と $\{\varphi>\beta\}$ はどちらも $X$ で稠密であり、$\{\varphi\le\beta\}$ は閉集合でも開集合でもない。
前半は連続写像による閉集合・開集合の逆像である。$\varphi$ が連続でないとする。超平面 の命題「線形超平面は閉か稠密か」により $\ker\varphi$ は稠密である。$\varphi(x_0)=\beta-1$ となる $x_0$ をとると $x_0+\ker\varphi\subset\{\varphi< \beta\}$ であり、平行移動は同相写像なので $x_0+\ker\varphi$ は稠密である。よって $\{\varphi< \beta\}$ は稠密で、同様に $\{\varphi>\beta\}$ も稠密である。$\{\varphi\le\beta\}$ は稠密で $X$ と異なるので閉でなく、補集合 $\{\varphi>\beta\}$ が稠密で $X$ と異なるので開でもない。$\square$
不連続な線形汎関数の例(多項式の空間の $p\mapsto p'(0)$)は 超平面 の例「反例:稠密な線形超平面」にある。
thm-hsp-main の仮定を 1 つずつ外すと、結論「$C$ は閉半空間である」が成り立たなくなる。
| 外す条件 | 例($\mathbb{R}^2$) | 成り立たなくなること |
|---|---|---|
| $C$ が閉 | ex-hsp-hemispace の $S$ | $C$ は閉半空間 |
| $\mathbb{R}^n\setminus C$ が凸 | 閉単位円板 | $C$ は閉半空間 |
| $C$ が凸 | 開単位円板の補集合 $\{x^2+y^2\ge1\}$ | $C$ は閉半空間 |
| $C\ne\mathbb{R}^n$ | $C=\mathbb{R}^2$ | $C$ は閉半空間 |
| $C\ne\emptyset$ | $C=\emptyset$ | $C$ は閉半空間 |
どの行も、外した 1 つの条件以外の仮定を満たす。
1 行目:$S$ は空でも全体でもなく、$S$ と補集合はどちらも凸である(ex-hsp-hemispace)。閉集合でない $S$ は、閉半空間(閉集合)ではない。
2 行目:閉単位円板は空でも全体でもない閉凸集合である。補集合は $(\pm2,0)$ を含み中点 $(0,0)$ を含まないので凸でない。閉半空間の補集合は凸なので(prop-hsp-basic の 3)、閉単位円板は閉半空間でない。
3 行目:$C=\{x^2+y^2\ge1\}$ は空でも全体でもない閉集合で、補集合の開単位円板は凸である。$C$ は $(\pm1,0)$ を含み中点 $(0,0)$ を含まないので凸でなく、閉半空間(凸)ではない。
4 行目:$\mathbb{R}^2$ は閉凸集合で、補集合 $\emptyset$ も凸である。閉半空間は $\mathbb{R}^2$ と異なる(prop-hsp-basic の 1)。
5 行目:$\emptyset$ は閉凸集合で、補集合 $\mathbb{R}^2$ も凸である。閉半空間は空でない(prop-hsp-basic の 1)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する