おはようございます.
今回も Boyd, Vandenberghe『Convex Optimization』の演習問題をやっていきます.
書影を得るためにAmazonのリンクを貼ってはいますが,この本は無償公開されているので興味のある方はぜひ読んでみてください.
問題文
Give an example of two closed convex sets that are disjoint but cannot be strictly separated. Boyd, Vandenberghe『Convex Optimization』Ex 2.23
問題の背景
へこみのない集合のことを,凸集合と言います.
凸集合の凸性のひとつの帰結として,分離定理というのがあります.
互いに交わりを持たない2つの凸集合 $C$, $D$ があるならば,$C$ と $D$ を分離する超平面 $H$ が存在する__という定理です.
ここで超平面とは何かというと,線形写像の逆像で表されるような空間のことです.つまり,ゼロでないベクトル $a \neq 0$ とベクトル $b$ について
という形に表される集合のことを,超平面と言っています.
そして超平面が $C$ と $D$ を分離するというのはどういうことかというと,$H$ を隔てて $C$ と $D$ が同じ側にないということです.具体的には $H = \{ x \mid a^ T x = b \}$ と表されているときに
(2) すべての $x \in D$ について $a^ Tx \geq b$
が成り立つときに(不等号の向きは逆でも構いません),$H$ は $C,D$ を分離すると言います.
この(1)(2) における不等号を狭義の不等号に変えても成立するとき,strict separation (狭義の分離)であるといいます.
分離定理によって,分離超平面の存在は保証されているのですが,狭義の分離超平面は存在しないこともあります.
具体例としては,$C,D$ が開集合であって境界がぴったり重なっているようなものを考えれば,すぐにわかります.
いまの例では開集合で例を挙げましたが,$C,D$ が閉集合という仮定をつけてもまだ狭義の分離超平面が存在しないことがあります.
その例を挙げなさいという問題です.
回答
$C = \{ (x,y) \in \mathbb{R}^2 \mid x \leq 0 \}$ として,
$D = \{ (x,y) \in \mathbb{R}^2 \mid x>0, y \geq 1/x \}$ とします.
Desmosで描画した図を載せておきましょう.見ればすぐわかると思います.
$C$ も $D$ も閉凸集合ですが,狭義の分離超平面は存在しません.
あとがき
「無限の果てで重なる」という概念は直観に反しているところがあって,こういう平面が無限に広がっているということを利用する例を思いつくのは結構大変です.
やはり無限という概念は人間にはまだ早いのかもしれません.