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

标签：

• Tokyo-University
• Projection-Theorem-for-Closed-Convex-Sets
• Separating-Hyperplane-Theorem
• Farkas-Lemma

Author

hari64boli64

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}$$

となる。

$\overline{(Q)}$ ならば、弱双対定理より、$(P)$ となる。