Table of Contents

おことわり

勉強中のため随時更新中です

モチベーション

関数の最大値または最小値を機械的に求めるためにはどうしたらよいかを知る

シュワルツの不等式

$$ |\boldsymbol{x}^T\boldsymbol{y}| \leq \|\boldsymbol{x}\| \|\boldsymbol{y} \| $$

$\boldsymbol{x}$ と $\boldsymbol{y}$ が1次従属となる場合に等号が成立する．これは，内積 $\vec{a} \cdot \vec{b} = |\vec{a}| |\vec{b}| \cos \theta$ をイメージするとわかりやすい．

Rolleの定理 rolle theorem

$f(x)$ が $[a,b]$ で連続， $(a,b)$ で微分可能， $f(a)=f(b)$ を満たすとき， $f’(c) = 0$ となる $a < c < b$ が存在する．

rolle

平均値の定理 mean-value theorem

$f(x)$ が $[a,b]$ で連続， $(a,b)$ で微分可能なとき， $\frac{f(b)-f(a)}{b-a} = f’(c)$ となる $a < c < b$ が存在する．

mean_value

テイラーの定理による関数の近似

1階微分可能な関数の近似（ラグランジュの剰余項）

関数 $f:\mathbb{ R }^n \to \mathbb{R}$ が１階微分可能のとき， $\boldsymbol{x_0,\delta} \in \mathbb{R}$ に対して実数 $c \in (0,1)$ が存在する．

$$ f(\boldsymbol{x_0}+\boldsymbol{\delta}) = f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0}+c\boldsymbol{\delta})^T \boldsymbol{\delta} $$

taylor1

上式を整理すると，以下のように，左辺の変化量を満たす$f$の勾配が $(\boldsymbol{x}, \boldsymbol{x} + \boldsymbol{\delta})$ の範囲内に存在すると解釈できる．これは平均値の定理である． $\boldsymbol{\delta}$ が非常に小さければ，微分の定義そのものであるが， $\boldsymbol{\delta}$ は実数全体を取りうるので，微分の定義とは異なることに注意．

$$ \frac{f(\boldsymbol{x}+\boldsymbol{\delta}) - f(\boldsymbol{x})}{\boldsymbol{\delta}} = \nabla f(\boldsymbol{x}+c\boldsymbol{\delta})^T $$

2階微分可能な関数の近似（ラグランジュの剰余項）

$\boldsymbol{x_0}$ から $\boldsymbol{\delta}$ だけずれた点の値 $f(\boldsymbol{x_0}+\boldsymbol{\delta})$ を，ずれ $\boldsymbol{\delta}$ の2次式で近似してみたい．つまり， $f(\boldsymbol{x_0}+\boldsymbol{\delta}) = f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta} + R \boldsymbol{\delta}^2$ で近似してみる．

係数RはRolleの定理を用いることで求めることができる．Rolleの定理を適用しやすいように，以下のような$F(x)$を定義する．

$$ F(x) = - f(\boldsymbol{x_0}+\boldsymbol{x}) + f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{x} + R \boldsymbol{x}^2 $$

$F(0)=0$ は明らかである． $F(δ)=F(0)=0$ とすれば， $F’(h)=0$ となるhが $0 < h < δ$ の範囲で存在することになる（Rolleの定理）．

$$ \begin{array}{l} F'(x) = - \nabla f(\boldsymbol{x_0}+\boldsymbol{x}) + \nabla f(\boldsymbol{x_0})^T + 2R \boldsymbol{x} \\ F'(h) = - \nabla f(\boldsymbol{x_0}+\boldsymbol{h}) + \nabla f(\boldsymbol{x_0})^T + 2R \boldsymbol{h} = 0 , (0 < h < δ)\\ \therefore R = \frac{\nabla f(\boldsymbol{x_0}+\boldsymbol{h}) - \nabla f(\boldsymbol{x_0})^T}{2h} = \frac{1}{2} \nabla^2 f(\boldsymbol{x_0}+c\boldsymbol{\delta}) , (0 < c < 1) \end{array} $$

よって，

$$ f(\boldsymbol{x_0}+\boldsymbol{\delta}) = f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta} + \frac{1}{2} \boldsymbol{\delta}^T \nabla^2 f(\boldsymbol{x_0}+c\boldsymbol{\delta}) \boldsymbol{\delta} $$

図形的な意味を考察する．以下の左図のように $\boldsymbol{x_0}$ の勾配を用いることで， $f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta}$ を求めることができるが， $f(\boldsymbol{x_0}+\boldsymbol{\delta})$ までには，緑太線ぶんの誤差が生じている．緑太線の長さは，右図のように，元の $f(x)$ から $f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta}$ を引くことで求まる．これを $F(x) = f(x) - (f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta})$ とおく．

taylors

右図において， $x_0$ から緑太線の頂上を結ぶ直線の傾きは $\frac{f(x) - (f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta})}{\delta}$ であり，また，平均値の定理より， $\frac{f(x) - (f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta})}{\delta}　= \nabla F(\boldsymbol{x_0} + h \boldsymbol{\delta})$ となるような $0 < h < 1$ が存在する．

これより，緑太線の長さは， $\nabla F(\boldsymbol{x_0} + h \boldsymbol{\delta}) \boldsymbol{\delta}$ で求まるので， $F(x) = f(x) - (f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta})$ を $\boldsymbol{\delta}$ で微分して，

$$ \begin{eqnarray} \nabla F(\boldsymbol{\boldsymbol{x_0}} + h \boldsymbol{\delta}) \boldsymbol{\delta} &=& \{\nabla f(\boldsymbol{x_0} + h \boldsymbol{\delta}) - \nabla f(\boldsymbol{x_0})\} \boldsymbol{\delta} \\ &=& h \frac{\nabla f(\boldsymbol{x_0} + h \boldsymbol{\delta}) - \nabla f(\boldsymbol{x_0})}{h \boldsymbol{\delta}} \boldsymbol{\delta}^2 \\ &=& h \nabla^2 f(\boldsymbol{x_0}+c\boldsymbol{\delta}) \boldsymbol{\delta}^2 , (0 < h < 1, 0 < c < 1) \end{eqnarray} $$

よって，Taylorの定理に近いものが以下のように求まる．

$$ f(\boldsymbol{x_0}+\boldsymbol{\delta}) = f(\boldsymbol{x_0}) + \nabla f(\boldsymbol{x_0})^T \boldsymbol{\delta} + h \boldsymbol{\delta}^T \nabla^2 f(\boldsymbol{x_0}+c\boldsymbol{\delta}) \boldsymbol{\delta} \\ c,h \in (0,1) $$

関数の近似（ベルヌーイの剰余項）

微積分の基本式

$$ f(x) - f(a) = \int_a^x f'(t) dt $$

を用いることで， $x$ から $\delta$ だけずれた点 $f(x+\delta)$ の値を以下のように求めることができる．

$$ f(x + \delta) = f(x) + \int_x^{x+\delta} f'(t) dt $$

$t=x+c\delta$ とすると， $c \in (0,1)$ において，

$$ f(x + \delta) = f(x) + \int_0^{1} f'(x+c\delta) \delta dc $$

と整理することができる．

勾配 $\nabla f(\boldsymbol{x}+\boldsymbol{\delta})$ などについても同様に表現することができ，2階微分可能な関数$f$について，

$$ \nabla f(\boldsymbol{x} + \boldsymbol{\delta}) = \nabla f(\boldsymbol{x}) + \int_0^{1} \nabla^2 f(\boldsymbol{x}+c\boldsymbol{\delta}) \boldsymbol{\delta} dc $$

が成り立つ．

凸関数の定義

関数 $f:\mathbb{ R }^n \to \mathbb{R} \cup \lbrace \infty \rbrace$ に対して実行定義域 $dom(f)$ を

$$ dom(f) = \lbrace \boldsymbol{x} \in \mathbb{R}^n | f(\boldsymbol{x}) < \infty \rbrace $$

と定義し任意の $\boldsymbol{u,v} \in dom(f)$ と $\lambda \in [0,1]$ に対して，

$$ f((1-\lambda)\boldsymbol{u} + \lambda \boldsymbol{v}) \leq (1-\lambda)f(\boldsymbol{u}) + \lambda f(\boldsymbol{v}) $$

が成り立つとき， $f$ を凸関数という．

convex_function

また， $\boldsymbol{u} \neq \boldsymbol{v}$ と $0 < \lambda < 1$ に対して以下が成り立つとき， $f$ を狭義凸関数という．

$$ f((1-\lambda)\boldsymbol{u} + \lambda \boldsymbol{v}) \lt (1-\lambda)f(\boldsymbol{u}) + \lambda f(\boldsymbol{v}) $$

勾配を用いた凸関数の表現

$S$ を閉凸集合とし， $f:S \to \mathbb{R}$ を微分可能な関数とする．このとき， $f$ が凸関数であることと， $\boldsymbol{x} \neq \boldsymbol{y}$ である任意の $\boldsymbol{x,y} \in S$ に対して次式が成り立つことは同値である．

$$ f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{ \mathrm{ T } }(\boldsymbol{y} - \boldsymbol{x}) $$

リプシッツ連続

関数 $f$ が以下を満たすとき，リプシッツ連続であるという．一階微分の絶対値が有限であるという性質．

$$ |f(\boldsymbol{x}) - f(\boldsymbol{y}) | \leq L | \boldsymbol{x}- \boldsymbol{y} | $$

γ-平滑

勾配 $\nabla f$ がリプシッツ連続を満たすとき，関数 $f$ はγ-平滑であるという．二階微分の絶対値が有限であるという性質．

$$ |\nabla f(\boldsymbol{x}) - \nabla f(\boldsymbol{y}) | \leq \gamma | \boldsymbol{x}- \boldsymbol{y} | $$

関数値の上下界

γ-平滑な関数 $f:\mathbb{R}^n \to \mathbb{R}$ に対して，次の不等式が成り立つ．

$$ f(\boldsymbol{y}) \leq f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{ \mathrm{ T } }(\boldsymbol{y} - \boldsymbol{x}) + \frac{\gamma}{2} \| \boldsymbol{y} - \boldsymbol{x} \|^2 $$

$f$ が凸関数である場合，次の不等式が成り立つ．

$$ f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \nabla f(\boldsymbol{x})^{ \mathrm{ T } }(\boldsymbol{y} - \boldsymbol{x}) + \frac{1}{2\gamma} \| \nabla f(\boldsymbol{y}) - \nabla f(\boldsymbol{x}) \|^2 $$

エピグラフ

関数 $f:\mathbb{R}^n \to \mathbb{R} \cup \lbrace \infty \rbrace$ のエピグラフ $epi(f)\subset \mathbb{R}^{n+1}$ を以下のように定義する．エピグラフは，関数 $f$ の上側の領域を指すものである． $f(\boldsymbol{x})=\infty$ となる $\boldsymbol{x}$ に対しては， $(\boldsymbol{x},t) \notin epi(f), t \in \mathbb{R}$ となる．

$$ epi(f)=\lbrace (\boldsymbol{x} ,t) \in \mathbb{R}^n \times \mathbb{R} | f(x) \geq t \rbrace $$

$f$ が凸関数であることと $epi(f)$ が凸集合であることは同値である．凸関数 $f$ のエピグラフが空集合でないとき， $f$ を真凸関数という．

$epi(f)$ が閉集合のとき， $f$ を閉凸関数という．

共役関数

関数 $f$ が微分可能であるなら，すべての点における接線を求めることで，接平面を定めることができる． 凸関数の場合，各点における接線はそれぞれユニークであるため，接平面の情報から関数を復元することが可能である．

真凸関数$f$に対して，共役関数 $f^*$ を以下のように定義する． $sup$ は上限を表す．

$$ f^*(\boldsymbol{s})=sup \lbrace \boldsymbol{s}^T \boldsymbol{x} - f(\boldsymbol{x}) | \boldsymbol{x} \in \mathbb{R^n} \rbrace $$

図形的な意味を調べてみる． $\boldsymbol{s}^T \boldsymbol{x} - f(\boldsymbol{x})$ の上限を求めることは， $f(\boldsymbol{x}) - \boldsymbol{s}^T \boldsymbol{x}$ の下限を求めることと等価である． $f(\boldsymbol{x}) - \boldsymbol{s}^T \boldsymbol{x}$ が微分可能であるとすると， $ \nabla f(\boldsymbol{x}) - \boldsymbol{s}^T = 0$ を満たす必要がある．よって， $s$ は $f(x)$ の勾配である．下図は $x=x^*$ における接線から求まる $-f^*(s)$ を表したものである．

conjugate_function

左図の青線は $y=f(x)=\frac{1}{2} x^2$ であり，橙線は各 $x$ における接線を表し，切片をxでマークしたものである．また，右図は $y=f(x)$ の接線の勾配$s$と共役関数の負の値 $-f^*(s)$ の関係を表したものである．

$f(x)$ が閉真凸関数であるとき $f^*(s)$ も閉真凸関数となり， $f^*(s)$ から $f(x)$ を完全に復元できる．これを双対な関係という．

conjugate_function_animation

%matplotlib notebook

import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation

def update(i, x, f, f_grad, ax1, ax2):
    ax1.cla()
    ax1.plot(x, f)
    ax1.plot(x, f_grad[i] * x + (f[i] - f_grad[i] * x[i]))
    ax1.plot(0, f[i] - f_grad[i] * x[i], marker='x')
    ax1.set_xlim(-2.0, 2.0)
    ax1.set_ylim(-2.0, 2.0)
    
    ax2.cla()
    ax2.plot(f_grad[i], -(f[i] - f_grad[i] * x[i]), marker='x')
    ax2.set_xlim(-2.0, 2.0)
    ax2.set_ylim(-2.0, 2.0)
    
    ax1.set_title('y=f(x) and tangent')
    ax1.set_xlabel("x")
    ax1.set_ylabel("y")
    ax2.set_title('conjugate function -f*(x)')
    ax2.set_xlabel("s")
    ax2.set_ylabel("-f*(s)")

def draw():
    fig = plt.figure()
    fig, (ax1, ax2) = plt.subplots(1,2,figsize = (10, 5))

    x = np.linspace(-2.0, 2.0, 100)
    f = 1/2 * x ** 2
    f_grad = np.gradient(f, x)
    
    ani = animation.FuncAnimation(fig, update, fargs = (x, f, f_grad, ax1, ax2), interval = 50, frames = 100, repeat=True)
    ani.save("conjugate_func.gif", writer = 'imagemagick')

draw()

劣微分・劣勾配

凸関数を最小化するために勾配情報が欲しいが，凸関数はいつでも微分可能であるとは限らない．例えば， $y=|x|$ は凸関数だが， $x=0$ で微分可能でない．このような関数に対して勾配（劣勾配）を定義してみる．

真凸関数 $f:\mathbb{R}^n \to \mathbb{R} \cup \{\infty\}$ かつ $x \in dom(f)$ の元で， $\forall y \in \mathbb{R}^n$ が

$$ f(\boldsymbol{y}) \geq f(\boldsymbol{x}) + \boldsymbol{g}^{\mathrm{T}}(\boldsymbol{y}-\boldsymbol{x}) $$

を満たすとき， $\boldsymbol{g}$ を $\boldsymbol{x}$ における劣勾配という．劣勾配の集合 $\partial f(\boldsymbol{x})$ を劣微分という．

$f(x)=|x|$ の $x=0$ における劣微分は，以下より， $\partial f(0) = [-1,1]$ と求まる．

強凸関数

関数 $f:\mathbb{R}^n \to \mathbb{R} \cup \{\infty\}$ と $\mu \geq 0$ が以下を満たすとき， $f$ をμ-強凸関数という．

任意の $\lambda \in (0,1)$ と任意の $\boldsymbol{u,v} \in dom(f)$ の元で，

$$ \frac{\mu}{2} \lambda (1-\lambda) \| \boldsymbol{u} - \boldsymbol{v} \|^2 + f((1-\lambda) \boldsymbol{u} + \lambda \boldsymbol{v}) \leq (1-\lambda) f(\boldsymbol{u}) + \lambda f(\boldsymbol{v}) $$

が成り立つ．図形的な意味は以下であり，強い凸関数であることがわかる．

strongly_convex_function

$f(x)=x^2$ は強凸関数である．

局所最適化

直線探索法と反復法による最適化

$\phi(0)=f(x_0)$ に比べて， $\phi(\alpha)=f(x_0+\alpha \boldsymbol{d})$ が小さくなるような，ステップ幅 $\alpha$ （ $\alpha \geq 0$ ）を探すことを直線探索という． $\boldsymbol{d}$ を探索方向という．

より具体的には，初期解 $x_0$ を設定し， $x_k$ から探索方向 $\boldsymbol{d}_k$ の方向に進み，ステップ幅 $\alpha_k \geq 0$ を直線探索で決定し，以下のように $x_k$ を更新した上で関数値を評価するような，反復法によって最適解を探す．

$$ x_{k+1} = x_k + \alpha_k \boldsymbol{d}_k $$

探索方向の選び方

$$ \nabla f(x_k)^T \boldsymbol{d}_k < 0 $$

を満たすように探索方向 $\boldsymbol{d}_k$ を選ぶ．勾配 $\nabla f(x_k)$ は登る方向なので， $\boldsymbol{d}_k$ は降下方向を選べば良い．

探索方向が勾配に対して直交方向に近すぎない限り，勾配ノルム$\|\nabla f(x_k)\|$が0に収束するという，ゾーテンダイク条件に起因する．

直線探索法によるステップ幅の選び方

探索方向さえ適切に設定できれば，ステップ幅を小さく設定し，反復法によって最適解を求めることができる．ただし，ステップ幅が小さいと，$x_k$の更新回数が増えるため，最適解にたどり着くまでに時間がかかってしまう．

うまいステップ幅を選択できれば（直線探索できれば），1回の直線探索で関数値が十分に減少することができるため，効率的に最適解を求めることができる．

ここでは，直線探索の例を3つ挙げる

$$ \phi(\alpha) \leq \phi(0) + c_1 \alpha \phi^{'}(0) $$

armijo_condition

$$ \phi(\alpha) \leq \phi(0) + c_1 \alpha \phi^{'}(0) \\ \phi^{'}(\alpha) \geq c_2 \phi^{'}(0) $$

wolfe_condition

$$ \phi(0) + (1-c) \alpha \phi^{'}(0) \leq \phi(0) \leq \phi(0) + c \alpha \phi^{'}(0) $$

$\alpha$ は自力で探す必要があると述べたが，機械的には，以下のバックトラッキングによって探索することができる．

  1. 初期値 $\alpha > 0$ と，縮小率 $\rho \in (0,1)$ を任意に設定する．
  2. $\alpha$ が直線探索の条件を満たす場合は， $\alpha$ をステップ幅として採用する．
  3. $\alpha \gets \rho \alpha$ として2.を評価する．

最適化アルゴリズムの停止条件

反復法において， $k$ ステップ目の数値解を $x_k$ とすると， $\nabla f(x_k)=0$ と正定値性 $\nabla^2 f(x_k) \succ O$ を満たせば， $x_k$ が局所最適解であると言えるので，反復法を終了させることができる．

しかし，計算機を用いた反復法において， $\nabla f(x_k)=0$ になるとは限らないので，

$$ \| \nabla f(x_k) \| <\varepsilon $$

を満たせば良しとする．

…

関数 $f$ が2階微分可能であり，局所最適解を $x^*$ とする．このとき， $\nabla f(x^*)=0, \nabla^2 f(x^*) \succ O$ が成り立つ．

ここで，反復法の$k$ステップ目で得られた数値解 $x_k$ と真の局所最適解 $x^*$ との差を $\delta = x_k - x^*$ ，関数値の差を $f(x_k) - f(x^*) = h$ とおくと，テイラーの定理を整理して以下が得られる． $t \in (0,1)$ である．

$$ f(x_k) = f(x^*) + \nabla f(x^*) \delta + \frac{1}{2} \delta \nabla^2 f(x^*+t \delta) \delta \\ \therefore h = \frac{1}{2} \delta \nabla^2 f(x^*+t \delta) \delta $$

これより， $h$ と $\delta$ のオーダーに関して， $\| \delta \| = O( \sqrt{h} )$ となっている．

勾配のテイラーの定理より，

$$ \nabla f(x_k) = \nabla f(x^*) + \int_0^1 \nabla^2 f(x^* + t \delta) \delta dt $$

なので， $\| \nabla f(x_k) \|$ のオーダーは $\| \delta \|$ と同じ $O( \sqrt{h} )$ になる．

よって， $h \to 0$ を目的とした反復法を用いるのなら， $h$ に $\varepsilon$ ぶんの誤差があるとした $\| \nabla f(x_k) \| <\varepsilon$ よりも，

$$ \| \nabla f(x_k) \| < \sqrt{\varepsilon} $$

を反復法の停止条件とするほうが適当であると言える．この停止条件と，以下の $h,\delta$ についての条件を，反復法を停止させるための判断材料とすることがある．

$$ h < \varepsilon \\ \delta < \sqrt{\varepsilon} $$

また， $h$ は $\delta$ の影響を受けるため， $\delta$ のスケーリングや単位系の変更が $h$ に伝播する．よって，停止条件を以下のように定めることもある．

$$ \| \nabla f(x_k) \| < \sqrt{\varepsilon} |f(x_k)| $$

が，最適値が0に近いときは，この停止条件は厳しくなってしまうため，正則化のような塩梅で，

$$ \| \nabla f(x_k) \| < \sqrt{\varepsilon} (1+|f(x_k)|) $$

を用いることもある．

収束速度（収束率）

反復法における数値解 $x_0,x_1,…$ が迅速に最適解 $x^*$ に収束するようなアルゴリズムを考える必要がある．最適解近傍での収束の速さを収束速度または収束率という．最適解の近傍に到達するまでの速さとは無関係であることに注意する．

収束速度は，1次収束，超1次収束，2次収束の3つに分けることができ，1次収束よりも2次収束のほうが収束速度が速い．

$$ \displaystyle \limsup_{ k \to \infty } \frac{\| x_{k+1} - x^* \|}{\| x_k - x^* \|} < 1 $$

また，定数 $C>0,r \in (0,1)$ を用いて以下のように表現することも可能である．

$$ \| x_k - x^* \| \leq C r^k $$

$$ \displaystyle \limsup_{ k \to \infty } \frac{\| x_{k+1} - x^* \|}{\| x_k - x^* \|} = 0 $$

また， $r_k \to 0 (k \to \infty)$ となる（つまり，数値解が最適解に近づくにつれて $r_k$ が小さくなっていく）数列 $r_k$ を用いて以下のように表現することも可能である．

$$ \| x_k - x^* \| \leq C \prod_{j=1}^k r_j $$
$$ \displaystyle \limsup_{ k \to \infty } \frac{\| x_{k+1} - x^* \|}{\| x_k - x^* \|^2} < \infty $$

収束率が高く，分母が限りなく0に近づくため， $k \to \infty$ 時は $\infty$ 未満となる．

また，定数 $C>0,r \in (0,1)$ を用いて以下のように表現することも可能である．

$$ \| x_k - x^* \| \leq C r^{2^k} $$

1次収束よりも収束率が高く，収束速度も速いことがわかる．