東京大学 情報理工学研究科 数理情報学 2023年度 第2問
Author
hari64boli64
Description
\(n\) 次元実ベクトル空間 \(\mathbb{R}^n\) のベクトル \(u\) の第 \(i\) 成分を \(u_i\) と表す。
すべての \(i = 1, \ldots, n\) に対して \(u_i > 0\) である \(u \in \mathbb{R}^n\) を正値であるといい。正値ベクトル全体の集合を \(\mathcal{X}_n\) で表す。
また、ベクトル \(a \in \mathbb{R}^n\) に対し、\((i, i)\) 成分が \(a_i \ (i = 1, \ldots, n)\) であるような対角行列を \(\text{diag}(a_1, \ldots, a_n)\) で表す。
行列 \(M\) の転置を \(M^T\) で表す。
正則な \(n \times n\) 実行列 \(A = (a_{ij})\), ベクトル \(v \in \mathbb{R}^n\) に対し、\(x \in \mathcal{X}_n\) の関数 \(F_i(x)\) を
\[
F_i(x)=x_i \left(v_i+\sum_{j=1}^{n}a_{ij}x_j \right) \quad (i = 1, \ldots, n)
\]
と定める。ここで、\(F_i(x^*) = 0 \ (i = 1, \ldots, n)\) を満たす \(x^* \in \mathcal{X}_n\) が存在するとする。
そして、\(x(t) \in \mathcal{X}_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{*} \label{*}
\end{align}
\]
を考える。以下の設問に答えよ。
(1) ベクトル \(c \in \mathcal{X}_n\) に対し、\(x \in \mathcal{X}_n\) の関数 \(L(x)\) を
\[
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' \in \mathcal{X}_n\) を初期値とする方程式 (\(\ref{*}\)) の解 \(x(t)\) に対し、\(\dot{L}(x')\) を \(\dot{L}(x') = \left. \frac{\text{d}L(x(t))}{\text{d}t} \right|_{t=0}\) と定める。
また、行列 \(C\) を \(C = \text{diag}(c_1, \ldots, c_n)\) と定める。対称行列 \(CA + A^T C\) が負定値となるとき、かつそのときに限り、任意の \(x' \in \mathcal{X}_n \setminus \{ x^* \}\) に対して \(\dot{L}(x') < 0\) となることを示せ。
(2) ベクトル \(w \in \mathcal{X}_n\) に対し、\(z \in \mathbb{R}^n\) の関数 \(H_w(z)\) を
\[
H_w(z) = \frac{1}{2} \sum_{i=1}^n w_i z_i^2
\]
とし、\(H_w(z)\) の \(z\) における勾配を \(\nabla H_w(z) = \left( \frac{\partial H_w}{\partial z_1}(z), \ldots, \frac{\partial H_w}{\partial z_n}(z) \right)^T\) と表す。
方程式 (\(\ref{*}\)) の解 \(x(t)\) に対して、\(z(t) = x(t) - x^*\) が
\[
\frac{\text{d}z(t)}{\text{d}t} = G(z(t)) \nabla H_w(z(t))
\]
を満たすような行列関数 \(G(z)\) を求めよ。
ただし、関数 \(G(z)\) は、\(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 = \text{diag}(c_1, \ldots, c_n)\) に対し、対称行列 \(CA + A^T C\) が負定値となる \(c \in \mathcal{X}_n\) が存在するとする。
このとき、次のことが成り立つようなベクトル \(w \in \mathcal{X}_n\) を一つ求めよ。
「\(z(t) \in U \setminus \{0\}\) ならば \(\frac{\text{d}H_w(z(t))}{\text{d}t} < 0\) となる、\(0 \in \mathbb{R}^n\) の開近傍 \(U \subset \mathbb{R}^n\) が存在する。」
Kai
(1)
まず、\(F_i(x^*)=0\) という条件より、
また、\(x^* \in \mathcal{X}_n\) より、\(x^*_i \neq 0\) であることより、
\(v_i=-\sum_{j=1}^{n}{a_{ij}x^*_j}\) である。
条件を整理していくと、
\[
\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}
\]
となる。
よって、
\[
\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'\) から \(y\) への変換には注意が必要である。
全ての \(y\in \mathbb{R}^n\) に対して、
\(x^*-x'=y\) を満たす \(x'\in \mathcal{X}_n\setminus \{x^*\}\)
が存在するとは限らない。
ここでは長さに関する定数倍の変換が挟まっている。
(2)
まず、\(\nabla H_w(z)= (w_1z_1,\dots,w_nz_n)^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}
\]
となるので、
\[
\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) \to 0}\) において、
\(\frac{\text{d}H_w(z(t))}{\text{d}t}<0\) を満たすような \(w\) を、\(c\) を用いて表現せよ、
ということになる。
このことを念頭に置いて式変形していくと、
\[
\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}
\]
となり、
\[
\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^*,Z\) が対角行列であることを用いた。
以上より、\((Z+X^*)C^{-1}(CA+A^TC)W^{-1}\) が \(CA+A^TC\) に関する
二次形式の形で記述出来る時、これはその負定値性より負になる。
これは、
\[
\begin{aligned}
& {W^{-1}}^T=(Z+X^*)C^{-1} \\
\Leftrightarrow & W=(Z+X^*)^{-1}C
\end{aligned}
\]
を意味し、\(Z \to 0\) を考慮すると、\(W=X^*C\) を満たすような \(w\) であれば、
題意を満たすことが分かる。