東京大学 情報理工学研究科 数理情報学 2024年度 第2問

Author

Kurosu9991

Description

\(\mathbb{R}^d\) 上で定義された十分滑らかな凸関数 \(f(x)\) の最小化問題を考える。ただし、最小解 \(x^{\ast}\) が存在することを仮定する。 \(f(x)\) の \(x=(x_1,\dots,x_d)^\top\in\mathbb{R}^d\) における勾配を \(\nabla f(x)=(\frac{\partial f}{\partial x_1}(x),\dots,\frac{\partial f}{\partial x_d}(x))^\top\) と表す。 また、 \(x\in\mathbb{R}^d\) のユークリッドノルムを \(\|x\|_2\) と表す。以下の設問に答えよ。

(1) 微分方程式

\[ \left\{\begin{aligned} \frac{\text{d}}{\text{d}t}x(t) & = \frac{2}{t+1}(v(t)-x(t)) \\ \frac{\text{d}}{\text{d}t}v(t) & = -\frac{t+1}{2}\nabla f(x(t)) \end{aligned}\right.\tag{*} \]

を \(t\geq 0\) に対して考える。ただし初期条件 \(x(0),v(0)\) は与えられているものとする。 \(E(t)=(t+1)^2(f(x(t))-f(x^\ast))+2\|v(t)-x^\ast \|_2^2\) とおく。 このとき、 \(\frac{\text{d}}{\text{d}t}E(t)\leq 0\) を示せ。 また、 \(t\) に依存しないある定数 \(C\) が存在して、 \(f(x(t))-f(x^\ast)\leq C/t^2\) が \(t>0\) で成立することを示せ。

(2) 微分方程式(*)の離散化として

\[ \left\{\begin{aligned} \delta^+x^{(k)} & = \frac{2hk+h+2}{(hk+1)^2}(v^{(k+1)}-x^{(k+1)}) \\ \delta^+v^{(k)} & = -\frac{2hk+h+2}{4}\nabla f(x^{(k+1)}) \end{aligned}\right.\tag{**} \]

を \(k=0,1,2,\dots\) に対して考える。 ただし、 \(\delta^+\) は任意のスカラーまたはベクトルの列 \(\{y^{(k)}\}\) に対して \(\delta^+y^{(k)}=(y^{(k+1)}-y^{(k)})/h \quad (h>0\) は定数 \()\) で定義される作用素とする。 \(x^{(0)}=x(0),v^{(0)}=v(0)\) とし、(**)に解が存在すると仮定する。 \(E^{(k)}=(hk+1)^2(f(x^{(k)})-f(x^\ast))+2\|v^{(k)}-x^\ast \|_2^2\) とおく。このとき、

\[ \delta^+\|v^{(k)}-x^\ast \|_2^2=2(v^{(k+1)}-x^\ast)^\top(\delta^+v^{(k)})-h\|\delta^+v^{(k)}\|_2^2 \]

を示し、さらに \(\delta^+E^{(k)}\leq 0\) を示せ。 ただし、任意のスカラー列 \(\{a^{(k)}\},\{b^{(k)}\}\) に対し成立する関係式 \(\delta^+(a^{(k)}b^{(k)})=(a^{(k+1)}b^{(k+1)}-a^{(k)}b^{(k)})/h=(\delta^+a^{(k)})b^{(k+1)}+a^{(k)}(\delta^+b^{(k)})\) を証明せず用いてよい。

(3) (**) に解が存在すると仮定する。このとき、 \(k\) に依存しないある定数 \(C'\) が存在して、 \(f(x^{(k)})-f(x^\ast) \leq C'/k^2\) が \(k=1,2,\dots\) で成立することを示せ。

Kai

(1)

\(E(t)\) を微分すると

\[ \begin{aligned} \frac{\text{d}}{\text{d}t}E(t) & = 2(t+1)(f(x(t))-f(x^\ast))+(t+1)^2\nabla f(x(t))\cdot\frac{\text{d}}{\text{d}t}x(t)+4(v(t)-x^\ast)\cdot\frac{\text{d}}{\text{d}t}v(t) \\ & = 2(t+1)(f(x(t))-f(x^\ast))+2(t+1)\nabla f(x(t))\cdot(v(t)-x(t))-2(t+1)\nabla f(x(t))\cdot(v(t)-x^\ast) \\ & = -2(t+1)\left(f(x^\ast)-f(x(t))-\nabla f(x(t))\cdot(x^\ast-x(t))\right) \\ & = -2(t+1)\left(\frac{1}{2}(x^\ast-x(t))^\top\frac{\partial^2f(x(t))}{\partial x^\top\partial x}(x^\ast-x(t))+\omicron(\rho^2)\right) \quad (\rho=\|x^\ast-x(t)\|_2) \end{aligned} \]

また、 \(f(x)\) は凸関数であるため、 \(\frac{\partial^2f(x(t))}{\partial x^\top\partial x}\) は正定値行列であり、 \(\frac{\text{d}}{\text{d}t}E(t)<0\) がわかる。

ゆえに、 \(t>0\) に対して

\[ \begin{aligned} & (t+1)^2(f(x(t))-f(x^\ast))+2\|v(t)-x^\ast \|_2^2 =E(t) \leq E(0) \\ \Rightarrow & (t+1)^2(f(x(t))-f(x^\ast)) \leq E(0) \\ \Rightarrow & f(x(t))-f(x^\ast) \leq \frac{E(0)}{t^2} \end{aligned} \]

となる。したがって、 \(C=E(0)\) とすればよい。

(2)

\[ \begin{aligned} \delta^+\|v^{(k)}-x^\ast\|_2^2 & = \delta^+\left((v^{(k)}-x^\ast)^\top(v^{(k)}-x^\ast)\right) \\ & = (\delta^+(v^{(k)}-x^\ast)^\top)(v^{(k+1)}-x^\ast)+(v^{(k)}-x^\ast)^\top(\delta^+(v^{(k)}-x^\ast)) \\ & = (v^{(k+1)}-x^\ast)^\top(\delta^+(v^{(k)}-x^\ast))+(v^{(k)}-x^\ast)^\top(\delta^+(v^{(k)}-x^\ast)) \\ & = (v^{(k)}+v^{(k+1)}-2x^\ast)^\top(\delta^+v^{(k)}) \\ & = 2(v^{(k+1)}-x^\ast)^\top(\delta^+v^{(k)})-(v^{(k+1)}-v^{(k)})^\top(\delta^+v^{(k)}) \\ & = 2(v^{(k+1)}-x^\ast)^\top(\delta^+v^{(k)})-h\|\delta^+v^{(k)}\|_2^2 \end{aligned} \]

よって、

\[ \begin{aligned} \delta^+E^{(k)} & = (\delta^+(hk+1)^2)(f(x^{(k+1)})-f(x^\ast))+(hk+1)^2(\delta^+f(x^{(k)}))+2\delta^+\|v^{(k)}-x^\ast\|_2^2 \\ & = (2s+h)(f(x^{(k+1)})-f(x^\ast))+s^2(\delta^+f(x^{(k)}))+4(v^{(k+1)}-x^\ast)^\top(\delta^+v^{(k)})-2h\|\delta^+v^{(k)}\|_2^2 \quad (s=hk+1)　\\ & = (2s+h)\left(f(x^{(k+1)})-f(x^\ast)\right)+s^2\left(\delta^+f(x^{(k)})\right)+4\left(\frac{s^2}{2s+h}(\delta^+x^{(k)})+x^{(k+1)}-x^\ast\right)^\top\left(-\frac{2s+h}{4}\nabla f(x^{(k+1)})\right)-2h\|\delta^+v^{(k)}\|_2^2 \\ & = (2s+h)\left(f(x^{(k+1)})-f(x^\ast)-(\nabla f(x^{(k+1)}))\cdot(x^{(k+1)}-x^\ast)\right) + s^2\left(\delta^+f(x^{(k)})-(\nabla f(x^{(k+1)}))\cdot(\delta^+x^{(k)})\right)-2h\|\delta^+v^{(k)}\|_2^2 \\ & = -(2s+h)\left(f(x^\ast)-f(x^{(k+1)})-(\nabla f(x^{(k+1)}))\cdot(x^\ast-x^{(k+1)})\right)-\frac{s^2}{h}\left(f(x^{(k)})-f(x^{(k+1)})-(\nabla f(x^{(k+1)}))\cdot(x^{(k)}-x^{(k+1)}) \right)-2h\|\delta^+v^{(k)}\|_2^2 \\ & \leq 0 \end{aligned} \]

となる。ただし、二行目から三行目の変形で、方程式 (**) を用いた。

(3)

(1) と同じように考えて、\(E^{(k)} \leq E^{(0)}\) を証明すれば良い（\(C'=E^{(0)}/h^2\)）。