最急降下法、共役勾配法辺りのメモ

誰かが「今日何やったか教えて」と言ってたんだけど、記憶から抜けていきそうになっているのでメモ。

Zoutendijkの条件

去年はどう役に立つか分かってなかったけど、今年は分かるという。

$\sum^\infty_{k=0}(\nabla f(\mathbf{x}_k)^T \mathbf{d}_k / ||\mathbf{d}_k||)^2 < \infty$ から $\lim_{k \rightarrow \infty}(\nabla f(\mathbf{x}_k)^T \mathbf{d}_k / ||\mathbf{d}_k||) = 0$ が得られるんだけど、 $\nabla f(\mathbf{x}_k)^T / ||\nabla f(\mathbf{x}_k)||$ と $\mathbf{d}_k / ||\mathbf{d}_k||$ が直交しないように選んであげれば、 $||\nabla f(\mathbf{x}_k)||$ はkを無限大に飛ばすと0にいく。これは、大域的最適解の必要条件になっているので、ある程度うれしいよねという流れ。

$\nabla f(\mathbf{x}_k)^T / ||\nabla f(\mathbf{x}_k)||$ と $\mathbf{d}_k / ||\mathbf{d}_k||$ が直交しないようにするにはどうしようか、という話のところは最急降下法では例えば $\mathbf{d}_k = - \nabla f(\mathbf{x}_k)$ として勾配ベクトルの負の向きを探索方向にしてやったりしていた。

最急降下法の収束のスピード

大変遅いのですが、どれくらい遅いのかというのを理論的に解析。 $f(\mathbf{x}) = 1 / 2 \mathbf{x}^T \mathbf{A} \mathbf{x} + \mathbf{b}^T \mathbf{x}$ を目的関数とする。Aは正定値対称行列として、 $\lambda_1$ をAの固有値の中で最小のもの、 $\lambda_n$ をAの固有値の中で最大のものとすると
$||\mathbf{x}_{k+1} - \mathbf{x}^*||_A = \frac{|\lambda_1 - \lambda_n|}{|\lambda_1 + \lambda_n|} ||\mathbf{x}_{k} - \mathbf{x}^*||_A$
という条件が導ける。前回のノートを参考にすると、これはq-1次収束というやつらしく、大変遅い部類に入る。

$||\cdot||_A$ というノルムが定義されているんだけど、これは $||\mathbf{v}||_A = \sqrt{\mathbf{v}^T \mathbf{A} \mathbf{v}}$ というノルムを考えたときのものである。ここで、「こういうものをノルムとして考えていいのか?」という問題があるんだけど、内積やノルムを一般化したときの話が出てきてこれもその定義を満たすので、ノルムとしておいてよい。

共役

$\mathbf{u}, \mathbf{v} \in \mathbf{R^n}$ が $\mathbf{A}$ に関して共役だとする。そのベクトルをPで変換したベクトルをそれぞれ $\mathbf{x} = \mathbf{P} \mathbf{u}$ 、 $\mathbf{y} = \mathbf{P} \mathbf{v}$ とすると、 $\mathbf{x}^T \mathbf{y} = \mathbf{u}^T \mathbf{P}^T \mathbf{P} \mathbf{v} = \mathbf{u}^T \mathbf{A} \mathbf{v} = 0$ となり、Pで移されたxとyは直交しているということが分かる。

共役勾配法の有限収束性

$\forall k=0,\cdots,n, \forall i=0,\cdots,k-1$ に対して、 $\nabla f(\mathbf{x}_k)^T \mathbf{d}_i = 0$
$\mathbf{x}_k = \mbox{argmin} \{f(x)|x \in \mathbf{S}_k\}$ 。ここで、 $\mathbf{S}_k = \{\mathbf{x}|\mathbf{x} = \mathbf{x}_0 + \mbox{span} \{\mathbf{d}_0,\cdots,\mathbf{d}_{k-1}\}\}$
高々n回の反復で $f(\mathbf{x})$ の最小解が得られる