まぁ探せばでてくるのだけど、まとめて書いておく。

準備

ちゃんとした定義は位相の本とか最適化の本とか参照してほしい。

無制約最適化問題

無制約最適化問題(unconstrained optimization)とは関数 $f: \mathbb{R}^n \to \mathbb{R}$ の最小解を求めるような問題:

$\min f(\boldsymbol{x}) \enspace \text{s.t.}~\boldsymbol{x} \in \mathbb{R}^n$

のことをいう。要は関数 $f$ の最小値を求めたいという問題。

近傍

点 $\boldsymbol{x} \in \mathbb{R}^n$ の近傍(neighborhood) $U \subseteq \mathbb{R}^n$ とは $\boldsymbol{x}$ を含むような適当なまとまった集合のことをいう。例えば点 $\boldsymbol{x} \in \mathbb{R}^3$ を中心とするような球とか点 $\boldsymbol{x} \in \mathbb{R}^2$ を中心とするような円などが近傍となる。

局所最小解

局所最小解(local minimum) $\boldsymbol{x}^*$ とは $\boldsymbol{x}^*$ の近傍 $U$ が存在して

$\forall \boldsymbol{x} \in U, f(\boldsymbol{x}^*) \leq f(\boldsymbol{x})$

を満たすことをいう。感覚としてはあるまとまった範囲内で関数を最小化するような解のことをいう。

大域最小解

局所最小解の定義にでてくる近傍を全体集合である $\mathbb{R}^n$ にしても成立するような解のことを大域最小解(global minumum)という。この解を探すのは広大な無限の空間から探してくるのでかなり難しいが、この解が満たしている性質がある。それは微分して $0$ となるところという性質。高校とかでやった二次関数の最小値を求めるやり方を思い出してもらえればいい。しかし、この性質では大域最小解のみを探すことはできない。なぜならば、これは局所最小解も満たすし、大域最小解でも局所最小解でもない鞍点と呼ばれる点もこの性質を満たすことになるからだ。しかも、二次関数のように単純な関数は現実世界ではほとんどでてこないし、そんな関数は全ての関数のごく小数にすぎない。しかし、現実には局所最小解をもとめられればいいということも多いと思う。今回紹介する最急勾配法でも大域最小解を求めるのではなく、微分したところが $0$ となるところを探すアルゴリズムとなっている。

原理

谷を降りていくところを想像しよう。谷底に辿り着くには谷を降りていけばいいのだけど、最も速く谷を降りるには最も勾配が急なところを降りていけばいい。この考えを関数の最小値を求めるのに利用したものが最急勾配法というのが直感的な考え方となる。しかし、一般には関数という谷における最急勾配からどれほど進めばよいのかを決めるのは難しい。最急勾配からどれだけ移動すればよいのかを決める方法はいくつか提案されていて、ここではそのうちいくつか触れるが、詳しくは各自で探してほしい。

アルゴリズム

最急勾配法のアルゴリズムはもの凄く単純。以下がアルゴリズムの全体像。

入力: 関数 $f$ とその微分 $\nabla f$ に初期点 $\boldsymbol{x}^0$

$k = 0$ とする

$\boldsymbol{x}^k$ が最適解に十分近ければ終了

最急降下方向 $\boldsymbol{d} = -\nabla f(\boldsymbol{x}^k)$ を求める

$\boldsymbol{x}^k$ と $\boldsymbol{d}$ を用いて直線探索問題 $\min f(\boldsymbol{x}^k + \alpha\boldsymbol{d}) \enspace \text{s.t.}~\alpha > 0$ を解いて移動量 $\alpha$ を求める

$\boldsymbol{x}^{k + 1} = \boldsymbol{x}^k + \alpha\boldsymbol{d}$ とする

$k = k + 1$ として 2. へ

たった6ステップで構成されている。短いし、必要な情報も解きたい関数 $f$ とその微分 $\nabla f$ だけでいい。初期点はランダムに生成してもかまわないが、選んだ初期点によっては鞍点が求められてしまう場合もある。

直線探索問題

しかし、アルゴリズムにおいて 4. で解いている直線探索問題を解くのは一般に難しい。ではどうするのかというと

2分割法
セカント法

の2つで近似的に解を得ることが多い。

2分割法

アルゴリズムは単純。

入力: 関数 $f$ 、初期値 $\alpha^0$ 、停止基準

$k = 0$ とする

停止基準が満たされたいたら終了

$\alpha^{k + 1} = \alpha^k / 2$ とする

$k = k + 1$ として1.へ

この停止基準としてはよく使われるものとして、

$f(\boldsymbol{x} + \alpha\boldsymbol{d}) \leq f(\boldsymbol{x}) + \xi\alpha\nabla f(\boldsymbol{x})^T\boldsymbol{d}$

となる $\alpha$ を採用するというArmijoの基準 が使われる。 $\xi$ は $0 \lt \xi \lt 1$ を満たしていればいい。他にはWolfeの基準があるが、ここでは扱わない。

セカント法

$g(\alpha) = f(\boldsymbol{x} + \alpha\boldsymbol{d})$ の微分が簡単に計算できる場合に使用されることがある。アイデアとしては目的関数である $g$ を二次近似:

$g(\alpha) \approx a(\alpha - b)^2 + c$

する。この関数の最適解は $\alpha = b$ で、もし等号が成立していれば、

$g'(\alpha) = 2a(\alpha - b)$

が成立する。 $\alpha^k, \alpha^{k - 1}$ を代入して $b$ を求めれば、

$b = \alpha^k - g'(\alpha^k)\frac{\alpha^k - \alpha^{k - 1}}{g'(\alpha^k) - g'(\alpha^{k - 1}}$

となるので、これを $\alpha^{k + 1}$ とするのである。具体的には

入力: 関数 $g$ とその微分 $g'$ 、および初期値 $\alpha^0, \alpha^1$ 、停止基準

$k = 1$ とする

停止基準が満たされていれば終了

$\alpha^{k + 1} = \alpha^k - g'(\alpha^k)\frac{\alpha^k - \alpha^{k - 1}}{g'(\alpha^k) - g'(\alpha^{k - 1}}$ とする。

$k = k + 1$ として 2. へ

停止基準は2分割法と同じようにArmijo基準などを使用すればいい。

補足

最急勾配法はアルゴリズムが非常に単純なのだけど、収束がわりと遅い。もし、関数 $f$ がさらにヘッセ行列までもとめられるならNewton法というアルゴリズムを利用する方が2次収束するのでより速く収束する。ただこのアルゴリズムの利点としては微分 $\nabla f$ までしか利用しないのと、アルゴリズムが非常に単純であるところにあるのだと思う。

バージョン管理された人

subversionで管理されてます

最急降下法について

準備