東京大学 情報理工学研究科 数理情報学 2018年8月実施 第3問

Author

hari64boli64

Description

を 次元ユークリッド空間とする。 の内積を で表し、 のノルムを とする。 以下の設問に答えよ。

(1) 非空な閉集合 と点 に対して、以下を示せ：

• (1-1) を満たす が存在する。
• (1-2) が凸なら、そのような点 は一意に定まる。
• (1-3) が凸で、 が に含まれないなら、ある と が存在して、

   となる。

(2) の部分集合 に対して を の元たちの非負結合全体とする。 すなわち、 の元 と非負実数 によって、 とかける点 からなる集合が である。

• (2-1) に対して、以下が成立することを示せ：

   ここで、和は、 のすべての一次独立な部分集合 にわたってとる。

• (2-2) が有限集合なら は閉集合となることを示せ。

(3) 実行列 と 次元ベクトル に対して、以下の 2 つの性質 , を考える：

• を満たす が存在する。
• を満たす が存在する。

ここで、 は転置を表し、ベクトル に対して記法 は の各成分が非負（非正）であることを意味する。以下を示せ：

• (3-1) と は同時に成立することはない。
• (3-2) と のどちらかは成立する。

Kai

(1)

これは分離定理を示す問題である。

(1-1)

における有界な閉集合 はコンパクト集合であること、及び、コンパクト集合上で定義される連続関数 は、最大値と最小値を持つことから、 を達成する が取れる。

なお、 は有界とは限らないが、本問に関しては、 からの距離で適当に区切っても題意に影響がない為、有界な閉集合に限定出来る。

(1-2)

凸性より明らか。省略する。

(1-3)

として良い。

イメージとしては、 と の間の垂直二等分線 (分離超平面) で、 と が別々の領域に分かれる為、内積の正負が反転するという感じである。

しかし、厳密にこれを記述することはかなり難しいと思われる。

ここでは省略する。

(「分離超平面定理」を参照)

(2)

(2-1)

は明らか。

を示す。

の元 を取る。

に関して、 と書けたと仮定する。

全ての に対して、 が成立すれば、 となる。

そうでない場合、 が最小の で になるようなインデックスを に取ると、 として、

となり、要素数を減らすことが出来る。

以下、帰納的に一次独立になるまで、この議論を繰り返せばよい。

よって、示された。

(2-2)

が閉集合であることが言えれば、有限個の閉集合の和集合は閉集合であることから、 も閉集合であると言える。

が閉集合であることを示す。

これは、有限生成錐の閉性を示せば良い。

これもかなり記述は難しい気がする。

ここでは省略する。

(「有限生成錐が閉集合になることについて」を参照)

(3)

以上を基に、ファルカスの補題を示す。

(3-1)

この時、 となり、 が示された。

(3-2)

の各列ベクトルが生成する有限生成錐 は非空な凸閉集合である。

ならば、 であり、分離定理より、 かつ、 となる が存在する。これは に他ならない。

よって、 が示された。

Knowledge

ファルカスの補題は、弱双対定理からも示せる。

記号を入れ替えて、

となる。

ならば、弱双対定理より、 となる。