東京大学情報理工学研究科数理情報学 2019年度第3問

Author

Description

\(\mathbb{R}^n\) を \(n\) 次元ユークリッド空間とする。 \(x, y \in \mathbb{R}^n\) の内積を \(\langle x, y \rangle\) で表し、\(x\) のノルムを \(\lVert x \rVert := \sqrt{\langle x, x \rangle}\) とする。以下の設問に答えよ。

(1) 非空な閉集合 \(K \subseteq \mathbb{R}^n\) と点 \(x \in \mathbb{R}^n\) に対して、以下を示せ：

(1-1) \(\lVert x - y \rVert = \inf_{z \in K} \lVert x - z \rVert\) を満たす \(y \in K\) が存在する。
(1-2) \(K\) が凸なら、そのような点 \(y\) は一意に定まる。
(1-3) \(K\) が凸で、\(x\) が \(K\) に含まれないなら、ある \(c \in \mathbb{R}^n\) と \(d \in \mathbb{R}\) が存在して、

\[ \begin{aligned} &(c, x) > d, \\ &(c, z) \leq d \quad (z \in K) \end{aligned} \]

となる。

(2) \(\mathbb{R}^n\) の部分集合 \(\mathcal{A}\) に対して \(C(\mathcal{A}) \subseteq \mathbb{R}^n\) を \(\mathcal{A}\) の元たちの非負結合全体とする。すなわち、\(\mathcal{A}\) の元 \(a_1, a_2, \ldots, a_m \ (m \geq 1)\) と非負実数 \(\lambda_1, \lambda_2, \ldots, \lambda_m\) によって、 \(x = \lambda_1 a_1 + \lambda_2 a_2 + \cdots + \lambda_m a_m\) とかける点 \(x\) からなる集合が \(C(\mathcal{A})\) である。

(2-1) \(\mathcal{A} \subseteq \mathbb{R}^n\) に対して、以下が成立することを示せ：

\[ C(\mathcal{A}) = \bigcup_B C(\mathcal{B}). \]

ここで、和は、\(\mathcal{A}\) のすべての一次独立な部分集合 \(\mathcal{B}\) にわたってとる。

(2-2) \(\mathcal{A} \subseteq \mathbb{R}^n\) が有限集合なら \(C(\mathcal{A})\) は閉集合となることを示せ。

(3) \(n \times m\) 実行列 \(A \in \mathbb{R}^{n \times m}\) と \(n\) 次元ベクトル \(x \in \mathbb{R}^n\) に対して、以下の 2 つの性質 \((P)\), \((Q)\) を考える：

\((P)\) \(A \lambda = x, \lambda \geq 0\) を満たす \(\lambda \in \mathbb{R}^m\) が存在する。
\((Q)\) \(c^\top A \leq 0, c^\top x > 0\) を満たす \(c \in \mathbb{R}^n\) が存在する。

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

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

Kai

(1)

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

(1-1)

\(\mathbb{R}^n\) における有界な閉集合 \(K\) はコンパクト集合であること、及び、コンパクト集合上で定義される連続関数 \(f:K \to \mathbb{R},f(z)=\lVert x-z \rVert\) は、最大値と最小値を持つことから、\(\lVert x-y \rVert=\inf_{z\in K}f(z)\) を達成する \(y \in K\) が取れる。

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

(1-2)

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

(1-3)

\(d=0\) として良い。

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

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

ここでは省略する。

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

(2)

(2-1)

\(C(\mathcal{A}) \supseteq \bigcup_{\mathcal{B}}C(\mathcal{B})\) は明らか。

\(C(\mathcal{A}) \subseteq \bigcup_{\mathcal{B}}C(\mathcal{B})\) を示す。

\(C(\mathcal{A})\) の元 \(x\) を取る。

\(x=\lambda_1 a_1+ \cdots + \lambda_m a_m\) に関して、\(a_m=\mu_1 a_1 + \cdots + \mu_{m-1} a_{m-1}\) と書けたと仮定する。

全ての \(1 \leq i < m\) に対して、\(\lambda_i+\lambda_m \mu_i \geq 0\) が成立すれば、\(x \in C(\{a_i | 1 \leq i < m \})\) となる。

そうでない場合、\(\lambda_i+k \mu_i\) が最小の \(k\) で \(0\) になるようなインデックスを \(i\) に取ると、\(\lambda_m=\lambda_m'+k\) として、

\[ \begin{aligned} x & =\lambda_1 a_1 + \cdots + \lambda_i a_i + \cdots + \lambda_m a_m \\ & =\lambda_1 a_1 + \cdots + \lambda_i a_i + \cdots +(\lambda_m'+k) a_m \\ & =\lambda_1 a_1 + \cdots + \lambda_i a_i + \cdots + \lambda_m' a_m + k(\mu_1a_1+\cdots+\mu_{m-1}a_{m-1}) \\ & =(k\mu_1+\lambda_1) a_1 + \cdots + (k\mu_i+\lambda_i)a_i + \cdots + (k \mu_{m-1}+\lambda_{m-1}) a_{m-1}+\lambda_m' a_m \\ & =(k\mu_1+\lambda_1) a_1 + \cdots + 0 + \cdots + (k \mu_{m-1}+\lambda_{m-1}) a_{m-1}+\lambda_m' a_m \\ & \in C(\{a_j | 1 \leq j \leq m, j\neq i \}) \end{aligned} \]

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

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

よって、示された。

(2-2)

\(C(\mathcal{B})\) が閉集合であることが言えれば、有限個の閉集合の和集合は閉集合であることから、\(C(\mathcal{A})\) も閉集合であると言える。

\(C(\mathcal{B})\) が閉集合であることを示す。

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

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

ここでは省略する。

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

(3)

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

(3-1)

\[ \begin{aligned} (P) & \Rightarrow \exists \lambda \in \mathbb{R}^m \text{ s.t. } A\lambda =x,\lambda \geq 0 \end{aligned} \]

この時、\(c^TA \leq 0 \Rightarrow c^TA\lambda =c^Tx \leq 0\) となり、\((P)\Rightarrow \overline{(Q)}\) が示された。

(3-2)

\(A\) の各列ベクトルが生成する有限生成錐 \(C(\mathcal{A}=\{a_i\}_{1\leq i \leq m})\) は非空な凸閉集合である。

\(\overline{(P)}\) ならば、\(x \notin C(\mathcal{A})\) であり、分離定理より、\(\langle c,x\rangle >0\) かつ、\(\langle c,a_i\rangle \leq 0\) となる \(c\) が存在する。これは \((Q)\) に他ならない。

よって、\(\overline{(P)}\Rightarrow (Q)\) が示された。

Knowledge

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

\[ \begin{aligned} \min_{x} c^Tx \text{ s.t. } Ax = b, x \geq \boldsymbol{0} \end{aligned} \]

\[ \begin{aligned} \max_{y} b^Ty \text{ s.t. } A^Ty \leq c \end{aligned} \]

記号を入れ替えて、

\[ \begin{aligned} & \min_{\lambda} \boldsymbol{0}^T\lambda \text{ s.t. } A\lambda = x, \lambda \geq \boldsymbol{0} \\ \Rightarrow & \min_{\lambda} 0 \text{ s.t. } A\lambda = x, \lambda \geq \boldsymbol{0} \end{aligned} \]

\[ \begin{aligned} & \max_{c} x^Tc \text{ s.t. } A^Tc \leq \boldsymbol{0} \\ \Rightarrow & \max_{c} c^Tx \text{ s.t. } c^TA \leq \boldsymbol{0} \end{aligned} \]