アルゴリズム
1. 初期値x ( 0 ) ∈ R n x _ {(0)} \in \mathbb{R} ^ n x ( 0 ) ∈ R n を定める(定め方は任意である)
2. 探索方向m ( k ) m _ {(k)} m ( k ) を点x ( k ) x _ {(k)} x ( k ) における勾配によってm ( k ) = − grad f ( x ( k ) ) m _ {(k)} = - \operatorname{grad} f (x _ {(k)}) m ( k ) = − grad f ( x ( k ) ) と定める
3. ステップサイズt ( k ) > 0 t _ {(k)} > 0 t ( k ) > 0 を定める(定め方は任意である)
4. 次の更新式を用いて現在の点を更新する
x ( k + 1 ) = x ( k ) + t ( k ) m ( k ) = x ( k ) − t ( k ) grad f ( x ( k ) ) \begin{aligned}
x _ {(k+1)} &= x _ {(k)} + t _ {(k)} m _ {(k)} \\
&= x _ {(k)} - t _ {(k)} \operatorname{grad} f ( x _ {(k)} )
\end{aligned} x ( k + 1 ) = x ( k ) + t ( k ) m ( k ) = x ( k ) − t ( k ) grad f ( x ( k ) ) 5. 収束していなければ手順 2 へ戻る
収束したかどうかの判定には小さい正の定数ε \varepsilon ε などを用いて
∥ grad f ( x ) ∥ < ε \| \operatorname{grad} f(x) \| < \varepsilon ∥ grad f ( x ) ∥ < ε とする。大抵は1 0 − 16 < ε < 1 0 − 8 10 ^ {-16} < \varepsilon < 10 ^ {-8} 1 0 − 16 < ε < 1 0 − 8 くらいの範囲に設定する。
原理
最急降下法 (steepest descent)はもっとも単純で基本的な直線探索法だが、目的関数の勾配(gradient)さえ計算できれば適用できるので汎用性が高い。
目的関数f : R n → R f \colon \mathbb{R} ^ n \to \mathbb{R} f : R n → R が定義域の全体で微分可能ならばその極値を与える点x x x では
grad f ( x ) = 0 (4.1.1) \operatorname{grad} f (x) = 0 \tag{4.1.1} grad f ( x ) = 0 ( 4.1.1 ) が成り立つ。最小値は極値であるから、最適化問題
arg min x ∈ R n f ( x ) \underset{x \in \mathbb{R} ^ n}{\operatorname{arg} \operatorname{min}} \,\, f(x) x ∈ R n arg min f ( x ) を解くには目的関数を単調減少させながら (4.1.1) 式を満たすまで更新を繰り返せば少なくとも最適解の候補には到達する(一般にf ( x ) f(x) f ( x ) が性質のよい関数でない限り真の最適解に到達するのはどんなアルゴリズムでも非常に難しいため極値で妥協する)。
現在の点x ( k ) ∈ R n x _ {(k)} \in \mathbb{R} ^ n x ( k ) ∈ R n は既知であるとして、更新方向m ( k ) ∈ R n m _ {(k)} \in \mathbb{R} ^ n m ( k ) ∈ R n として妥当な方向を探す。ステップサイズはあとから定めるからm ( k ) m _ {(k)} m ( k ) は方向の情報だけが重要であり、∥ m ( k ) ∥ = 1 \| m _ {(k)} \| = 1 ∥ m ( k ) ∥ = 1 としてよい。目的関数f : R n → R f \colon \mathbb{R} ^ n \to \mathbb{R} f : R n → R の点x ( k ) x _ {(k)} x ( k ) の周りで Taylor の定理(1次近似)を適用する、すなわち (2.6) 式でΔ x = t m ( k ) ( t > 0 ) \Delta x = t m _ {(k)} \,\,(t > 0) Δ x = t m ( k ) ( t > 0 ) とおくと、
f ( x ( k ) + t m ( k ) ) = f ( x ( k ) ) + < grad f ( x ( k ) ) , t m ( k ) > + o ( ∥ t m ( k ) ∥ ) = f ( x ( k ) ) + t < grad f ( x ( k ) ) , m ( k ) > + o ( t ∥ m ( k ) ∥ ) = f ( x ( k ) ) + t < grad f ( x ( k ) ) , m ( k ) > + o ( t ) (4.1.2) \begin{aligned}
f(x _ {(k)} + t m _ {(k)}) &= f(x _ {(k)}) + \left< \operatorname{grad} f(x _ {(k)}), t m _ {(k)} \right> + o \left( \| t m _ {(k)} \| \right) \\
&= f(x _ {(k)}) + t \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + o \left( t \| m _ {(k)} \| \right) \\
&= f(x _ {(k)}) + t \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + o \left( t \right)
\end{aligned} \tag{4.1.2} f ( x ( k ) + t m ( k ) ) = f ( x ( k ) ) + ⟨ grad f ( x ( k ) ) , t m ( k ) ⟩ + o ( ∥ t m ( k ) ∥ ) = f ( x ( k ) ) + t ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + o ( t ∥ m ( k ) ∥ ) = f ( x ( k ) ) + t ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + o ( t ) ( 4.1.2 ) である。したがって、更新後の目的関数の値と更新前のそれとの差Δ f \Delta f Δ f は
Δ f = f ( x ( k ) + t m ( k ) ) − f ( x ( k ) ) = t < grad f ( x ( k ) ) , m ( k ) > + o ( t ) = t ( < grad f ( x ( k ) ) , m ( k ) > + o ( t ) t ) (4.1.3) \begin{aligned}
\Delta f &= f(x _ {(k)} + t m _ {(k)}) - f(x _ {(k)}) \\
&= t \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + o \left( t \right) \\
&= t \left( \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + \frac{o \left( t \right)}{t} \right)
\end{aligned} \tag{4.1.3} Δ f = f ( x ( k ) + t m ( k ) ) − f ( x ( k ) ) = t ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + o ( t ) = t ( ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + t o ( t ) ) ( 4.1.3 ) である。ここでo ( t ) o(t) o ( t ) の素性は (4.1.2) 式から (2.5) 式まで辿れるから、
o ( t ) = o ( ∥ t m ( k ) ∥ ) = h 1 ( t m ( k ) ) ∥ t m ( k ) ∥ = t ⋅ h 1 ( t m ( k ) ) o(t) = o (\| t m _ {(k)} \|) = h _ 1 (t m _ {(k)}) \| t m _ {(k)} \| = t \cdot h _ 1 (t m _ {(k)}) o ( t ) = o ( ∥ t m ( k ) ∥ ) = h 1 ( t m ( k ) ) ∥ t m ( k ) ∥ = t ⋅ h 1 ( t m ( k ) ) であるとわかる。したがって Taylor の定理から
lim t → 0 o ( t ) t = lim t → 0 o ( t ) t = lim t → 0 t ⋅ h 1 ( t m ( k ) ) t = lim t → 0 h 1 ( t m ( k ) ) = 0 \begin{aligned}
\lim _ {t \to 0} \frac{o(t)}{t} &= \lim _ {t \to 0} \frac{o(t)}{t} \\
&= \lim _ {t \to 0} \frac{t \cdot h _ 1(t m _ {(k)})}{t} \\
&= \lim _ {t \to 0} h _ 1 (t m _ {(k)}) \\
&= 0
\end{aligned} t → 0 lim t o ( t ) = t → 0 lim t o ( t ) = t → 0 lim t t ⋅ h 1 ( t m ( k ) ) = t → 0 lim h 1 ( t m ( k ) ) = 0 が求まる。点x ( k ) x _ {(k)} x ( k ) が極値や停留点でなければgrad f ( x ( k ) ) ≠ 0 \operatorname{grad} f(x _ {(k)}) \neq 0 grad f ( x ( k ) ) = 0 であるから、m ( k ) m _ {(k)} m ( k ) をgrad f ( x ( k ) ) \operatorname{grad} f(x _ {(k)}) grad f ( x ( k ) ) と直交しないように取れば∣ < grad f ( x ( k ) ) , m ( k ) > ∣ > 0 \left| \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> \right| > 0 ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ > 0 であるから、t t t を 0 に近づける途中で、あるt t t が存在して
∣ < grad f ( x ( k ) ) , m ( k ) > ∣ > ∣ o ( t ) t ∣ (4.1.4) \left| \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> \right| > \left| \frac{o \left( t \right)}{t} \right| \tag{4.1.4} ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ > t o ( t ) ( 4.1.4 ) となる。ゆえにt t t が十分小さいとき (4.1.3) の符号は
sign ( Δ f ) = sign ( < grad f ( x ( k ) ) , t m ( k ) > ) \operatorname{sign}(\Delta f) = \operatorname{sign} \left( \left< \operatorname{grad} f(x _ {(k)}), tm _ {(k)} \right> \right) sign ( Δ f ) = sign ( ⟨ grad f ( x ( k ) ) , t m ( k ) ⟩ ) によって定まることがわかるので、t > 0 t > 0 t > 0 であることを思い出せば
< grad f ( x ( k ) ) , m ( k ) > < 0 \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> < 0 ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ < 0 となるようにm ( k ) m _ {(k)} m ( k ) を選べば目的関数が単調減少するようにt t t を選ぶことが可能になる。
以上の議論はこれから紹介するうちでニュートン法を除くすべての直線探索法に共通した議論であり、直線探索法のバリエーションはこのm ( k ) m _ {(k)} m ( k ) の選び方を変えたものに過ぎない。
探索方向m ( k ) m _ {(k)} m ( k ) はgrad f ( x ( k ) ) \operatorname{grad} f(x _ {(k)}) grad f ( x ( k ) ) を用いた式で定義されることが多いので、これらの手法を総称して勾配法 (gradient descent)ともいう。
最急降下法
最急降下法はm ( k ) = − grad f ( x ( k ) ) m _ {(k)} = - \operatorname{grad} f(x _ {(k)}) m ( k ) = − grad f ( x ( k ) ) とする手法で、
< grad f ( x ( k ) ) , m ( k ) > = < grad f ( x ( k ) ) , − grad f ( x ( k ) ) > = − < grad f ( x ( k ) ) , grad f ( x ( k ) ) > = − ∥ grad f ( x ( k ) ) ∥ 2 < 0 \begin{aligned}
\left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> &= \left< \operatorname{grad} f(x _ {(k)}), - \operatorname{grad} f(x _ {(k)})\right> \\
&= - \left< \operatorname{grad} f(x _ {(k)}), \operatorname{grad} f(x _ {(k)})\right> \\
&= - \| \operatorname{grad} f(x _ {(k)}) \| ^ 2 < 0
\end{aligned} ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ = ⟨ grad f ( x ( k ) ) , − grad f ( x ( k ) ) ⟩ = − ⟨ grad f ( x ( k ) ) , grad f ( x ( k ) ) ⟩ = − ∥ grad f ( x ( k ) ) ∥ 2 < 0 より、点x ( k ) x _ {(k)} x ( k ) の近傍で十分小さいt t t を選べば目的関数は単調減少する。
「最急降下(steepest descent)」の名は∣ < grad f ( x ( k ) ) , m ( k ) > ∣ \left| \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> \right| ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ がもっとも大きくなる探索方向m ( k ) m _ {(k)} m ( k ) を用いていることに由来する。実際に、Cauchy-Schwarz の不等式と∥ m ( k ) ∥ = 1 \| m _ {(k)} \| = 1 ∥ m ( k ) ∥ = 1 より
∣ < grad f ( x ( k ) ) , m ( k ) > ∣ ≤ ∥ grad f ( x ( k ) ) ∥ ⋅ ∥ m ( k ) ∥ = ∥ grad f ( x ( k ) ) ∥ \left| \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> \right| \leq \| \operatorname{grad} f(x _ {(k)}) \| \cdot \| m _ {(k)} \| = \| \operatorname{grad} f(x _ {(k)}) \| ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ ≤ ∥ grad f ( x ( k ) ) ∥ ⋅ ∥ m ( k ) ∥ = ∥ grad f ( x ( k ) ) ∥ となる。不等式の等号成立は
m ( k ) = ± grad f ( x ( k ) ) ∥ grad f ( x ( k ) ) ∥ m _ {(k)} = \pm \frac{\operatorname{grad} f(x _ {(k)})}{ \| \operatorname{grad} f(x _ {(k)}) \| } m ( k ) = ± ∥ grad f ( x ( k ) ) ∥ grad f ( x ( k ) ) のときであり、ただそのときに限る。したがってt → 0 t \to 0 t → 0 の極限、すなわち点x ( k ) x _ {(k)} x ( k ) の周りのごく狭い範囲ではm ( k ) = − grad f ( x ( k ) ) m _ {(k)} = - \operatorname{grad} f(x _ {(k)}) m ( k ) = − grad f ( x ( k ) ) が目的関数をもっとも減少させる方向である。
ニュートン法
ニュートン法は関数の2次近似から導出されるので、誤解を防ぐためここでは説明しない。
4.3. ニュートン法 共役勾配法
共役とは簡単に言えば「直交している」という意味である。つまり勾配に直交するベクトルr ( k ) r _ {(k)} r ( k ) をm ( k ) m _ {(k)} m ( k ) に加えてm ( k ) + r ( k ) m _ {(k)} + r _ {(k)} m ( k ) + r ( k ) を探索方向とするのが共役勾配法である。
(4.1.4) 式の時点でm ( k ) m _ {(k)} m ( k ) はgrad f ( x ( k ) ) \operatorname{grad}f(x _ {(k)}) grad f ( x ( k ) ) と直交しないものを選んだが、そうして選んだm ( k ) m _ {(k)} m ( k ) にgrad f ( x ( k ) ) \operatorname{grad} f (x _ {(k)}) grad f ( x ( k ) ) と直交するベクトルr ( k ) r _ {(k)} r ( k ) を加えても
< grad f ( x ( k ) ) , m ( k ) + r ( k ) > = < grad f ( x ( k ) ) , m ( k ) > + < grad f ( x ( k ) ) , r ( k ) > = < grad f ( x ( k ) ) , m ( k ) > + 0 = < grad f ( x ( k ) ) , m ( k ) > \begin{aligned}
\left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} + r _ {(k)} \right> &= \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + \left< \operatorname{grad} f(x _ {(k)}), r _ {(k)} \right> \\
&= \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> + 0 \\
&= \left< \operatorname{grad} f(x _ {(k)}), m _ {(k)}\right>
\end{aligned} ⟨ grad f ( x ( k ) ) , m ( k ) + r ( k ) ⟩ = ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + ⟨ grad f ( x ( k ) ) , r ( k ) ⟩ = ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ + 0 = ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ となるので目的関数が単調減少するようなt t t が選べるという議論は変わらない。
4.4. 共役勾配法 準ニュートン法
準ニュートン法はB ( k ) B _ {(k)} B ( k ) を正定値行列としてm ( k ) m _ {(k)} m ( k ) に
m ( k ) = − B ( k ) grad f ( x ( k ) ) m _ {(k)} = - B _ {(k)} \operatorname{grad} f(x _ {(k)}) m ( k ) = − B ( k ) grad f ( x ( k ) ) を選ぶ方法である。このときやはり
< grad f ( x ( k ) ) , m ( k ) > = < grad f ( x ( k ) ) , − B ( k ) grad f ( x ( k ) ) > = − < grad f ( x ( k ) ) , B ( k ) grad f ( x ( k ) ) > < 0 \begin{aligned}
\left< \operatorname{grad} f(x _ {(k)}), m _ {(k)} \right> &= \left< \operatorname{grad} f(x _ {(k)}), - B _ {(k)}\operatorname{grad} f(x _ {(k)})\right> \\
&= - \left< \operatorname{grad} f(x _ {(k)}), B _ {(k)} \operatorname{grad} f(x _ {(k)})\right> < 0
\end{aligned} ⟨ grad f ( x ( k ) ) , m ( k ) ⟩ = ⟨ grad f ( x ( k ) ) , − B ( k ) grad f ( x ( k ) ) ⟩ = − ⟨ grad f ( x ( k ) ) , B ( k ) grad f ( x ( k ) ) ⟩ < 0 が成り立つのでm ( k ) m _ {(k)} m ( k ) は依然として降下方向である。
4.5. 準ニュートン法 収束性
最急降下法は1次収束のアルゴリズムである。
特徴
最急降下法は1次収束のアルゴリズムで、本書で紹介する中ではもっとも収束性が悪い部類に入るが、実装がもっとも簡単であり、イテレーションごとの計算量も勾配を計算するだけなので比較的小さい。
勾配法でうまくいくかどうかを検証するためにまずとりあえず最急降下法を実装してみるのは手段としてはありである。収束性は悪いが回しておけば徐々に最適解には近づいていくので、一晩回しておいて最適解の候補を得ておけば他の手法を試すときにも安心感がある。
参考文献