跳到主要内容

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

标签：

Author​

Kurosu9991

Description​

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

(1) 微分方程式

{ddtx(t)=2t+1(v(t)−x(t))ddtv(t)=−t+12∇f(x(t))(*)\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≥0t\geq 0 に対して考える。ただし初期条件 x(0),v(0)x(0),v(0) は与えられているものとする。 E(t)=(t+1)2(f(x(t))−f(x∗))+2∥v(t)−x∗∥22E(t)=(t+1)^2(f(x(t))-f(x^\ast))+2\|v(t)-x^\ast \|_2^2 とおく。 このとき、 ddtE(t)≤0\frac{\text{d}}{\text{d}t}E(t)\leq 0 を示せ。 また、 tt に依存しないある定数 CC が存在して、 f(x(t))−f(x∗)≤C/t2f(x(t))-f(x^\ast)\leq C/t^2 が t>0t>0 で成立することを示せ。

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

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

δ+∥v(k)−x∗∥22=2(v(k+1)−x∗)⊤(δ+v(k))−h∥δ+v(k)∥22\delta^+\|v^{(k)}-x^\ast \|_2^2=2(v^{(k+1)}-x^\ast)^\top(\delta^+v^{(k)})-h\|\delta^+v^{(k)}\|_2^2

を示し、さらに δ+E(k)≤0\delta^+E^{(k)}\leq 0 を示せ。 ただし、任意のスカラー列 {a(k)},{b(k)}\{a^{(k)}\},\{b^{(k)}\} に対し成立する関係式 δ+(a(k)b(k))=(a(k+1)b(k+1)−a(k)b(k))/h=(δ+a(k))b(k+1)+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) (**) に解が存在すると仮定する。このとき、 kk に依存しないある定数 C′C' が存在して、 f(x(k))−f(x∗)≤C′/k2f(x^{(k)})-f(x^\ast) \leq C'/k^2 が k=1,2,…k=1,2,\dots で成立することを示せ。

Kai​

(1)​

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

ddtE(t)=2(t+1)(f(x(t))−f(x∗))+(t+1)2∇f(x(t))⋅ddtx(t)+4(v(t)−x∗)⋅ddtv(t)=2(t+1)(f(x(t))−f(x∗))+2(t+1)∇f(x(t))⋅(v(t)−x(t))−2(t+1)∇f(x(t))⋅(v(t)−x∗)=−2(t+1)(f(x∗)−f(x(t))−∇f(x(t))⋅(x∗−x(t)))=−2(t+1)(12(x∗−x(t))⊤∂2f(x(t))∂x⊤∂x(x∗−x(t))+ο(ρ2))(ρ=∥x∗−x(t)∥2)\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)f(x) は凸関数であるため、 ∂2f(x(t))∂x⊤∂x\frac{\partial^2f(x(t))}{\partial x^\top\partial x} は正定値行列であり、 ddtE(t)<0\frac{\text{d}}{\text{d}t}E(t)<0 がわかる。

ゆえに、 t>0t>0 に対して

(t+1)2(f(x(t))−f(x∗))+2∥v(t)−x∗∥22=E(t)≤E(0)⇒(t+1)2(f(x(t))−f(x∗))≤E(0)⇒f(x(t))−f(x∗)≤E(0)t2\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)C=E(0) とすればよい。

(2)​

δ+∥v(k)−x∗∥22=δ+((v(k)−x∗)⊤(v(k)−x∗))=(δ+(v(k)−x∗)⊤)(v(k+1)−x∗)+(v(k)−x∗)⊤(δ+(v(k)−x∗))=(v(k+1)−x∗)⊤(δ+(v(k)−x∗))+(v(k)−x∗)⊤(δ+(v(k)−x∗))=(v(k)+v(k+1)−2x∗)⊤(δ+v(k))=2(v(k+1)−x∗)⊤(δ+v(k))−(v(k+1)−v(k))⊤(δ+v(k))=2(v(k+1)−x∗)⊤(δ+v(k))−h∥δ+v(k)∥22\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}

よって、

δ+E(k)=(δ+(hk+1)2)(f(x(k+1))−f(x∗))+(hk+1)2(δ+f(x(k)))+2δ+∥v(k)−x∗∥22=(2s+h)(f(x(k+1))−f(x∗))+s2(δ+f(x(k)))+4(v(k+1)−x∗)⊤(δ+v(k))−2h∥δ+v(k)∥22(s=hk+1)　=(2s+h)(f(x(k+1))−f(x∗))+s2(δ+f(x(k)))+4(s22s+h(δ+x(k))+x(k+1)−x∗)⊤(−2s+h4∇f(x(k+1)))−2h∥δ+v(k)∥22=(2s+h)(f(x(k+1))−f(x∗)−(∇f(x(k+1)))⋅(x(k+1)−x∗))+s2(δ+f(x(k))−(∇f(x(k+1)))⋅(δ+x(k)))−2h∥δ+v(k)∥22=−(2s+h)(f(x∗)−f(x(k+1))−(∇f(x(k+1)))⋅(x∗−x(k+1)))−s2h(f(x(k))−f(x(k+1))−(∇f(x(k+1)))⋅(x(k)−x(k+1)))−2h∥δ+v(k)∥22≤0\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)≤E(0)E^{(k)} \leq E^{(0)} を証明すれば良い（C′=E(0)/h2C'=E^{(0)}/h^2）。

本页目录