強凸関数のヘッセ行列と逆行列の，最大固有値，最小固有値，スペクトルノルムの不等式を証明する

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

勉強を進めていて，強凸性(strong convexity)を仮定する関数のヘッセ行列と逆行列の，最大固有値，最小固有値，スペクトルノルムのみたす不等式を証明したので，メモしておくことにしました．

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

強凸関数の定義は冒頭の過去記事(強凸関数のヘッセ行列の逆行列)(1.1)(1.2)にあります．

$n \times n$ 行列 $A$ の最大固有値，最小固有値を $\lambda_{\mathrm{max}} \left[ A \right], \lambda_{\mathrm{min}} \left[ A \right]$ とします．

行列のスペクトルノルムの定義は文献[2]にあります．

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

以下の事実を示します．

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

強凸関数 $f$ のヘッセ行列とその逆行列について，以下が成り立つ．

(1.1) $\;\;\;\;\; m \le \lambda_{\mathrm{min}} \left[ \nabla^2 f(x) \right], \;\;\;\;\;\; \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] \;\;\; \le M$

(1.2) $\;\;\; \frac{1}{M} \le \lambda_{\mathrm{min}} \left[ \nabla^2 f(x)^{-1} \right], \;\;\; \lambda_{\mathrm{max}} \left[ \nabla^2 f(x)^{-1} \right] \le \frac{1}{m}$

証明.

強凸関数の定義よりヘッセ行列は正定値である．したがって $\nabla^2 f(x)$ は正定値であり冒頭の過去記事(行列が半正定値)事実.より $\lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right],\lambda_{\mathrm{min}} \left[ \nabla^2 f(x) \right]$ は正である．

(1.1)を示す．冒頭の過去記事(強凸関数のヘッセ行列の逆行列)事実.の証明.より以下を得る．

$\;\;\; m z_1^2 + \cdots + m z_n^2 \le \lambda_1 z_1^2 + \cdots + \lambda_n z_n^2 \le M z_1^2 + \cdots + M z_n^2, \;\;\; z \in \mathbb{R}^n, \; z \neq 0$

$\Rightarrow \ m z_1^2 + \cdots + m z_n^2 \le \lambda_{\mathrm{min}} \left[ \nabla^2 f(x) \right] z_1^2 + \cdots + \lambda_{\mathrm{min}} \left[ \nabla^2 f(x) \right] z_n^2$

$\;\;\; m z_1^2 + \cdots + m z_n^2 \le \lambda_1 z_1^2 + \cdots + \lambda_n z_n^2 \le M z_1^2 + \cdots + M z_n^2, \;\;\; z \in \mathbb{R}^n, \; z \neq 0$

$\Rightarrow \ \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] z_1^2 + \cdots + \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] z_n^2 \le M z_1^2 + \cdots + M z_n^2$

(1.2)を示す．

$\;\;\; \frac{1}{\lambda_{\mathrm{min}} \left[ \nabla^2 f(x) \right]} \le \frac{1}{m} , \;\;\;\; \frac{1}{M} \le \frac{1}{\lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right]} \;\;\; \because$ (1.1)

$\Leftrightarrow \ \lambda_{\mathrm{max}} \left[ \nabla^2 f(x)^{-1} \right] \le \frac{1}{m} , \;\;\;\; \frac{1}{M} \le \lambda_{\mathrm{min}} \left[ \nabla^2 f(x)^{-1} \right] \;\;\; \because$ 冒頭の過去記事(逆行列の固有値)事実.

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

以下の事実を示します．

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

強凸関数 $f$ のヘッセ行列とその逆行列のスペクトルノルムについて，以下が成り立つ．

(2.1) $\;\;\; \left\| \nabla^2 f(x) \right\|_2 \;\;\; = \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] \;\;\; \le M$

(2.2) $\;\;\; \left\| \nabla^2 f(x)^{-1} \right\|_2 = \lambda_{\mathrm{max}} \left[ \nabla^2 f(x)^{-1} \right] \le \frac{1}{m}$

証明.

$\;\;\; \left\| \nabla^2 f(x) \right\|_2 = \left| \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] \right| \;\;\; \because$ 冒頭の過去記事(エルミート行列のスペクトルノルム)事実.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \lambda_{\mathrm{max}} \left[ \nabla^2 f(x) \right] \;\;\; \because$ 冒頭の過去記事(行列が半正定値)事実.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le M \;\;\; \because$ (1.1)

冒頭の過去記事(正定値行列の逆行列)事実.より， $\nabla^2 f (x)^{-1}$ は正定値である．

$\left\| \nabla^2 f(x)^{-1} \right\|_2 = \left| \lambda_{\mathrm{max}} \left[ \nabla^2 f(x)^{-1} \right] \right| \;\;\; \because$ 冒頭の過去記事(エルミート行列のスペクトルノルム)事実.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = \lambda_{\mathrm{max}} \left[ \nabla^2 f(x)^{-1} \right] \;\;\; \because$ 冒頭の過去記事(行列が半正定値)事実.

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \le \frac{1}{m} \;\;\; \because$ (1.2)

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

以上，強凸関数のヘッセ行列と逆行列の，最大固有値，最小固有値，スペクトルノルムの不等式を証明しました．

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

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

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

強凸関数のヘッセ行列と逆行列の，最大固有値，最小固有値，スペクトルノルムの不等式を証明する