エンジニアを目指す浪人のブログ

情報系に役立ちそうな応用数理をゆるめにメモします

ニュートンデクリメントの別表現を導出する

数学 数理最適化

本記事は以下の過去記事の内容を用います．

制約なし凸最適化問題に対するニュートン法と，ニュートンステップの定義，解釈，性質をまとめる - エンジニアを目指す浪人のブログ

正定値行列の逆行列は正定値であることの証明をメモする - エンジニアを目指す浪人のブログ

行列式の対数はその行列の凹関数であることを証明する - エンジニアを目指す浪人のブログ


勉強を進めていて，ニュートン法におけるニュートンデクリメント(newton decrement)の別表現を導出したので，メモしておくことにしました．Boyd and Vandenberghe(2004)の9章6節(の3の一部)をベースにしています．


ニュートンステップの定義は冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.1)にあります．

(0.1){\displaystyle \;\;\; \Delta x_{\mathrm{nt}} = - \nabla^2 f(x)^{-1} \nabla f(x) }

ニュートンデクリメントの定義は冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.1)(2.2.3)にあります．

(0.2){\displaystyle \;\;\; \lambda (x) = \left[ \nabla f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) \right]^{1/2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left[ \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} \right]^{1/2} }

ニュートン法では {\displaystyle \nabla^2 f(x) } は正定値を仮定するので，冒頭の過去記事(正定値行列の逆行列)事実.より {\displaystyle \nabla^2 f(x)^{-1} } は正定値です．さらに冒頭の過去記事(行列式の対数)事実0.4.より {\displaystyle \nabla^2 f(x)^{1/2},\nabla^2 f(x)^{-1/2} } が存在します．


以上の設定の下で，本記事の目的に進みます．

以下の事実を示します．

'--------------------------------------------------------------------------------------------------------------------------------------------
事実.

ニュートンデクリメント {\displaystyle \lambda } について，以下が成り立つ．

(1.1){\displaystyle \;\;\; \lambda (x) = \left[ \nabla f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) \right]^{1/2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \left[ \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} \right]^{1/2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ v^T \nabla^2 f(x) v = 1 } \left( - v^T \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \;\;\;\;\; \sup_{ v \neq 0 } \frac{ - v^T \nabla f(x) }{ \left[ v^T \ \nabla^2 f(x) \ v \right]^{1/2} } \;\;\;\;\;\; } (1.1)(※)


(1.2){\displaystyle \;\;\; \frac{ - v^T \nabla f(x) }{ \left[ v^T \ \nabla^2 f(x) \ v \right]^{1/2} } \le \lambda (x) \;\;\; v \neq 0, \;\; } 等号成立は {\displaystyle v = \Delta x_{ \mathrm{nt} } } のとき


証明.

はじめに(1.1)を示します．

(1.3){\displaystyle \;\;\; \sup_{ v^T \nabla^2 f(x) v = 1 } \left( - v^T \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ v^T \nabla^2 f(x)^{1/2} \ \nabla^2 f(x)^{1/2} v = 1 } \left( - v^T \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \left\| \nabla^2 f(x)^{1/2} \ v \ \right\|_2^2 = 1 } \left( - v^T \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \left\| \nabla^2 f(x)^{1/2} \ v \ \right\|_2 = 1 } \left( - v^T \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \left\| \nabla^2 f(x)^{1/2} \ v \ \right\|_2 = 1 } - \nabla f(x)^T v }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \left\| \nabla^2 f(x)^{1/2} \ v \ \right\|_2 = 1 } - \nabla f(x)^T \nabla^2 f(x)^{-1/2} \ \nabla^2 f(x)^{1/2} v }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \{ v \ : \ v = \nabla^2 f(x)^{-1/2} \ w, \ \left\| w \right\|_2 = 1 \} } - \nabla f(x)^T \nabla^2 f(x)^{-1/2} w \;\;\;\;\;\; } (1.3)(※)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = - \inf_{ \{ v \ : \ v = \nabla^2 f(x)^{-1/2} \ w, \ \left\| w \right\|_2 = 1 \} } \nabla f(x)^T \nabla^2 f(x)^{-1/2} w }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = - \inf_{ \{ v \ : \ v = \nabla^2 f(x)^{-1/2} \ w, \ \left\| w \right\|_2 = 1 \} } w^T \left( \nabla f(x)^T \nabla^2 f(x)^{-1/2} \right)^T }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = - \inf_{ \{ v \ : \ v = \nabla^2 f(x)^{-1/2} \ w, \ \left\| w \right\|_2 = 1 \} } w^T \left( \nabla^2 f(x)^{-1/2} \nabla f(x) \right) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = - \left[ \left( - \frac{ \nabla^2 f(x)^{-1/2} \nabla f(x) }{ \left\| \nabla^2 f(x)^{-1/2} \nabla f(x) \right\|_2 } \right)^T \nabla^2 f(x)^{-1/2} \nabla f(x) \right] }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{ \left[ \nabla^2 f(x)^{-1/2} \nabla f(x) \right]^T \left[ \nabla^2 f(x)^{-1/2} \nabla f(x) \right] }{ \left\| \nabla^2 f(x)^{-1/2} \nabla f(x) \right\|_2 } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \frac{ \left[ \nabla^2 f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) \right] }{ \left\| \nabla^2 f(x)^{-1/2} \nabla f(x) \right\|_2 } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \left[ \nabla^2 f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) \right]^{1/2} }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = \lambda (x) }


一方，以下は(1.3)(※)と等しい．

(1.4){\displaystyle \;\;\; \sup_{ v \neq 0 } \frac{ - v^T \nabla f(x) }{ \left[ v^T \ \nabla^2 f(x) \ \nabla v \right]^{1/2} } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ v \neq 0 } \frac{ - \nabla f(x)^T v }{ \left\| \nabla^2 f(x)^{1/2} \ v \right\|_2 } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ v \neq 0 } \frac{ - \nabla f(x)^T \nabla^2 f(x)^{-1/2} \nabla^2 f(x)^{1/2} v }{ \left\| \nabla^2 f(x)^{1/2} \ v \right\|_2 } }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\; = \sup_{ \{ v \ : \ v = \nabla^2 f(x)^{-1/2} \ w, \ \left\| w \right\| = 1 \} } - \nabla f(x)^T \nabla^2 f(x)^{-1/2} w }


つぎに(1.2)を示す．(1.1)(※)に(0.1)を代入すればよい．

(証明終わり)
'--------------------------------------------------------------------------------------------------------------------------------------------


以上，ニュートンデクリメントの別表現を導出しました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.