跳到主要内容

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

标签：

Author​

hari64boli64

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 が存在する。」

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⇔(∀x′∈Xn∖{x∗})(x∗−x′)TCA(x∗−x′)<0⇔(∀x′∈Xn∖{x∗})((x∗−x′)TCA(x∗−x′)<0)∧((x∗−x′)TATC(x∗−x′)<0)⇔(∀y∈Rn)yT(CA+ATC)y<0⇔CA+ATC≺0\begin{aligned} & (\forall x'\in \mathcal{X}_n\setminus \{x^*\}) \dot{L(x')} < 0 \\ \Leftrightarrow & (\forall x'\in \mathcal{X}_n\setminus \{x^*\})(x^*-x')^TCA(x^*-x')<0 \\ \Leftrightarrow & (\forall x'\in \mathcal{X}_n\setminus \{x^*\}) \left((x^*-x')^TCA(x^*-x')< 0 \right) \wedge \left((x^*-x')^TA^TC(x^*-x')< 0 \right) \\ \Leftrightarrow & (\forall y \in \mathbb{R}^n) y^T(CA+A^TC)y< 0 \\ \Leftrightarrow & CA+A^TC \prec 0 \end{aligned}

となる。 なお、x∗−x′x^*-x' から yy への変換には注意が必要である。 全ての y∈Rny\in \mathbb{R}^n に対して、 x∗−x′=yx^*-x'=y を満たす x′∈Xn∖{x∗}x'\in \mathcal{X}_n\setminus \{x^*\} が存在するとは限らない。 ここでは長さに関する定数倍の変換が挟まっている。

(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 を用いて表現せよ、 ということになる。

このことを念頭に置いて式変形していくと、

dHw(z(t))dt=∑i=1nwizi(t)dzi(t)dt=∇Hw(z(t))TG(z(t))∇Hw(z(t))=∇Hw(z(t))T((Z+X∗)AW−1)∇Hw(z(t))\begin{aligned} \frac{\text{d}H_w(z(t))}{\text{d}t} & =\sum_{i=1}^{n}{w_iz_i(t)\frac{\text{d}z_i(t)}{\text{d}t}} \\ & =\nabla H_w(z(t))^TG(z(t))\nabla H_w(z(t)) \\ & =\nabla H_w(z(t))^T\left((Z+X^*)AW^{-1}\right)\nabla H_w(z(t)) \end{aligned}

となり、

dHw(z(t))dt<0⇔∇Hw(z(t))T((Z+X∗)AW−1)∇Hw(z(t))<0⇔∇Hw(z(t))T((Z+X∗)C−1(CA+ATC)W−1)∇Hw(z(t))<0\begin{aligned} & \frac{\text{d}H_w(z(t))}{\text{d}t}<0 \\ \Leftrightarrow & \nabla H_w(z(t))^T\left((Z+X^*)AW^{-1}\right)\nabla H_w(z(t))<0 \\ \Leftrightarrow & \nabla H_w(z(t))^T\left((Z+X^*)C^{-1}(CA+A^TC)W^{-1}\right)\nabla H_w(z(t))<0 \end{aligned}

となる。 なお、最後の変形で、W,X∗,ZW,X^*,Z が対角行列であることを用いた。

以上より、(Z+X∗)C−1(CA+ATC)W−1(Z+X^*)C^{-1}(CA+A^TC)W^{-1} が CA+ATCCA+A^TC に関する 二次形式の形で記述出来る時、これはその負定値性より負になる。

これは、

W−1T=(Z+X∗)C−1⇔W=(Z+X∗)−1C\begin{aligned} & {W^{-1}}^T=(Z+X^*)C^{-1} \\ \Leftrightarrow & W=(Z+X^*)^{-1}C \end{aligned}

を意味し、Z→0Z \to 0 を考慮すると、W=X∗CW=X^*C を満たすような ww であれば、 題意を満たすことが分かる。

本页目录