直線探索を用いる反復法において、探索方向をとするのではなく、もっと良い探索方向を見つけようというのが本記事の趣旨です。
共役勾配法はニュートン法のように計算量の多いを計算する必要はありません。
共役勾配法
現在の近似解がであるとき、関数の2次近似は次のように書けます。
現在の位置から解に進むには、であるようなの方向に移動すればよいことが分かります。
を共役勾配と呼びます。
点での等高線の接線ベクトルをとすると、勾配とは直交するので、以下の式が成り立ちます。
はからある程度方向にずれています。
ある定数を用いると、次の式が成り立ちます。
イメージは下図です。
をに代入して、について解きます。
のを用いて、方向に直線探索をおこなえば、の極値に達することができます。
※この直線探索は勾配法などを用いて割と正確に求める必要があります。
直線探索の結果で極値に到達したとします。
その点で探索直線は関数の等高線に接しています。
よって、探索直線の方向がでの接線方向になっており、です。
イメージを下図に記しました。
以上より、次の共役勾配法の反復公式を得ます。
のは直線探索におけるステップ幅です。
偉人の名言
決して諦めないヤツを打ち負かすことだけはできない。
ベーブ・ルース
参考文献
これなら分かる最適化数学
動画
なし