共役勾配法 - 大人になってからの再学習

まず最急降下法について。

最適化問題の局所的探索法に最急降下法がある。
この最急降下法の考え方は次のような感じ。

「最も勾配が急な方向に進みましょう。その方向で一番低い場所に到達したら、進む向きを変えましょう。新しい方向は、その地点で最も勾配が急な方向です。これを繰り返すことで、やがては最も低い点に到着するでしょう。」

考え方は単純でわかりやすい。
その性質上、向きを変えるときには、それまでの進行方向と新しい進行方向が直交し、直角にジグザグと進むことになる。

下図のような感じ。

この楕円が扁平な場合、最急降下法だとジグザグの回数が増えて、なかなか最適解に収束しないという問題がある。
下図のように最適解に向かって進むものの、次第にステップサイズが小さくなって、なかなか収束しない。

で、もっといい方法があるんじゃないの？ということで共役勾配法が考え出された。

これは「最も勾配が急な方向」ではなくて、「共役勾配方向」に進みましょう。という考え方。共役勾配方向に進むと、とっても早く収束するので便利！

では、共役勾配の方向ってなに？

数式での定義はいくらでも教科書に載っているけど、イメージを理解するのが難しい。
正確ではないことは承知の上で無理やり書くと次のように言える。

楕円を円に直してあげて、円の中心に進む方向を、もう一度楕円に戻した方向

下の図のような感じ。

なんとなくでもイメージがつかめたら、数式での説明をもう一回追いかけてみるといい。

■参考
連立1次方程式II - 反復法 - 桂田祐史
http://www.math.meiji.ac.jp/~mk/labo/text/linear-eq-2.pdf