おことわり

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

モチベーション

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

シュワルツの不等式

とが1次従属となる場合に等号が成立する．これは，内積をイメージするとわかりやすい．

Rolleの定理 rolle theorem

がで連続，で微分可能，を満たすとき，となるが存在する．

rolle

平均値の定理 mean-value theorem

がで連続，で微分可能なとき，となるが存在する．

mean_value

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

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

関数が１階微分可能のとき，に対して実数が存在する．

taylor1

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

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

からだけずれた点の値を，ずれの2次式で近似してみたい．つまり，で近似してみる．

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

は明らかである．とすれば，となるhがの範囲で存在することになる（Rolleの定理）．

よって，

図形的な意味を考察する．以下の左図のようにの勾配を用いることで，を求めることができるが，までには，緑太線ぶんの誤差が生じている．緑太線の長さは，右図のように，元のからを引くことで求まる．これをとおく．

taylors

右図において，から緑太線の頂上を結ぶ直線の傾きはであり，また，平均値の定理より，となるようなが存在する．

これより，緑太線の長さは，で求まるので，をで微分して，

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

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

微積分の基本式

を用いることで，からだけずれた点の値を以下のように求めることができる．

とすると，において，

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

勾配などについても同様に表現することができ，2階微分可能な関数について，

が成り立つ．

凸関数の定義

関数に対して実行定義域を

と定義し任意のとに対して，

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

convex_function

また，とに対して以下が成り立つとき，を狭義凸関数という．

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

を閉凸集合とし，を微分可能な関数とする．このとき，が凸関数であることと，である任意のに対して次式が成り立つことは同値である．

リプシッツ連続

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

γ-平滑

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

関数値の上下界

γ-平滑な関数に対して，次の不等式が成り立つ．

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

エピグラフ

関数のエピグラフを以下のように定義する．エピグラフは，関数の上側の領域を指すものである．となるに対しては，となる．

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

が閉集合のとき，を閉凸関数という．

共役関数

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

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

 $𝕟$

図形的な意味を調べてみる．の上限を求めることは，の下限を求めることと等価である．が微分可能であるとすると，を満たす必要がある．よって，はの勾配である．下図はにおける接線から求まるを表したものである．

conjugate_function

左図の青線はであり，橙線は各における接線を表し，切片を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()

劣微分・劣勾配

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

真凸関数かつの元で，が

を満たすとき，をにおける劣勾配という．劣勾配の集合を劣微分という．

のにおける劣微分は，以下より，と求まる．

の場合，なので，
の場合，なので，
の場合，なので，

強凸関数

関数とが以下を満たすとき，をμ-強凸関数という．

任意のと任意のの元で，

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

strongly_convex_function

は強凸関数である．

局所最適化

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

に比べて，が小さくなるような，ステップ幅（）を探すことを直線探索という．を探索方向という．

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

探索方向の選び方

を満たすように探索方向を選ぶ．勾配は登る方向なので，は降下方向を選べば良い．

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

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

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

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

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

アルミホ条件
- を設定し，以下を満たすを自力で探す．下図の例では，青矢印の範囲内が適切なとなる．
- アルミホ条件では小さなが許容されるので，大きめのを選択しなければ，直線探索の回数が多くなってしまう．

armijo_condition

ウルフ条件
- を設定し，以下を満たすを自力で探す．下図の例では，青矢印の範囲内が適切なとなる．
- アルミホ条件の弱点（極めて小さなを許容してしまう弱点）を回避することが可能．
- を用いると，強いウルフ条件になる．

wolfe_condition

ゴールドシュタイン条件
- を設定し，以下を満たすを自力で探す．
- アルミホ条件の弱点（極めて小さなを許容してしまう弱点）を回避することが可能．

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

初期値と，縮小率を任意に設定する．
が直線探索の条件を満たす場合は，をステップ幅として採用する．
として2.を評価する．

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

反復法において，ステップ目の数値解をとすると，と正定値性を満たせば，が局所最適解であると言えるので，反復法を終了させることができる．

しかし，計算機を用いた反復法において，になるとは限らないので，

を満たせば良しとする．

…

関数が2階微分可能であり，局所最適解をとする．このとき，が成り立つ．

ここで，反復法のステップ目で得られた数値解と真の局所最適解との差を，関数値の差をとおくと，テイラーの定理を整理して以下が得られる．である．

これより，とのオーダーに関して，となっている．

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

なので，のオーダーはと同じになる．

よって，を目的とした反復法を用いるのなら，にぶんの誤差があるとしたよりも，

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

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

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

を用いることもある．

収束速度（収束率）

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

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

1次収束する場合は以下を満たす．

また，定数を用いて以下のように表現することも可能である．

超1次収束する場合は以下を満たす．

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

2次収束する場合は以下を満たす．

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