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

标签：

• 东京大学
• 闭凸集的投影定理
• 分离超平面定理
• Farkas 引理

Author

hari64boli64, 祭音Myyura

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)$ のどちらかは成立する。

题目描述

在欧氏空间 $\mathbb R^n$ 中，以 $\langle x,y\rangle$ 表示内积， $\|x\|=\sqrt{\langle x,x\rangle}$。

1. 对非空闭集 $K\subseteq\mathbb R^n$ 与点 $x\in\mathbb R^n$：

   1. 证明存在 $y\in K$ 达到距离下确界，

      $$\|x-y\|=\inf_{z\in K}\|x-z\|;$$

   2. 若 $K$ 为凸集，证明该最近点唯一；

   3. 若 $K$ 为凸集且 $x\notin K$，证明存在 $c\in\mathbb R^n,d\in\mathbb R$，使

      $$\langle c,x\rangle>d,\qquad \langle c,z\rangle\le d\quad(z\in K).$$

2. 对集合 $\mathcal A\subseteq\mathbb R^n$，记 $C(\mathcal A)$ 为 $\mathcal A$ 中有限多个向量的所有非负线性组合构成的锥。

   1. 证明

      $$C(\mathcal A)=\bigcup_{\mathcal B}C(\mathcal B),$$

      其中并集遍历 $\mathcal A$ 的所有线性无关子集 $\mathcal B$；

   2. 若 $\mathcal A$ 有限，证明 $C(\mathcal A)$ 为闭集。

3. 给定 $A\in\mathbb R^{n\times m}$ 与 $x\in\mathbb R^n$，考虑：

   • (P) 存在 $\lambda\in\mathbb R^m$，使 $A\lambda=x,\lambda\ge0$；
   • (Q) 存在 $c\in\mathbb R^n$，使 $c^\top A\le0,c^\top x>0$。

   证明：

   1. (P)、(Q) 不可能同时成立；
   2. (P)、(Q) 至少有一个成立。

Kai

(1)

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

(1-1)

$z_0\in K$ を一つ取り、$K'=K\cap\{z\mid\|x-z\|\leq\|x-z_0\|\}$ とおく。$K'$ は非空な有界閉集合なのでコンパクトである。$K\setminus K'$ の点は $z_0$ より $x$ に近くないため、$K'$ 上で $\|x-z\|$ を最小にする点 $y$ は $K$ 上でも最小点である。

(1-2)

最小点が $y_1,y_2$ の二つあり、最小距離を $r$ とする。凸性より $(y_1+y_2)/2\in K$ であり、

$$\left\|x-\frac{y_1+y_2}{2}\right\|^2 =r^2-\frac14\|y_1-y_2\|^2.$$

$y_1\ne y_2$ なら右辺は $r^2$ より小さく矛盾する。よって $y_1=y_2$ である。

(1-3)

(1-1) の最小点を $y$ とする。任意の $z\in K$ に対し、$y+t(z-y)\in K\ (0\leq t\leq1)$ なので、$t=0$ で距離の二乗が最小になることから

$$\langle x-y,z-y\rangle\leq0.$$

$c=x-y$, $d=\langle c,y\rangle$ とおけば、$\langle c,z\rangle\leq d$ であり、$x\notin K$ より $\langle c,x\rangle=d+\|x-y\|^2>d$ となる。

(2)

(2-1)

$m\geq1$ の和だけを認める定義では、$\mathcal A=\{0\}$ のとき $C(\mathcal A)=\{0\}$ だが、$\mathcal A$ に非空の一次独立部分集合はなく、 $C(\varnothing)=\varnothing$ となるため、等式は成立しない。 以下では空和を $0$、$C(\varnothing)=\{0\}$ とする規約のもとで示す。

$C(\mathcal{A}) \supseteq \bigcup_{\mathcal{B}}C(\mathcal{B})$ は明らかである。逆向きを示すため、 $x=\sum_{i=1}^m\lambda_i a_i\ (\lambda_i\geq0)$ とする。$a_1,\ldots,a_m$ が一次従属なら、ある $\mu\ne0$ が存在して $\sum_i\mu_i a_i=0$ となる。必要なら符号を反転し、

$$t=\min_{\mu_i>0}\frac{\lambda_i}{\mu_i},\qquad \lambda_i'=\lambda_i-t\mu_i$$

とおく。全ての $\lambda_i'$ は非負で、少なくとも一つは $0$ となり、$x=\sum_i\lambda_i'a_i$ である。係数が $0$ となった項を取り除くと項数が減るので、この操作を一次独立になるまで有限回繰り返せばよい。

(2-2)

$\mathcal A$ は有限なので、(2-1) の和集合は有限個である。一次独立な $\mathcal B=\{b_1,\ldots,b_k\}$ に対し、線形写像 $T:\mathbb R^k\to\operatorname{span}\mathcal B$, $T\lambda=\sum_i\lambda_i b_i$ は同型であり、$T^{-1}$ は連続である。$\operatorname{span}\mathcal B$ は閉集合なので、$T\lambda^{(r)}\to x$, $\lambda^{(r)}\geq0$ なら $x\in\operatorname{span}\mathcal B$ かつ $\lambda^{(r)}\to T^{-1}x\geq0$ であり、$x\in C(\mathcal B)$ となる。よって各 $C(\mathcal B)$、したがって $C(\mathcal A)$ は閉集合である。

(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})$ であり、(1-3) より $\langle c,x\rangle>d$, $\langle c,z\rangle\leq d\ (z\in C(\mathcal A))$ となる $c,d$ が存在する。$0\in C(\mathcal A)$ より $d\geq0$ である。また錐の任意の元を正数倍できるので、$\langle c,z\rangle\leq0$ がすべての $z\in C(\mathcal A)$ について成り立つ。ゆえに $c^Tx>0$, $c^TA\leq0$、すなわち $(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}$$

となる。

この実行可能性の二者択一を双対性から導くには強双対定理が必要であり、弱双対定理だけでは十分でない。