東京大学 新領域創成科学研究科 複雑理工学専攻 2017年8月実施 専門基礎科目 第2問

标签：

• Tokyo-University
• Convex-Combination
• Systems-of-Linear-Equations
• Inner-Product-and-Orthogonality
• Pareto-Dominance

Author

之遥

Description

実数の集合および非負実数の集合をそれぞれ $\mathbb{R} = (-\infty,\infty) ,\mathbb{R}_{+} = [0,\infty)$ をする。次の $3$ 次元ベクトル $\boldsymbol{a}_1,\boldsymbol{a}_2,\boldsymbol{a}_3,\boldsymbol{a}_4 \in \mathbb{R}^3$ および $3 \times 4$ 行列 $\boldsymbol{A} \in \mathbb{R}^{3 \times 4}$ を考える。

$$\boldsymbol{A} = (\boldsymbol{a}_1,\boldsymbol{a}_2,\boldsymbol{a}_3,\boldsymbol{a}_4) = \begin{pmatrix} 5 & 1 & 4 & 2\\ 3 & 0 & 5 & 1\\ 1 & 4 & 0 & 3\\ \end{pmatrix}$$

$4$ 次元ベクトルを $\boldsymbol{x} = (x_1,x_2,x_3,x_4)^{\mathrm{T}} \in \mathbb{R}$ で表す。ここで, $\mathrm{T}$ はベクトルの転置を表す。さらに, 集合 $P$ を

$$P = \{\boldsymbol{x} \in \mathbb{R}_{+}^4 :x_1 + x_2 + x_3 + x_4 = 1\}$$

と定義する。このとき, 以下の問に答えよ。

(問1) 集合 $S \subset \mathbb{R}^3$ を $x_1 + x_3 = 1$ かつ $x_2 + x_4 = 1$ を満たす $\boldsymbol{x} \in \mathbb{R}^4$ に対して点 $\boldsymbol{Ax}$ がなす集合とする, すなわち

$$S = \{\boldsymbol{Ax :x} \in \mathbb{R}^4,x_1 + x_3 = 1,x_2 + x_4 = 1\}$$

とする。$S$ と直交する単位ベクトル $\boldsymbol{c} \in \mathbb{R}^3$ を求めよ。

(問2) $x_4 = 0$ かつ $\boldsymbol{Ax} = \boldsymbol{a}_4$ を満たす $\boldsymbol{x} \in \mathbb{R}$ を求めよ。

(問3) $\boldsymbol{x} \in P$ のうち次の $2$ つの条件を同時に満たすものを $1$ つ挙げよ。ここで, (問 2) の結果を用いてもよい。

• (a) $x_4$ = 0
• (b) $\boldsymbol{ya}_4 \le \boldsymbol{yAx}$ が任意の $\boldsymbol{y} = (y_1,y_2,y_3) \in \mathbb{R}_{+}^3$ に対して成り立つ

(問4) 任意の固定した $\boldsymbol{x}' \in P$ に対して, 次の $2$ つの条件を同時に満たす $\boldsymbol{x} \in P$ が存在することを示せ。ここで, (問 3) の結果を用いてもよい。

• (a) $x_4$ = 0
• (b) $\boldsymbol{yAx}' \le \boldsymbol{yAx}$ が任意の $\boldsymbol{y} = (y_1,y_2,y_3) \in \mathbb{R}_{+}^3$ に対して成り立つ

题目描述

记

$$\mathbb R=(-\infty,\infty),\qquad \mathbb R_+=[0,\infty),$$

并给定列向量 $\boldsymbol a_1,\ldots,\boldsymbol a_4\in\mathbb R^3$ 组成的矩阵

$$\boldsymbol A=(\boldsymbol a_1,\boldsymbol a_2,\boldsymbol a_3,\boldsymbol a_4) = \begin{pmatrix} 5&1&4&2\\ 3&0&5&1\\ 1&4&0&3 \end{pmatrix}.$$

对四维列向量 $\boldsymbol x=(x_1,x_2,x_3,x_4)^T$，定义概率单纯形

$$P=\{\boldsymbol x\in\mathbb R_+^4\mid x_1+x_2+x_3+x_4=1\}.$$

回答：

1. 定义仿射集合
   $$S=\{\boldsymbol A\boldsymbol x\mid \boldsymbol x\in\mathbb R^4,\qquad x_1+x_3=1,\ x_2+x_4=1\}.$$
   求一个与 $S$ 的方向空间正交的单位向量 $\boldsymbol c\in\mathbb R^3$。
2. 求满足
   $$x_4=0,\qquad \boldsymbol A\boldsymbol x=\boldsymbol a_4$$
   的四维向量 $\boldsymbol x$。原题在此处把所属空间排作 $\mathbb R$，但由四个分量及矩阵乘法可确定所求对象为四维向量。
3. 在 $\boldsymbol x\in P$ 中举出一例，同时满足：
   • $x_4=0$；
   • 对任意非负权重行向量 $\boldsymbol y=(y_1,y_2,y_3)\in\mathbb R_+^3$，
     $$\boldsymbol y\boldsymbol a_4 \le\boldsymbol y\boldsymbol A\boldsymbol x.$$
   可使用第 2 问结果。
4. 对任意固定的 $\boldsymbol x'\in P$，证明存在 $\boldsymbol x\in P$ 同时满足：
   • $x_4=0$；
   • 对任意 $\boldsymbol y\in\mathbb R_+^3$，
     $$\boldsymbol y\boldsymbol A\boldsymbol x' \le\boldsymbol y\boldsymbol A\boldsymbol x.$$
   可使用第 3 问结果。

考点

• 仿射集合与正交方向：把线性约束代入 $\boldsymbol A\boldsymbol x$，求所得平面的两个方向向量及单位法向量。
• 线性方程组：在 $x_4=0$ 下解三元线性系统，把第四列表示为前三列的线性组合。
• 凸组合与概率单纯形：检查系数非负且和为 1，并把原组合中第四列的权重重新分配到前三列。
• Pareto 支配：把对所有非负权重 $\boldsymbol y$ 的不等式等价为分量逐一不减，证明消去第四方案后仍支配原方案。

Kai

(問1)

$$Ax = \begin{bmatrix} 5 & 1 & 4 & 2\\ 3 & 0 & 5 & 1\\ 1 & 4 & 0 & 3\\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ 1 - x_1 \\ 1 - x_2 \\ \end{bmatrix} = \begin{bmatrix} x_1 - x_2 + 6 \\ -2x_1 - x_2 + 6 \\ x_1 + x_2 + 3 \\ \end{bmatrix} = \begin{bmatrix} 6 \\ 6 \\ 3 \\ \end{bmatrix} + x_1 \begin{bmatrix} 1 \\ -2 \\ 1 \end{bmatrix} + x_2 \begin{bmatrix} -1 \\ -1 \\ 1 \\ \end{bmatrix}$$

$$\begin{bmatrix} 1 \\ -2 \\ 1 \\ \end{bmatrix} \times \begin{bmatrix} -1 \\ -1 \\ 1 \\ \end{bmatrix} = \begin{bmatrix} i & j & k \\ 1 & -2 & 1 \\ -1 & -1 & 1 \\ \end{bmatrix} = (-1,-2,-3)$$

$$c = \frac{1}{\sqrt{14}} \begin{bmatrix} 1 \\ 2 \\ 3 \\ \end{bmatrix}$$

(問2)

$$\begin{bmatrix} 5 & 1 & 4 & 2\\ 3 & 0 & 5 & 1\\ 1 & 4 & 0 & 3\\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ 0 \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 3 \\ \end{bmatrix} \quad \begin{bmatrix} 5 & 1 & 4 \\ 3 & 0 & 5 \\ 1 & 4 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \end{bmatrix} = \begin{bmatrix} 2 \\ 1 \\ 3 \\ \end{bmatrix} \quad \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ \end{bmatrix} = \frac{1}{47} \begin{bmatrix} 9 \\ 33 \\ 4 \\ \end{bmatrix}$$

$$x = \frac{1}{47} \begin{bmatrix} 9 \\ 33 \\ 4 \\ 0 \\ \end{bmatrix}$$

(問3)

From (問2) , we have $a_4 = \begin{bmatrix}a_1 & a_2 & a_3 & a_4\end{bmatrix}\begin{bmatrix}\frac{9}{47}\\\frac{33}{47}\\\frac{4}{47}\\0\\ \end{bmatrix}$, hence

$$yAx - ya_4 = yA\left(x - \begin{bmatrix}\frac{9}{47}\\\frac{33}{47}\\\frac{4}{47}\\0\\\end{bmatrix}\right)$$

Since $y \in \mathbb{R}_{+}^3$ and $A_{ij} \ge 0(i = 1,2,3;j = 1,2,3,4)$, we have $ya_4 \le yAx$ for any $y \in \mathbb{R}_{+}^3$ when every element of $\left(x - \begin{bmatrix}\frac{9}{47}\\\frac{33}{47}\\\frac{4}{47}\\0\\\end{bmatrix}\right)$ is larger than or equal to $0$.

Therefore,

$$\left\{ \begin{aligned} &x_1 + x_2 + x_3 + x_4 = \frac{46}{47} \neq 1 \\ &x_1 \ge \frac{1}{47} \\ &x_2 \ge \frac{33}{47} \\ &x_3 \ge \frac{4}{47} \\ \end{aligned} \right.$$

one solution is

$$x = \begin{bmatrix}\frac{10}{47}\\\frac{33}{47}\\\frac{4}{47}\\0\\ \end{bmatrix}$$

(問4)

$$\begin{aligned} yA(x - x') &= y\begin{bmatrix}a_1 & a_2 & a_3 & \frac{9a_1 + 33a_2 + 4a_3}{47}\end{bmatrix} \left( \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ 0 \\ \end{bmatrix} - \begin{bmatrix} x_1' \\ x_2' \\ x_3' \\ x_4' \\ \end{bmatrix} \right) \\ &= y\bigg[a_1(x_1 - x_1' - \frac{9}{47}x_4') + a_2(x_2 - x_2' - \frac{33}{47}x_4 ') + a_3(x_3 - x_3' - \frac{4}{47}x_4')\bigg] \end{aligned}$$

Since $y \in \mathbb{R}_{+}^3$ and every element of $a_1,a_2$ and $a_3$ is larger than or equal to $0$, if every element of $(x_1 - x_1' - \frac{9}{47}x_4'),(x_2 - x_2' - \frac{33}{47}x_4')$ and $(x_3 - x_3' - \frac{4}{47}x_4')$ is larger than or equal to $0$ , we will obtain that $yAx' \le yAx$ for any $y \in \mathbb{R}_{+}^3$.

Therefore,

$$\left\{ \begin{aligned} &x_1 + x_2 + x_3 = 1 \\ &x_1' + x_2' + x_3' + x_4' = 1 \\ &x_1 \ge x_1' + \frac{9}{47}x_4'\\ &x_2 \ge x_2' + \frac{33}{47}x_4'\\ &x_3 \ge x_3' + \frac{4}{46}x_4'\\ \end{aligned} \right.$$

one solution is

$$x = \begin{bmatrix} x_1' + \frac{10}{47}x_4' \\ x_2' + \frac{33}{47}x_4' \\ x_3' + \frac{4}{47}x_4' \\ 0 \\ \end{bmatrix}$$