今回も『Convex Optimization』を読んでいきます．
書影を得るためにAmazonのリンクを貼っていますが，この本は無料で公開されていますので興味のある方はぜひ．
演習2.22をやっていきます．
問題文
Finish the proof of the separating hyperplane theorem in §2.5.1: Show that a separating hyperplane exists for two disjoint convex sets $C$ and $D$. You can use the result proved in §2.5.1, i.e., that a separating hyperplane exists when there exist points in the two sets whose distance is equal to the distance between the two sets.
Hint. If $C$ and $D$ are disjoint convex sets, then the set $\{ x-y \mid x \in C, y \in D \}$ is convex and does not contain the origin.
この問題の背景
問題文に描かれている通り，本文中の separating hyperplane theorem の証明を完成させなさいという問題です．
この定理のステートメントは次の通りでした．
つまり，ある $a \neq 0$ と $b$ が存在して，
すべての $x \in C$ に対して $a^ T x \leq b$ かつ，
すべての $x \in D$ に対して $a^ T x \geq b$ を満たす．
本文ではこの定理を，特別な場合にのみ証明しました．
どういう場合かというと，$\mathrm{dist}(C,D) > 0$ かつ $| c -d | = \mathrm{dist}(C,D)$ を満たすような $(c,d) \in C \times D$ が存在するというケースです．
この条件は，$C$ と $D$ がコンパクト集合ならば明らかに満たされることに注意します．
問題として求められているのは，この定理の証明を一般の場合について完成させることです．
回答
ヒントに従ってみる
ヒントに $C - D$ を考えてみなさいという指示がありますね．
従ってみると，こんな感じになりました．
一見うまくいくいってるように見えます．
しかし，最後にコメントで書いてある通り，超平面であることを保証するには $v \neq 0$ を示す必要があります．
それは必ずしも成立しないため，結局 $v=0$ のケースと $v \neq 0$ のケースで場合分けをする必要が生じます．
ちょっと面倒ですね．
おまけに，特別な場合で示した分離定理をうまく使うことができていません．
コンパクト凸集合で近似
そこで，ヒントとは違いますが，コンパクト凸集合で近似する方法を使いましょう．
$C = \bigcup_{n=1}^{\infty} C_n$ を満たすような単調増加するコンパクト凸集合の列 $C_n$ を取ります．同様に $D = \bigcup_{n=1}^{\infty} D_n$ を満たすような コンパクト凸集合の列 $D_1 \subseteq D_2 \subseteq \cdots$ を取ります．
そうすると各 $C_n$ と $D_n$ に対しては分離定理が適用できますので，分離超平面 $h_n$ が存在します．$h_n$ はある $a_n \neq 0$ と $b_n$ によって $h_n = \{ x \mid a_n^ {T} x = b_n \}$ と表すことができます．$a_n$ と $b_n$ は $\| a_n \| = 1$ であるように取ります．
このとき $b_n$ のノルムもある $x_0 \in D_1$ によって $\| b_n \| \leq \|x_0\|$ と抑えられることに注意します．
したがって点列 $(a_n, b_n)$ は集積点を持つので，そのひとつを $(a,b)$ とします． そうすると，$a$ はゼロベクトルではなく（ここが重要！）$(a,b)$ が定義する超平面は $C$ と $D$ を分離します．（証明終わり）
感想
ヒントを使う方針で証明することも可能だとは思いますが，却って回り道になる気がします．
ここで採用したコンパクト凸集合で近似する証明は，マトウシェクの離散幾何学の本から引いてきたものですが，素直で良いと思います．
実は関数解析で習うハーン・バナッハの定理の仲間みたいな定理だそうです．私は関数解析には詳しくなくて，ハーン・バナッハの分離定理のありがたみもあまり理解していないのですが，この手の定理はいろんな分野で重要になりがちなのかもしれません．
この『Convex Optimization』という本の前提知識に何が必要かわからなくて困っていたのですが，コンパクト集合の概念が必要なら，位相空間論も必要ですね．ブックガイドにこの本を入れるときには位相空間論の後になるようにします．
