有限生成錐 ↔ 多面体的錐の証明

有限生成錐は多面体的錐であり，逆も成り立つ，という定理がある．（p.77, 線形代数II 室田+杉原, 丸善出版）

作者: 室田一雄,杉原正顯,東京大学工学教程編纂委員会
出版社/メーカー: 丸善出版
発売日: 2013/10/09
メディア: 単行本（ソフトカバー）
この商品を含むブログを見る

この証明は読みやすいものであるが，後で自分で再現できる自信がなく，いつでも再現できそうな証明を作った．双対錐を考えることで見通しが良い証明になった気がします．

質問，指摘など歓迎します．

定理

任意の行列 $A$ について，ベクトルの有限集合 $D$ が存在して $\{x : Ax \geq 0\} = \text{cone}(D)$

任意のベクトルの有限集合 $D$ について，行列 $A$ が存在して $\{x : Ax \geq 0\} = \text{cone}(D)$

ここで $\text{cone}(X)$ はベクトルの集合 $X$ を含む最小の凸錐．

証明

2 は Fourier–Motzkin elimination - Wikipedia, the free encyclopedia を用いればOK．

1 を示す．任意の多面体的錐の双対錐が有限生成であることをいえばOK．（∵ これが示されれば，2. とあわせて双対錐が多面体的だといえる．したがって双対錐の双対錐（多面体的錐は閉凸錐であるので元の錐と一致する）が有限生成だと言える．）

$A^\top$ の列ベクトル集合が生成する閉凸錐も $\text{cone}(A^\top)$ と書くことにする．また注目する錐を $K = \{x : Ax \geq 0\}$ とする． $K^* = \text{cone}(A^\top)$ を言えれば十分．これは（ $K, \text{cone}(A^\top)$ が閉凸錐であるから） $K = \text{cone}(A^\top)^*$ と同値であるので，これを示す．

まず $K \subseteq \text{cone}(A^\top)^*$ を示す． $x \in K$ つまり $Ax \geq 0$ とする． $\text{cone}(A^\top)$ の任意の元 $y = A^\top b, b\geq 0$ と内積をとると $y^\top x = b^\top (A x) \geq 0$ ．従って $x \in \text{cone}(A^\top)^*$

つぎに $K \supseteq \text{cone}(A^\top)^*$ を示す． $x$ を $\text{cone}(A^\top)^*$ の元とする．任意の $b \geq 0$ について $x^\top A^\top b \geq 0$ ．特に任意の $i \in I$ （ $I$ は $A$ の行集合）について $x^\top A^\top e_i \geq 0$ （ $e_i$ は標準基底の元）．したがって $x^\top A^\top \geq 0$ であり， $x \in K$ ．

buq’s blog

覚えておきたいけど覚えておけなさそうなことを書きます?

有限生成錐 ↔ 多面体的錐の証明

証明