跳到主要内容

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

标签：

Author​

hari64boli64, 祭音Myyura

Description​

nn 次元実ベクトル空間 Rn\mathbb{R}^n のベクトル uu の第 ii 成分を uiu_i と表す。 すべての i=1,…,ni = 1, \ldots, n に対して ui>0u_i > 0 である u∈Rnu \in \mathbb{R}^n を正値であるといい。正値ベクトル全体の集合を Xn\mathcal{X}_n で表す。 また、ベクトル a∈Rna \in \mathbb{R}^n に対し、(i,i)(i, i) 成分が ai (i=1,…,n)a_i \ (i = 1, \ldots, n) であるような対角行列を diag(a1,…,an)\text{diag}(a_1, \ldots, a_n) で表す。 行列 MM の転置を MTM^T で表す。

正則な n×nn \times n 実行列 A=(aij)A = (a_{ij}), ベクトル v∈Rnv \in \mathbb{R}^n に対し、x∈Xnx \in \mathcal{X}_n の関数 Fi(x)F_i(x) を

Fi(x)=xi(vi+∑j=1naijxj)(i=1,…,n)F_i(x)=x_i \left(v_i+\sum_{j=1}^{n}a_{ij}x_j \right) \quad (i = 1, \ldots, n)

と定める。ここで、Fi(x∗)=0 (i=1,…,n)F_i(x^*) = 0 \ (i = 1, \ldots, n) を満たす x∗∈Xnx^* \in \mathcal{X}_n が存在するとする。 そして、x(t)∈Xnx(t) \in \mathcal{X}_n についての微分方程式系

dxi(t)dt=Fi(x(t))(t≥0, i=1,…,n)\begin{align} \frac{\text{d}x_i(t)}{\text{d}t} = F_i(x(t)) \quad (t \geq 0, \ i = 1, \ldots, n) \tag{*} \end{align}

を考える。以下の設問に答えよ。

(1) ベクトル c∈Xnc \in \mathcal{X}_n に対し、x∈Xnx \in \mathcal{X}_n の関数 L(x)L(x) を

L(x)=∑i=1nci[xi∗log⁡xi∗xi−xi∗+xi]L(x) = \sum_{i=1}^n c_i \left[ x_i^* \log \frac{x_i^*}{x_i} - x_i^* + x_i \right]

とする。 x(0)=x′∈Xnx(0) = x' \in \mathcal{X}_n を初期値とする方程式 (∗*) の解 x(t)x(t) に対し、L˙(x′)\dot{L}(x') を L˙(x′)=dL(x(t))dt∣t=0\dot{L}(x') = \left. \frac{\text{d}L(x(t))}{\text{d}t} \right|_{t=0} と定める。 また、行列 CC を C=diag(c1,…,cn)C = \text{diag}(c_1, \ldots, c_n) と定める。対称行列 CA+ATCCA + A^T C が負定値となるとき、かつそのときに限り、任意の x′∈Xn∖{x∗}x' \in \mathcal{X}_n \setminus \{ x^* \} に対して L˙(x′)<0\dot{L}(x') < 0 となることを示せ。

(2) ベクトル w∈Xnw \in \mathcal{X}_n に対し、z∈Rnz \in \mathbb{R}^n の関数 Hw(z)H_w(z) を

Hw(z)=12∑i=1nwizi2H_w(z) = \frac{1}{2} \sum_{i=1}^n w_i z_i^2

とし、Hw(z)H_w(z) の zz における勾配を ∇Hw(z)=(∂Hw∂z1(z),…,∂Hw∂zn(z))T\nabla H_w(z) = \left( \frac{\partial H_w}{\partial z_1}(z), \ldots, \frac{\partial H_w}{\partial z_n}(z) \right)^T と表す。 方程式 (∗*) の解 x(t)x(t) に対して、z(t)=x(t)−x∗z(t) = x(t) - x^* が

dz(t)dt=G(z(t))∇Hw(z(t))\frac{\text{d}z(t)}{\text{d}t} = G(z(t)) \nabla H_w(z(t))

を満たすような行列関数 G(z)G(z) を求めよ。 ただし、関数 G(z)G(z) は、A,W=diag(w1,…,wn),X∗=diag(x1∗,…,xn∗),Z=diag(z1,…,zn)A, W = \text{diag}(w_1, \ldots, w_n), X^* = \text{diag}(x_1^*, \ldots, x_n^*), Z = \text{diag}(z_1, \ldots, z_n) を用いて表すこと。

(3) 対角行列 C=diag(c1,…,cn)C = \text{diag}(c_1, \ldots, c_n) に対し、対称行列 CA+ATCCA + A^T C が負定値となる c∈Xnc \in \mathcal{X}_n が存在するとする。 このとき、次のことが成り立つようなベクトル w∈Xnw \in \mathcal{X}_n を一つ求めよ。

「z(t)∈U∖{0}z(t) \in U \setminus \{0\} ならば dHw(z(t))dt<0\frac{\text{d}H_w(z(t))}{\text{d}t} < 0 となる、0∈Rn0 \in \mathbb{R}^n の開近傍 U⊂RnU \subset \mathbb{R}^n が存在する。」

题目描述​

以 uiu_i 表示向量 u∈Rnu\in\mathbb{R}^n 的第 ii 个分量。若对所有 i=1,…,ni=1,\ldots,n 都有 ui>0u_i>0，则称 uu 为正向量，并以 Xn\mathcal{X}_n 表示所有正向量的集合。对 a∈Rna\in\mathbb{R}^n，以 diag⁡(a1,…,an)\operatorname{diag}(a_1,\ldots,a_n) 表示第 (i,i)(i,i) 个元素为 aia_i 的对角矩阵；矩阵 MM 的转置记为 MTM^T。

给定可逆实矩阵 A=(aij)∈Rn×nA=(a_{ij})\in\mathbb{R}^{n\times n} 和向量 v∈Rnv\in\mathbb{R}^n，对 x∈Xnx\in\mathcal{X}_n 定义

Fi(x)=xi(vi+∑j=1naijxj)(i=1,…,n).F_i(x)=x_i\left(v_i+\sum_{j=1}^n a_{ij}x_j\right) \qquad(i=1,\ldots,n).

假设存在 x∗∈Xnx^*\in\mathcal{X}_n，使 Fi(x∗)=0 (i=1,…,n)F_i(x^*)=0\ (i=1,\ldots,n)。考虑微分方程组

dxi(t)dt=Fi(x(t))(t≥0, i=1,…,n),(*)\frac{dx_i(t)}{dt}=F_i(x(t)) \qquad(t\geq0,\ i=1,\ldots,n), \tag{*}

其中 x(t)∈Xnx(t)\in\mathcal{X}_n。回答下列问题。

(1) 对 c∈Xnc\in\mathcal{X}_n，定义

L(x)=∑i=1nci[xi∗log⁡xi∗xi−xi∗+xi].L(x)=\sum_{i=1}^n c_i \left[x_i^*\log\frac{x_i^*}{x_i}-x_i^*+x_i\right].

设 x(t)x(t) 是方程 (∗)(*) 在初值 x(0)=x′∈Xnx(0)=x'\in\mathcal{X}_n 下的解，并定义

L˙(x′)=dL(x(t))dt∣t=0,C=diag⁡(c1,…,cn).\dot L(x')=\left.\frac{dL(x(t))}{dt}\right|_{t=0}, \qquad C=\operatorname{diag}(c_1,\ldots,c_n).

证明：对称矩阵 CA+ATCCA+A^TC 负定，当且仅当对任意 x′∈Xn∖{x∗}x'\in\mathcal{X}_n\setminus\{x^*\} 都有 L˙(x′)<0\dot L(x')<0。

(2) 对 w∈Xnw\in\mathcal{X}_n，定义

Hw(z)=12∑i=1nwizi2,H_w(z)=\frac12\sum_{i=1}^n w_i z_i^2,

并以

∇Hw(z)=(∂Hw∂z1(z),…,∂Hw∂zn(z))T\nabla H_w(z)= \left( \frac{\partial H_w}{\partial z_1}(z),\ldots, \frac{\partial H_w}{\partial z_n}(z) \right)^T

表示其梯度。对方程 (∗)(*) 的解 x(t)x(t)，令 z(t)=x(t)−x∗z(t)=x(t)-x^*。求矩阵值函数 G(z)G(z)，使得

dz(t)dt=G(z(t))∇Hw(z(t)),\frac{dz(t)}{dt}=G(z(t))\nabla H_w(z(t)),

并用 AA 以及

W=diag⁡(w1,…,wn),X∗=diag⁡(x1∗,…,xn∗),Z=diag⁡(z1,…,zn)W=\operatorname{diag}(w_1,\ldots,w_n),\quad X^*=\operatorname{diag}(x_1^*,\ldots,x_n^*),\quad Z=\operatorname{diag}(z_1,\ldots,z_n)

表示 G(z)G(z)。

(3) 假设存在 c∈Xnc\in\mathcal{X}_n，使 C=diag⁡(c1,…,cn)C=\operatorname{diag}(c_1,\ldots,c_n) 满足对称矩阵 CA+ATCCA+A^TC 负定。求一个 w∈Xnw\in\mathcal{X}_n，使得存在原点 0∈Rn0\in\mathbb{R}^n 的开邻域 U⊂RnU\subset\mathbb{R}^n，且只要 z(t)∈U∖{0}z(t)\in U\setminus\{0\}，就有

dHw(z(t))dt<0.\frac{dH_w(z(t))}{dt}<0.

Kai​

(1)​

まず、Fi(x∗)=0F_i(x^*)=0 という条件より、 また、x∗∈Xnx^* \in \mathcal{X}_n より、xi∗≠0x^*_i \neq 0 であることより、 vi=−∑j=1naijxj∗v_i=-\sum_{j=1}^{n}{a_{ij}x^*_j} である。

条件を整理していくと、

L(x′)˙=dL(x(t))dt∣t=0=∑i=1nci(−xi∗xi′+1)dxidt∣t=0=∑i=1nci(−xi∗xi′+1)Fi(x′)=∑i=1nci(−xi∗xi′+1)xi′(vi+∑j=1naijxj′)=∑i=1nci(−xi∗+xi′)(vi+∑j=1naijxj′)=−∑i=1ncixi∗vi−∑i=1ncixi∗(∑j=1naijxj′)+∑i=1ncixi′vi+∑i=1ncixi′(∑j=1naijxj′)=∑i=1n∑j=1ncixi∗aijxj∗−∑i=1n∑j=1ncixi∗aijxj′−∑i=1n∑j=1ncixi′aijxj∗+∑i=1n∑j=1ncixi′aijxj′=x∗TCAx∗−x∗TCAx′−x′TCAx∗+x′TCAx′=(x∗−x′)TCA(x∗−x′)\begin{aligned} \dot{L(x')} & =\left.\frac{\text{d}L(x(t))}{\text{d}t}\right|_{t=0} \\ & =\sum_{i=1}^{n}{c_i \left(-\frac{x_i^*}{x'_i}+1 \right)\left.\frac{\text{d}x_i}{\text{d}t}\right|_{t=0}} \\ & =\sum_{i=1}^{n}{c_i \left(-\frac{x_i^*}{x'_i}+1 \right)F_i(x')} \\ & =\sum_{i=1}^{n}{c_i \left(-\frac{x_i^*}{x'_i}+1 \right)x'_i \left(v_i+\sum_{j=1}^{n}a_{ij}x'_j \right)} \\ & =\sum_{i=1}^{n}{c_i \left(-x_i^*+x'_i \right) \left(v_i+\sum_{j=1}^{n}a_{ij}x'_j \right)} \\ & =-\sum_{i=1}^{n}{c_ix_i^*v_i}-\sum_{i=1}^{n}{c_ix_i^* \left(\sum_{j=1}^{n}a_{ij}x'_j \right)} +\sum_{i=1}^{n}{c_ix'_iv_i}+\sum_{i=1}^{n}{c_ix'_i \left(\sum_{j=1}^{n}a_{ij}x'_j \right)} \\ & =\sum_{i=1}^{n}\sum_{j=1}^{n}{c_ix_i^*a_{ij}x^*_j}-\sum_{i=1}^{n}\sum_{j=1}^{n}{c_ix_i^*a_{ij}x'_j} -\sum_{i=1}^{n}\sum_{j=1}^{n}{c_ix'_ia_{ij}x^*_j}+\sum_{i=1}^{n}\sum_{j=1}^{n}{c_ix'_ia_{ij}x'_j} \\ & ={x^*}^TCAx^*-{x^*}^TCAx'-{x'}^TCAx^*+{x'}^TCAx' \\ & =(x^*-x')^TCA(x^*-x') \end{aligned}

となる。

よって、

(∀x′∈Xn∖{x∗})L(x′)˙<0⇔(∀y∈Rn∖{0}) yTCAy<0⇔(∀y∈Rn∖{0}) yT(CA+ATC)y<0⇔CA+ATC≺0\begin{aligned} & (\forall x'\in \mathcal{X}_n\setminus \{x^*\}) \dot{L(x')} < 0 \\ \Leftrightarrow & (\forall y\in\mathbb{R}^n\setminus\{0\})\ y^TCAy<0 \\ \Leftrightarrow & (\forall y\in\mathbb{R}^n\setminus\{0\})\ y^T(CA+A^TC)y<0 \\ \Leftrightarrow & CA+A^TC \prec 0 \end{aligned}

となる。実際、任意の y≠0y\ne0 に対し、十分小さい ε>0\varepsilon>0 を選べば x′=x∗−εy∈Xnx'=x^*-\varepsilon y\in\mathcal X_n である。 二次形式の斉次性より、x∗−x′x^*-x' が取り得る範囲での負値性は 全ての y≠0y\ne0 での負値性と同値である。また、 yTCAy=12yT(CA+ATC)yy^TCAy=\frac12y^T(CA+A^TC)y を用いた。

(2)​

まず、∇Hw(z)=(w1z1,…,wnzn)T\nabla H_w(z)= (w_1z_1,\dots,w_nz_n)^T である。

ここで、

dzi(t)dt=dxi(t)dt=Fi(x(t))=xi(t)(vi+∑j=1naijxj(t))=(xi(t)−xi∗+xi∗)(∑j=1naij(xj(t)−xj∗))=(zi(t)+xi∗)(∑j=1naijzj(t))\begin{aligned} \frac{\text{d}z_i(t)}{\text{d}t} & =\frac{\text{d}x_i(t)}{\text{d}t} \\ & =F_i(x(t)) \\ & =x_i(t)\left(v_i+\sum_{j=1}^{n}a_{ij}x_j(t) \right) \\ & =(x_i(t)-x^*_i+x^*_i)\left(\sum_{j=1}^{n}a_{ij}(x_j(t)-x^*_j) \right) \\ & =(z_i(t)+x^*_i)\left(\sum_{j=1}^{n}a_{ij}z_j(t) \right) \end{aligned}

となるので、

dz(t)dt=(Z+X∗)Az(t)=(Z+X∗)AW−1Wz(t)=(Z+X∗)AW−1∇Hw(z(t))\begin{aligned} \frac{\text{d}z(t)}{\text{d}t} & =(Z+X^*) A z(t) \\ & =(Z+X^*) A W^{-1} W z(t) \\ & =(Z+X^*) A W^{-1} \nabla H_w(z(t)) \end{aligned}

となる。

(3)​

条件をより平易な表現で言い表すと、lim⁡z(t)→0\lim_{z(t) \to 0} において、 dHw(z(t))dt<0\frac{\text{d}H_w(z(t))}{\text{d}t}<0 を満たすような ww を、cc を用いて表現せよ、 ということになる。

ここで

W=C(X∗)−1,すなわちwi=cixi∗>0W=C(X^*)^{-1}, \qquad\text{すなわち}\qquad w_i=\frac{c_i}{x_i^*}>0

と選ぶ。このとき WX∗=CWX^*=C であるから、

dHw(z(t))dt=z(t)TW(Z+X∗)Az(t)=12z(t)T(CA+ATC)z(t)+z(t)TWZAz(t).\begin{aligned} \frac{\text{d}H_w(z(t))}{\text{d}t} &=z(t)^TW(Z+X^*)Az(t)\\ &=\frac12z(t)^T(CA+A^TC)z(t)+z(t)^TWZAz(t). \end{aligned}

CA+ATC≺0CA+A^TC\prec0 より、ある λ>0\lambda>0 に対して第1項は −λ∥z∥22/2-\lambda\|z\|_2^2/2 以下である。一方、 ∥Z∥≤∥z∥2\|Z\|\leq\|z\|_2 より第2項の絶対値は ∥W∥∥A∥∥z∥23\|W\|\|A\|\|z\|_2^3 以下である。したがって十分小さい r>0r>0 に対し、U={z:∥z∥2<r}U=\{z:\|z\|_2<r\} とすれば、 z(t)∈U∖{0}z(t)\in U\setminus\{0\} のとき ddtHw(z(t))<0\frac{\text{d}}{\text{d}t}H_w(z(t))<0 となる。

本页目录