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

局所最適解と正定値

最適化理論

めもめも。。。今日が第一回。今日はごりごり証明とかでした。4章のところをやっている。

大域的最適解であるとは

{\bf x}^* \in {\bf R}^nが大域的最適解であるとは、\forall {\bf x} \in {\bf R}^n \quad f({\bf x}^*) \leq f({\bf x})が成立することである。{\bf x}^*はuniqueである必要はない。

近傍

N(\bar{\bf x},\epsilon) = \{{\bf x} \in {\bf R}^n | || {\bf x} - \bar{{\bf x}}|| < \epsilon\}
が定義。\bar{\bf x}とのノルムが\epsilonで抑えられるようなところ。ノルムは色々種類があって、

  • 2ノルム
  • 1ノルム
  • ∞ノルム

とかが図と一緒に紹介されていた。

局所的最適解であるとは

\exists \epsilon > 0 \quad \forall {\bf x} \in N({\bf x},\epsilon) \quad f({\bf x}^*) \leq f({\bf x})
\epsilon近傍では{\bf x}より小さいものはないよ、\epsilonより外ではいるかもしれないけど」という感じ。

局所的最適解が持っている条件

  1. {\bf x} \in {\bf R}^nは局所的最適解
  2. fは{\bf x}のある近傍で連続微分可能

これが言えれば、\nabla f({\bf x}) = 0であることが言える。これは本当かいな?ということの証明が平均値の定理の高次元版とか背理法を使って証明されていた。

  • オミクロン関数
  • 偏微分可能だけど、全微分可能ではない例

とかが登場。ここでの「微分可能」というのは全微分可能という意味で使われていることに注意。

fは\bar{\bf x} \in {\bf R}^nで微分可能であるというのをちゃんと書くと、\exists {\bf a} \in {\bf R}^n \quad \forall {\bf x} \in {\bf R}^n \quad f({\bf x}) = f(\bar{\bf x}) + {\bf a}^T ({\bf x} - \bar{\bf x}) + \mbox{o}(||{\bf x} - \bar{\bf x}||)という感じになる。これはあとでも結構出てきてたかな。

図的な解釈

等高線っぽいのと合成関数をほげほげして。g(t)が定数であるから、g'(0)=0となるというのを利用していく。g'(t)というのは合成関数の微分より、g'(0) = (\nabla f (\bar{\bf x}))^T \phi'(0)とできるんだけど、これが0であることから、それぞれのベクトルは直交している。等高線の図とかを見るとベクトル(\nabla f (\bar{\bf x}))の向いている方向が分かる、というような流れだった。

「局所的最適解が持っている条件」を強める

二回微分可能まで条件に付け加えると、\nabla^2 f({\bf x})は半正定値であることが言える。これはヘッセ行列と呼ばれるもの。\nabla^2 f({\bf x})は実は対称行列なので、固有値は実数で全て0以上であることなどが言えるらしい。

これを証明するにも背理法が使われていた。f({\bf x} + t {\bf d})をテイラー展開して、条件を使って局所的最適解であることと矛盾することを示す。

ここまでやってきたわけだけど、「局所的最適解の性質は分かった。だけど、どうなっていたら局所的最適解であるかのほうが知りたいよね。そのほうが使い勝手もいいし」という流れで定理4.1(2)に行く。

定理4.1(2)

f:{\bf R}^n \rightarrow {\bf R}は二階微分可能とすると、

  • \nabla f({\bf x}^*) = 0
  • \nabla^2 f({\bf x}^*)は正定値

であるならば、{\bf x}^*は局所的最適解である。

これの証明には背理法…ではなかったw。\nabla^2 f({\bf x}^*)は正定値、というのを近傍でも大丈夫という性質を使って(あとで証明)、f({\bf x}^* + {\bf d})をテイラー展開、条件を使って局所的最適解ということを示す。

宿題

最小二乗法と同等の式の\nabla f({\bf x})\nabla^2 f({\bf x})を実際に書いてみるというやつ。これはできそうな気がする。

これなら分かる最適化数学―基礎原理から計算手法まで

これなら分かる最適化数学―基礎原理から計算手法まで