勾配法

提供: Internet Web School

一次アルゴリズム

UNIQ4cf7b113cbe8652-MathJax-56-QINU を例にとる.UNIQ4cf7b113cbe8652-MathJax-57-QINUを列ベクトルと行列

UNIQ4cf7b113cbe8652-MathJax-58-QINU

を使って表現すると

UNIQ4cf7b113cbe8652-MathJax-59-QINU

から UNIQ4cf7b113cbe8652-MathJax-60-QINU と書ける．

ここで,UNIQ4cf7b113cbe8652-MathJax-61-QINUのUNIQ4cf7b113cbe8652-MathJax-62-QINUについての偏微分係数はそれぞれ,

UNIQ4cf7b113cbe8652-MathJax-63-QINU

である。これらを要素にもつ列ベクトルは, UNIQ4cf7b113cbe8652-MathJax-64-QINUのUNIQ4cf7b113cbe8652-MathJax-65-QINUについて の微分であり,

UNIQ4cf7b113cbe8652-MathJax-66-QINU

である。

また,UNIQ4cf7b113cbe8652-MathJax-67-QINUの２階微分は

UNIQ4cf7b113cbe8652-MathJax-68-QINU である。

UNIQ4cf7b113cbe8652-MathJax-69-QINU とすると

UNIQ4cf7b113cbe8652-MathJax-70-QINU

である.

これを一般化する.関数UNIQ4cf7b113cbe8652-MathJax-71-QINUが解析的な関数なら,

UNIQ4cf7b113cbe8652-MathJax-72-QINU

となる．UNIQ4cf7b113cbe8652-MathJax-73-QINUは３次以上の高位の項である。

勾配を使う計算法

UNIQ4cf7b113cbe8652-MathJax-74-QINUを最小化するため先ず,

初期点　　 UNIQ4cf7b113cbe8652-MathJax-75-QINU を与えて,UNIQ4cf7b113cbe8652-MathJax-76-QINUを求め,次に,

UNIQ4cf7b113cbe8652-MathJax-77-QINUでのUNIQ4cf7b113cbe8652-MathJax-78-QINUの微分,

UNIQ4cf7b113cbe8652-MathJax-79-QINU

を求め,これと微小な正数UNIQ4cf7b113cbe8652-MathJax-80-QINUを使って,

UNIQ4cf7b113cbe8652-MathJax-81-QINU

として,UNIQ4cf7b113cbe8652-MathJax-82-QINUを計算すると,

UNIQ4cf7b113cbe8652-MathJax-83-QINU

ここで,任意のベクトル UNIQ4cf7b113cbe8652-MathJax-84-QINU について

UNIQ4cf7b113cbe8652-MathJax-85-QINU であるからUNIQ4cf7b113cbe8652-MathJax-86-QINUである。

同様に,

UNIQ4cf7b113cbe8652-MathJax-87-QINU

UNIQ4cf7b113cbe8652-MathJax-88-QINU

である。

UNIQ4cf7b113cbe8652-MathJax-89-QINUが十分小さければ, UNIQ4cf7b113cbe8652-MathJax-90-QINU として, UNIQ4cf7b113cbe8652-MathJax-91-QINU となる．

UNIQ4cf7b113cbe8652-MathJax-92-QINU を新たな初期点としてこれを繰り返すことができる．このような方法を勾配法と呼ばれる．

特に,毎回の繰り返しで,

UNIQ4cf7b113cbe8652-MathJax-93-QINU

となるように,UNIQ4cf7b113cbe8652-MathJax-94-QINUを選ぶ繰り返し計算法を最急降下法と呼ぶ．

UNIQ4cf7b113cbe8652-MathJax-95-QINU

を繰り返しながら

UNIQ4cf7b113cbe8652-MathJax-96-QINU

を生成し, UNIQ4cf7b113cbe8652-MathJax-97-QINU

とする計算法は,一次アルゴリズムと呼ばれている．

2次アルゴリズム

UNIQ4cf7b113cbe8652-MathJax-98-QINU

を使って,高速なアルゴリズムを造る．

UNIQ4cf7b113cbe8652-MathJax-99-QINU

とおき,上の式の右辺を書き換える．

UNIQ4cf7b113cbe8652-MathJax-100-QINU

これはUNIQ4cf7b113cbe8652-MathJax-101-QINUについての２次式である。この式がUNIQ4cf7b113cbe8652-MathJax-102-QINUについて,極小になるための 条件は,極値条件(UNIQ4cf7b113cbe8652-MathJax-103-QINUについての微分がUNIQ4cf7b113cbe8652-MathJax-104-QINUベクトル)

UNIQ4cf7b113cbe8652-MathJax-105-QINU

である。これから,行列 UNIQ4cf7b113cbe8652-MathJax-106-QINU が正則(逆行列をもつ)とすれば,

UNIQ4cf7b113cbe8652-MathJax-107-QINU

が得られる．

UNIQ4cf7b113cbe8652-MathJax-108-QINU を繰り返すアルゴリズムはニュートン法と呼ばれる．