交わらない凸集合は超平面で分けられる、ハーン・バナッハの分離定理

交わらない $2$ つの凸集合のあいだには、超平面を $1$ 枚さし込めます。片方が開いていれば、無限次元でも同じことが言える^[1]。

汎関数を延ばす定理と、集合を分ける定理。この $2$ つが同じハーン・バナッハの定理の表と裏になります。

凸であることは外せません。少しでもへこんでいると、分ける平面が消えます。

超平面と汎関数

$f$ を $0$ でない連続線形汎関数、$\alpha$ を実数とします。次の集合を超平面と呼びます。

$$H=\{x\in X:f(x)=\alpha \}$$

超平面は空間を $2$ つの半空間に切ります。$f(x)\le \alpha$ の側と $f(x)\ge \alpha$ の側です。

集合 $A$ と $B$ を分けるとは、$A$ が片方の半空間に、$B$ がもう片方に入ることをいいます。$1$ 本の汎関数と $1$ つの数で言い表せる。

開いているほうを使う版

いちばん軽い仮定の形はこうです。$A$ を空でない開凸集合、$B$ を空でない凸集合とし、交わらないとします^[2]。

このとき $0$ でない連続線形汎関数 $f$ と実数 $\alpha$ があって、次が成り立ちます。

$$f(a)<\alpha \le f(b)(a\in A,b\in B)$$

開いている側では不等号が厳しくなる。境界を含まないので、平面に乗る点がありません。

$B$ には閉じている条件もコンパクト性も要りません。片方が開いていれば十分です^[3]。

すきまを作る版

もっと強い結論には、コンパクト性が要ります。$K$ を空でないコンパクト凸集合、$M$ を空でない閉凸集合とし、交わらないとします^[2]。

$$\underset{x\in K}{\sup }f(x)<\underset{y\in M}{\inf }f(y)$$

$2$ つの値のあいだにすきまが空きます。超平面を $2$ 枚とって、そのあいだに何も入らない帯を作れる。

理由は距離にあります。コンパクトと閉が交わらなければ、$2$ つの集合の距離は正になる。この余裕が不等号のすきまへ変わります。

例：点を閉凸集合から切り離す

$M$ を閉凸集合、$x\notin M$ とします。$1$ 点は当然コンパクトなので、強い版がそのまま使えます^[2]。

$$f(x)<\underset{y\in M}{\inf }f(y)$$

ヒルベルト空間なら、この $f$ を手で書けます。$M$ への最近点を $p$ とし、$u=x-p$ とおきましょう。

最近点の性質から、すべての $y\in M$ で $⟨y-p,u⟩\le 0$ が成り立ちます。展開すると次の形になる。

$$⟨y,u⟩\le ⟨p,u⟩=⟨x,u⟩-\Vert u{\Vert }^2$$

$u\ne 0$ なので $\Vert u{\Vert }^2>0$ です。$f=⟨\cdot ,u⟩$ とすれば、$M$ の上での上限が $f(x)$ より $\Vert u{\Vert }^2$ だけ小さくなります。

分離する汎関数が、最近点との差ベクトルとして具体的に出てきました。

例：平面で数値を入れる

$A$ を原点中心の単位円板、$B=\{(x,y):x\ge 2\}$ とします。どちらも凸で、交わりません。

$f(x,y)=x$ をとると、$A$ の上での上限は $1$、$B$ の上での下限は $2$ です。

$$\underset{A}{\sup }f=1<2=\underset{B}{\inf }f$$

$\alpha$ は $1$ と $2$ のあいだのどれでもよい。$\alpha =1.5$ とすれば、直線 $x=1.5$ が $2$ つを分けます。

$A$ はコンパクトなので、すきまが空く形になりました。幅は $1$ です。

厳密には分けられない例

$2$ つとも閉じているだけでは、すきまが空くとはかぎりません^[4]。

$A=\{(x,y):x\le 0\}$、$B=\{(x,y):x>0,y\ge 1/x\}$ とします。どちらも閉じた凸集合で、交わりません。

$x$ を大きくすると $B$ の点は $y$ 軸から離れますが、$x$ を小さくすると $B$ の点は $y$ 軸にいくらでも近づきます。

$2$ つの集合の距離は $0$ です。分ける直線は $x=0$ しかなく、それは $A$ に接してしまう。

コンパクト性を落とすと、結論が「すきまが空く」から「接してもよい」へ弱まります。仮定と結論がきれいに対応している。

支持超平面

境界の点をとると、そこで集合に接する超平面が作れます。支持超平面と呼びます^[4]。

凸集合 $A$ と境界点 $a_0$ に対し、$f(a_0)=\alpha$ かつ $A$ 全体が $f(x)\le \alpha$ に入る $f$ がある、という主張です。

内部が空でない場合は、内部と $1$ 点を分ける形で作れます。開集合版をそのまま当てればよい。

閉凸集合は半空間の共通部分

支持超平面を全部集めると、集合そのものが復元できます^[1]。

閉凸集合は、それを含む閉半空間すべての共通部分に等しい。外側から平面で削っていくと、ちょうど元の集合が残ります。

凸でない集合ではこうなりません。半空間の共通部分はいつでも凸なので、へこみを再現できない。

凸でないと壊れる

$A$ を原点中心の単位円周、$B=\{0\}$ とします。$2$ つは交わりません。

$f$ を $0$ でない線形汎関数とすると、円周の上で $f$ は $-\Vert f\Vert$ から $\Vert f\Vert$ まで値をとります。

$f(0)=0$ はこの範囲のまんなかです。$B$ は $A$ の値の内側に入るので、どちら側にも寄せられません。

分けられないのは、円周が凸でないためです。凸包をとれば円板になり、中心が中に入ってしまう。

解析の形との関係

延長定理の形では、劣線形関数 $p$ に押さえられた汎関数を全体へ延ばします。分離定理では、この $p$ を集合から作ります^[1]。

原点を内部に含む凸集合 $C$ に対し、ミンコフスキー汎関数を次で定めます。

$$p(x)=\inf \{t>0:x/t\in C\}$$

$p$ は劣線形になり、$C$ は $p(x)\le 1$ の集合として書けます。集合の形が関数に翻訳され、延長定理が使える形になる。

同じ定理の $2$ つの顔だと言われるのは、この翻訳があるためです。

例：数列空間で切り離す

${\ell }^2$ で $M=\{x:x_1=0\}$ とします。閉部分空間なので、閉じた凸集合でもあります。

$x=e_1$ は $M$ に入りません。$M$ への最近点は原点なので、差ベクトルは $u=e_1$ です。

$f=⟨\cdot ,e_1⟩$ をとると、$M$ の上ではつねに $f=0$、いっぽう $f(e_1)=1$。すきまの幅は $1$ になりました。

例：部分空間と距離をつなぐ

$M$ が閉部分空間で $x\notin M$ のときは、もっと強い形が言えます^[1]。

$M$ の上で $0$ になり、ノルムが $1$ で、$f(x)=\mathrm{dist}(x,M)$ をみたす $f$ がとれる。分離の幅が距離そのものになります。

上の例で確かめましょう。$\mathrm{dist}(e_1,M)=1$ で $f(e_1)=1$ なので、ぴったり一致している。

検算

分離する汎関数を見つけたら、両側の値を計算して不等号の向きを確かめます。

${\sup }_{A}f$ と ${\inf }_{B}f$ を数値で出し、あいだに $\alpha$ が入るかを見る。等号が混じるなら、開いている側がどちらかを確かめます。

すきまが空くはずの場面で空かないときは、コンパクト性の仮定が抜けている疑いがある。

つまずきやすいところ

凸であること、そして片方に開性かコンパクト性があること。この $2$ 点がそろえば、平面は必ず入ります。

参考文献