next up previous
Next: Newton法 Up: 制約なし最適化問題の解法 Previous: 制約なし最適化問題の解法

最急降下法

$ \vec{x}$$ n$次のベクトル, $ f$をスカラー関数とし,

$\displaystyle y=f(\vec{x})$ (1)

が最小値を取る$ \vec{x}$を計算機によって求める問題を考える。 ただし, $ f$は必要な回数だけ微分可能であると仮定しておく。 この問題を解くための最も簡単な方法が, 最急降下法あるいは勾配法と呼ばれる方法である。

$ f$の勾配ベクトル

$\displaystyle \nabla f= \begin{bmatrix}\displaystyle \frac{\partial f}{\partial x_1},\ldots,\frac{\partial f}{\partial x_n} \end{bmatrix}$ (2)

は,関数 $ f(\vec{x})$の「等高面」, すなわち

$\displaystyle f(\vec{x})=$一定 (3)

という$ n$次元空間内の曲面の法線ベクトルを与える。 このベクトルの向きは関数の値の増加する方向になる。

例 1   関数

$\displaystyle f(x_1,x_2)=x_1^2+x_2^2$ (4)

を考える。式(4)の等高線は円である。 一方,

$\displaystyle \frac{\partial f}{\partial x_1}=2 x_1,\quad \frac{\partial f}{\partial x_2}=2 x_2$ (5)

であるから, ある点における勾配ベクトルの向きは原点とその点を結ぶ方向になる。 これは円の法線ベクトルである(図1)。
図 1: 関数 $ f(x_1,x_2)=x_1^2+x_2^2$の等高線と勾配ベクトル
\includegraphics[width=.6\textwidth]{circle.eps}

例 2   関数

$\displaystyle f(x_1,x_2)=x_1+x_2$ (6)

を考える。式(6)の等高線は傾き$ -1$の直線である。 一方,

$\displaystyle \frac{\partial f}{\partial x_1}=1,\quad \frac{\partial f}{\partial x_2}=1$ (7)

であるから, ある点における勾配ベクトルはつねにベクトル$ [1,1]^T$に平行になる。 これは傾き$ -1$の直線と直交する(図2)。
図 2: 関数 $ f(x_1,x_2)=x_1+x_2$の等高線と勾配ベクトル
\includegraphics[width=.6\textwidth]{line.eps}

さて, 図1のように, 式(1)の関数が極大値を取らず, かつ 唯一の点において極小値を取る場合を考えよう。 極小値が唯一であることからこの値は最小値にもなるわけだが, この場合, 等高線の法線ベクトルの逆向きの方向は 関数の値が一番減る方向なのだから, 法線ベクトルの逆向きに解の候補を少しずつ 動かしてゆく以下のような繰り返し計算をおこなうと, 繰り返しの回数を十分多く取れば, この関数の最小値を (もしあれば)求めることができると期待できる。

G1)
初期値 $ \vec{x}_{0}$を適当に定め, $ k=0$とする。
G2)
$ \nabla f(\vec{x}_{k})=\vec{0}^T$なら終了。
G3)
探索ベクトル $ \vec{d}_{k}$

$\displaystyle \vec{d}_{k}=-(\nabla f(\vec{x}_{k}))^T$ (8)

によって定め, ステップ幅 $ \alpha_{k}$を適当に決め,

$\displaystyle \vec{x}_{k+1}=\vec{x}_{k}+ \alpha_{k}\vec{d}_{k}$ (9)

により $ \vec{x}_{k+1}$を定める。
G4)
$ k=k+1$とする。
このような方法を最急降下法と呼ぶ。

なお, ステップ幅 $ \alpha_{k}$は, アルゴリズムの安定性という 観点からは小さい正の定数であれば良いのだが, このようにすると収束が極めて遅くなり実用に耐えない。 だから, 最急降下法を用いて実用的なプログラムを作成するときには, 直線探索と呼ばれる方法を用いてステップ幅 $ \alpha_{k}$を決定することが多い。 ただし直線探索についてはこの実験では取り扱わない。

最急降下法には, 簡単である, 各ステップごとの計算量が少ない, 関数が唯一の極小点を持つときには大域的な収束性が保証されるという 利点がある一方で, 解の収束が極めて遅いという欠点がある。 また, 関数に複数の極小点があるときには, 求められるのはいくつかの極小点のうちのいずれかであって, それが 最小点であるという保証はない。


next up previous
Next: Newton法 Up: 制約なし最適化問題の解法 Previous: 制約なし最適化問題の解法
Shigeru HANBA
平成15年11月16日