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

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

最適化理論

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

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は直交しているということが分かる。

共役勾配法の有限収束性

  1. \forall k=0,\cdots,n, \forall i=0,\cdots,k-1に対して、\nabla f(\mathbf{x}_k)^T \mathbf{d}_i = 0
  2. \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}\}\}
  3. 高々n回の反復でf(\mathbf{x})の最小解が得られる

最初のが重要らしく、この主張より

  • \nabla f(\mathbf{x}_1)^T \mathbf{d}_0 = 0
  • \nabla f(\mathbf{x}_2)^T \mathbf{d}_0 = 0
  • \nabla f(\mathbf{x}_2)^T \mathbf{d}_1 = 0
  • \nabla f(\mathbf{x}_3)^T \mathbf{d}_0 = 0
  • \nabla f(\mathbf{x}_3)^T \mathbf{d}_1 = 0
  • \nabla f(\mathbf{x}_3)^T \mathbf{d}_2 = 0

というようなことが得られて、\mathbf{x}_nに対して

  • \nabla f(\mathbf{x}_n)^T \mathbf{d}_0 = 0
  • \nabla f(\mathbf{x}_n)^T \mathbf{d}_i = 0
  • \nabla f(\mathbf{x}_n)^T \mathbf{d}_{n-1} = 0

というのが成立するが、\mathbf{d}_iというのは一次独立なように作るので、これより\nabla f(\mathbf{x}_n)=0が得られる。来週はこの辺を帰納法を使って証明していく。

工学基礎 最適化とその応用 (新・工科系の数学)

工学基礎 最適化とその応用 (新・工科系の数学)