共役勾配法

はじめに

この記事は「これなら分かる最適化数学 -基礎原理から計算手法まで-」(金谷健一著,共立出版)の3.3「共役勾配法」を基に書いている。また、自主ゼミで担当した回に向けての内容になっているため、一部「前回の内容で説明済」との理由から説明を省略した箇所があるが、そこについては追って編集をする(かもしれない)。

イメージ

１変数勾配法のアルゴリズムは、「傾きが正の間は進み、傾きが負になったら戻る」という山登りをして、山頂を探すようなものであった。

これがn変数の場合は、山登りを繰り返して、関数の極値へ向かっていった。

この図を見て、あることを思う。

「スタート地点からゴールの極値まで一直線に探索する方法があれば、もっと効率いいんじゃない？」

これこそが共役勾配法のモチベーションである。
関数$f$の地点$x^{(K)}$における接ベクトル$t^{(K)}$と勾配$\nabla f^{(K)}$、現時点$x^{(K)}$と最適解$x$を結ぶ直線方向のベクトル$m^{(K)}$を考え、図で表すと次のようになる。

この、$m^{(K)}$を共役勾配といい、$^\exists\alpha:$const.に対して次の式で表現できる。

\boldsymbol{m}^{(K)}=\nabla f^{(K)}+\alpha^{(K)}\boldsymbol{t}^{(K)} \qquad (3.66)

これは、共役勾配が「勾配」と「接ベクトルを何倍かしたもの」の合成ベクトルである、と捉えれば理解できそうである。さらに、接ベクトルと勾配は垂直であることがわかっているので

(\boldsymbol{t}^{(K)},\nabla f^{(K)})=0

あとは、$\alpha^{(K)}$が何であるかさえ分かれば、現在地から最適解へと向かうベクトルを得ることができるのだが、そこには一手間が必要である。次の節で説明しよう。

共役勾配

関数$ f\in C^{\infty}$について$x=(x^{(K)},y^{(K)})$周りでTaylor展開すると

f(x,y) = \bar{f}+\dfrac{\partial \bar{f}}{\partial x}(x-x^{K})+\dfrac{\partial \bar{f}}{\partial y}(y-y^{K})+\dfrac{1}{2}\left(\dfrac{\partial^2 \bar{f}}{\partial x^2}(x-x^{(K)})^2+2\dfrac{\partial^2 \bar{f}}{\partial x\partial y}(x-x^{(K)})(y-y^{(K)})+\dfrac{\partial^2 \bar{f}}{\partial y^2}(y-y^{(K)})^2\right)+\cdots

である。但し、$\bar{f}$は関数$f$の$(x^{(K)},y^{(K)})$での値である。ここから、関数$f$の２次近似$g$は$\boldsymbol{x}=\left(\begin{array}{c} x, y\end{array}\right)^T$、勾配$\nabla f$、ヘッセ行列$\boldsymbol{H}$を用いて

g(\boldsymbol{x})=\bar{f}+(\nabla \bar{f},\boldsymbol{x}-\boldsymbol{x}^{(K)})+\dfrac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}^{(K)},\boldsymbol{H}^{(K)}(\boldsymbol{x}-\boldsymbol{x}^{(K)})\right)

となる。これより先、$(x^{(K)},y^{(K)})$での$f,\nabla f,\boldsymbol{x},\boldsymbol{H}$の値は右肩に「$\cdot ^{(K)}$」を乗せて表現するように統一しよう。

g(\boldsymbol{x})=f^{(K)}+(\nabla f^{(K)},\boldsymbol{x}-\boldsymbol{x}^{(K)})+\dfrac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}^{(K)},\boldsymbol{H}^{(K)}(\boldsymbol{x}-\boldsymbol{x}^{(K)})\right)

ここで、「関数$g$の極値を求める」という方針を取ろう。関数$f$の極値を求めたいが、$f$をある程度良い精度で近似した関数$g$の極値を求めれば、それは$f$の極値に近い、という気分である。さて、全ての変数の増加率が0になったとき、つまり勾配が0となったときが関数の極値であるから、ベクトルの微分の公式

\nabla (\boldsymbol{a},\boldsymbol{x})=\boldsymbol{a}

\nabla (\boldsymbol{x},\boldsymbol{Ax})=2\boldsymbol{Ax}

を用いて、まずは$g$の勾配を求めよう。

\nabla g = \nabla f^{(K)}+\boldsymbol{H}^{(K)}(\boldsymbol{x}-\boldsymbol{x}^{(K)})=0 \qquad \cdots{(3.63)}

では、真の解$\boldsymbol{x}$へ近似解である現在の位置$\boldsymbol{x}^{(K)}$から向かうには、$\boldsymbol{m}^{(K)}\propto \boldsymbol{x}-\boldsymbol{x}^{(K)}$なるベクトル$\boldsymbol{m}^{(K)}$の方向へ向かえばよい。

この$m^{(K)}$を共役勾配とよぶ。この共役勾配は式$(*)$から

\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)}\propto \nabla f^{(K)} \qquad \cdots (3.64)

の関係をもつ。

点$\boldsymbol{x}^{(K)}$での等高線の接線ベクトルを$\boldsymbol{t}^{(K)}$とすると、勾配$\nabla f^{(K)}$は接線と直交する。つまり、$(\boldsymbol{t}^{(K)},\nabla f^{(K)})=0$となる。これと式(3.64)から

(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)})=0 \qquad (3.65)

ここで、共役勾配$\boldsymbol{m}^{(K)}$は勾配$\nabla f^{(K)}$からある程度接線方向へずれている。つまり$^\exists\alpha:$const.に対して

\boldsymbol{m}^{(K)}=\nabla f^{(K)}+\alpha^{(K)}\boldsymbol{t}^{(K)} \qquad (3.66)

として表現できる。式(3.65)に代入して

\begin{align*}
(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)})&=0\\
\left(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\left(\nabla f^{(K)}+\alpha^{(K)}\boldsymbol{t}^{(K)}\right)\right)&=0\\
(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\nabla f^{(K)})+(\boldsymbol{t}^{(K)},\alpha^{(K)}\boldsymbol{H}^{(K)}\boldsymbol{t}^{(K)})&=0\\
(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\nabla f^{(K)})+\alpha^{(K)}(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{t}^{(K)})&=0
\end{align*}

より

\alpha^{(K)}=-\dfrac{(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\nabla f^{(K)})}{(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{t}^{(K)})}

を得て、式(3.66)に代入して

\boldsymbol{m}^{(K)}=\nabla f^{(K)}-\dfrac{(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\nabla f^{(K)})}{(\boldsymbol{t}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{t}^{(K)})}\boldsymbol{t}^{(K)} \qquad \cdots(**)

として共役勾配$\boldsymbol{m}^{(K)}$が求めることができる。あとは、このベクトル$\boldsymbol{m}^{(K)}$方向に進んでいけば、$g$の極値に達することができるはずである。これが、共役勾配法の考え方である。

なお、$\boldsymbol{m}^{(K)}$方向に極値を探索する際には、勾配法を用いればよい。

イメージとしては、$\boldsymbol{m}^{(K)}$方向(図中の緑線)で関数を切って、その断面を山登りしていくような感じである。これを直線探索という。

さて勾配法による直線探索の結果、点$x^{(K+1)}$で極値(付近)に達したとしよう。ここで、勾配法による直線探索の性質として次の定理3.1があった。

【定理3.1】関数$f(x_1,\dots,x_n)$に対する勾配法の直線探索で定まる点では、その点を通る$f(x_1,\dots,x_n)$の等値面が探索直線に接する。

これを今回の話に置きかえよう。いま、探索直線は$\boldsymbol{m}^{(K)}$方向の緑色の線である。このベクトル方向が、$\boldsymbol{x}^{(K+1)}$での接線方向$\boldsymbol{t}^{(K+1)}$になっているということである。

つまりは、

\boldsymbol{t}^{(K+1)}=\boldsymbol{m}^{(K)}

という関係が成り立つことを意味する。これを式$(**)$に入れてあげると

\begin{align*}
\boldsymbol{m}^{(K)} &= \nabla f^{(K)}-\dfrac{(\boldsymbol{m}^{(K-1)},\boldsymbol{H}^{(K)}\nabla f^{(K)})}{(\boldsymbol{m}^{(K-1)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K-1)})}m^{(K-1)}\\
\boldsymbol{m}^{(0)} &= \nabla f^{(0)}\\
\boldsymbol{x}^{(K+1)} &= \boldsymbol{x}^{(K)}+t^{(K)}\boldsymbol{m}^{(K)}
\end{align*}

を得て、これをfor文などで反復すればよい。

fが二次式の場合

以上の議論は直線探索を関数$f$にそのまま適用したものとして利用できるが、関数$f$が2次式かつ、$f$をその2次近似$g$で代用した場合は、さらに議論が進められる。実はパラメータ$t^{(K)}$は勾配法を使わずに直接計算できるのである。

$f$が2次式ならば、式(3.63)を満たす$\boldsymbol{x}$が真の解、つまり極値を与える$\boldsymbol{x}$である。この$\boldsymbol{x}$に対して

\boldsymbol{x} = \boldsymbol{x}^{(K)}+t^{(K)}\boldsymbol{m}^{(K)}

と置くと、これを式(3.63)に代入すると

\nabla f^{(K)}+t^{(K)}\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)}=0

この両辺について、$\boldsymbol{m}^{(K)}$との内積をとると

(\boldsymbol{m}^{(K)},\nabla f^{(K)})+t^{(K)}(\boldsymbol{m}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)})=0

から、

t^{(K)}=-\dfrac{(\boldsymbol{m}^{(K)},\nabla f^{(K)})}{(\boldsymbol{m}^{(K)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K)})}

を得る。
もちろん、関数$g$について共役勾配法を適用していることになるので、この結果は$g$の極値を探していることとなる。しかし、$g$は2次式$f$の2次近似であるから、極値もよく近似されているであろうというモチベーションである。もし、$f$が2次式でない場合、たとえば3次式を2次近似してもあまり良い精度がでないことは容易にイメージがつくであろう。この場合は、反復回数を増すことで極値に収束させることとなる。$f$が2次式でない場合は、この方法ではなく直線探索に勾配法を用いる方が賢明である。

n変数への拡張

ここまでの議論はそのままn変数へ拡大することができる。各点$x^{(K)}$で１つ前のステップの探索直線の方向$m^{(K-1)}$とその点での関数$f$の勾配$\nabla$$f^{(K)}$の張る平面を考え、その平面上で関数$f$の等高線に対し２変数の共役勾配法を適用する、と考えればよい。

共役勾配法は、勾配法に比べて収束が速いことで知られている。しかし、1次収束であることに代わりはないので、ニュートン法の2次収束には及ばない。ただ、ニュートン法はヘッセ行列$\boldsymbol{H}$の逆行列を計算しなければならない点でコストがかかる分、１回の反復の計算量が少ないのは共役勾配法である。つまり、変数の数が大きい場合など、共役勾配法の方が高効率な場合もある。(問題に依存する)

Tips

「共役」とは

「共役」とは「直交」の概念を拡張したものである。

正値対称行列$\boldsymbol{Q}$に対してベクトル$\boldsymbol{x},\boldsymbol{y}$が$(\boldsymbol{x},\boldsymbol{Qy})=0$を満たすとき、$\boldsymbol{x}$,$\boldsymbol{y}$を$\boldsymbol{Q}$に関して互いに共役という。

たとえば、$\boldsymbol{Q}=\boldsymbol{I}$(単位行列)のとき$\boldsymbol{x}$と$\boldsymbol{y}$の内積が0、つまり$\boldsymbol{x}$と$\boldsymbol{y}$は直交すると言える。今回の例においては、式(3.65)から「等高線の接線方向$\boldsymbol{t}^{(K)}$とヘッセ行列$\boldsymbol{H}^{(K)}$について共役な方向が共役勾配$\boldsymbol{m}^{(K)}$」と言えるだろう。
この観点に立てば、勾配法は、常に直前の探索方向と(単位行列$\boldsymbol{I}$について共役な)直交する方向を探索する点と言うことができる。

ヘッセ行列の計算回避

ヘッセ行列は、２階偏微分を含む行列であるため、その計算をしていては、コストがかかる。これを回避するためにいくつかの方法が存在する。共役勾配法でヘッセ行列を含む部分は

\alpha^{(K)}=-\dfrac{(\boldsymbol{m}^{(K-1)},\boldsymbol{H}^{(K)}\nabla f^{(K)})}{(\boldsymbol{m}^{(K-1)},\boldsymbol{H}^{(K)}\boldsymbol{m}^{(K-1)})}

であったが、これを次のように計算する手法がある。
[1]ビール・レンソンの式

\alpha^{(K)}=-\dfrac{(\nabla f^{(K)},\nabla f^{(K)}-\nabla f^{(K-1)})}{(\boldsymbol{m}^{(K-1)},\nabla f^{(K)}-\nabla f^{(K-1)})}

[2]ポラック・リビエールの式

\alpha^{(K)}=-\dfrac{(\nabla f^{(K)},\nabla f^{(K)}-\nabla f^{(K-1)})}{||\nabla f^{(K-1)}||^2}

[3]フレッチャー・リーブスの式

\alpha^{(K)}=-\dfrac{||\nabla f^{(K)}||^2}{||\nabla f^{(K-1)}||^2}

おわりに

今回は共役勾配法の概要を説明した。結局は、探索直線を作って勾配法に帰着させることによって最適解を求めるという形であった。