共役な方向とは？

最適化問題の局所的探索法のひとつに共役勾配法がある。この共役な勾配について簡単にまとめる。

いま、最小化すべき関数を$f\left(\vec{x}\right)$とする。$\vec{x}$ 近傍の微小量 $\vec{u}$ と $\vec{v}$ を考え、 $f\left(\vec{x}+\vec{u}+\vec{v}\right)$ を $\vec{x}$ 近傍でTayler展開し、2次の項までとる。 $$\begin{eqnarray} f\left(\vec{x}+\vec{u}+\vec{v}\right)&=&f\left(\vec{x}\right)+\sum_{i}\frac{\partial f\left(\vec{x}\right)}{\partial x_i}\left(u_i + v_i\right)+\frac{1}{2}\sum_{ij}\frac{\partial^2 f\left(\vec{x}\right)}{\partial x_i \partial x_j}\left(u_i + v_i\right)\left(u_j + v_j\right)\nonumber \\ &=& f\left(\vec{x}\right) + \sum_{i}\frac{\partial f\left(\vec{x}\right)}{\partial x_i}u_i + \frac{1}{2}\sum_{ij}\frac{\partial^2 f\left(\vec{x}\right)}{\partial x_i \partial x_j}u_i\; u_j \nonumber \\ &+& \sum_{i}\frac{\partial f\left(\vec{x}\right)}{\partial x_i}v_i + \frac{1}{2}\sum_{ij}\frac{\partial^2 f\left(\vec{x}\right)}{\partial x_i \partial x_j}v_i\; v_j \nonumber \\ &+& \sum_{ij}\frac{\partial^2 f\left(\vec{x}\right)}{\partial x_i \partial x_j}u_i\;v_j \end{eqnarray}$$ ここで、$b_i=\frac{\partial f}{\partial x_i}$、$A_{ij}=\frac{\partial^2 f}{\partial x_i \partial x_j}$と書くと $$\begin{equation} \delta f = \left(\vec{b}^{\;T}\vec{u} + \frac{1}{2}\vec{u}^{\;T} A \;\vec{u}\right) +\left(\vec{b}^{\;T}\vec{v} + \frac{1}{2}\vec{v}^{\;T} A \;\vec{v}\right) + \vec{u}^{\;T}\;A\;\vec{v} \end{equation}$$ となる。上式右辺の最後の項が存在しなければ、$\vec{u}$ と $\vec{v}$ について独立に局所的探索法を適用できる。 $\vec{u}^{\;T}\;A\;\vec{v}= 0$ となるような組 $\{\vec{u},\vec{v}\}$ を共役な関係にあるベクトルと呼ぶ。共役な関係にある勾配の集合を適当に作り、互いに干渉することなく効率良く最適解を探索する手法が共役勾配法である。