読者です 読者をやめる 読者になる 読者になる

主に、強化学習

情報系の大学2年生が確率に関連したことを多めに書いてるブログ

共役勾配法

はじめに

春休みに入ってあまりにも数学(勉強)を触ってなく、高専時代の友達が「ブログ書いた」とか「受験で忙しい(輝いてる)」みたいな雰囲気を出してきてニート状態の私は焦燥感で死にそうになったので少し復習のつもりで、金谷さんの最適化数学を少し読み返してみました。友達が2変数の極値問題について昨日ブログかいてたので私は共役勾配法について少し書きたいと思います。

共役勾配法(CG法)

数学定義は難しいものだと思います。
ここらへんが反復法の説明でわかりやすいんじゃないでしょうか? (すみません、読んでないです. [共役勾配法 pdf]でググッてトップのやつを貼りました)

共役勾配法を理解するにあたって、勾配法とニュートン法を理解しておくと良いと思います. あと二変数関数の場合、ヘッセ行列が役に立ちます。書くのも簡単なのでヘッセ行列を使います。
CG法では二次近似が求まるので、勾配法も使うそうです。

f:id:reonreon3reon:20160404144059j:plain

ニュートン法の場合、ニュートン法逆行列を求める必要があるのですが共役勾配\mathbb{m^{k}}さえ求めれば、直線探索すればよいです。
\mathbb{t^{k}}を曲線の接線とし,
\mathbb{H^{k}}をヘシアンとし,
\mathbb{m^{k}}を共役勾配とし,
\nabla \mathbb{f}^{k}を接線\mathbb{t^{k}}と直行している勾配とし,
\alpha^{k}をある定数とすると,

 (\mathbb{t^{k}},\mathbb{H^{k}} \mathbb{m^{k}} ) = 0 \tag{1} \mathbb{m}^{k} = \nabla \mathbb{f}^{k} + \alpha^{k} \mathbb{t}^{k} \tag{2} (2)(1)に代入し, (\mathbb{t^{k}},\mathbb{H^{k}} \nabla \mathbb{f}^{k}) + \alpha^{k} (\mathbb{t^{k}},\mathbb{H^{k}}\mathbb{m^{k}})= 0 \tag{3} となります. (3)を変形し, \displaystyle \alpha^{k} = - \frac{ (\mathbb{t^{k}},\mathbb{H^{k}} \nabla \mathbb{f}^{k} )}{ (\mathbb{t^{k}},\mathbb{H^{k}}\mathbb{m^{k}})} \tag{4}

\mathbb{x}^{k+1}での探索直線方向は\mathbb{t}^{k+1}と同じであり, 要は\mathbb{m}^{k}と同義です.

\therefore 反復式は \displaystyle \mathbb{m}^{k} = \nabla \mathbb{f}^{k} + \alpha^{k} \mathbb{m}^{k-1}, \hspace{12pt}  \alpha^{k} = - \frac{ (\mathbb{\mathbb{m}^{k-1}},\mathbb{H^{k}} \nabla \mathbb{f}^{k} ) }{ (\mathbb{\mathbb{m}^{k-1}},\mathbb{H^{k}}\mathbb{m^{k}} ) }, \hspace{12pt}  \
 \mathbb{x}^{k+1} = \mathbb{x}^{k} + t^{k} \mathbb{m}^{k}

となります.

式変形してるときに、「あ、内積って線形性あったのか」って知ったので勉強不足も甚だしいです…
ちなみに、他にも正値性対称性があります.
気持ちがあれば、続きにプログラムを貼ります.