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

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

目的関数に強凸性を仮定するときのニュートンデクリメントの不等式を証明する

数学 数理最適化

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

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

強凸関数のヘッセ行列の逆行列の不等式を証明する - エンジニアを目指す浪人のブログ


勉強を進めていて，目的関数に強凸性を仮定するときのニュートンデクリメント(newton decrement)のみたす不等式を証明したので，メモしておくことにしました．


問題を設定するため，いくつか準備をします．

ニュートンステップの定義は冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.1)にあります．
ニュートンデクリメントの定義は冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.1)にあります．
強凸関数の定義は冒頭の過去記事(強凸関数のヘッセ行列の逆行列)(1.1)(1.2)にあります．


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

以下の事実を示します．

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

目的関数 {\displaystyle f : \mathbb{R}^n \to \mathbb{R} } は強凸であると仮定する．このときニュートンデクリメント {\displaystyle \lambda } について，以下が成り立つ．

(1.1){\displaystyle \;\;\; \frac{1}{M} \left\| \nabla^2 f(x) \right\|_2^2 \le \lambda (x)^2 \le \frac{1}{m} \left\| \nabla^2 f(x) \right\|_2^2 }

(1.2){\displaystyle \;\;\;\;\;\;\;\; m \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 \le \lambda (x)^2 \le M \left\| \Delta x_{\mathrm{nt}} \right\|_2^2 }


証明.

{\displaystyle f } は強凸なので凸であり(文献[2]にあります)，よって {\displaystyle x } が最適点でなければ {\displaystyle \nabla f(x) \neq 0 } である．

{\displaystyle f } は強凸なので，冒頭の過去記事(強凸関数のヘッセ行列の逆行列)(1.1)より {\displaystyle \nabla^2 f(x) } は正定値である．したがって {\displaystyle \nabla f(x) \neq 0 } と冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(1.1.2)より {\displaystyle \Delta x_\mathrm{nt} \neq 0 } である．


{\displaystyle \;\;\; \lambda (x)^2 = \nabla f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \ge \nabla f(x)^T \left[ M^{-1} I \right] \nabla f(x) \;\;\; \because } 冒頭の過去記事(強凸関数のヘッセ行列の逆行列)事実.

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = M^{-1} \left\| \nabla^2 f(x) \right\|_2^2 }


{\displaystyle \;\;\; \lambda (x)^2 = \nabla f(x)^T \ \nabla^2 f(x)^{-1} \nabla f(x) }

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \le \nabla f(x)^T \left[ m^{-1} I \right] \nabla f(x) \;\;\; \because } 冒頭の過去記事(強凸関数のヘッセ行列の逆行列)事実.

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = m^{-1} \left\| \nabla^2 f(x) \right\|_2^2 }


{\displaystyle \;\;\; \lambda (x)^2 = \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \ge \Delta x_\mathrm{nt}^T \left[ m I \right] \Delta x_\mathrm{nt} \;\;\; \because } 冒頭の過去記事(強凸関数のヘッセ行列の逆行列)(1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = m \left\| \Delta x_\mathrm{nt} \right\|_2^2 }


{\displaystyle \;\;\; \lambda (x)^2 = \Delta x_\mathrm{nt}^T \ \nabla^2 f(x) \ \Delta x_\mathrm{nt} }
{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \because } 冒頭の過去記事(制約なし凸最適化問題に対するニュートン法)(2.2.3)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; \le \Delta x_\mathrm{nt}^T \left[ M I \right] \Delta x_\mathrm{nt} \;\;\; \because } 冒頭の過去記事(強凸関数のヘッセ行列の逆行列)(1.2)

{\displaystyle \;\;\;\;\;\;\;\;\;\;\;\; = M \left\| \Delta x_\mathrm{nt} \right\|_2^2 }


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


以上，目的関数に強凸性を仮定するときのニュートンデクリメントの不等式を証明しました．



参考文献
[1] Boyd, S., and Vandenberghe, L. (2004), Convex Optimization, Cambridge University Press.
[2] Wikipedia Convex function のページ https://en.wikipedia.org/wiki/Convex_function